Spiral matrix

Produce a spiral array. A spiral array is a square arrangement of the first N² natural numbers, where the numbers increase sequentially as you go around the edges of the array spiralling inwards.

For example, given 5, produce this array:

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

ALGOL 68

Translation of: Python

Works with: ALGOL 68 version Standard - no extensions to language used

Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

INT empty=0;

PROC spiral = (INT n)[,]INT: (
    INT dx:=1, dy:=0;            # Starting increments #
    INT x:=0, y:=0;              # Starting location #
    [0:n-1,0:n-1]INT my array;
    FOR y FROM LWB my array TO UPB my array DO
        FOR x FROM LWB my array TO UPB my array DO
            my array[x,y]:=empty
        OD
    OD;
    FOR i TO n**2 DO
        my array[x,y] := i;
        INT nx:=x+dx, ny:=y+dy;
        IF ( 0<=nx AND nx<n AND 0<=ny AND ny<n | my array[nx,ny] = empty | FALSE ) THEN
            x:=nx; y:=ny
        ELSE
            INT swap:=dx; dx:=-dy; dy:=swap;
            x+:=dx; y+:=dy
        FI
    OD;
    my array
);
 
PROC print spiral = ([,]INT my array)VOID:(
    FOR y FROM LWB my array TO UPB my array DO
        FOR x FROM LWB my array TO UPB my array DO
            print(whole(my array[x,y],-3))
        OD;
        print(new line)
    OD
);
 
print spiral(spiral(5))

Output:

  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

Fortran

Works with: Fortran version 90 and later

<lang fortran> PROGRAM SPIRAL

  IMPLICIT NONE
 
  INTEGER, PARAMETER :: size = 5
  INTEGER :: i, x = 0, y = 1, count = size, n = 0
  INTEGER :: array(size,size)

  DO i = 1, count
    x = x + 1 
      array(x,y) = n
    n = n + 1
  END DO

  DO
    count = count  - 1
      DO i = 1, count
        y = y + 1
        array(x,y) = n
        n = n + 1
      END DO
      DO i = 1, count
        x = x - 1
        array(x,y) = n
        n = n + 1
      END DO
      IF (n > size*size-1) EXIT
      count = count - 1
      DO i = 1, count
        y = y - 1
        array(x,y) = n
        n = n + 1
      END DO
      DO i = 1, count
        x = x + 1
        array(x,y) = n
        n = n + 1
      END DO	
      IF (n > size*size-1) EXIT
  END DO
   
  DO y = 1, size
    DO x = 1, size
      WRITE (*, "(I4)", ADVANCE="NO") array (x, y)
    END DO
    WRITE (*,*)
  END DO

END PROGRAM SPIRAL</lang>

Haskell

Solution based on the J hints:

grade xs = map snd. sort $ zip xs [0..]
values n = cycle [1,n,-1,-n]
counts n = (n:).concatMap (ap (:) return)  $ [n-1,n-2..1]
reshape n = unfoldr (\xs -> if null xs then Nothing else Just (splitAt n xs))

spiral n = reshape n . grade. scanl1 (+). concat $ zipWith replicate (counts n) (values n)

J

This function is the result of some beautiful insights:

   spiral =. ,~ $ [: /: }.@(2 # >:@i.@-) +/\@# <:@+: $ (, -)@(1&,)

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

Would you like some hints that will allow you to reimplement it in another language?

These inward spiralling arrays are known as "involutes"; we can also generate outward-spiraling "evolutes", and we can start or end the spiral at any corner, and go in either direction (clockwise or counterclockwise). See the first link (to JSoftware.com).

Octave

The function make_spiral (and helper functions) are modelled after the J solution.

<lang octave>function rs = runsum(v)

 for i = 1:numel(v)
   rs(i) = sum(v(1:i));
 endfor

endfunction

function g = grade(v)

 for i = 1:numel(v)
   g(v(i)+1) = i-1;
 endfor

endfunction

function spiral = make_spiral(spirald)

 series = ones(1,spirald^2);
 l = spirald-1; p = spirald+1;
 s = 1;
 while(l>0)
   series(p:p+l-1) *= spirald*s;
   series(p+l:p+l*2-1) *= -s;
   p += l*2;
   l--; s *= -1;
 endwhile
 series(1) = 0;
 spiral = reshape(grade(runsum(series)), spirald, spirald)';

endfunction

make_spiral(5)</lang>

Perl

<lang perl>sub spiral

{my ($n, $x, $y, $dx, $dy, @a) = (shift, 0, 0, 1, 0);
 foreach (0 .. $n**2 - 1)
    {$a[$y][$x] = $_;
     my ($nx, $ny) = ($x + $dx, $y + $dy);
     ($dx, $dy) =
         $dx ==  1 && ($nx == $n || defined $a[$ny][$nx])
       ? ( 0,  1)
       : $dy ==  1 && ($ny == $n || defined $a[$ny][$nx])
       ? (-1,  0)
       : $dx == -1 && ($nx  <  0 || defined $a[$ny][$nx])
       ? ( 0, -1)
       : $dy == -1 && ($ny  <  0 || defined $a[$ny][$nx])
       ? ( 1,  0)
       : ($dx, $dy);
     ($x, $y) = ($x + $dx, $y + $dy);}
 return @a;}

foreach (spiral 5)

  {printf "%3d", $_ foreach @$_;
   print "\n";}</lang>

Python

<lang python> def spiral(n):

   dx,dy = 1,0            # Starting increments
   x,y = 0,0              # Starting location
   myarray = [[None]* n for j in range(n)]
   for i in xrange(n**2):
       myarray[x][y] = i
       nx,ny = x+dx, y+dy
       if 0<=nx<n and 0<=ny<n and myarray[nx][ny] == None:
           x,y = nx,ny
       else:
           dx,dy = -dy,dx
           x,y = x+dx, y+dy
   return myarray

def printspiral(myarray):

   n = range(len(myarray))
   for y in n:
       for x in n:
           print "%2i" % myarray[x][y],
       print

printspiral(spiral(5)) </lang> Sample output:

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

Recursive Solution

<lang python>def spiral(n):

   def spiral_part(x, y, n):
       if x == -1 and y == 0:
           return -1
       if y == (x+1) and x < (n // 2):
           return spiral_part(x-1, y-1, n-1) + 4*(n-y)
       if x < (n-y) and y <= x:
           return spiral_part(y-1, y, n) + (x-y) + 1
       if x >= (n-y) and y <= x:
           return spiral_part(x, y-1, n) + 1
       if x >= (n-y) and y > x:
           return spiral_part(x+1, y, n) + 1
       if x < (n-y) and y > x:
           return spiral_part(x, y-1, n) - 1

   array = [[0] * n for j in xrange(n)]
   for x in xrange(n):
       for y in xrange(n):
           array[x][y] = spiral_part(y, x, n)
   return array

for row in spiral(5):

   print " ".join("%2s" % x for x in row)</lang>

Adding a cache for the spiral_part function it could be quite efficient.

Another way, based on preparing lists ahead

<lang python> def spiral(n):

   dat = [[None] * n for i in range(n)]
   le = [[i + 1, i + 1] for i in reversed(range(n))]
   le = sum(le, [])[1:]  # for n = 5 le will be [5, 4, 4, 3, 3, 2, 2, 1, 1]
   dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]] * ((len(le) + 4) / 4)  # long enough
   x, y, val = -1, 0, -1
   for steps, (dx, dy) in zip(le, dxdy):
       x, y, val = x + dx, y + dy, val + 1
       for j in range(steps):
           dat[y][x] = val
           if j != steps-1:
               x, y, val = x + dx, y + dy, val + 1
   return dat

for row in spiral(5): # calc spiral and print it

   print ' '.join('%3s' % x for x in row)

</lang>

Tcl

Using print_matrix from Matrix Transpose#Tcl <lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop} proc spiral size {

   set m [lrepeat $size [lrepeat $size .]]
   set x 0; set dx 0
   set y -1; set dy 1
   set i -1
   while {$i < $size ** 2 - 1} {
       if {$dy == 0} {
           incr x $dx
           if {0 <= $x && $x < $size && [lindex $m $x $y] eq "."} {
               lset m $x $y [incr i]
           } else {
               # change direction
               incr x [* -1 $dx]
               set dy [* -1 $dx]
               set dx 0
           }
       } else {
           incr y $dy
           if {0 <= $y && $y < $size && [lindex $m $x $y] eq "."} {
               lset m $x $y [incr i]
           } else {
               # change direction
               incr y [* -1 $dy]
               set dx $dy
               set dy 0
           }
       }
   }
   return $m

}

print_matrix [spiral 5]</lang>

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