Traverse 2D Array in Spiral pattern using recursion.

Question

Hi, I am preparing for an interview and have been stuck on this question for quite some time now. Could anybody please help me with the code. If not complete then may be a snippet of it? Please..

Answer 1

Python 2, prints a 2D nested list in clockwise direction, from the top left corner to the center:

>>> def clockwise(r):
...     return list(r[0]) + clockwise(list(reversed(zip(*r[1:])))) if r else []
... 
>>> a = [ 
...   [ 1,  2,  3], 
...   [ 5,  6,  7], 
...   [ 9, 10, 11]]
>>> clockwise(a)
[1, 2, 3, 7, 11, 10, 9, 5, 6]
>>> a = [ 
...   [ 1,  2,  3,  4], 
...   [ 5,  6,  7,  8], 
...   [ 9, 10, 11, 12],
...   [13, 14, 15, 16]]
>>> clockwise(a)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

So what happens here? The argument to clockwise is a two-dimensional array r. We want to print its contents from left to right, clockwise. So if the two dimensional array is not empty, then we can print it's first element, which is the top row. Next, we want to print the last elements of the remaining rows (the numbers on the right). We don't want to repeat ourselves. So what we do, is to transform the remaining rows such that the next numbers to be printed are on the top row. We do this by transposing the remaining rows (so that they become columns) and then reversing them.

Perhaps the algorithm becomes clearer if I write it in Haskell:

import Data.List

clockwise :: [[a]] -> [a] 
clockwise (x:xs) = x ++ (clockwise $ reverse $ transpose $ xs) 
clockwise _      = []