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.
Programming Praxis 
[…] 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…
#!/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[0]: 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 xOoops. 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[0]: 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 xMy 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).
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 4A 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)))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.
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) ]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); }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:
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 listMMy 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
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[0].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 67Here 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)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
#!/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->[0] }) { $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)