Spiral matrix

Spiral matrix
You are encouraged to solve this task according to the task description, using any language you may know.

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

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).

Python

<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)) </python> 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

<python> 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

</python>

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

Another way

<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:]  # le = [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)

</Python>