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
.
.
.
. . . . 2n1 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][$secondD1]  ($secondD1) <
+0);
$cnt++;
}
$firstD;
while (!$shiza[$firstD][$secondD] && $firstD >= 0 && $inc == 0) {
$shiza[$firstD][$secondD] = $cnt;
$firstD unless($shiza[$firstD1][$secondD]  ($firstD1) < 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 TI89 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.
Re: Spiraling integers
by lidden (Curate) on Aug 28, 2005 at 01:30 UTC

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..$n1){
for my $x (0..$n1){
printf "%5d ", $AoA[$x][$y]; # for some value of 5
}
print "\n";
}
 [reply] [d/l] 
Re: Spiraling integers
by GrandFather (Saint) on Aug 28, 2005 at 01:55 UTC

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..($n1));
sub buildRing
{
my ($first, $last) = @_;
$matrix[$first][$_] = $count++ for ($first..$last);
$matrix[$_][$last] = $count++ for (($first+1)..$last);
$matrix[$last][$last$_+$first1] = $count++ for ($first..$last1);
for ($_ = $last; $_ > $first; $_)
{$matrix[$_][$first] = $count++}
$matrix[$first][$last] = $count if (++$first == $last);
buildRing ($first, $last) if ($first<$last);
}
Update: added (smaller) nonrecursive version and golf version
Perl is Huffman encoded by design.
 [reply] [d/l] [select] 
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__
 [reply] [d/l] 
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 TI89 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 N^{2} 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:
 [reply] [d/l] [select] 
Re: Spiraling integers
by salva (Canon) on Aug 28, 2005 at 14:24 UTC

matrix(S, M) :
length(M, S),
matrix1(M, S).
matrix1([], _).
matrix1([HT], 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([IxT], 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).
 [reply] [d/l] 
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*$x1,reverse@$_),++$i],reverse
+f($x1)):()
}
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 
   . 
  ***  . 
   . 
 ++ 2n1
++
where the *** box is the (n1) x (n1) spiral, rotated 180 degrees and 2n1 added to each component.
Update: oops, moved a reverse to the right spot (didn't affect char count).
 [reply] [d/l] [select] 
Re: Spiraling integers
by tye (Sage) on Aug 29, 2005 at 15:02 UTC

This is mostly just the straightforward 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,$n1);
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+$n1];
 [reply] [d/l] 

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 straightforward. 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$n1] is just above:
my @d= ( 1, $n+1, 1, $n1 );
# 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+$n1 ] ) {
# Sentinel values represent newlines:
if( $_ < 0 ) {
print $/;
} else {
# Otherwise leftjustify 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 righthand 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 (...)x5 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 (...)x4 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+$n1 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()].
 [reply] [d/l] [select] 
Re: Spiraling integers
by CountZero (Bishop) on Aug 28, 2005 at 20:59 UTC

In English (you said "in any language"): On a piece of paper, draw a square with sides equal to n.
 Divide the square into n x n equal little squares (call these "cells")
 Starting at the leftmost cell in the top row, write in it the figure 1
 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.
 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
 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 4pass compiler."  Conway's Law
 [reply] 
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,
 first get a
J User Licence by filling this form;
 download J;
 set it up by the instructions in readme.txt (comes with the download);
 save the above code as spiral.ijs (don't break the long line);
 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.  :@:<:
 [reply] [d/l] [select] 

You don't to get a user license any more to use J...
 [reply] 
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__
 [reply] [d/l] 

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;
 [reply] [d/l] 
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.
 [reply] [d/l] 
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
 [reply] [d/l] [select] 
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 2d 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 .. $k2 ];
unshift @a, my $r=[];
unshift @$r, pop @nums
for 1 .. $k;
}
else # even
{
unshift @$_, pop @nums
for @a[ 0 .. $k2 ];
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;
}
}
 [reply] [d/l] 
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.
 [reply] 

1 2 3
8 9 4
7 6 5
We subtract it from 10,
101 102 103
108 109 104
107 106 105
=
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 onecharater change to any other existing solutions? :)
 [reply] [d/l] [select] 

#!/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][$secondD1]  ($secondD1) <
+0);
$cnt;
}
$firstD;
while (!$shiza[$firstD][$secondD] && $firstD >= 0 && $inc == 0) {
$shiza[$firstD][$secondD] = $cnt;
$firstD unless($shiza[$firstD1][$secondD]  ($firstD1) < 0)
+;
$cnt;
}
$secondD++;
$inc = 1;
}
for (@shiza) {
for (@{$_}) {
print "$_\t" if($_);
}
print "\n";
}
 [reply] [d/l] 

Changing for (1 .. $n * $n ){ to for (reverse 1 .. $n * $n ){
 [reply] [d/l] [select] 
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="UTF8" 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/22rdfsyntaxns#"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns="http://www.w3.org/2000/svg"
xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi0.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:documentunits="px"
inkscape:currentlayer="layer1"
showgrid="false"
inkscape:windowwidth="1073"
inkscape:windowheight="740"
inkscape:windowx="0"
inkscape:windowy="0"
inkscape:windowmaximized="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;fillopacity:1;stroke:none"
id="rect2985"
width="1"
height="1"
x="$x"
y="$y"
ry="0" />
);
}
return();
}
print WRT q(
</svg>);
print "done\n";
 [reply] [d/l] 
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 .. ($n1))
{
print join " ", $s>getRow($_);
print "\n";
}
 [reply] [d/l] [select] 
Re: Spiraling integers
by ambrus (Abbot) on Dec 03, 2007 at 19:50 UTC

 [reply] 

 [reply] 
Re: Spiraling integers
by ambrus (Abbot) on Jun 04, 2008 at 19:40 UTC

 [reply] 
Re: Spiraling integers
by hdb (Monsignor) 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;
 [reply] [d/l] 
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?
 [reply] [d/l] 

