Monday 20 April 2009

Spiral matrix

Today I found a very interesting set of 'simple' problems. It is a list of Berkeley University's "hardcore tech-interview style riddles and mathematical puzzles". I was specially interested in the Computer Science section (as you might have guessed) and, in particular, one problem caught my attention (probably because of the large matrix).

The problem

The problem reads as follows:

Write a program that will display a "spiral" of NxN numbers, using constant space (no arrays allowed). For example, here's what the spiral looks like for N=10:

99 98 97 96 95 94 93 92 91 90
64 63 62 61 60 59 58 57 56 89
65 36 35 34 33 32 31 30 55 88
66 37 16 15 14 13 12 29 54 87
67 38 17 4 3 2 11 28 53 86
68 39 18 5 0 1 10 27 52 85
69 40 19 6 7 8 9 26 51 84
70 41 20 21 22 23 24 25 50 83
71 42 43 44 45 46 47 48 49 82
72 73 74 75 76 77 78 79 80 81



Sounds simple enough.

The solution


As I've been reading a lot of "Real World Haskell" lately (and considering the language is great for the task at hand) I decided to code this program in Haskell. If you don't already know Haskell I recommend you to go and learn it on your free time. It is an excellent language with a very unorthodox view of programming (not only functional, but pure!) that will open your mind to a very new and interesting programming style. A good resource for learning Haskell (besides the book, which I highly recommend and will do so with further details in a future post about books) is the classical Gentle introduction to Haskell. But if you prefer a nice colourful website with cool drawings and good info to match the cool design (I know I do!) you can check Learn you a Haskell for great good.

Enough with the language. Into the problem.

To analyse the solution I enumerated some of the matrices, from which matrices of size 4 and 5 were the most useful

15, 14, 13, 12,
4, 3, 2, 11,
5, 0, 1, 10,
6, 7, 8, 9


24, 23, 22, 21, 20,
9, 8, 7, 6, 19,
10, 1, 0, 5, 18,
11, 2, 3, 4, 17,
12, 13, 14, 15, 16


A matrix of size n contains the numbers from n*n-1 to 0. So the next matrix will contain 2n-1 new elements and the rest will be the same elements in a different order. This gives us the idea that the algorithm can be solved recursively.
If we look with more detail into the two matrices outlined above, we can notice that the top row and rightmost column contains all the new elements and that, due to the spiral ordering described in the problem, they will always be located in these positions (there are 2n-1 slots there).

What's left is to figure out how the elements in the previous matrix map to those in the next one and we'll have ourselves a recursive algorithm. We can notice that the first element in the matrix of size 4 is the last element in the sub-matrix formed by removing the new elements from the matrix of size 5. Because of the spiral order the next element to the right in the old matrix becomes the next to the left in the new one and the element that was beneath a number is transposed above it. We can see it as a 90 degree rotation on the old matrix.

The code


Knowing this all that's left is to write the code.
We will need a function that given the position in the n-sized matrix will return the element
that belongs to that position.


spiral :: Int -> Int -> Int -> Int
spiral 0 j n = n*n - 1 - j
spiral i j n
| j == (n-1) = n*n - n - i
|otherwise = spiral (n-1-i) (n-j-2) (n-1)


The first line of this function (after the signature) is one of our base cases: The top row of the matrix is formed by the numbers from (n*n)-1 to n*(n-1). The second definition our second base case: the rightmost column. In this case each element descends from the element in the top right corner (i.e.: n*(n-1) ) one number by row. The rest of the function (the otherwise clause) is our recursive case. On the matrix of size n-1, we are interested in the element that occupies the row n2-i where n2 is the size of the smaller matrix (i.e.: n-1) and the column n2-j-1. Note that the difference between the row and the column is that in the column case we need to substract an extra 1 which refers to the extra columns that appears in the larger matrix. If we don't do this, the transformation would be transposed to the right.

Extra

This code is enough to solve the problem. But to better calculate the results (without having to calculate each index at a time) I provided some extra functions.


-- claculates an index based on the previous matrix
spiral :: Int -> Int -> Int -> Int
spiral 0 j n = n*n - 1 - j
spiral i j n
| j == (n-1) = n*n - n - i
|otherwise = spiral (n-1-i) (n-j-2) (n-1)

-- returns the numbers from 0 to n-1
range :: Int -> [Int]
range n = take n (iterate (1+) 0)

-- returns every possible index of an NxN matrix
matrix :: Int -> [(Int,Int)]
matrix n = [(i,j) | i<-range n, j<-range n] -- a helper function for the map in printSpiral revSp :: Int -> (Int, Int) -> Int
revSp n (i,j) = spiral i j n

-- returns the result for each index
printSpiral :: Int -> [Int]
printSpiral n = map (revSp n) (matrix n)

-- calculates all spiral matrices from 0 to n
through :: Int -> [[Int]]
through n = map printSpiral (range (n+1))


Does anyone have a better (or different) solution?


5 comments:

  1. range = enumFromTo 0

    ReplyDelete
  2. Hey!! I liked a lot your post!. This is the kind of stuff that makes me follow a blog: unexpected, challenging and interesting posts :P

    I writed some code to solve this problem, also in haskell and with a similar approach. I tried to make it shorter and clearer than the one you proposed, but it wasn't possible :P, however it runs faster for big instances (100 onwards)

    Here goes the code and bit of explanation.
    ------------------
    This is and also recursive implementation. The idea is to find the spiral matrix of n, using the spiral matrix of n-1 and so on.

    Unlike your implementation, this one returns a list of lists, where each sub list corresponds to a row.

    The basic procedure is the following:
    For example to find the spiralM of order 3,already having spiral of order 2 --> [[3,2], [0,1]]

    We want to add at the end of each row of the submatrix
    the elements that don't correspond to the first row of the next matrix (as Nicolas explained ).This is '5' and '4'. Let's call this two elements 'last of row' elements.
    To do this we may add each 'last of row'element at the start of each sublist that corresponds to it in ascending order. Then reverse the list resulting of reversing every Sublist.
    And we'll obtain: -> [[1,0,5], [2,3,4]]

    Here we first got [[5,0,1],[4,3,2]] and the we double-reverse this list.

    At last we must add at the beginning of the current matrix the list the sublist [8..6]. This will result in the Spiral Matrix we are looking for.

    Why adding elements add start? Because it's requires less time in processing, avoiding all the time using functions as append (++) that requires to walk over the entire list.

    Here goes the code... Thank you again for this great post

    -- returns the spiral matrix of order n
    spiral:: Int -> [[Int]]
    spiral 1 = [[0]]
    spiral n = nextSpiral n (spiral (n-1))

    -- returns the next spiral matrix given the
    -- previous'oldSpiral'
    nextSpiral:: Int -> [[Int]] -> [[Int]]
    nextSpiral n oldSpiral= ((firstRow (n*n) (n*n - n )) : doubleReverse (addBegin oldSpiral ((n-1)*(n-1))))

    -- returns the list resulting from adding the next
    -- element of the descendent count starting whith 'n' -- and finishing with 'stop' at the start of each
    -- element
    addBegin:: [[Int]] -> Int -> [[Int]]
    addBegin [] _ = []
    addBegin (xs:ys) n = ((n:xs) : addBegin ys (n+1))

    -- reverse a list after reversing every sublist
    doubleReverse :: [[Int]] -> [[Int]]
    doubleReverse xs = reverse (map reverse xs)

    -- returns the list from last to n-1
    firstRow:: Int -> Int -> [Int]
    firstRow n last = reverse [last..n-1]

    ReplyDelete
  3. Sorry I made a mistake... When i said

    "Here we first got [[5,0,1],[4,3,2]] and the we double-reverse this list."

    I mixed the order of the sublists. I wanted to say
    "Here we first got [[4,3,2],[5,0,1]] and the we double-reverse this list."

    ReplyDelete
  4. I am newbie and I want to write this(spiral matrix) in C
    can somebody help me

    ReplyDelete
  5. May somebody help me to adjust the above algorithm(about spiral matrix) for C
    thanks in advance

    ReplyDelete