Oblong Spiral Puzzle

Originally posted Sep 25, 2010 · 6 min read

Brian Jones posted a solution to the Oblong Spiral Puzzle recently. I don’t normally mess with puzzles, but after looking at his solution I thought I would take a stab at it and see if I could come up with a solution in Python that was a little less complicated.

The Puzzle

The complete definition of the puzzle is on the Code Golf site. The challenge is to fill in an n x m array with a sequence of numbers starting at the upper left, and working around the outside, spiraling inwards. For example:

$ python spiral.py 3 3
  1   2   3
  8   9   4
  7   6   5

$ python spiral.py 4 5
  1   2   3   4
 14  15  16   5
 13  20  17   6
 12  19  18   7
 11  10   9   8

The actual contest applies a few other rules about submission formats, but I don’t plan to enter so I haven’t paid close attention to them.

Solution

One way to solve the puzzle is to work out an algorithm for determining the next row and column index for each element in the list of values, then iterate over the list and put each value into the right cell in the array. I chose to look at it the other way around, and iterate over the array, picking the proper value to go into each cell.

The solution starts by creating lists containing the numerical indexes of the rows and columns in the output, based on arguments given on the command line.

import itertools
import sys

if len(sys.argv) != 3:
    print 'Usage: %s &lt;num_cols&gt; &lt;num_rows&gt;' % sys.argv[0]
    sys.exit(1)
num_cols = int(sys.argv[1])
num_rows = int(sys.argv[2])

rows = range(num_rows)
cols = range(num_cols)

The next step is to initialize the array. I used a list comprehension to create a list of lists based on the row size.

# Initialize the array
spiral = [ [] * num_cols for row in xrange(num_rows) ]

As process the rows and columns are processed, I will want to know the “next” number to put in each cell. I use itertools.count() for that, skipping over the value `` since that is not supposed to be used.

# Establish a counter
n = itertools.count()
n.next() # skip zero

To fill in the array, I use a loop that fills in one row and one column each time around. After a row is completed, the remaining column indexes are reversed so that the next row is filled in going the other direction. The same operation is applied to the row indexes at the end of a column.

while rows and cols:

    # Fill in cells across the current row
    r = rows.pop()
    for c in cols:
        spiral[r][c] = n.next()

    # Walk the next row in the other direction
    cols.reverse()

    # Fill in cells along the current column
    c = cols.pop()
    for r in rows:
        spiral[r][c] = n.next()

    # Walk the next column in the other direction
    rows.reverse()

And finally the results are printed:

# Show the results
for r in xrange(num_rows):
    for c in xrange(num_cols):
        print '%3d' % spiral[r][c],
    print

The same effect could be achieved by computing the cell position each time through the loop, keeping track of when to add and when to subtract for each of the row and column counters. But by using list.reverse(), I avoid the computation and testing to see if the end of the column or row has been reached, and I think the resulting algorithm is simpler to follow. Using itertools.count() instead of incrementing an integer variable myself was just a final touch to see if I could eliminate all arithmetic from the solution.

Without Reversing the Lists

Doug Napoleone pointed out in comments that my original solution processed the data in the rows and cols lists every time reverse() was called. Unfolding the outer loop one more time so it makes a complete circuit of the spiral lets me use a reverse-iterator instead (see PEP 322). I also changed the way the counter is initialized, based on a comment from Christian Oudard. Here’s the new version:

n = itertools.count(1)

while rows or cols:

    # Row left to right
    if rows:
        r = rows.pop()
        for c in cols:
            spiral[r][c] = n.next()

    # Column top to bottom
    if cols:
        c = cols.pop(-1)
        for r in rows:
            spiral[r][c] = n.next()

    # Row right to left
    if rows:
        r = rows.pop(-1)
        for c in reversed(cols):
            spiral[r][c] = n.next()

    # Column bottom to top
    if cols:
        c = cols.pop()
        for r in reversed(rows):
            spiral[r][c] = n.next()

Sample Output

Here are a few sample runs:

$ python spiral2.py 10 4
  1   2   3   4   5   6   7   8   9  10
 24  25  26  27  28  29  30  31  32  11
 23  40  39  38  37  36  35  34  33  12
 22  21  20  19  18  17  16  15  14  13

$ python spiral2.py 15 15
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
 56  57  58  59  60  61  62  63  64  65  66  67  68  69  16
 55 104 105 106 107 108 109 110 111 112 113 114 115  70  17
 54 103 144 145 146 147 148 149 150 151 152 153 116  71  18
 53 102 143 176 177 178 179 180 181 182 183 154 117  72  19
 52 101 142 175 200 201 202 203 204 205 184 155 118  73  20
 51 100 141 174 199 216 217 218 219 206 185 156 119  74  21
 50  99 140 173 198 215 224 225 220 207 186 157 120  75  22
 49  98 139 172 197 214 223 222 221 208 187 158 121  76  23
 48  97 138 171 196 213 212 211 210 209 188 159 122  77  24
 47  96 137 170 195 194 193 192 191 190 189 160 123  78  25
 46  95 136 169 168 167 166 165 164 163 162 161 124  79  26
 45  94 135 134 133 132 131 130 129 128 127 126 125  80  27
 44  93  92  91  90  89  88  87  86  85  84  83  82  81  28
 43  42  41  40  39  38  37  36  35  34  33  32  31  30  29

$ python spiral2.py 3 9
  1   2   3
 20  21   4
 19  22   5
 18  23   6
 17  24   7
 16  25   8
 15  26   9
 14  27  10
 13  12  11

Oblong Spiral Puzzle

The Puzzle

Solution

Without Reversing the Lists

Sample Output

See also