Re^2: Spiraling integers (explained)

[tye]

in reply to Re: Spiraling integers
in thread Spiraling integers

It was suggested I explain my approach, but since it took me days to get around to it, an 'update' notice is inappropriate (and I never 'got' the taboo against "self replies").

As I said, I consider the approach pretty straight-forward. First, you need a square grid to fill in. Add to it a few markers so you can tell when you've fallen off the edge (called "sentinel values"):

  0  0  0  0 -1
  0  0  0  0
  0  0  0  0 -1
  0  0  0  0
          -1

Then start at the upper left, move along filling in increasing values until you run into an occupied spot, at which point you turn to the right and continue (unless the spot to the right is already full, in which case you are done):

  1  2  3  4*-1
  0  0  0  5
  0  0  0  6 -1
  0  0  0  7
           *
          -1

The "*"s show the "collisions" with the sentinel values that cause a change in direction.

But, how do you represent this matrix? For ease of coding, I used a single array and just treated it like a rectangle of width N+1:

  1  2  3  4 -1
  0  0  0  5  x
  0  0  0  6 -1
  0  0  0  7  x
  x  x  x -1...

Which explains that third sentinel value:

  1  2  3  4 -1
  *
 12  0  0  5  x
 11  0  0  6 -1>
<10  9  8  7  x
  x  x  x -1...

Note the "<" and ">" showing the two sides of the next collision.

So, on to the code, less compactly written:

#!/usr/bin/perl -w
use strict;

# The width of our square
# ($ARGV[0] or 5 if no arguments given):
my $n= (@ARGV,5)[0];

# Our square, of size $n+1 x $n+1 due to the sentinel values:
my @s= ( ( (0)x$n, -1 )x$n, (-1)x$n, -1 );

# The directions we will move (right, down, left, up)
# since from $s[$p], $s[$p+1] is just to the right and
# $s[$p-$n-1] is just above:
my @d= ( 1, $n+1, -1, -$n-1 );

# Our starting direction, an index into @d; 0 for "right", $d[0]:
my $d= 0;

# Our starting position (index into @s); -1 so our first step
# to the right will land us at $s[0]:
my $p= -1;

# Our starting value (to be stored into @s);
# 0 so we'll enter 1 after our first step:
my $v= 0;

# Take a step ($p +=).  If that step lands on an occupied
# spot, then we're done.  So continue while zero (not true):
while(  ! $s[ $p += $d[$d] ]  ) {
    # Store the next value where we just stepped to:
    $s[$p]= ++$v;

    # Look where we will step next.
    # If occupied (not zero, i.e. true)...
    if(  $s[ $p + $d[$d] ]  ) {
        # ...then switch to the "next" direction in @d
        # wrapping back to $d[0] if needed:
        $d= ($d+1) % @d;
    }
}

# Print out the 1..$v values plus $n newlines represented
# by the first $v+$n elements of @s:
for(  @s[ 0 .. $v+$n-1 ]  ) {
    # Sentinel values represent newlines:
    if(  $_ < 0  ) {
        print $/;
    } else {
        # Otherwise left-justify the value, just
        # wide enough to hold the largest value, $v:
        printf " %".length($v)."d", $_;
    }
}

Note that

my @s= ( ( (0)x$n, -1 )x$n, (-1)x$n, -1 );

Sets up $n rows of ( $n zeros followed by one -1 ), then a row of $n+1 -1s:

  0  0  0  0 -1
  0  0  0  0 -1
  0  0  0  0 -1
  0  0  0  0 -1
 -1 -1 -1 -1 -1

This is convenient because the code is compact and we can use the right-hand -1s to represent newlines when we print things out.

Note that final extra -1 and note that we got it in via (-1)x$n, -1 and not (-1)x($n+1). Why is it there and why via that code?

Because I prefer my code to behave reasonbly even in the face of unreasonable input. Consider $n == -5. Perl silently treats (...)x-5 the same as (...)x0, giving an empty list. So @s ends up containing simply (-1), but would have been completely empty if we'd written the code the other way since (...)x-4 also gives an empty list.

And if @s is empty, our while loop becomes an infinite loop generating a infinite number of warnings. But with @s= (-1), our while loop immediately ends instead.

Note also that the printing loop goes from 0..$v+$n-1 not 0..$n*$n+$n (for example). Otherwise, the print loop would print a newline, 19 zeros, and 19 warnings when given $n= -5. Instead, it is also sane and does nothing for negative values of $n.

Also note that by never calculating $n*$n, my code sanely treats 2.9 exactly the same as it treats 2 [and without me having to use int()].