Number Spiral Fun

I love puzzles, and I came across the Oblong Number Spiral challenge on Code Golf over the past week and dove in. Here’s the basic idea, from the challenge at Code Golf:

This challenge involves you having to create a number spiral such as :

 1  2  3
10 11  4
 9 12  5
 8  7  6

Note how the numbers spiral in clockwise towards the centre. Here’s a larger example :

 1  2  3  4  5
18 19 20 21  6
17 28 29 22  7
16 27 30 23  8
15 26 25 24  9
14 13 12 11 10

So, the program should take input as two numbers separated by a space, which represent the width and height of the matrix you’ll output. Then you need to determine the location in the output for each number in the matrix, so when it’s sent to the screen, it looks like the examples above.

I’ve never done a spiral matrix before, but I suspected I’d probably start with a matrix full of dummy values that I’d replace using some algorithm that would understand how to turn “turn and move in a negative direction along the x axis” into placement in the matrix. I did a little reading and found I was on the right path, so I kept on trudging along and this is what I came up with:

#!/usr/bin/env python

def number_spiral(h, w):
   # total number of elements in array
   n = w * h

   # start at top left (row 0 column 0)
   row, column = 0,0

   # first move is on the same row, to the right
   d_row, d_column = 0, 1

   # fill 2d array with dummy values we'll overwrite later
   arr = [[None ]* w for z in range(h)]

   for i in xrange(1,n+1):
      arr[row][column] = i

      # next row and column
      nrow, ncolumn = row + d_row, column + d_column

      if 0 <= nrow < h and 0 <= ncolumn < w and arr[nrow][ncolumn] == None:
         # no out of bounds accesses or overwriting already-placed elements.
         row, column = nrow, ncolumn
      else:
         # change direction
         d_row , d_column = d_column, -d_row
         row, column = row + d_row, column + d_column

   # print it out!
   for a in range(h):
      for b in range(w):
         print "%2i" % arr[a][b],
      print

if __name__ == '__main__':
   number_spiral(5, 3)