Month: August 2008

The weekend PHP size competiton I mentioned on friday has come to an end, with the results being as follows:

CNU (253 bytes)
Helge (261 bytes)
Ymgve (267 bytes)
Me (365 bytes)
dibon&zep (which never delivered, but had working solutions)

For those who are interested in the strategies and tactics employed by the contestants, I’ve included a small write-up and analysis of the various contributions. We decided early on that using eval() and gzinflate on the content were something that everyone could apply, so the size would be counted for the decompressed code. If any contestant implemented their own decompressor in the user space code themselves, we would accept that. It would not be any advantage anyways, as the decompressor code would eat up more space than the best contributions used in total.

I’ve included the writers own comments if they had any. The biggest change in size happened when people started using one dimensional strings instead of arrays.

CNU’s contribution

$b='';foreach(file('maps.txt',2)as$l){if(!$l){$q[1]=strpos($b,'.');for($b=str_split($b);$p=&$q[++$l];)foreach(array($p-$w,$p+$w,$p-1,$p+1)as$x){$c=$b[$p]+1;$d=&$b[$x];if($d=='X')echo$c.'
';if($d==' ')$q[]=$x;$d=$c;}$q=$b='';}$b.=$l;$w=strlen($l);}

Helge’s contribution

$m="";foreach(file("maps.txt")as$l){if($l!="
"&&($m.=$l)+$w=strlen($l))continue;for($y=$d[$v[]=strpos($m,'.')]=0;strpos($m,'X')-$u=$v[$y++];)for($x=-$w;$x<=$w;$x+=$x+1?$w-1:2)in_array($n=$u+$x,$v)|$m[$n]=="#"||$d[$v[]=$n]=$d[$u]+1;echo"$d[$u]
";$m=$v="";}

Helge also included an annotated version with comments in norwegian:

/** 
 * $l = én linje (av maps.txt)
 * $m = ett map
 * $w = vidden til et kart
 * $d = distansen til et vilkårlig punkt
 * $v = open/closed-array (putter både squares 
        of interest og visited squares her)
 * $u = "current square", utgangspunktet til å 
        generere naboer
 * $n = nabo
 * $x = hjelpevariabel for å generere $n
 * $y = hjelpevariabel for å generere $u
 */


/* Klarte aldri å finne en måte å skippe initialisering av 
   $m her.. (den resettes på siste linja og.. føles waste)
   * En idé var å bruke to for(;;)'s istedenfor en foreach 
   og continue, men jeg tror jeg hadde økt i kode da.. */
$m="";

/* Foreach var nyttig fant jeg ut.. den stopper når filen er 
   ferdig lest av seg selv, så slipper kode på sjekking av det, 
   $f[$y++], osv. */
foreach(file("maps.txt") as $l) {
    if(
        /* Når $l=="\n" (som betyr slutten på et kart) skal 
           vi slutte å appende til $m og heller breake if'en 
           så vi kan starte pathfinding */
        $l != "\n" &&

        /* Bruker en 1-dimensjonal string istedenfor array 
           (= win!) */
        ($m .= $l) +

        /* Trenger vidden når jeg skal regne ut naboene til et 
           gitt felt. */
        $w = strlen($l)
    )
        /* Gjør så $l blir feedet en ny linje av kartet vårt til 
           kartet er ferdig */
        continue;

    /* Pathfinding start! */
    for(
        /* Setter $y og $d[starten] lik 0, og putter startposisjon 
           inn i $v i samma slengen. */
        $y = $d[ $v[] = strpos($m, '.') ] = 0;

        /**
         * Gjør så for(;;) breaker når sluttposisjon-$u blir 0 
         * (synonymt med $u == strpos($m, 'X');
         * Tar også neste $u fra $v i samma slengen */
        strpos($m, 'X') - $u = $v[ $y++ ];
        
    )
        /* For hver nabo */
        for(
            /* Genererer naboer.
             * Den starter på -width (som blir opp), går så til -1 
               (som blir venstre), 1 (som blir høyre) og tilslutt 
               width (som blir ned) */
            $x = -$w;
            $x <= $w;
            $x += $x+1 ? $w-1 : 2
        )
            /* Om naboen (summen av $u og $x) er i $v: continue */
            in_array($n = $u+$x, $v) | /* fancy bitwise or som kan 
                                          brukes fordi det er snakk 
                                          om 2 booleans */

            /* Om naboen er en '#' på kartet: continue */
            $m[$n] == "#" ||

            /* Hvis ikke, sett distansen til naboen lik distansen 
               til $u + 1 og putt naboen inn i $v */
            $d[ $v[] = $n ] = $d[$u]+1;

    /* Skriv ut distansen til $u (skal være sluttpunktet nå) */
    echo "$d[$u]\n";

    /* Disse må resettes.. */
    $m=$v="";
}

Ymgve's contribution

foreach(file("maps.txt")as$l){for($i=0;-75<$e=ord($l[$i++])-88;$m[]=$e+56?$e:1e6,$z=array(-1,1,-$i,$i))$e+42||$q[0]=count($m);if($i<3){for($d=$k=$c=0;;$c++-$k||$i++&$k=$d)for($j=4;$j;$g>$i&&($g=$i)&$q[++$d]=$p)if(!$g=&$m[$p=$q[$c]+$z[--$j]])break 2;echo"$i
";}}

My own contribution

Breadth-first Search, Delivered Version, 365 bytes:

Prettyprinted:

This is mostly your usual run-of-the-mill BFS, where the search itself is implemented as a simple queue. 
We loop through all the lines in the file (observe that you can remove the space character on both sides of as, saving you two bytes!):
foreach(file('maps.txt')as$l)

The part within the else condition builds the map to search for the exit point:
    // for each line in the file, we do this
    for($x=0;$l[$x++]!="
";$m[$y][$x]=$l[$x]=="#"?0:$l[$x])
        if($l[$x]=='.')$q[]=array($y,$x,0);

The for() loops through each character on the line, until it hits the newline marker at the end. Instead of entering "\n", you simply use the actual newline. This way you save another byte. The map ($m) is then populated using the current y,x coordinate (y being the line, x being the character on that line).
$m[$y][$x]=$l[$x]=="#"?0:$l[$x] can be expanded to:
if ($l[$x] == "#")
{
    $m[$y][$x] = 0;
}
else
{
    $m[$y][$x] = $l[$x];
}

Meaning that if the character is a wall, we store the value zero; if any other value, we store the character itself. We'll use this attribute when searching to determine when we've reached our goal. All of this is kept inside the for()-construct itself. The only thing contained in the for()-loop, is the statement if($l[$x]=='.')$q[]=array($y,$x,0);. This checks if the current character is the starting point, and if that's the case, adds it to our queue of points to check (making it the starting point of our BFS).
When we hit an empty line in the file (through the if("

"==$l) check), we execute our BFS.
    /* while $q is valid (this handles empty labyrinths), we fetch the 
        current y and x coordinates, in addition to d, the distance to 
        the location we're fetching from the queue. No {} here, as the 
        for only contains the if() statement below. */
    for(;$q&&list($y,$x,$d)=array_shift($q);)

        /* if this spot has a value (remember that we assigned 0 to walls, 
            while we kept the character value for other fields when we 
            parsed the file. We use empty() as the coordinates may not be 
            valid indexes into the array, as we don't do any checks when 
            we add them. one call to empty() is better than four ifs and 
            duplicate array references). */
        if(!empty($m[$y][$x]))
        {
            // create a reference (saves one byte instead of referencing $m[$y][$x] twice.
            $k=&$m[$y][$x];

            /* if we've found the X, echo the distance to the X. Under any 
                under circumstance, you'd break; out of the for/while here, 
                but as bytes count more than speed, we save six bytes by 
                searching the whole labyrinth instead of ending early. Funny 
                detail: as echo is a language construct, you can skip the space. 
                If the character is not 'X', we simply echo an empty string 
                instead of using a conditional echo. Saves a couple of bytes. */
            echo$k=='X'?"$d
":'';

            // unset the value, so that we don't visit this node again.
            $k=0;

            /* add all neighbours to our queue. We pre-increment $d, instead 
                of adding +1 in all the adds. */
            $q[]=array($y,$x-1,++$d);
            $q[]=array($y-1,$x,$d);
            $q[]=array($y,$x+1,$d);
            $q[]=array($y+1,$x,$d);
        }
        
        /* Reset the values. PHP generates a warning if a value has never
            been set before when used, but will happily accept null values 
            as empty arrays or 0. The double assignment is also a trick worth 
            remembering to save bytes. */
        $m=$y=null;

Some of tricks used in the competition

Multi-variable assignment: $a=$b=0;
Actual newline when detecting a newline: if ($a=="

"){}
Using null to be able to reset both integers and arrays in one statement.
The more code you can fit into a for() statement, the better. You get three "free" line endings by doing this. for(;;) is the same length as while(), but you can get several statements evaluated.
You can skip the spaces in foreach().
Create references to avoid using long array indices several times.
The ternary operator (?:) is your friend!
Remember that {}'s can be dropped when you have a single statement that contains all subsequent code (as long as you don't get any conflicts with else etc. on different levels):

for(;;) <-- no { here.

if ()

{

}
Simulating arrays with strings

The scripts were run with a set of pre-made labyrinths and a collection of 20 random labyrinths (more like maps, but they still test the code the same). The script for creating the labyrinths is available here. All delivered contributions passed all tests.