## Unwrapping A Spiral

### June 1, 2010

This exercise appeared on Proggit a while ago. The task is to enumerate the elements of a matrix in spiral order. For instance, consider the matrix:

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

The spiral starts across the first row, yielding 1, 2, 3, and 4. Then the spiral turns right and runs down the right column, yielding 8, 12, 16, and 20. The spiral turns right again and runs across the bottom row, from right to left, yielding 19, 18, and 17. Then up the first column with 13, 9, 5, right with 6 and 7, down with 11 and 15, right to 14, and up to 10. Thus, unwrapping the given matrix in a spiral gives the list of elements 1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5, 6, 7, 11, 15, 14, and 10.

Your task is to write a function to unwrap spirals. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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

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