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 6Note 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)