|Don't ask to ask, just ask|
Re^2: Spiraling integers (explained)by tye (Sage)
|on Sep 03, 2005 at 06:38 UTC||Need Help??|
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"):
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):
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:
Which explains that third sentinel value:
Note the "<" and ">" showing the two sides of the next collision.
So, on to the code, less compactly written:
Sets up $n rows of ( $n zeros followed by one -1 ), then a row of $n+1 -1s:
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()].