Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

comment on

( #3333=superdoc: print w/replies, xml ) 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"):

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()].

- tye        

In reply to Re^2: Spiraling integers (explained) by tye
in thread Spiraling integers by Elijah

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (5)
    As of 2020-09-19 15:29 GMT
    Find Nodes?
      Voting Booth?
      If at first I donít succeed, I Ö

      Results (114 votes). Check out past polls.