## 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.

Pages: 1 2

### 23 Responses to “Unwrapping A Spiral”

1. […] 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 […]

2. Remco Niemeijer said

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

```import Data.List

spiral :: [[a]] -> [a]
spiral []     = []
spiral (x:xs) = x ++ spiral (transpose \$ map reverse xs)
```
3. 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))

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

```#!/usr/bin/env python

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

sdata = map(lambda x : x.split(),  [x for x in spiral.split('\n')])

def traverse(spiral):
sdata = map(lambda x : x.split(),  [x for x in spiral.split('\n')])
while len(sdata) > 0:
for x in sdata:
yield x
sdata = sdata[1:]
for r in sdata:
r.reverse()
sdata = map(lambda x : list(x), zip(*sdata))

for x in traverse(spiral):
print x
```
5. Ooops. Left a line in that was unnecessary.

```#!/usr/bin/env python

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

def traverse(spiral):
sdata = map(lambda x : x.split(),  [x for x in spiral.split('\n')])
while len(sdata) > 0:
for x in sdata:
yield x
sdata = sdata[1:]
for r in sdata:
r.reverse()
sdata = map(lambda x : list(x), zip(*sdata))

for x in traverse(spiral):
print x
```
6. Mike said

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.

```def unwrap(matrix):
spiral = []
while matrix:
spiral.extend( matrix )
matrix = list( reversed( zip( *matrix[1:] ) ) )

return spiral

#test
data = """
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
17 18 19 20
"""

matrix = [row.split() for row in matrix.strip().splitlines()]

print ' '.join( unwrap( matrix ) )

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

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

8. Mike said

Oops. Line 18 should be:

```matrix = [row.split() for row in data.strip().splitlines()]
```
9. My Java solution can be seen here. I must say mine seems overly verbose in comparison to the solutions showed here. Awesome!

10. Jan Van lent said

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

```unwrap n1 n2 = unwrap' n1 n2 0 1 n2

unwrap' 0  n2 k d1 d2 = []
unwrap' n1 0  k d1 d2 = []
unwrap' n1 n2 k d1 d2 = xs ++ ys
where xs = [k,k+d1..k']
ys = unwrap' n2 (n1-1) (k'+d2) d2 (-d1)
k' = k + (n2-1)*d1

unwrap 5 4
```
11. Jan Van lent said

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

```(use-package :iterate)

(defun range (n &key (start 0) (step 1))
(iter (repeat n) (for i from start by step) (collect i)))

(defun unwrap-spiral (m n &optional (k 0) (d1 1) (d2 n))
(if (and (> m 0) (> n 0))
(append (range n :start k :step d1)
(unwrap-spiral n (- m 1) (+ k (* (- n 1) d1) d2) d2 (- d1)))
'()))

(defun unwrap-spiral-it (m n &optional (k 0) (d1 1) (d2 n))
(iter (while (and (> m 0) (> n 0)))
(appending (range n :start k :step d1))
(psetf m n
n (- m 1)
k (+ k (* (- n 1) d1) d2)
d1 d2
d2 (- d1))))
```

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

```(use-package :iterate)

(defun map-spiral (f m n &optional (k 0) (d1 1) (d2 n))
(iter outer
(while (and (> m 0) (> n 0)))
(iter (repeat n) (for i from k by d1)
(in outer (collect (funcall f i))))
(psetf m n
n (- m 1)
k (+ k (* (- n 1) d1) d2)
d1 d2
d2 (- d1))))

(defun unwrap-spiral-matrix (a)
(apply #'map-spiral (lambda (k) (row-major-aref a k))
(array-dimensions a)))
```
12. Amit said

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)
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!!

13. Jan Van lent said

Python code using generators.

```def spiral1(n1, n2, start=0):
k = start-1
d1, d2 = 1, n2
while n1 > 0 and n2 > 0:
for l in range(n2):
k += d1
yield k
d1, d2 = d2, -d1
n1, n2 = n2, n1-1

def spiral2(n1, n2):
i, j = 0, -1
d1, d2 = 0, 1
while n1 > 0 and n2 > 0:
for l in range(n2):
i, j = i+d1, j+d2
yield (i, j)
d1, d2 = d2, -d1
n1, n2 = n2, n1-1

n1, n2 = 5, 4
a = [ [ n2*i+j for j in range(n2) ] for i in range(n1) ]
print a
print [ k for k in spiral1(n1, n2) ]
print [ n2*i+j for (i, j) in spiral2(n1, n2) ]
print [ a[i][j] for (i, j) in spiral2(n1, n2) ]
```
14. mr. T said

A quick c/c++ hack:

```#define CUTZERO(x) (x < 0 ? 0 : x)

struct Rect {
int xmin, xmax, ymin, ymax;
int size() { return CUTZERO(xmax - xmin + 1) * CUTZERO(ymax - ymin + 1); }
void shrink() { xmin++; xmax--; ymin++; ymax--; }
};

void spiralUnwrap(char** matrix, int cx, int cy)
{
int x = -1, y = 0;
Rect sq = {0, cx - 1, 0, cy - 1};

while(sq.size() > 0)
{
while(x < sq.xmax)
printf("%c, ", matrix[y][++x]);
while(y < sq.ymax)
printf("%c, ", matrix[++y][x]);
while(x > sq.xmin)
printf("%c, ", matrix[y][--x]);
while(y > sq.ymin + 1)
printf("%c, ", matrix[--y][x]);
sq.shrink();
}
printf("\n");
}

void main()
{
char* matrix[] = {
"abcd1",
"efgh2",
"ijkl3",
"mnop4",
"!@#\$5"};
spiralUnwrap(matrix, 5, 5);
}
```
15. Kripa K S said

``` 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) 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)): listM.append(matrix[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 ```

16. Kripa K S said

My python code:

```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)
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)):
listM.append(matrix[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
```
17. fa said

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.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();
}
}

18. fa said

Unwrapp.java

/home/fabio/Desktop/Unwrapp.java

``` 1 import java.util.Iterator;
2
3 public class Unwrapp<T> implements Iterator<T>, Iterable<T>
4 {
5    private enum Direction { EAST, SOUTH, WEST, NORTH }
6
7    private int row, col, minRow, maxRow, minCol, maxCol;
8    private T matrix[][];
9    private Direction d;
10
11    public Unwrapp(T aMatrix[][]) {
12       matrix = aMatrix;
13       row = col = 0;
14       minRow = 0; maxRow = matrix.length - 1;
15       minCol = 0; maxCol = matrix.length - 1;
16       d = Direction.EAST;
17    }
18
19    public Iterator<T> iterator() { return this; }
20    public void remove() { throw new UnsupportedOperationException(); }
21
22    public boolean hasNext() {
23       return (d == Direction.EAST && col <= maxCol)
24          || (d == Direction.SOUTH && row <= maxRow)
25          || (d == Direction.WEST && col >= minCol)
26          || (d == Direction.NORTH && row >= minRow);
27    }
28
29    public T next() {
30       T x = matrix[row][col];
31
32       switch (d) {
33          case EAST:
34             if (col == maxCol) { ++minRow; ++row; d = Direction.SOUTH; }
35             else ++col;
36             break;
37          case SOUTH:
38             if (row == maxRow) { --maxCol; --col; d = Direction.WEST; }
39             else ++row;
40             break;
41          case WEST:
42             if (col == minCol) { --maxRow; --row; d = Direction.NORTH; }
43             else --col;
44             break;
45          case NORTH:
46             if (row == minRow) { ++minCol; ++col; d = Direction.EAST; }
47             else --row;
48             break;
49       }
50       return x;
51    }
52
53    public static void main(String args[]) {
54       Integer matrix[][] = {
55          {1, 2, 3, 4},
56          {5, 6, 7, 8},
57          {9, 10, 11, 12},
58          {13, 14, 15, 16},
59          {17, 18, 19, 20}
60       };
61
62       for (Integer i :  new Unwrapp<Integer>(matrix)) System.out.print(" " + i);
63       System.out.println();
64    }
65 }
66
67
```
19. Here is an R version, with shortness of code traded for memory/performance:

```unwrap <- function(mat)
{
if(nrow(mat)==1) return(mat)

c(mat[1, ], unwrap(t(mat[-1, ncol(mat):1, drop=F])))
}

mat <- matrix(c(1:20), ncol=4, byrow=T)

unwrap(mat)
```
20. anil said

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).

21. mcmillhj said

Similar to @mikes solution, but in Perl

```#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

sub transpose {
my (\$matrix) = @_;

my \$transposed = [];
for my \$i (0 .. \$#\$matrix) {
for my \$j (0 .. \$#{ \$matrix-> }) {
\$transposed->[\$j][\$i] = \$matrix->[\$i][\$j];
}
}

return \$transposed;
}

sub unwrap {
my (\$matrix) = @_;

my @spiral;
while ( \$matrix && @\$matrix ) {
push @spiral,
map { @\$_ } shift @\$matrix;

\$matrix = [reverse @{transpose(\$matrix)}];
}

return \@spiral;
}

my \$matrix = [
[qw( 1  2  3  4)],
[qw( 5  6  7  8)],
[qw( 9 10 11 12)],
[qw(13 14 15 16)],
[qw(17 18 19 20)],
];

print Dumper unwrap(\$matrix)
```