Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
We don't bite newbies here... much
 
PerlMonks  

Spiraling integers

by Elijah (Hermit)
on Aug 28, 2005 at 00:08 UTC ( #487200=CUFP: print w/ replies, xml ) Need Help??

I came across a challenge at a site I visit regularly and decided to give it a go.

The challenge was to write a program (in any language) to get a spiraling printout of integers based upon the user input. For example if the user input "5" then the output would be:

1   2   3   4   5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

. . . . n
.
.
.
. . . . 2n-1 and so on...

I decided to of course write it in perl and used a two dimensional array method. Here is the code I came up with:

#!/usr/bin/perl -w use strict; print "Enter n: "; chomp(my $n = <>); my @shiza; my $firstD = my $secondD = 0; my $cnt = my $inc = 1; while ($cnt <= ($n*$n)) { while (!$shiza[$firstD][$secondD] && $secondD < $n && $inc == 1) { $shiza[$firstD][$secondD] = $cnt; $secondD++ unless($shiza[$firstD][$secondD+1] || ($secondD+1) >= + $n); $cnt++; } $firstD++; while (!$shiza[$firstD][$secondD] && $firstD < $n && $inc == 1) { $shiza[$firstD][$secondD] = $cnt; $firstD++ unless($shiza[$firstD+1][$secondD] || ($firstD+1) >= $ +n); $cnt++; } $secondD--; $inc = 0; while (!$shiza[$firstD][$secondD] && $secondD >= 0 && $inc == 0) { $shiza[$firstD][$secondD] = $cnt; $secondD-- unless($shiza[$firstD][$secondD-1] || ($secondD-1) < +0); $cnt++; } $firstD--; while (!$shiza[$firstD][$secondD] && $firstD >= 0 && $inc == 0) { $shiza[$firstD][$secondD] = $cnt; $firstD-- unless($shiza[$firstD-1][$secondD] || ($firstD-1) < 0) +; $cnt++; } $secondD++; $inc = 1; } for (@shiza) { for (@{$_}) { print "$_\t" if($_); } print "\n"; }
I am sure there is a mathematical equation that would simplify this but I was spending too much time with my TI-89 Titanium trying to figure it out so I just decided to write it assigning the values to the two dimensional way in a spiraling manner also.

Comment on Spiraling integers
Download Code
Re: Spiraling integers
by lidden (Deacon) on Aug 28, 2005 at 01:30 UTC
    I had to spiral too.
    my $n = shift; my @AoA; my $flip = 0; my @directions = ( 'right', 'down', 'left', 'up'); my $direction = $directions[ $flip % 4 ]; my ($x, $y) = (0, 0); for ( 1 .. $n * $n ){ $AoA[ $x ][ $y ] = $_; $flip++ if 'right' eq $direction and ( $x == $n - 1 or $AoA[ $x + +1 ][ $y ]); $flip++ if 'down' eq $direction and ( $y == $n - 1 or $AoA[ $x ][ + $y + 1 ]); $flip++ if 'left' eq $direction and ( $x == 0 or $AoA[ $x - +1 ][ $y ]); $flip++ if 'up' eq $direction and ( $AoA[ $x ][ + $y - 1 ]); $direction = $directions[ $flip % 4 ]; $x++ if 'right' eq $direction; $y++ if 'down' eq $direction; $x-- if 'left' eq $direction; $y-- if 'up' eq $direction; } for my $y (0..$n-1){ for my $x (0..$n-1){ printf "%5d ", $AoA[$x][$y]; # for some value of 5 } print "\n"; }
Re: Spiraling integers
by GrandFather (Cardinal) on Aug 28, 2005 at 01:55 UTC

    A recursive solution:

    use strict; use warnings; my $n = shift; my $count = 1; my @matrix; push @matrix, [(0)] for (1..$n); buildRing (0, $n - 1); my $width = length sprintf ("%s", '' . $count); my $format = "%${width}d"; print "" . (join " ", map {sprintf $format, $_} @{$matrix[$_]}) . "\n" + for (0..($n-1)); sub buildRing { my ($first, $last) = @_; $matrix[$first][$_] = $count++ for ($first..$last); $matrix[$_][$last] = $count++ for (($first+1)..$last); $matrix[$last][$last-$_+$first-1] = $count++ for ($first..$last-1); for ($_ = --$last; $_ > $first; --$_) {$matrix[$_][$first] = $count++} $matrix[$first][$last] = $count if (++$first == $last); buildRing ($first, $last) if ($first<$last); }
    Update: added (smaller) non-recursive version and golf version

    Perl is Huffman encoded by design.
Re: Spiraling integers
by ambrus (Abbot) on Aug 28, 2005 at 09:50 UTC
    to write a program (in any language)

    Would it offend the dear monks if I posted a program in J then? I hope no. (Even though you say any language, that's for the original question, ant this is perlmonks.)

    Here's the program:

    spiral =: 3 : 0 >: (,~ y.) $ (i. *: y.) i.~ /: ,/ (-@>.&| , -@{:@*.@(1j_1&*)@j.)"0/~ ( +i. y.) - -:<: y. ) 2!:55[0[ 1!:2&2 spiral 5".>{: ARGV

    To run it,

    1. first get a J User Licence by filling this form;
    2. download J;
    3. set it up by the instructions in readme.txt (comes with the download);
    4. save the above code as spiral.ijs (don't break the long line);
    5. and run jconsole spiral.ijs 5 (5 is an integer giving the spiral size, defaults to 5).
    (You can of course skip the first four steps if you have already done them.)

    Update 2007 dec 7: better definition for the spiral function is

    spiral =: - ]\ i.@:*: [`]`[} [: \: [: ,/ [: (>.&| , 12&o.@(1j_1&*)@j.) +"0/~ i. - -:@:<:
      You don't to get a user license any more to use J...
Re: Spiraling integers
by ambrus (Abbot) on Aug 28, 2005 at 09:58 UTC

    Btw, I have already written something similar in perl.

    I had to generate the sequence of (x,y) coordinates in spiral, something like this:

    0,0 0,1 1,1 1,0 1,-1 0,-1 -1,-1 -1,0 -1,1 -1,2 0,2 1,2 2,2 2,1 2,0 2,-1 ...

    This was for an internet game. I wanted to discover the islands on a map with a ship in some order. This order is good becuse this way the ship travels only 1 units of distance in each step, so the discovery was fast, and I discovered the islands near my island first (as that's where the center of the spiral was).

    Bots have since been banned in that game, so I have deleted the code. Sorry.

Re: Spiraling integers
by ambrus (Abbot) on Aug 28, 2005 at 11:08 UTC

    Here's my perl solution, which is more or less the translation of the J solution:

    #!perl use warnings; use strict; use List::Util "max"; use Math::Complex; # what for? my $n = int($ARGV[-1] || 5); my($i, $j, $k, $x, $y, @l, @a, @v, @r, $wd, $fmt); for $i (0 .. $n - 1) { $x = $i - ($n - 1)/2; for $j (0 .. $n - 1) { $y = $j - ($n - 1)/2; $k = $i * $n + $j; $l[$k] = -max(abs($x), abs($y)); $a[$k] = -arg(cplx(1, -1) * cplx($x, $y)); } } @v = sort { $l[$a] <=> $l[$b] || $a[$a] <=> $a[$b] } 0 .. $n**2 - 1; @r[@v] = 1 .. $n**2; $wd = length($n**2); $fmt = join(" ", ("%${wd}d") x $n) . "\n"; for $i (0 .. $n - 1) { printf $fmt, @r[$i * $n .. $i * $n + $n - 1]; } __END__
Re: Spiraling integers
by salva (Monsignor) on Aug 28, 2005 at 14:24 UTC
    in prolog...
    matrix(S, M) :- length(M, S), matrix1(M, S). matrix1([], _). matrix1([H|T], S) :- length(H, S), matrix1(T, S). next(A, B, A, B). next(1, 0, 0, 1). next(0, 1, -1, 0). next(-1, 0, 0, -1). next(0, -1, 1, 0). solve(N, M) :- N2 is N*N, numlist(1, N2, L), matrix(N, M), solve(L, -1, 0, 1, 0, M). solve([], _, _, _, _, _). solve([Ix|T], X, Y, Dx, Dy, M) :- next(Dx, Dy, Dx1, Dy1), Y1 is Y+Dy1, X1 is X+Dx1, nth0(Y1, M, Row), nth0(X1, Row, Ix), !, solve(T, X1, Y1, Dx1, Dy1, M). :- solve(5, M), writeln(M).
Re: Spiraling integers
by CountZero (Chancellor) on Aug 28, 2005 at 20:59 UTC
    In English (you said "in any language"):
    1. On a piece of paper, draw a square with sides equal to n.
    2. Divide the square into n x n equal little squares (call these "cells")
    3. Starting at the leftmost cell in the top row, write in it the figure 1
    4. In the empty cell to the right of the cell you just wrote into, write the value you just wrote plus 1; if there is no empty cell to the right, change your direction of movement to downwards.
    5. Keep moving in the same direction and writing down a number, equal to the one last written plus 1; if there is no empty cell in the direction you were moving, change direction as follows:
      • If you were moving to the right, change to downwards
      • If you were moving downwards, change to left
      • If you were moving to the left, change to upwards
      • If you were moving up, change to right
    6. Stop when the last number written is equal to n x n

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: Spiraling integers
by Limbic~Region (Chancellor) on Aug 28, 2005 at 22:08 UTC
    Elijah,
    I am sure there is a mathematical equation that would simplify this but I was spending too much time with my TI-89 Titanium trying to figure it out so...

    There is an underlying pattern that can be reduced to simple enough instructions to end up with a single array of N2 elements populated iteratively. It didn't take me too long to figure it out once I flattened a couple of starting lists with their corresponding solutions

    01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 01 02 03 04 12 13 15 05 11 16 15 06 10 09 08 07 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2 +4 25 01 02 03 04 05 16 17 18 19 06 15 24 25 20 07 14 23 22 21 08 13 12 11 1 +0 09
    You can see the solution below:

    Cheers - L~R

Re: Spiraling integers
by blokhead (Monsignor) on Aug 29, 2005 at 01:03 UTC
    81 chars to recursively construct the 2d array (not including "sub f {}"):
    sub f { #234567890123456789012345678901234567890123456789012345678901234567890 +12345678901 my$x=my$i=pop;$x?([1..$x],map[(map$_+2*$x-1,reverse@$_),++$i],reverse +f($x-1)):() }
    The first argument is the dimension of the spiral.
    ## print "@$_\n" for f(5); 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
    The recursive pattern is the following: An n x n spiral looks like this:
    +---------------+ | 1 2 3 ... n | | +-------+ n+1 | | | | . | | | *** | . | | | | . | | +-------+ 2n-1| +---------------+
    where the *** box is the (n-1) x (n-1) spiral, rotated 180 degrees and 2n-1 added to each component.

    Update: oops, moved a reverse to the right spot (didn't affect char count).

    blokhead

Re: Spiraling integers
by demerphq (Chancellor) on Aug 29, 2005 at 11:55 UTC

    Non recursive implementation, strict safe, but not warning free. 252 chars.

    use strict; sub spiral { my$S=pop;my($z,$s,$t,$d,$x,$y,@b)=($S**2,1);@_=([1, 0],[0,1],[-1,0],[0,-1]);$b[$S][$_]=$b[$_][$S]=$/for 0..$S;map{$b[$y][$x]=sprintf"%0*d",length$z,$_;($s, $t)=@{$_[++$d%4]}if$s&&$b[$y][$x+$s]||$t&&$b[$y+$t] [$x];$x+=$s;$y+=$t}1..$z;pop@b;print"@$_"for@b; } for (1..10) { spiral($_); print "\n---\n"; }

    It could go smaller fairly easily by using globals, but then couldnt be run more than once per process.

    Update: And here is the annotated version. Funny, while annotating it I noticed a couple of things I could have done to make it smaller :-)

    use strict; sub spiral { my $size = pop; # get the size from the arguments my $elements = $size**2; # how many numbers in the square my $dir=0; # we will go right at start my ($dx,$dy)=(1,0); # starting deltas (must match $dir) my ($x,$y)=(0,0); # start top left my @board; # the board we will use my @delta=([1,0], # deltas for going right [0,1], # ... down [-1,0], # ... left [0,-1]); # ... up # Set up sentinal values in (x,$size) and ($size,y) # ie, a column on the right and a row at the bottom $board[$size][$_]=$board[$_][$size]="\n" for 0..$size; # The strategy is to treat $x,$y as a cursor on the grid. # each square we move in the direction specified by $dir # via the @delta table, assuming that is that the new # cell has not been filled already. if it has we turn to # the right by incrementing $dir and finding new deltas. for (1..$elements) { # neatly set up the value in the grid, we use the length of # the center element to determine how many digits to use per " +cell" $board[$y][$x] = sprintf"%0*d",length $elements, $_; # if we bump into something we need to turn to the right # the sentinals mean we dont have to check for anything other # than the cell being nonempty in the direction we are travell +ing ($dx,$dy)=@{$delta[++$dir%4]} if $dx && $board[$y][$x+$dx] || $dy && $board[$y+$dy][$x]; # and adjust our position according to the deltas $x+=$dx; $y+=$dy }; # we need to remove the bottom row as it is just a list of newline +s pop @board; # and now we print it out, we dont need to remove the right hand # sentinals as they conveniently end the line for us. print"@$_" for @board; } for (1..10) { spiral($_); print "\n---\n"; }
    ---
    $world=~s/war/peace/g

Re: Spiraling integers
by ambrus (Abbot) on Aug 29, 2005 at 12:38 UTC
    I am sure there is a mathematical equation that would simplify this

    Well, here's it. I hope it works. Has someone written a test program that compares the outputs of different solutions in this thread with each other?

    #!perl use warnings; use strict; my($n, $wd, $fmt, $x, $y, $r); $n = int($ARGV[-1] || 5); $wd = length($n**2); $fmt = "%${wd}d "; for $x (0 .. $n - 1) { for $y (0 .. $n - 1) { $r = $x <= $y ? $x + $y <= $n - 1 ? -4*$x**2 + 4*$n*$x - $x + $y + 1 : -4*$y**2 + 4*$n*$y - 5*$y + $x + 2*$n +- 1 : $x + $y <= $n - 1 ? -4*$y**2 + 4*$n*$y - 7*$y - $x + 4*$n +- 3 : -4*$x**2 + 4*$n*$x - 3*$x - $y + 2*$n +- 1; printf $fmt, $r; } print "\n"; } __END__
      Well I used this program I did over a year ago to compare numbers from diffrent programs. I would have done it diffrently now so don't complan too much about the sub optimal stuff.
      #!/usr/bin/perl -w use strict; use constant true => 1; use constant false => 0; use Perl6::Say; use Perl6::Variables; exit say 'You must give at least two file names as arguments.' unless +@ARGV > 1; my $tmp_path = '/tmp/same_or.tmp'; my @files; my $i = 0; my @num; foreach my $file (@ARGV) { open IN, $file or die "Damn $file: $!"; open OUT, '>', $tmp_path . $i or die $!; my $num = 0; while (<IN>) { s/^\s+//; my @text = split /\s+/, $_; $num += scalar @text; foreach (@text) { say OUT $_; } } close IN or die $!; close OUT or die $!; @num[ $i ] = $num; push @files, $tmp_path . $i; $i++; } my $first = shift @files; say "\@num[0] = @num[0]"; $i = 1; foreach my $file (@files) { open IN1, $first or die $!; open IN2, $file or die $!; say "\@num[$i] = @num[$i]"; unless ( @num[ 0 ] == @num[ $i ] ) { unlink $first; unlink @files; exit print "Different length\n"; } while (<IN1>) { # (my $i = 0; $i < @first; $i++){ my $in2 = <IN2>; unless ( $_ == $in2 ) { unlink $first; unlink @files; chomp; chomp $in2; exit print "Numbers $_ == $in2 failed\n"; } } close IN1 or die $!; close IN2 or die $!; $i++; } print "Same \n"; unlink $first; unlink @files;
Re: Spiraling integers
by tye (Cardinal) on Aug 29, 2005 at 15:02 UTC

    This is mostly just the straight-forward way I'd do it, but I'm posting it because it appears shorter than most of the solutions so far (though, intentionally written more compactly than usual):

    #!/usr/bin/perl -w use strict; my $n= (@ARGV,5)[0]; my @s= (((0)x$n,-1)x$n,(-1)x$n,-1); my @d= (1,$n+1,-1,-$n-1); my($p,$d,$v)=(-1,0,0); while( ! $s[$p+=$d[$d]] ) { $s[$p]= ++$v; $d= ($d+1)%@d if $s[$p+$d[$d]]; } printf $_<0?$/:" %".length($v)."d", $_ for @s[0..$v+$n-1];

    - tye        

      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        

Re: Spiraling integers
by jimX11 (Friar) on Aug 30, 2005 at 00:40 UTC

    Putting a real world twist on this interesting puzzle, the type of unexpected twists I often see, how would your solution adapt to the following alteration.

    The client loves your solution, but asks how hard would it be to make the spiral start at the center.

      Easy,

      I made three simple changes.
      First: start $cnt as $n*$n instead of 1.
      Second: change while loop to continue until $cnt is not greater then 0.
      Third: decrement $cnt everywhere it was incremented before.

      #!/usr/bin/perl -w use strict; print "Enter n: "; chomp(my $n = <>); my @shiza; my $firstD = my $secondD = 0; my $cnt = $n*$n; my $inc = 1; while ($cnt > 0) { while (!$shiza[$firstD][$secondD] && $secondD < $n && $inc == 1) { $shiza[$firstD][$secondD] = $cnt; $secondD++ unless($shiza[$firstD][$secondD+1] || ($secondD+1) >= + $n); $cnt--; } $firstD++; while (!$shiza[$firstD][$secondD] && $firstD < $n && $inc == 1) { $shiza[$firstD][$secondD] = $cnt; $firstD++ unless($shiza[$firstD+1][$secondD] || ($firstD+1) >= $ +n); $cnt--; } $secondD--; $inc = 0; while (!$shiza[$firstD][$secondD] && $secondD >= 0 && $inc == 0) { $shiza[$firstD][$secondD] = $cnt; $secondD-- unless($shiza[$firstD][$secondD-1] || ($secondD-1) < +0); $cnt--; } $firstD--; while (!$shiza[$firstD][$secondD] && $firstD >= 0 && $inc == 0) { $shiza[$firstD][$secondD] = $cnt; $firstD-- unless($shiza[$firstD-1][$secondD] || ($firstD-1) < 0) +; $cnt--; } $secondD++; $inc = 1; } for (@shiza) { for (@{$_}) { print "$_\t" if($_); } print "\n"; }

      Easy, just subtract every number from n**2 + 1. See, here's the original spiral:

      1 2 3 8 9 4 7 6 5
      We subtract it from 10,
      10-1 10-2 10-3 10-8 10-9 10-4 10-7 10-6 10-5 = 9 8 7 2 1 6 3 4 5

      Also note that in my J solution, all you have to do is to change the /: operator to \:. Can you do this with a one-charater change to any other existing solutions? :)

      Changing for (1 .. $n * $n ){ to for (reverse 1 .. $n * $n ){
Re: Spiraling integers
by jdporter (Canon) on Aug 31, 2005 at 15:02 UTC
    Well, you've already got lots of solutions, but here's mine. I build the spiral, as a 2-d array, from the inside out.
    spiral_numbers(5); sub spiral_numbers { my $n = shift; local $_; my @nums = 1 .. $n**2; my @a = ( [ pop @nums ] ); for my $k ( 2 .. $n ) { if ( $k & 1 ) # odd { push @$_, pop @nums for @a[ reverse 0 .. $k-2 ]; unshift @a, my $r=[]; unshift @$r, pop @nums for 1 .. $k; } else # even { unshift @$_, pop @nums for @a[ 0 .. $k-2 ]; push @a, my $r=[]; push @$r, pop @nums for 1 .. $k; } } # print it out local( $\, $, ) = ( "\n", "\t" ); if ( $n & 1 ) # odd { print @$_ for @a; } else # even { print reverse @$_ for reverse @a; } }
Re: Spiraling integers
by danmcb (Monk) on Sep 06, 2005 at 08:48 UTC

    Nice problem! and some nice solutions ... everyone loves a diversion ...

    Here's mine. For variety, and cos I'm looking for a new job (wink) I went for an OO approach. Certainly not the least characters, and I'm not sure it adds much in readability, but something different. Perhaps not even that, as I suspect that it is really a dressed up version of the iterative solution that was given already. Anyhow, here it is. I had fun doing it.

    The object itself:

    package SpiralSq; use strict; sub new { my ($class, $size, $offset) = @_; $offset = 1 unless defined ($offset); my $self = { 'size'=>$size, 'offset' => $offset, 'nextoffset' => (4*($size - 1) + $offset)}; bless $self, $class; return $self; } sub getInside { my ($self) = @_; $self->{'inside'} = new SpiralSq($self->{'size'} - 2, $self->{'nextoffset'}) unless (defined $self->{'inside'}); return $self->{'inside'}; } sub getRow { my ($self, $r) = @_; my $o = $self->{'offset'}; my $s = $self->{'size'}; my $n = $self->{'nextoffset'}; my @row; if ($r == 0) { @row = ($o .. ($s - 1 + $o)); } elsif ($r == $s - 1) { @row = ((2*($s - 1) + $o) .. (3*($s - 1) + $o)); @row = reverse @row; } elsif ($r < $s) { @row = (($n - $r), $self->getInside->getRow($r - 1), ($s -1 + $r + $o)); } else { die "error!"; } return @row; } 1;

    And a test script:

    #!/opt/perl/bin/perl -w use strict; use SpiralSq; my $n = 18; my $s = new SpiralSq($n); for (0 .. ($n-1)) { print join " ", $s->getRow($_); print "\n"; }

Re: Spiraling integers
by ambrus (Abbot) on Sep 10, 2005 at 21:40 UTC

    Yet another J solution. This one has two functions that mutually recursively build the spiral. This one too accepts the size of the spiral as argument.

    spiralh =: (,:@i. , ] + [: |:@|. spirals) ` ((1 0$0)"_) @. (<:&0) spirals =: ,:@i. , ] + [: |:@|. [: spiralh <: spiral =: ([: >: spirals)"0 2!:55[0[ 1!:2&2 spiral 5".>{: ARGV

    This is getting addictive, isn't it?

Re: Spiraling integers
by ambrus (Abbot) on Dec 03, 2007 at 19:50 UTC

      Hadn't looked, myself, although I realized from your mention of the outward spiral that that one would be the base used in to produce a Ulam spiral (which I know has been asked about here before).

Re: Spiraling integers
by ambrus (Abbot) on Jun 04, 2008 at 19:40 UTC
Re: Spiraling integers
by oakbox (Chaplain) on Nov 16, 2012 at 23:07 UTC
    I was just playing with this for funsies after seeing a youtube video from Vi Hart about Ulam's Spiral. http://www.youtube.com/embed/Yhlv5Aeuo_k

    So, I wrote the following spiral generator that writes the output to a SVG file. It takes about 10 seconds on my laptop to generate a graph of all primes between 1 and 10,000,000.

    I see now that lot's of other people have taken a crack at this, but TMTOWTDI :)

    #!/usr/bin/perl my $x = 1; my $y = 1; use Math::Prime::XS qw(is_prime); my $maxcount = 1000000; open(WRT,">primegrid.svg"); print WRT q(<?xml version="1.0" encoding="UTF-8" standalone="no"?> <!-- Created with Inkscape (http://www.inkscape.org/) --> <svg xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://creativecommons.org/ns#" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:svg="http://www.w3.org/2000/svg" xmlns="http://www.w3.org/2000/svg" xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" width="1" height="1" id="svg2" version="1.1" inkscape:version="0.48.3.1 r9886" sodipodi:docname="New document 1"> <defs id="defs4" /> <sodipodi:namedview id="base" pagecolor="#ffffff" bordercolor="#666666" borderopacity="1.0" inkscape:pageopacity="1" inkscape:pageshadow="2" inkscape:zoom="42.250643" inkscape:cx="8.8460039" inkscape:cy="2.865365" inkscape:document-units="px" inkscape:current-layer="layer1" showgrid="false" inkscape:window-width="1073" inkscape:window-height="740" inkscape:window-x="0" inkscape:window-y="0" inkscape:window-maximized="0" /> <metadata id="metadata7"> <rdf:RDF> <cc:Work rdf:about=""> <dc:format>image/svg+xml</dc:format> <dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage" /> <dc:title></dc:title> </cc:Work> </rdf:RDF> </metadata>); my $gridholder; my $direction; foreach my $number ( 1 ... $maxcount ){ print "$number\r"; if($direction eq ""){ $gridholder->{$x}->{$y} = $number; markprime($x,$y,$number); $direction = 'r'; next; } if($direction eq 'r'){ $x++; $gridholder->{$x}->{$y} = $number; markprime($x,$y,$number); my $yp = $y + 1; if($gridholder->{$x}->{$yp} eq ""){ $direction = 'd'; } next; } if($direction eq 'd'){ $y++; $gridholder->{$x}->{$y} = $number; markprime($x,$y,$number); my $xp = $x - 1; if($gridholder->{$xp}->{$y} eq ""){ $direction = 'l'; } next; } if($direction eq 'l'){ $x--; $gridholder->{$x}->{$y} = $number; markprime($x,$y,$number); my $yp = $y - 1; if($gridholder->{$x}->{$yp} eq ""){ $direction = 'u'; } next; } if($direction eq 'u'){ $y--; $gridholder->{$x}->{$y} = $number; markprime($x,$y,$number); my $xp = $x + 1; if($gridholder->{$xp}->{$y} eq ""){ $direction = 'r'; } next; } } sub markprime { my ($x, $y, $number) = @_; if(is_prime($number)){ print WRT qq( <rect style="fill:#000000;fill-opacity:1;stroke:none" id="rect2985" width="1" height="1" x="$x" y="$y" ry="0" /> ); } return(); } print WRT q( </svg>); print "done\n";
Re: Spiraling integers
by hdb (Parson) on Jan 22, 2014 at 09:02 UTC

    Here is my ASCII version of Ulam's spiral, ie. spiralling outwards not inwards.

    use strict; use warnings; use Math::Prime::XS 'sieve_primes'; my $n = shift; my %primes = map { $_ => 'O' } sieve_primes $n; my @spiral; my $o = 1 + int( sqrt( $n )/2 ); my ( $x, $y ) = ( $o, $o ); # starting point my ( $xs, $ys ) = ( 1, 0 ); # initial direction my $flip = 1; # change of direction indicator my $m = 1; # length of current lag for my $i ( 1..$n ) { $spiral[$y][$x] = $primes{ $i }//' '; $x += $xs; $y += $ys; ($xs, $ys) = ( ( $flip=1-$flip ) and $m++ ) ? ($ys, 0) : (0, -$xs) + unless $i%$m; } $spiral[$o][$o] = 'X'; print join '', map { $_//' '} @$_, "\n" for @spiral;

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://487200]
Approved by Zaxo
Front-paged by caedes
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (5)
As of 2014-04-20 04:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls