Spiral

From Rosetta Code

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

[edit] Ada

-- Spiral Square
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;
 
procedure Spiral_Square is
   type Array_Type is array(Positive range <>, Positive range <>) of Natural;
 
   function Spiral (N : Positive) return Array_Type is
      Result  : Array_Type(1..N, 1..N);
      Row     : Natural := 1;
      Col     : Natural := 1;
      Max_Row : Natural := N;
      Max_Col : Natural := N;
      Min_Row : Natural := 1;
      Min_Col : Natural := 1;
   begin
      for I in 0..N**2 - 1 loop
         Result(Row, Col) := I;
         if Row = Min_Row then
            Col := Col + 1;
            if Col > Max_Col then
               Col := Max_Col;
               Row := Row + 1;
            end if;
         elsif Col = Max_Col then
            Row := Row + 1;
            if Row > Max_Row then
               Row := Max_Row;
               Col := Col - 1;
            end if;
         elsif Row = Max_Row then
            Col := Col - 1;
            if Col < Min_Col then
               Col := Min_Col;
               Row := Row - 1;
            end if;
         elsif Col = Min_Col then
            Row := Row - 1;
            if Row = Min_Row then  -- Reduce spiral
               Min_Row := Min_Row + 1;
               Max_Row := Max_Row - 1;
               Row := Min_Row;
               Min_Col := Min_Col + 1;
               Max_Col := Max_Col - 1;
               Col := Min_Col;
            end if;
         end if;
      end loop;
      return Result;
   end Spiral;
 
   procedure Print(Item : Array_Type) is
      Num_Digits : constant Float := Log(X => Float(Item'Length(1)**2), Base => 10.0);
      Spacing    : constant Positive := Integer(Num_Digits) + 2;
   begin
      for I in Item'range(1) loop
         for J in Item'range(2) loop
            Put(Item => Item(I,J), Width => Spacing);
         end loop;
         New_Line;
      end loop;
   end Print;
 
begin
   Print(Spiral(5));
end Spiral_Square;
 

The following is a variant using a different algorithm (which can also be used recursively):

 
   function Spiral (N : Positive) return Array_Type is
      Result : Array_Type (1..N, 1..N);
      Left   : Positive := 1;
      Right  : Positive := N;
      Top    : Positive := 1;
      Bottom : Positive := N;
      Index  : Natural  := 0;
   begin
      while Left < Right loop
         for I in Left..Right - 1 loop
            Result (Top, I) := Index;
            Index := Index + 1;
         end loop;
         for J in Top..Bottom - 1 loop
            Result (J, Right) := Index;
            Index := Index + 1;
         end loop;
         for I in reverse Left + 1..Right loop
            Result (Bottom, I) := Index;
            Index := Index + 1;
         end loop;
         for J in reverse Top + 1..Bottom loop
            Result (J, Left) := Index;
            Index := Index + 1;
         end loop;
         Left   := Left   + 1;
         Right  := Right  - 1;
         Top    := Top    + 1;
         Bottom := Bottom - 1;
      end loop;
      Result (Top, Left) := Index;
      return Result;
   end Spiral;
 

[edit] Fortran

Works with: Fortran version 90 and later

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

[edit] 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)

[edit] 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).

[edit] Python

 
def spiral(n):
    dx,dy = 1,0            # Starting increments
    x,y = 0,0              # Starting location
    i = 0                  # starting value
    myarray = [[None]* n for j in range(n)]
    while i < n**2:
        myarray[x][y] = i
        i += 1
        nx,ny = x+dx, y+dy
        if 0<=nx<n and 0<=ny<n and myarray[nx][ny] == None:
            x,y = nx,ny
            continue
        else:
            dx,dy = (-dy,dx) if dy else (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))
 

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

[edit] Recursive Solution

 
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
 
def spiral(n):
    array = [[None]*n for j in range(n)]
    for x in range(n):
        for y in range(n):
            array[x][y] = spiral_part(x,y,n)
    return array
 

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

Another way, based on preparing lists ahead

 
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 != range(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)