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)
  • http://www.doughellmann.com/ Doug Hellmann

    I came up with an answer without using any arithmetic. http://www.doughellmann.com/articles/misc/oblong-spiral-puzzle/index.html

  • http://regebro.wordpress.com Lennart Regebro

    Bug: You print with “%2i” while the width can vary between 1 and 3 characters. ;)

    My solution was quite different, I simply walk through the spiral until it’s full.

  • http://sites.google.com/site/tzotzioy/ ΤΖΩΤΖΙΟΥ

    I mixed itertools and recursion and came up with this:
    http://bpaste.net/show/9771/

    Obviously it won’t be a serious contender to the Code Golf site :)

    Note that I made use of a dict, so no need to pre-fill with dummy values.

  • Doug Napoleone

    Spiral index generator and using enumerate to fill in the values:

    http://pastebin.com/y1nwU28F