Spiral Wrapping
October 14, 2014
As embarrassing as it is to admit, it always takes me a couple of tries to get things like this right, and today’s exercise was no exception. The answer, of course, is practice, practice, practice. Here’s my solution:
(define (unwrap m)
(let ((r (matrix-rows m)) (c (matrix-cols m)))
(let loop ((x c) (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))))))))
Variables x and y are the absolute coordinates of the current cell, variables r and c keep track of the current number of rows and columns that remain to be swept, variables dx and dy keep track of the current direction of movement, and variable i keeps track of the length of the current row or column. Here’s an example, with the values of the loop control variables made visible at each invocation of the loop, so you can see how they change:
> (unwrap #(#(1 2 3 4) #(5 6 7 8) #(9 10 11 12) #(13 14 15 16) #(17 18 19 20)))
4 0 -1 0 5 4 ()
3 0 -1 0 5 4 (4)
2 0 -1 0 5 4 (3 4)
1 0 -1 0 5 4 (2 3 4)
0 0 -1 0 5 4 (1 2 3 4)
0 0 0 1 4 4 (1 2 3 4)
0 1 0 1 4 4 (5 1 2 3 4)
0 2 0 1 4 4 (9 5 1 2 3 4)
0 3 0 1 4 4 (13 9 5 1 2 3 4)
0 4 0 1 4 4 (17 13 9 5 1 2 3 4)
0 4 1 0 4 3 (17 13 9 5 1 2 3 4)
1 4 1 0 4 3 (18 17 13 9 5 1 2 3 4)
2 4 1 0 4 3 (19 18 17 13 9 5 1 2 3 4)
3 4 1 0 4 3 (20 19 18 17 13 9 5 1 2 3 4)
3 4 0 -1 3 3 (20 19 18 17 13 9 5 1 2 3 4)
3 3 0 -1 3 3 (16 20 19 18 17 13 9 5 1 2 3 4)
3 2 0 -1 3 3 (12 16 20 19 18 17 13 9 5 1 2 3 4)
3 1 0 -1 3 3 (8 12 16 20 19 18 17 13 9 5 1 2 3 4)
3 1 -1 0 3 2 (8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 1 -1 0 3 2 (7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
1 1 -1 0 3 2 (6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
1 1 0 1 2 2 (6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
1 2 0 1 2 2 (10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
1 3 0 1 2 2 (14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
1 3 1 0 2 1 (14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 3 1 0 2 1 (15 14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 3 0 -1 1 1 (15 14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 2 0 -1 1 1 (11 15 14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 2 -1 0 1 0 (11 15 14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
2 2 0 1 0 0 (11 15 14 10 6 7 8 12 16 20 19 18 17 13 9 5 1 2 3 4)
(4 3 2 1 5 9 13 17 18 19 20 16 12 8 7 6 10 14 15 11)
We used the matrix primitives from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/26yqRd2B.
Programming Praxis 
(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);(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:
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";Haskell: http://codepad.org/C9LValE7
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))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) ]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 :)
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).
recursive scheme solution using matrix rotation
http://repl.it/18y
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=: $ /:@spiralIndicesAnd here’s the sample output;
#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;
}
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–)
{……}
}