Posts Tagged ‘spiral’

Programming Praxis – Unwrapping A Spiral

June 1, 2010

In today’s Programming Praxis exercise our task is to write a function that walks a 2-dimensional array in a spiral pattern and returns the elements it finds. The provided Scheme solution accomplishes this in 8 lines. Let’s see if we can do any better.

First, a quick import:

import Data.List

The Scheme solution works by having an x and y coordinate and changing them as appropriate. We’re going to take a different approach based on recursion. The easiest way to get the spiral is to remove the first row, rotate the array counterclockwise, and repeat. Rotating the array in this manner can be done by reversing all the rows and then transposing the array.

spiral :: [[a]] -> [a]
spiral []     = []
spiral (x:xs) = x ++ spiral (transpose $ map reverse xs)

Let’s see if this approach works correctly.

main :: IO ()
main = do print $ spiral [[1..4],[5..8],[9..12], [13..16],[17..20]]
            == [1,2,3,4,8,12,16,20,19,18,17,13,9,5,6,7,11,15,14,10]

Yup. And at a mere two lines I’d say that’s not half bad.