Programming Praxis – Unwrapping A Spiral

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.

About these ads

Tags: , , , , , , ,

2 Responses to “Programming Praxis – Unwrapping A Spiral”

  1. programmingpraxis Says:

    Shorter program, yes. But a different data type, lists of lists rather than two-dimensional matrix. And there’s lots of motion. Moving that data all around is expensive if the matrix is large, and may interfere if the matrix is used for some other purpose.

  2. Remco Niemeijer Says:

    Yeah, this is obviously by no means a highly efficient program. But on this blog, given a choice between length and efficiency I will choose the former, particularly on problems such as this one where practical applications are very limited.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: