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