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.

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 628 other followers

%d bloggers like this: