## Unwrapping A Spiral

### June 1, 2010

The basic idea is to regard the *x*,*y* coordinates of the matrix as absolute and all movement through the spiral as relative:

`(define (spiral m)`

(let ((r (matrix-rows m)) (c (matrix-cols m)))

(let loop ((x -1) (y 0) (dx 1) (dy 0) (r r) (c c) (i 0) (xs '()))

(cond ((zero? r) (reverse xs))

((= i c) (loop x y (- dy) dx c (- r 1) 0 xs))

(else (let ((x (+ x dx)) (y (+ y dy)))

(loop x y dx dy r c (+ i 1)

(cons (matrix-ref m y x) xs))))))))

*Dx* and *dy* give the change in the *x* and *y* coordinates from one element to the next, and *r* and *c* give the number of remaining rows and columns. Each time the spiral turns, the roles of *dx* and *dy* are interchanged, as are the roles of *r* and *c*. Here’s an example:

`> (spiral #(`

#( 1 2 3 4)

#( 5 6 7 8)

#( 9 10 11 12)

#(13 14 15 16)

#(17 18 19 20)))

(1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10)

We used the matrix functions `matrix-rows`

, `matrix-cols`

, and `matrix-ref`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/fCkL3Qmj.

[…] Praxis – Unwrapping A Spiral By Remco Niemeijer In today’s Programming Praxis exercise our task is to write a function that walks a 2-dimensional array in a […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/06/01/programming-praxis-unwrapping-a-spiral/ for a version with comments):

hm, implemented the reverse thing in common lisp, from an spiral list to an matrix:

(defparameter *spiral* ‘(1 2 3 4 8 12 16 20 19 18 17 13 9 5 6 7 11 15 14 10))

(defun spiral-unwind (spiral)

(let* ((partion ‘())

(delta (maplist

#'(lambda (x)

(if (> (length x) 1)

(let ((delta (- (second x) (first x))))

(if (and partion (= delta (car (car partion))))

(setf (car partion) (cons delta (car partion)))

(push (list delta) partion))

delta)

0))

spiral))

(dimension-x (+ 1 (length (first (reverse partion)))))

(dimension-y (+ 1 (length (second (reverse partion)))))

(matrix (make-array (list dimension-y dimension-x)))

(x 0) (y 0))

(loop

for elem in spiral

for d in delta

do (progn

(setf (aref matrix y x) elem)

(cond ((= d 1) (incf x))

((= d -1) (decf x))

((= d (- dimension-y 1)) (incf y))

(t (decf y)))))

matrix))

A few minutes of playing around yielded this faintly obscure Python version…

Ooops. Left a line in that was unnecessary.

My Python version:

‘matrix’ is a list of lists in row major order. The idea is to append the top row of the matrix to the spiral. Then rotate the rest of the matrix (rows 2 through n) ccw, so that the right-most column is now the top row. Repeat until the matrix is empty.

I like yours better, Mike. I bow to your tidy Python-fu.

Oops. Line 18 should be:

My Java solution can be seen here. I must say mine seems overly verbose in comparison to the solutions showed here. Awesome!

A Haskell solution that generates a list of indices (starting from 0, matrix stored by rows).

A recursive and an iterative solution in Common Lisp along the same lines as the Haskell solution.

If we do not want to allocate an intermediate list with indices we could do something like:

a=[[1,2,3,4],

[5,6,7,8],

[9,10,11,12],

[13,14,15,16],

[17,18,19,20]]

def unwrap(matrix):

rows=len(matrix)

cols=len(matrix[0])

counter=0

curr_row=0

curr_col=0

while (counter<rows*cols):

j=curr_col

while (j<(cols-curr_col)):

print matrix[curr_row][j],

counter=counter+1

j=j+1

curr_col=j-1

i=curr_row+1

while (i=(cols-curr_col-1)):

print matrix[curr_row][j],

counter=counter+1

j=j-1

curr_col=j+1

i=curr_row-1

while (i>(rows-curr_row-1)):

print matrix[i][curr_col],

counter=counter+1

i=i-1

curr_row=i+1

curr_col=curr_col+1

unwrap(a)

——————————————————————————————

This is a very simple code written in python…very easy to understand!!

Python code using generators.

A quick c/c++ hack:

def spiral(matrix):

while len(matrix):

matrix = horizontal(matrix)

if (len(matrix)):

matrix = vertical(matrix)

for i in range(len(matrix)):

matrix[i].reverse()

matrix.reverse()

def vertical(matrix):

lastCol = len(matrix[0])

for i in range(len(matrix)):

listM.append(matrix[i][lastCol-1])

del(matrix[i][lastCol-1])

return matrix

def horizontal(matrix):

for i in range(len(matrix[0])):

listM.append(matrix[0][i])

return matrix[1:len(matrix)]

`listM =[]`

matrixM = [ [1,2,3,4],

[5,6,7,8],

[9,10,11,12],

[13,14,15,16],

[17,18,19,20]

]

spiral(matrixM)

print listM

My python code:

My C implementation

http://codepad.org/LhPOJjmq

:)

Little bit modified

http://codepad.org/dpnlp8zz

Thanks :)

import java.util.Iterator;

public class Unwrapp implements Iterator, Iterable

{

private enum Direction { EAST, SOUTH, WEST, NORTH }

private int row, col, minRow, maxRow, minCol, maxCol;

private T matrix[][];

private Direction d;

public Unwrapp(T aMatrix[][]) {

matrix = aMatrix;

row = col = 0;

minRow = 0; maxRow = matrix.length – 1;

minCol = 0; maxCol = matrix[0].length – 1;

d = Direction.EAST;

}

public Iterator iterator() { return this; }

public void remove() { throw new UnsupportedOperationException(); }

public boolean hasNext() {

return (d == Direction.EAST && col <= maxCol)

|| (d == Direction.SOUTH && row = minCol)

|| (d == Direction.NORTH && row >= minRow);

}

public T next() {

T x = matrix[row][col];

switch (d) {

case EAST:

if (col == maxCol) { ++minRow; ++row; d = Direction.SOUTH; }

else ++col;

break;

case SOUTH:

if (row == maxRow) { –maxCol; –col; d = Direction.WEST; }

else ++row;

break;

case WEST:

if (col == minCol) { –maxRow; –row; d = Direction.NORTH; }

else –col;

break;

case NORTH:

if (row == minRow) { ++minCol; ++col; d = Direction.EAST; }

else –row;

break;

}

return x;

}

public static void main(String args[]) {

Integer matrix[][] = {

{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12},

{13, 14, 15, 16},

{17, 18, 19, 20}

};

for (Integer i : new Unwrapp(matrix)) System.out.print(” ” + i);

System.out.println();

}

}

Unwrapp.java

/home/fabio/Desktop/Unwrapp.java

Here is an R version, with shortness of code traded for memory/performance:

I want program to print reverse spiral program. e.g If a matrix of 4×4, instead of statig A(oo), I want to print revesre spiral order starting from D(33).

Similar to @mikes solution, but in Perl