Andrew Shitov

The after-story about the Perl Golf contest, which took place during the two-day YAPC::Russia conferece in Moscow

Perl Golf is a contest, where participants solve the task with the shortest Perl programme possible. This year's Golf rules were announced by Vadim Pushtaev right after the conference start.

You can find a formal desciption and all the received solutions in the YAPC_Russia_2015_perl_golf GitHub repository.

The task. The script takes two parameters, matrix's width and height, and within the given rectangular field prints a series of incremented numbers starting by 1, going along the spiral towards the centre of the field:

$ perl script.pl 7 6
1  2  3  4  5  6  7
22 23 24 25 26 27 8
21 36 37 38 39 28 9
20 35 42 41 40 29 10
19 34 33 32 31 30 11
18 17 16 15 14 13 12

The columns are left-aligned and are separated by exactly one space.

The minimal demo solution bronton.pl, which was a part of the task, contained 338 symbols, and it was of no interest to submit anything longer. It was funny to watch the lengths of the different solutions that the participants were submitting during the days of the conference. Once, there were three files, of 244, 245 and 246 symbols each, and there was a feeling that those candidates could win by only removing one or two characters in their programmes. But a few hours before the deadline,
Denis Ibaev submitted his version, which was 205-symbol long, and although he was the absolute leader, Denis managed to make the code even shorter (202 chars). For me it's extremely notable that the whole script was written on an iPad.

202 dionys.pl
208 agrishaev.pl
213 andrey_shitov.pl
229 nikolas_shulyakovskiy_s.pl
243 kyusev.pl
246 andrey_fedorov.pl
258 khripunov.pl
294 bor_vas.pl
303 orlenko_aleksandr.pl
326 evgeniy_kim.pl
338 bronton.pl

I'll describe my solution (the readers can explore other solutions themselves :-).

First of all, I had to understand how to make the spiral in the most optimal way. I wanted to create or find a formula, which translates cell coordinates into the value. In the internets, you can find the Ulam spiral --- same as in the Golf task but rolling in opposite direction --- and even some kind of a formula I needed but I rejected that path because it was not clear how to calculate the number of spaces between columns. Having the formula, it was tempting to immediately print the result, skipping the second loop for printing.

Anyway, two steps were done: generating and printing. To make the spiral, you need to turn at the corners, keeping the already filled cells unchanged. I drew a few matrices on paper and found out that each time the spiral makes its turn the length of the next segment decrements by 1. In other words, for the 7×5 matrix the first two segments are 7 and 4 steps, the next two are 6 and 3, then 5 and 2, etc.

All the above gave the following initial script.

#!/usr/bin/perl

($w,$h)=@ARGV; # width and height

exit if !($w*$h);
#$n=0; # cell value
#$x=0; # initial horisontal position

$y=1; # initial vertical position

$v=1; # vector of moving horisontally
$u=1; # and vertically

# main loop - by width
while ($wi=$w--) { # the above-mentioned decrement of a segment 
    while ($wi--) { # before spiral turn
        $x+=$v; # moving one cell right or left
        $a[$x][$y]=++$n; # fixing the result
        $L[$x]=$n; # @L is a one-dimentional array, one value for each line,
                   # it is being filled with the currently generated value,
                   # thus when the matrix is filled, 
                   # @L will contain values with maximum possible length
                   # in each column, thus we know the column width. 
    };

    $v=-$v; # preparing for the next horizontal segment,
            # changing direction.

    $hi=$h--;
    while(--$hi) { # and now traverse vertically
        $y+=$u;    # up (-1) or down (+1)
        $a[$x][$y]=++$n;
        $L[$x]=$n;
    }
    $u=-$u;
    last if !$h;
}

($w,$h)=@ARGV; # initial values are already broken, re-read them

# simple loop printing @a
for $y (1..$h) {
    for $x (1..$w) {
        # the only less obvious part is 
        # the formatting string like "%-5i" with the length from @L
        $s = $x != $w ? 1+length $L[$x] : '';
        printf "%-${s}i", $a[$x][$y];
    }
    print "\n";
}

Interestingly, the solution of Denis Ibaev does not contain two-dimentional matrix, and all the values are kept in a bare array.

It became obvious that it is not possible to determine the width of the column as 1 + length $w*$h, because it might occur that there will be only one long number, and it will break the whole picture making one of the columns one char wider than others.

$ perl script.pl 10 10
1  2  3  4  5   6  7  8  9  10
36 37 38 39 40  41 42 43 44 11
35 64 65 66 67  68 69 70 45 12
34 63 84 85 86  87 88 71 46 13
33 62 83 96 97  98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93  92 91 74 49 16
30 59 80 79 78  77 76 75 50 17
29 58 57 56 55  54 53 52 51 18
28 27 26 25 24  23 22 21 20 19

That's why the @L array was introduced.

Now we come to some optimisations. First of all, it is possible to gain a few characters when re-reading the arguments:

($p,$q)=($w,$h)=@ARGV;

Also, it is wise to remove any data checks because the Golf test script did not use any incorrect initial values :-) Zero or negative width or height potentially can create infinitive loops but we don't care.

exit if !($w*$h);

The column length is determined by the width of the number contained in the corresponding element of the @L array. To get rid of trailing spaces we can make the length of the last element zero:

$L[$p]='';

This allows to exclude the check for the final column:

$s = $x != $w ? 1+length $L[$x] : '';

Now it would be nice to get rid of the condition to stop the loop. The loop itself looks like this:

while ($wi=$w--) {
   . . .
   last if !$h;
}

Instead, you can say this:

while ($h * ($wi=$w--)) {
   . . .
}

Variable initialisation (those which should start with a non-zero value) can be done in one turn:

$y=$v=$u=1;

The same for the following code lines, and instead of

$a[$x][$y]=++$n;
$L[$x]=$n;

write

$L[$x]=$a[$x][$y]=++$n;

Now a small but useful optimisation of the print loop by introducing the postfix form of for:

for $y (1..$q) {
    printf "%-".(1+length$L[$_])."i", $a[$_][$y] for 1..$p;
    print "\n";
}

Then it came to my mind that the $u and $v variables both change at the same time: it never happens that you use one of them before the second one has changed. Even more, both of them are always either -1, or 1. So, we can replace them with a single $d variable, altering its sign at the end of the external loop:

$d=1;

while ($h * ($i=$w--)) {
    . . .
    $d=-$d; 
}

The nested while loop also could be modified to become postfix but first let's try factoring out some repeating code, which was a good idea:

sub p {
    $L[$x]=$a[$x][$y]=++$n
}

Instead of

while($wi--) {
    $x+=$v;
    $L[$x]=$a[$x][$y]=++$n;
}

and

while(--$hi) {
    $y+=$u;
    $L[$x]=$a[$x][$y]=++$n;
}

the code looks like this now:

$x+=$d, p while $i--;

. . .

$y+=$d, p while --$i;

It was very promising to make the above decrements $i-- and --$i both either prefix or postfix and remove even more duplicated code but it was not that easy to achieve. Instead, I spent some time for an attempt of creating a function changing either$xor$y`:

#sub e {
#   eval "\$$_[0]+=$d, p while $_[1]"
#}

. . .

#e 'x','$i--';
. . .
#e 'y','--$i';

The result was longer than before, thus this modification had to be rejected.

The local failure was followed by a successful change, which made the initial value of $y zero instead of 1, and the $y = 0 instruction is obviously redundant for the Golf script.

So, the final spiral generation loop is this:

$d=1;
while ($h * ($i=$w--)) {        
    $x+=$d, p while $i--;
    $i=$h--;
    $y+=$d, p while --$i;
    $d=-$d; 
}

And one more thing to change in the printing code. First I gain one char by replacing the \n with a real newline character:

print "
"

But then, after reading perldoc perlop and Perl Golf 101, I discovered that the golfers have already invented using the $/ special variable instead of "\n".

Finally, a small but useful experiment by replacing string concatenation

printf "%-".(1+length$L[$_])."i"

with interpolation with embedded code "@{[]}":

printf "%-@{[1+length$L[$_]]}i"

Done. 213 symbols:

sub p{$L[$x]=$a[$x][$y]=++$n}($p,$q)=($w,$h)=@ARGV;$d=1;while($h*($i=$w--))
{$x+=$d,p while$i--;$i=$h--;$y+=$d,p while--$i;$d=-$d}$L[$p]='';
for$y(0..$q-1){printf"%-@{[1+length$L[$_]]}i",$a[$_][$y]for 1..$p;print$/}

A few words about other interesting stuff that you can find in the solutions of other participants.

Alexander Orlenko duplicated the initial parameters:

($w,$h,$y,$z)=(@ARGV)x2;

Althought this is two characters longer than this:

($p,$q)=($w,$h)=@ARGV;

In the Golf announcer's version bronton.pl there's another interesting method of initialising variables:

($c,$m,$n)=(1,@ARGV);

Nevertheless it is shorter to make it step by step:

$c=1;($m,$n)=@ARGV;

Nikolay Shulyakovsky exploited the seldomly used flip-flop operator ...:

do{$r[$j][$v+($i+=$v)]+1}...do{$r[$v+($j+=$v)][$i]+1and$v*=-1}

Andrey Fedorov changes the direction, with multiplying by -1 or 0, making the trick to get it from the current position:

$X*=!!$Y--;$k*=-1;

By the way, multiplying by one is of the same length as an explicit sign change:

$k*=-1;
$k=-$k;

Andrey also found the way to make printf's format shorter and used the %-*d format string, passing the length in a separate argument, thus getting rid of string interpolation:

printf'%-*d ',$s[$_],$$B[$_]for 0..$w-2;

Sergey Khripunov used a useful hack to gain characters by avoiding the length keyword:

$l=y///c;

In the Eugeniy Kim's solution the corners are being calculated with the pre-filled border matrix:

@r=([1,0],[0,1],[-1,0],[0,-1]);
. . .
($x,$y)=@{$r[++$d%4]}

Anatoly Grishaev first creates the dummy matrix and then fills it with numbers:

($a,$b)=@ARGV;$_=('1 'x$a++."0\n")x$b;@s=split;s/\d/$z++/ge;

(Originally published in Russian in the Pragmatic Perl magazine #28)