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.

About these ads

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[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 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[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 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[0] )
    		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[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!!

  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[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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: