The "Spiral Matrix" is a recurring exercise in computer science classes and occasionally programming job interviews. I've come across the problem in various settings a number of times over the years, but only had occasion to develop a solution yesterday morning (circa June 2011). The matrix at right illustrates the 'spiral' nature of the exercise:
The first 95% of the solution is entirely straightforward. But depending on approach, the thought-provoking task is the final step of calculating each cell value on the fly.
- I quickly determined to avoid an exercise of 'chasing' the spiral through the matrix with a series of nested for-next loops, since this is both convoluted and unnecessary (and, furthermore, "Yougly" -- as Jar Jar Binks might say ;-)
- I found it equally redundant and unnecessary to separate the tasks of populating nested arrays with the solution, then subsequently displaying it in the page,
- Consequently, I simply build the matrix (a table) dynamically in a document fragment, calculating the value of each cell in row, column sequence as I went, and, finally, add the completed fragment to the document's array container (i.e. div) when done;
- In order to do this, I adopted the notion (although not the Ruby code) that a spiral actually consists of a series of concentric 'rings', each of which presents a fixed starting value ("offset") at its northeast origin. This is well-explained at www.rubyquiz.com/quiz109.html;
- The example below is designed to work for all possibilities of odd numbers of horizontal cells. It would be a minor extension to make it work for even numbers as well, but that's beyond the purpose of this example.
- Finally, the cell value calculations are mine. They simply calculate the number of cells which have preceded the current cell in the ring and subtract it from the offset. Note from the ternary operator in the code that the final leg of each ring is an exception since it decrements in ascending (reversed) direction.
Build a Spiral or view the Rings and Offsets: