Spiral Wrapping

October 14, 2014

Today’s exercise appears regularly on lists of interview questions. We’ve done something similar in the past, but since it’s so common we’ll do it again.

Given a matrix, print a list of elements of the matrix. Start in the top-right corner of the matrix, move left across the top row, then down the left column, then across the bottom row, then up the right column to the element below the top row, then left, then down, then right, and so on, collecting the elements of the matrix as it goes. For instance, with this matrix

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

the elements are collected in order 4, 3, 2, 1, 5, 9, 13, 17, 18, 19, 20, 16, 12, 8, 7, 6, 10, 14, 15, 11.

Your task is to write a program to unwrap the elements of a matrix in the indicated spiral. 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

12 Responses to “Spiral Wrapping”

  1. (Sorry it is not a complete solution)
    You can define a bijection between both representations (enumeration spaces) with O(1) cost (per cell).
    Then, you can transform using whatever “path function” from one space to another one (eg. take only numbers inside some circle; numbers into a line; …).

    The next `coords` function transform from spiral enumeration to coordinates; to solve the problem we need to code the inverse of that function.

    Of course, this is a generalized solution.

    // C# code
    Func<int, int, Point> coords = ( z, n ) => { 
        var s = inSquare(z, n); 
        var l = perimeter(s, n) / 4;
        var l2 = l + l; 
        var l3 = l2 + l; 
        var d = diagonalPos(s, n); 
        if( z <= d + l  ) return new Point(s + z - d, s); 
        if( z <= d + l2 ) return new Point(s + l, s + z - d - l); 
        if( z <= d + l3 ) return new Point(s + d + l3 - z, s + l); 
        return new Point(s, s + d + l2 + l2 - z); 
    };
    Func<int, int, int> perimeter = ( x, n ) => 4 * ( n - 2 * x + 1 ); 
    Func<int, int, int> diagonalPos = ( x, n ) => -4 * x * x + ( 4 * n + 8 ) * x - 4 * n - 3; 
    Func<int, int, int> inSquare = ( z, n ) => (int) Math.Floor(n * 0.5 - 0.5 * Math.Sqrt(n * n - z + 1.0) + 1.0); 
    
  2. (argh! I can’t edit my wrong comment, sorry!)

    “to solve the problem we need to code the inverse of that function”

    no, only `spiral -> coordinates -> cell` then, `coords == spiral -> coordinates` then:

    // compute cell number given spiral enumeration index
    var p = coords(z, n);
    return (p.Y - 1) * n + p.X;
    
  3. use strict;
    use warnings;
    
    ## Set up grid and direction map!
    my $grid = [ [ 1..4 ], [ 5..8 ], [ 9..12 ], [ 13..16 ], [ 17..20 ] ];
    my $dir_map = [ [-1,0],[0,1],[1,0],[0,-1] ];
    
    ## Get information about grid!
    my ($h,$w) = (scalar @{$grid}, scalar @{$grid->[0]} );
    
    ## Initialize
    my ($x,$y,$dir,@res) = ($w-1,0,0);
    
    while(defined $grid->[$y][$x] ) {
      push @res, $grid->[$y][$x];
      $grid->[$y][$x] = undef;
      my($dx,$dy) = @{$dir_map->[$dir]};
      ($dx,$dy) = @{$dir_map->[$dir=$dir==3?0:$dir+1]} if
        $x+$dx < 0 || $x+$dx >= $w || $y+$dy < 0 || $y+$dy >= $h || ! defined $grid->[$y+$dy][$x+$dx];
      $x+=$dx;
      $y+=$dy;
    }
    
    print "@res\n";
    
  4. Brett Warren said

    A functional, recursive approach.

    def recursive_spiral(matrix):
        def border_remove(matrix):
            new = []
            for n in matrix[1:-1]:
                new.append(n[1:-1])
            return new
        
        if not matrix:
            return list()
        order_border = matrix[0][::-1] + ([n[0] for n in matrix][1:] + matrix[-1][1:] + [n[-1] for n in matrix][::-1])[:-1]
        return order_border + recursive_spiral(border_remove(matrix))
    
    if __name__ == "__main__":
        example = [list(range(5)), list(range(5)), list(range(5)), list(range(5))]
        print(recursive_spiral(example))
    
  5. Jan Van lent said

    Similar Python solution as for the previously posted problem.

    def spiral2(n1, n2):
        i, j = 0, n2     # initial values
        d1, d2 = 0, -1   # direction
        while n1 > 0 and n2 > 0:
            for l in range(n2):
                i, j = i+d1, j+d2
                yield (i, j)
            d1, d2 = -d2, d1   # rotation
            n1, n2 = n2, n1-1  # new dimensions
    
    n1, n2 = 5, 4
    a = [ [ n2*i+j+1 for j in range(n2) ] for i in range(n1) ]
    print a
    print [ a[i][j] for (i, j) in spiral2(n1, n2) ]
    
  6. Jussi Piitulainen said

    Allowing any rectangle of integer coordinates between an included point b and and an excluded point e, vertical real axis growing down, horizontal imaginary axis growing right, left and right turn specified as the positive and negative imaginary units, stopping when area vanishes. Risking inexact arithmetic, but both Gambit-C (gsi) and Guile appear sensible.

    (define (direction b e t)
      (let ((dh (if (< (magnitude (- e (+ b +i))) (magnitude (- e b))) +i -i))
            (dv (if (< (magnitude (- e (+ b +1))) (magnitude (- e b))) +1 -1)))
        (if (< (magnitude (- (* t dh) dv)) (magnitude (- (* t dv) dh))) dh dv)))

    (define (empty? b e)
      (or (zero? (- (real-part b) (real-part e)))
          (zero? (- (imag-part b) (imag-part e)))))

    (define (spirally b e t)
      (let loop ((p b)
                 (d (direction b e t))
                 (b b)
                 (e e)
                 (r '()))
        (cond
         ((empty? b e) (reverse r))
         ((empty? p e)
          (let ((b (+ (- p d) (* d t)))
                (e (+ e (- b p d))))
            (loop b (* d t) b e r)))
         (else (loop (+ p d) d b e (cons p r))))))

    Mapping coordinates to values that give the example matrix in row-major order between (0,0) inclusive and (5,4) exclusive.

    (define (M p) (inexact->exact (+ (* 4 (real-part p)) (imag-part p) 1)))
    (define (C r k) (make-rectangular r k))

    (define (test exp obs)
      (display "expected: ") (display exp) (newline)
      (display "observed: ") (display obs) (newline) (newline))

    ; From top right, left turns
    (test '(4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11)
          (map M (spirally (C 0 3) (C 5 -1) +i)))

    ; From top right, right turns
    (test '(4 8 12 16 20 19 18 17 13 9 5 1 2 3 7 11 15 14 10 6)
          (map M (spirally (C 0 3) (C 5 -1) -i)))

    ; Down last column, up next column
    (test '(4 8 12 16 20 21 17 13 8 5)
          (map M (spirally (C 0 3) (C 5 5) +i)))

    Observing some expected results.

    $ gsi spiral.scm
    expected: (4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11)
    observed: (4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11)

    expected: (4 8 12 16 20 19 18 17 13 9 5 1 2 3 7 11 15 14 10 6)
    observed: (4 8 12 16 20 19 18 17 13 9 5 1 2 3 7 11 15 14 10 6)

    expected: (4 8 12 16 20 21 17 13 8 5)
    observed: (4 8 12 16 20 21 17 13 9 5)


    Er, that one discrepancy is a typo in the expected value :)

  7. Jussi Piitulainen said

    A mechanical translation of my original Scheme to C99 (only printing the values of the extended matrix M).

    #include <complex.h>
    #include <stdio.h>
    
    #define C(r, k) (r + k * I)
    
    complex double direction(complex double b, complex double e, complex double t) {
      complex double dh = (cabs(e - b - I) < cabs(e - b)) ? +I : -I;
      complex double dv = (cabs(e - b - 1) < cabs(e - b)) ? +1 : -1;
      return (cabs(t * dh - dv) < cabs(t * dv - dh)) ? dh : dv;
    }
    
    int is_empty(complex double b, complex double e) {
      return (creal(b) - creal(e) == 0) || (cimag(b) - cimag(e) == 0);
    }
    
    void spirally_print_M(complex double b, complex double e, complex double t) {
      complex double p = b;
      complex double d = direction(b, e, t);
      while (! is_empty(b, e)) {
        if (is_empty(p, e)) {
              e += b - p - d;
              b = p - d + d * t;
              p = b; d *= t;
            }
          else {
    	printf("%ld ", (long)(4 * creal(p) + cimag(p) + 1));
            p += d;
          }
        }
      printf("\n");
    }
    
    int main(void) {
      spirally_print_M(C(0, 3), C(5, -1), +I);
      spirally_print_M(C(0, 3), C(5, -1), -I);
      spirally_print_M(C(0, 3), C(5, 5), +I);
    }
    

    Hm. Forgot to return from main. There’s always something.

    Again observing the expected, as described in my original Scheme entry (the task matrix spirally as specified, then clockwise, and then the last column down and the next column up).

    $ gcc --std=c99 -Wall spiral.c -lm
    $ ./a.out 
    4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11 
    4 8 12 16 20 19 18 17 13 9 5 1 2 3 7 11 15 14 10 6 
    4 8 12 16 20 21 17 13 9 5 
    
  8. Jakob Lund said

    recursive scheme solution using matrix rotation

    http://repl.it/18y

  9. Johann Hibschman said

    Here’s a J solution:

    NB. Spiral indices, starting from the top right.
    spiralIndices=: 3 : 0
      'nr nc'=. y
      mv=. (, -) _1,nc                         NB. moves: left,down,right,up
      cp=. ({.~ i.&0) ,(nc,nr-1) -"1 ,.~ i.nc  NB. copies of each move
      dx=. cp#(#cp)$mv                         NB. duplicate the moves
      nc + +/\dx                               NB. indices
    )
    NB. Get the items on the spiral from a matrix.
    spiralGet=: spiralIndices@$ { ,
    NB. Generate a spiral matrix.
    involute=: $ /:@spiralIndices
    

    And here’s the sample output;

       >:i.5 4
     1  2  3  4
     5  6  7  8
     9 10 11 12
    13 14 15 16
    17 18 19 20
       spiralGet >:i.5 4
    4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11
       involute 5 4
    3  2  1  0
    4 15 14 13
    5 16 19 12
    6 17 18 11
    7  8  9 10
       spiralIndices 5 4
    3 2 1 0 4 8 12 16 17 18 19 15 11 7 6 5 9 13 14 10
    
  10. Claire said

    #include
    using namespace std;

    #define SIZE 5

    void SPiralArray(int size,int array[][SIZE])
    {
    int a = size/2*2 + 1;
    int y = a/2,x =a/2;
    //for(int i = 1; i=1; i–)
    {
    if(x=y)
    {
    array[y][x] = i;
    x++;
    }
    else if(x>a-y-1 && x>y)
    {
    array[y][x] = i;
    y++;
    }
    else if(x>a-y-1 && x<= y)
    {
    array[y][x] = i;
    x–;
    }
    else if(x<=a-y-1&& x<y)
    {
    array[y][x] = i;
    y–;
    }
    }
    }
    int main(int argc, char *argv[])
    {
    int array[SIZE][SIZE];
    for( int i = 0; i<SIZE; i++)
    {
    for(int j = 0; j<SIZE; j++)
    array[i][j] = 0;
    }
    SPiralArray(SIZE, array);
    for( int i = 0; i<SIZE; i++)
    {
    for(int j = 0; j<SIZE; j++)
    {
    cout << array[i][j] << "\t";
    }
    cout<<endl;
    }
    return 0;
    }

  11. Claire said

    It is really weird, some of the codes that I posted are missing. It should be like this way:
    void SPiralArray(int size,int array[][SIZE])
    {
    int a = size/2*2 + 1;
    int y = a/2,x =a/2;
    for(int i =size*size; i>=1; i–)
    {……}
    }

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

%d bloggers like this: