Spiral

From Rosetta Code

Jump to: navigation, search

Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.

Code examples should be formatted along the lines of one of the existing prototypes.

Produce a spiral array. A spiral array is a square arrangement of the first N2 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

Contents

[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)
 
Personal tools