Spiral matrix: Difference between revisions

Content added Content deleted

Inline

Revision as of 04:09, 16 November 2010

Produce a spiral array. A spiral array is a square arrangement of the first N² natural numbers, where the numbers increase sequentially as you go around the edges of the array spiralling inwards.

For example, given 5, produce this array:

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

ALGOL 68

Translation of: Python

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

<lang algol68>INT empty=0;

PROC spiral = (INT n)[,]INT: (

   INT dx:=1, dy:=0;            # Starting increments #
   INT x:=0, y:=0;              # Starting location #
   [0:n-1,0:n-1]INT my array;
   FOR y FROM LWB my array TO UPB my array DO
       FOR x FROM LWB my array TO UPB my array DO
           my array[x,y]:=empty
       OD
   OD;
   FOR i TO n**2 DO
       my array[x,y] := i;
       INT nx:=x+dx, ny:=y+dy;
       IF ( 0<=nx AND nx<n AND 0<=ny AND ny<n | my array[nx,ny] = empty | FALSE ) THEN
           x:=nx; y:=ny
       ELSE
           INT swap:=dx; dx:=-dy; dy:=swap;
           x+:=dx; y+:=dy
       FI
   OD;
   my array

);

PROC print spiral = ([,]INT my array)VOID:(

   FOR y FROM LWB my array TO UPB my array DO
       FOR x FROM LWB my array TO UPB my array DO
           print(whole(my array[x,y],-3))
       OD;
       print(new line)
   OD

);

print spiral(spiral(5))</lang> Output:

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

AutoHotkey

Translation of: Python

ahk forum: discussion <lang AutoHotkey>n := 5, dx := x := y := v := 1, dy := 0

Loop % n*n {

  a_%x%_%y% := v++
  nx := x+dx, ny := y+dy
  If (1 > nx || nx > n || 1 > ny || ny > n || a_%nx%_%ny%)
     t := dx, dx := -dy, dy := t
  x := x+dx, y := y+dy

}

Loop %n% { ; generate printout

  y := A_Index                 ; for each row
  Loop %n%                     ; and for each column
     s .= a_%A_Index%_%y% "`t" ; attach stored index
  s .= "`n"                    ; row is complete

} MsgBox %s% ; show output /*

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

/</lang>

C++

<lang cpp>#include <vector>

include <memory> // for auto_ptr
include <cmath> // for the ceil and log10 and floor functions
include <iostream>
include <iomanip> // for the setw function

using namespace std;

typedef vector< int > IntRow; typedef vector< IntRow > IntTable;

auto_ptr< IntTable > getSpiralArray( int dimension ) { auto_ptr< IntTable > spiralArrayPtr( new IntTable( dimension, IntRow( dimension ) ) );

int numConcentricSquares = static_cast< int >( ceil( static_cast< double >( dimension ) / 2.0 ) );

int j; int sideLen = dimension; int currNum = 0;

for ( int i = 0; i < numConcentricSquares; i++ ) { // do top side for ( j = 0; j < sideLen; j++ ) ( *spiralArrayPtr )[ i ][ i + j ] = currNum++;

// do right side for ( j = 1; j < sideLen; j++ ) ( *spiralArrayPtr )[ i + j ][ dimension - 1 - i ] = currNum++;

// do bottom side for ( j = sideLen - 2; j > -1; j-- ) ( *spiralArrayPtr )[ dimension - 1 - i ][ i + j ] = currNum++;

// do left side for ( j = sideLen - 2; j > 0; j-- ) ( *spiralArrayPtr )[ i + j ][ i ] = currNum++;

sideLen -= 2; }

return spiralArrayPtr; }

void printSpiralArray( const auto_ptr< IntTable >& spiralArrayPtr ) { size_t dimension = spiralArrayPtr->size();

int fieldWidth = static_cast< int >( floor( log10( static_cast< double >( dimension * dimension - 1 ) ) ) ) + 2;

size_t col; for ( size_t row = 0; row < dimension; row++ ) { for ( col = 0; col < dimension; col++ ) cout << setw( fieldWidth ) << ( *spiralArrayPtr )[ row ][ col ]; cout << endl; } }

int main() { printSpiralArray( getSpiralArray( 5 ) ); }</lang>

Common Lisp

Translation of: Python

<lang lisp>(defun spiral (rows columns)

 (do ((N (* rows columns))
      (spiral (make-array (list rows columns) :initial-element nil))
      (dx 1) (dy 0) (x 0) (y 0)
      (i 0 (1+ i)))
     ((= i N) spiral)
   (setf (aref spiral y x) i)
   (let ((nx (+ x dx)) (ny (+ y dy)))
     (cond
      ((and (< -1 nx columns)
            (< -1 ny rows)
            (null (aref spiral ny nx)))
       (setf x nx
             y ny))
      (t (psetf dx (- dy)
                dy dx)
         (setf x (+ x dx)
               y (+ y dy)))))))</lang>

> (pprint (spiral 6 6))

#2A((0 1 2 3 4 5)
    (19 20 21 22 23 6)
    (18 31 32 33 24 7)
    (17 30 35 34 25 8)
    (16 29 28 27 26 9)
    (15 14 13 12 11 10))

> (pprint (spiral 5 3))

#2A((0 1 2)
    (11 12 3)
    (10 13 4)
    (9 14 5)
    (8 7 6))

E

First, some quick data types to unclutter the actual algorithm.

/** Missing scalar multiplication, but we don't need it. */
def makeVector2(x, y) {
  return def vector {
    to x() { return x }
    to y() { return y }
    to add(other) { return makeVector2(x + other.x(), y + other.y()) }
    to clockwise() { return makeVector2(-y, x) }
  }
}

/** Bugs: (1) The printing is specialized. (2) No bounds check on the column. */
def makeFlex2DArray(rows, cols) {
  def storage := ([null] * (rows * cols)).diverge()
  return def flex2DArray {
    to __printOn(out) {
      for y in 0..!rows {
        for x in 0..!cols {
          out.print(<import:java.lang.makeString>.format("%3d", [flex2DArray[y, x]]))
        }
        out.println()
      }
    }
    to get(r, c) { return storage[r * cols + c] }
    to put(r, c, v) { storage[r * cols + c] := v }
  }
}

<lang e>def spiral(size) {

 def array := makeFlex2DArray(size, size)
 var i := -1                   # Counter of numbers to fill
 var p := makeVector2(0, 0)    # "Position"
 var dp := makeVector2(1, 0)   # "Velocity"
 
 # If the cell we were to fill next (even after turning) is full, we're done.
 while (array[p.y(), p.x()] == null) {
 
   array[p.y(), p.x()] := (i += 1) # Fill cell
   def next := p + dp              # Look forward
   
   # If the cell we were to fill next is already full, then turn clockwise.
   # Gimmick: If we hit the edges of the array, by the modulo we wrap around
   # and see the already-filled cell on the opposite edge.
   if (array[next.y() %% size, next.x() %% size] != null) {
     dp := dp.clockwise()
   }
   
   # Move forward
   p += dp
 }
 
 return array

}</lang>

Example:

<lang e>? print(spiral(5))

0  1  2  3  4

15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8</lang>

Solution based on the J hints: <lang haskell>grade xs = map snd. sort $ zip xs [0..] values n = cycle [1,n,-1,-n] counts n = (n:).concatMap (ap (:) return) $ [n-1,n-2..1] reshape n = unfoldr (\xs -> if null xs then Nothing else Just (splitAt n xs))

spiral n = reshape n . grade. scanl1 (+). concat $ zipWith replicate (counts n) (values n)</lang>

J

This function is the result of some beautiful insights: <lang j>spiral =. ,~ $ [: /: }.@(2 # >:@i.@-) +/\@# <:@+: $ (, -)@(1&,)

  spiral 5
0  1  2  3 4

15 16 17 18 5 14 23 24 19 6 13 22 21 20 7 12 11 10 9 8</lang> Would you like some hints that will allow you to reimplement it in another language?

These inward spiralling arrays are known as "involutes"; we can also generate outward-spiraling "evolutes", and we can start or end the spiral at any corner, and go in either direction (clockwise or counterclockwise). See the first link (to JSoftware.com).

Java

Translation of: C++

Works with: Java version 1.5+

<lang java5>public class Blah {

 public static void main(String[] args) {
   print2dArray(getSpiralArray(5));
 }

 public static int[][] getSpiralArray(int dimension) {
   int[][] spiralArray = new int[dimension][dimension];

   int numConcentricSquares = (int) Math.ceil((dimension) / 2.0);

   int j;
   int sideLen = dimension;
   int currNum = 0;

   for (int i = 0; i < numConcentricSquares; i++) {
     // do top side
     for (j = 0; j < sideLen; j++) {
       spiralArray[i][i + j] = currNum++;
     }

     // do right side
     for (j = 1; j < sideLen; j++) {
       spiralArray[i + j][dimension - 1 - i] = currNum++;
     }

     // do bottom side
     for (j = sideLen - 2; j > -1; j--) {
       spiralArray[dimension - 1 - i][i + j] = currNum++;
     }

     // do left side
     for (j = sideLen - 2; j > 0; j--) {
       spiralArray[i + j][i] = currNum++;
     }

     sideLen -= 2;
   }

   return spiralArray;
 }

 public static void print2dArray(int[][] array) {
   for (int[] row : array) {
     for (int elem : row) {
       System.out.print(elem + " ");
     }
     System.out.println();
   }
 }

}</lang> Output:

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

JavaScript

Works with: SpiderMonkey

for the print() function.

Subclasses the Matrix class defined at Matrix Transpose#JavaScript <lang javascript>function SpiralMatrix(n) {

   this.height = n;
   this.width = n;

   this.mtx = [];
   for (var i = 0; i < n; i++) 
       this.mtx[i] = [];

   var m=0, x=-1, y=0, dx=1, dy=0;
   while (n > 0) {
       for (var j = 0; j < n; j++) {
           x += dx;
           y += dy; 
           this.mtx[y][x] = m++; 
       }
       if (dx) {
           dy = dx;
           dx = 0;
           n--;
       }
       else {
           dx = -dy;
           dy = 0;
       }
   }

} SpiralMatrix.prototype = Matrix.prototype;

var s = new SpiralMatrix(5); print(s);</lang> output

0,1,2,3,4
15,16,17,18,5
14,23,24,19,6
13,22,21,20,7
12,11,10,9,8

Lua

<lang lua>av, sn = math.abs, function(s) return s~=0 and s/av(s) or 0 end function sindex(y, x) -- returns the value at (x, y) in a spiral that starts at 1 and goes outwards

 if y == -x and y >= x then return (2*y+1)^2 end
 local l = math.max(av(y), av(x))
 return (2*l-1)^2+4*l+2*l*sn(x+y)+sn(y^2-x^2)*(l-(av(y)==l and sn(y)*x or sn(x)*y)) -- OH GOD WHAT

end

function spiralt(side)

 local ret, start, stop = {}, math.floor((-side+1)/2), math.floor((side-1)/2)
 for i = 1, side do
   ret[i] = {}
   for j = 1, side do
     ret[i][j] = side^2 - sindex(stop - i + 1,start + j - 1) --moves the coordinates so (0,0) is at the center of the spiral
   end
 end
 return ret

end

for i,v in ipairs(spiralt(8)) do for j, u in ipairs(v) do io.write(u .. " ") end print() end</lang>

Mathematica

We split the task up in 2 functions, one that adds a 'ring' around a present matrix. And a function that adds rings to a 'core': <lang Mathematica>AddSquareRing[x_List/;Equal@@Dimensions[x] && Length[Dimensions[x]]==2]:=Module[{new=x,size,smallest},

size=Length[x];
smallest=x1,1;
Do[
 newi=Prepend[newi,smallest-i];
 newi=Append[newi,smallest-3 size+i-3]
,{i,size}];
PrependTo[new,Range[smallest-3size-3-size-1,smallest-3size-3]];
AppendTo[new,Range[smallest-size-1,smallest-size-size-2,-1]];
new

] MakeSquareSpiral[size_Integer/;size>0]:=Module[{largest,start,times},

start=size^2+If[Mod[size,2]==0,{{-4,-3},{-1,-2}},Template:-1];
times=If[Mod[size,2]==0,size/2-1,(size-1)/2];
Nest[AddSquareRing,start,times]

]</lang> Examples: <lang Mathematica>MakeSquareSpiral[2] // MatrixForm MakeSquareSpiral[7] // MatrixForm</lang> gives back:

$\left({\begin{array}{cc}0&1\\3&2\end{array}}\right)$

$\left({\begin{array}{ccccccc}0&1&2&3&4&5&6\\23&24&25&26&27&28&7\\22&39&40&41&42&29&8\\21&38&47&48&43&30&9\\20&37&46&45&44&31&10\\19&36&35&34&33&32&11\\18&17&16&15&14&13&12\end{array}}\right)$

MATLAB

There already exists a command to generate a spiral matrix in MATLAB. But, it creates a matrix that spirals outward, not inward like the task specification requires. It turns out that these matrices can be transformed into each other using some pretty simple transformations.

We start with a simple linear transformation: $(-spiral(n))+n^{2}$ Then depending on if n is odd or even we use either an up/down or left/right mirror transformation.

<lang MATLAB>function matrix = reverseSpiral(n)

   matrix = (-spiral(n))+n^2;
   
   if mod(n,2)==0
       matrix = flipud(matrix);
   else
       matrix = fliplr(matrix);
   end

end %reverseSpiral</lang>

Sample Usage: <lang MATLAB>>> reverseSpiral(5)

ans =

    0     1     2     3     4
   15    16    17    18     5
   14    23    24    19     6
   13    22    21    20     7
   12    11    10     9     8</lang>

OCaml

<lang ocaml>let next_dir = function

 |  1,  0 ->  0, -1
 |  0,  1 ->  1,  0
 | -1,  0 ->  0,  1
 |  0, -1 -> -1,  0
 | _ -> assert false

let next_pos ~pos:(x,y) ~dir:(nx,ny) = (x+nx, y+ny)

let next_cell ar ~pos:(x,y) ~dir:(nx,ny) =

 try ar.(x+nx).(y+ny)
 with _ -> -2

let for_loop n init fn =

 let rec aux i v =
   if i < n then aux (i+1) (fn i v)
 in
 aux 0 init

let spiral ~n =

 let ar = Array.make_matrix n n (-1) in
 let pos = 0, 0 in
 let dir = 0, 1 in
 let set (x, y) i = ar.(x).(y) <- i in
 let step (pos, dir) =
   match next_cell ar pos dir with
   | -1 -> (next_pos pos dir, dir)
   | _ -> let dir = next_dir dir in (next_pos pos dir, dir)
 in
 for_loop (n*n) (pos, dir)
          (fun i (pos, dir) -> set pos i; step (pos, dir));
 (ar)

let print =

 Array.iter (fun line ->
   Array.iter (Printf.printf " %2d") line;
   print_newline())

let () = print(spiral 5)</lang>

Octave

The function make_spiral (and helper functions) are modelled after the J solution.

<lang octave>function rs = runsum(v)

 for i = 1:numel(v)
   rs(i) = sum(v(1:i));
 endfor

endfunction

function g = grade(v)

 for i = 1:numel(v)
   g(v(i)+1) = i-1;
 endfor

endfunction

function spiral = make_spiral(spirald)

 series = ones(1,spirald^2);
 l = spirald-1; p = spirald+1;
 s = 1;
 while(l>0)
   series(p:p+l-1) *= spirald*s;
   series(p+l:p+l*2-1) *= -s;
   p += l*2;
   l--; s *= -1;
 endwhile
 series(1) = 0;
 spiral = reshape(grade(runsum(series)), spirald, spirald)';

endfunction

make_spiral(5)</lang>

Oz

Simple, recursive solution: <lang oz>declare

 fun {Spiral N}
    %% create nested array
    Arr = {Array.new 1 N unit}
    for Y in 1..N do Arr.Y := {Array.new 1 N 0} end
    %% fill it recursively with increasing numbers
    C = {Counter 0}
 in
    {Fill Arr 1 N C}
    Arr
 end

 proc {Fill Arr S E C}
    %% go right
    for X in S..E do
       Arr.S.X := {C}
    end
    %% go down
    for Y in S+1..E do
       Arr.Y.E := {C}
    end
    %% go left
    for X in E-1..S;~1 do
       Arr.E.X := {C}
    end
    %% go up
    for Y in E-1..S+1;~1 do
       Arr.Y.S := {C}
    end
    %% fill the inner rectangle
    if E - S > 1 then {Fill Arr S+1 E-1 C} end
 end

 fun {Counter N}
    C = {NewCell N}
 in
    fun {$}
       C := @C + 1
    end
 end

in

 {Inspect {Spiral 5}}</lang>

Perl

<lang perl>sub spiral

{my ($n, $x, $y, $dx, $dy, @a) = (shift, 0, 0, 1, 0);
 foreach (0 .. $n**2 - 1)
    {$a[$y][$x] = $_;
     my ($nx, $ny) = ($x + $dx, $y + $dy);
     ($dx, $dy) =
         $dx ==  1 && ($nx == $n || defined $a[$ny][$nx])
       ? ( 0,  1)
       : $dy ==  1 && ($ny == $n || defined $a[$ny][$nx])
       ? (-1,  0)
       : $dx == -1 && ($nx  <  0 || defined $a[$ny][$nx])
       ? ( 0, -1)
       : $dy == -1 && ($ny  <  0 || defined $a[$ny][$nx])
       ? ( 1,  0)
       : ($dx, $dy);
     ($x, $y) = ($x + $dx, $y + $dy);}
 return @a;}

foreach (spiral 5)

  {printf "%3d", $_ foreach @$_;
   print "\n";}</lang>

Perl 6

Suppose we set up a Turtle class like this: <lang perl6>enum Dir < north northeast east southeast south southwest west northwest >; my $debug = 0;

class Turtle {

   has @.loc = 0,0;
   has Dir $.dir = north;

   my @dv =  [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1];
   my @num-to-dir = Dir.invert.sort».value;
   my $points = +Dir;

   my %world;
   my $maxegg;
   my $range-x;
   my $range-y;

   method turn-left ($angle = 90) { $!dir -= $angle / 45; $!dir %= $points; }
   method turn-right($angle = 90) { $!dir += $angle / 45; $!dir %= $points; }

   method lay-egg($egg) {

%world{~@!loc} = $egg; $maxegg max= $egg; $range-x minmax= @!loc[0]; $range-y minmax= @!loc[1];

   method look($ahead = 1) {

my $there = @!loc »+« (@dv[$!dir] X* $ahead); say "looking @num-to-dir[$!dir] to $there" if $debug; %world{~$there};

   method forward($ahead = 1) {

my $there = @!loc »+« (@dv[$!dir] X* $ahead); @!loc = @($there); say " moving @num-to-dir[$!dir] to @!loc[]" if $debug;

   method showmap() {

my $form = "%{$maxegg.chars}s"; my $endx = $range-x.max;

   	for $range-y.list X $range-x.list -> $y, $x {

print (%world{"$x $y"} // ).fmt($form); print $x == $endx ?? "\n" !! ' '; }

}</lang>

Now we can build the spiral in the normal way from outside-in like this:

<lang perl6>sub MAIN($size as Int) {

   my $t = Turtle.new(dir => east);
   my $counter = 0;
   $t.forward(-1);
   for 0..^ $size -> $ {

$t.forward; $t.lay-egg($counter++);

   }
   for $size-1 ... 1 -> $run {

$t.turn-right; $t.forward, $t.lay-egg($counter++) for 0..^$run; $t.turn-right; $t.forward, $t.lay-egg($counter++) for 0..^$run;

   }
   $t.showmap;

}</lang>

Or we can build the spiral from inside-out like this:

<lang perl6>sub MAIN($size as Int) {

   my $t = Turtle.new(dir => ($size %% 2 ?? south !! north));
   my $counter = $size * $size;
   while $counter {

$t.lay-egg(--$counter); $t.turn-left; $t.turn-right if $t.look; $t.forward;

   }
   $t.showmap;

}</lang> Note that with these "turtle graphics" we don't actually have to care about the coordinate system, since the showmap method can show whatever rectangle was modified by the turtle. So unlike the standard inside-out algorithm, we don't have to find the center of the matrix first.

PL/I

<lang PL/I> /* Generates a square matrix containing the integers from 0 to N**2-1, */ /* where N is the length of one side of the square. */ /* Written 22 February 2010. */

  declare n fixed binary;

put skip list ('Please type the size of the square:'); get list (n);

begin;

  declare A(n,n) fixed binary;
  declare (i, j, iinc, jinc, q) fixed binary;

  A = -1;

  i, j = 1; iinc = 0; jinc = 1;
  do q = 0 to n**2-1;
     if a(i,j) < 0 then
        a(i,j) = q;
     else
        do;
            /* back up */
            j = j -jinc; i = i - iinc;
            /* change direction */
            if iinc = 0 & jinc = 1 then do; iinc = 1; jinc = 0; end;
            else if iinc =  1 & jinc =  0 then do; iinc =  0; jinc = -1; end;
            else if iinc =  0 & jinc = -1 then do; iinc = -1; jinc =  0; end;
            else if iinc = -1 & jinc =  0 then do; iinc =  0; jinc =  1; end;
           /* Take one step in the new direction */
            i = i + iinc; j = j + jinc;
            a(i,j) = q;
        end;
     if i+iinc > n | i+iinc < 1 then
        do;
           iinc = 0; jinc = 1;
           if j+1 > n then jinc = -1; else if j-1 < 1 then jinc = 1;
           if a(i+iinc,j+jinc) >= 0 then jinc = -jinc;
           /* j = j + jinc; /* to move on from the present (filled) position */
        end;
     else i = i + iinc;
     if j+jinc > n | j+jinc < 1 then
        do;
           jinc = 0; iinc = 1;
           if i+1 > n then iinc = -1; else if i-1 < 1 then iinc = 1;
           if a(i+iinc,j+jinc) >= 0 then iinc = -iinc;
           i = i + iinc; /* to move on from the present (filled) position */
        end;
     else j = j + jinc;
  end;

  /* Display the square. */
  do i = 1 to n;
     put skip edit (A(i,*)) (F(4));
  end;

end; </lang>

PicoLisp

This example uses 'grid' from "lib/simul.l", which maintains a two-dimensional structure and is normally used for simulations and board games. <lang PicoLisp>(load "@lib/simul.l")

(de spiral (N)

  (prog1 (grid N N)
     (let (Dir '(north east south west .)  This 'a1)
        (for Val (* N N)
           (=: val Val)
           (setq This
              (or
                 (with ((car Dir) This)
                    (unless (: val) This) )
                 (with ((car (setq Dir (cdr Dir))) This)
                    (unless (: val) This) ) ) ) ) ) ) )

(mapc

  '((L)
     (for This L (prin (align 3 (: val))))
     (prinl) )
  (spiral 5) )</lang>

Output:

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

PureBasic

Translation of: Fortran

<lang PureBasic>Procedure spiralMatrix(size = 1)

 Protected i, x = -1, y, count = size, n
 Dim a(size - 1,size - 1)
 
 For i = 1 To count
   x + 1
   a(x,y) = n
   n + 1
 Next
 
 Repeat
   count - 1
   For i = 1 To count
     y + 1
     a(x,y) = n
     n + 1
   Next
   For i = 1 To count
     x - 1
     a(x,y) = n
     n + 1
   Next

   count - 1
   For i = 1 To count
     y - 1
     a(x,y) = n
     n + 1
   Next
   For i = 1 To count
     x + 1
     a(x,y) = n
     n + 1
   Next
 Until count < 1
     
 PrintN("Spiral: " + Str(Size) + #CRLF$)
 Protected colWidth = Len(Str(size * size - 1)) + 1
 For y = 0 To size - 1
   For x = 0 To size - 1
     Print("" + LSet(Str(a(x, y)), colWidth, " ") + "")
   Next
   PrintN("")
 Next
 PrintN("")

EndProcedure

If OpenConsole()

 spiralMatrix(2)
 PrintN("")
 spiralMatrix(5)
 
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
 Input()
 CloseConsole()

EndIf</lang> Sample output:

Spiral: 2

0 1
3 2


Spiral: 5

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

Python

<lang python>def spiral(n):

   dx,dy = 1,0            # Starting increments
   x,y = 0,0              # Starting location
   myarray = [[None]* n for j in range(n)]
   for i in xrange(n**2):
       myarray[x][y] = i
       nx,ny = x+dx, y+dy
       if 0<=nx<n and 0<=ny<n and myarray[nx][ny] == None:
           x,y = nx,ny
       else:
           dx,dy = -dy,dx
           x,y = x+dx, y+dy
   return myarray

def printspiral(myarray):

   n = range(len(myarray))
   for y in n:
       for x in n:
           print "%2i" % myarray[x][y],
       print

printspiral(spiral(5))</lang> Sample output:

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

Recursive Solution

<lang python>def spiral(n):

   def spiral_part(x, y, n):
       if x == -1 and y == 0:
           return -1
       if y == (x+1) and x < (n // 2):
           return spiral_part(x-1, y-1, n-1) + 4*(n-y)
       if x < (n-y) and y <= x:
           return spiral_part(y-1, y, n) + (x-y) + 1
       if x >= (n-y) and y <= x:
           return spiral_part(x, y-1, n) + 1
       if x >= (n-y) and y > x:
           return spiral_part(x+1, y, n) + 1
       if x < (n-y) and y > x:
           return spiral_part(x, y-1, n) - 1

   array = [[0] * n for j in xrange(n)]
   for x in xrange(n):
       for y in xrange(n):
           array[x][y] = spiral_part(y, x, n)
   return array

for row in spiral(5):

   print " ".join("%2s" % x for x in row)</lang>

Adding a cache for the spiral_part function it could be quite efficient.

Another way, based on preparing lists ahead

<lang python>def spiral(n):

   dat = [[None] * n for i in range(n)]
   le = [[i + 1, i + 1] for i in reversed(range(n))]
   le = sum(le, [])[1:]  # for n = 5 le will be [5, 4, 4, 3, 3, 2, 2, 1, 1]
   dxdy = [[1, 0], [0, 1], [-1, 0], [0, -1]] * ((len(le) + 4) / 4)  # long enough
   x, y, val = -1, 0, -1
   for steps, (dx, dy) in zip(le, dxdy):
       x, y, val = x + dx, y + dy, val + 1
       for j in range(steps):
           dat[y][x] = val
           if j != steps-1:
               x, y, val = x + dx, y + dy, val + 1
   return dat

for row in spiral(5): # calc spiral and print it

   print ' '.join('%3s' % x for x in row)</lang>

Functional Solution

Works with: Python version 2.6, 3.0

<lang python>import itertools

concat = itertools.chain.from_iterable def partial_sums(items):

   s = 0
   for x in items:
       s += x
       yield s

grade = lambda xs: sorted(range(len(xs)), key=xs.__getitem__) values = lambda n: itertools.cycle([1,n,-1,-n]) counts = lambda n: concat([i,i-1] for i in range(n,0,-1)) reshape = lambda n, xs: zip(*([iter(xs)] * n))

spiral = lambda n: reshape(n, grade(list(partial_sums(concat(

                      [v]*c for c,v in zip(counts(n), values(n)))))))

for row in spiral(5):

   print(' '.join('%3s' % x for x in row))</lang>

R

Translation of: Octave

<lang R>runsum <- function(v) {

 rs <- c()
 for(i in 1:length(v)) {
   rs <- c(rs, sum(v[1:i]))
 }
 rs

}

grade <- function(v) {

 g <- vector("numeric", length(v))
 for(i in 1:length(v)) {
   g[v[i]] <- i-1
 }
 g

}

makespiral <- function(spirald) {

 series <- vector("numeric", spirald^2)
 series[] <- 1
 l <- spirald-1; p <- spirald+1
 s <- 1
 while(l > 0) {
   series[p:(p+l-1)] <- series[p:(p+l-1)] * spirald*s
   series[(p+l):(p+l*2-1)] <- -s*series[(p+l):(p+l*2-1)]
   p <- p + l*2
   l <- l - 1; s <- -s
 }
 matrix(grade(runsum(series)), spirald, spirald, byrow=TRUE)

}

print(makespiral(5))</lang>

REXX

Logic stolen (mostly) from the Fortran code. <lang rexx> /*REXX program to show a spiral in a square array (of any size). */

arg size . /*get the array size from arg. */ if size== then size=5 /*if no argument, use the default*/ tot=size**2 /*total # of elements in spiral. */ k=size /*K is the counter for the sprial*/ row=1 /*start with row one. */ col=0 /*start with col zero. */ n=0 /*start the sprial at 0 (zero).*/

/*─────────────────────────────────────build the spiral─────────────────*/

     do n=0 for k;  col=col+1;  @.col.row=n;  end
  do until n>=tot
  k=k-1
     do n=n for k;  row=row+1;  @.col.row=n;  end
     do n=n for k;  col=col-1;  @.col.row=n;  end
 if n>=tot then leave
 k=k-1
     do n=n for k;  row=row-1;  @.col.row=n;  end
     do n=n for k;  col=col+1;  @.col.row=n;  end
  end

/*─────────────────────────────────────display the spiral───────────────*/

 do col=1 for size;  _=
   do row=1 for size
   _=_ right(@.row.col,length(tot))
   end
 say substr(_,2)
 end

</lang> Output (using the default array size of 5):

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

Output (using an array size of 36):

   0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35
 139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173   36
 138  271  272  273  274  275  276  277  278  279  280  281  282  283  284  285  286  287  288  289  290  291  292  293  294  295  296  297  298  299  300  301  302  303  174   37
 137  270  395  396  397  398  399  400  401  402  403  404  405  406  407  408  409  410  411  412  413  414  415  416  417  418  419  420  421  422  423  424  425  304  175   38
 136  269  394  511  512  513  514  515  516  517  518  519  520  521  522  523  524  525  526  527  528  529  530  531  532  533  534  535  536  537  538  539  426  305  176   39
 135  268  393  510  619  620  621  622  623  624  625  626  627  628  629  630  631  632  633  634  635  636  637  638  639  640  641  642  643  644  645  540  427  306  177   40
 134  267  392  509  618  719  720  721  722  723  724  725  726  727  728  729  730  731  732  733  734  735  736  737  738  739  740  741  742  743  646  541  428  307  178   41
 133  266  391  508  617  718  811  812  813  814  815  816  817  818  819  820  821  822  823  824  825  826  827  828  829  830  831  832  833  744  647  542  429  308  179   42
 132  265  390  507  616  717  810  895  896  897  898  899  900  901  902  903  904  905  906  907  908  909  910  911  912  913  914  915  834  745  648  543  430  309  180   43
 131  264  389  506  615  716  809  894  971  972  973  974  975  976  977  978  979  980  981  982  983  984  985  986  987  988  989  916  835  746  649  544  431  310  181   44
 130  263  388  505  614  715  808  893  970 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055  990  917  836  747  650  545  432  311  182   45
 129  262  387  504  613  714  807  892  969 1038 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1056  991  918  837  748  651  546  433  312  183   46
 128  261  386  503  612  713  806  891  968 1037 1098 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1114 1057  992  919  838  749  652  547  434  313  184   47
 127  260  385  502  611  712  805  890  967 1036 1097 1150 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1164 1115 1058  993  920  839  750  653  548  435  314  185   48
 126  259  384  501  610  711  804  889  966 1035 1096 1149 1194 1231 1232 1233 1234 1235 1236 1237 1238 1239 1206 1165 1116 1059  994  921  840  751  654  549  436  315  186   49
 125  258  383  500  609  710  803  888  965 1034 1095 1148 1193 1230 1259 1260 1261 1262 1263 1264 1265 1240 1207 1166 1117 1060  995  922  841  752  655  550  437  316  187   50
 124  257  382  499  608  709  802  887  964 1033 1094 1147 1192 1229 1258 1279 1280 1281 1282 1283 1266 1241 1208 1167 1118 1061  996  923  842  753  656  551  438  317  188   51
 123  256  381  498  607  708  801  886  963 1032 1093 1146 1191 1228 1257 1278 1291 1292 1293 1284 1267 1242 1209 1168 1119 1062  997  924  843  754  657  552  439  318  189   52
 122  255  380  497  606  707  800  885  962 1031 1092 1145 1190 1227 1256 1277 1290 1295 1294 1285 1268 1243 1210 1169 1120 1063  998  925  844  755  658  553  440  319  190   53
 121  254  379  496  605  706  799  884  961 1030 1091 1144 1189 1226 1255 1276 1289 1288 1287 1286 1269 1244 1211 1170 1121 1064  999  926  845  756  659  554  441  320  191   54
 120  253  378  495  604  705  798  883  960 1029 1090 1143 1188 1225 1254 1275 1274 1273 1272 1271 1270 1245 1212 1171 1122 1065 1000  927  846  757  660  555  442  321  192   55
 119  252  377  494  603  704  797  882  959 1028 1089 1142 1187 1224 1253 1252 1251 1250 1249 1248 1247 1246 1213 1172 1123 1066 1001  928  847  758  661  556  443  322  193   56
 118  251  376  493  602  703  796  881  958 1027 1088 1141 1186 1223 1222 1221 1220 1219 1218 1217 1216 1215 1214 1173 1124 1067 1002  929  848  759  662  557  444  323  194   57
 117  250  375  492  601  702  795  880  957 1026 1087 1140 1185 1184 1183 1182 1181 1180 1179 1178 1177 1176 1175 1174 1125 1068 1003  930  849  760  663  558  445  324  195   58
 116  249  374  491  600  701  794  879  956 1025 1086 1139 1138 1137 1136 1135 1134 1133 1132 1131 1130 1129 1128 1127 1126 1069 1004  931  850  761  664  559  446  325  196   59
 115  248  373  490  599  700  793  878  955 1024 1085 1084 1083 1082 1081 1080 1079 1078 1077 1076 1075 1074 1073 1072 1071 1070 1005  932  851  762  665  560  447  326  197   60
 114  247  372  489  598  699  792  877  954 1023 1022 1021 1020 1019 1018 1017 1016 1015 1014 1013 1012 1011 1010 1009 1008 1007 1006  933  852  763  666  561  448  327  198   61
 113  246  371  488  597  698  791  876  953  952  951  950  949  948  947  946  945  944  943  942  941  940  939  938  937  936  935  934  853  764  667  562  449  328  199   62
 112  245  370  487  596  697  790  875  874  873  872  871  870  869  868  867  866  865  864  863  862  861  860  859  858  857  856  855  854  765  668  563  450  329  200   63
 111  244  369  486  595  696  789  788  787  786  785  784  783  782  781  780  779  778  777  776  775  774  773  772  771  770  769  768  767  766  669  564  451  330  201   64
 110  243  368  485  594  695  694  693  692  691  690  689  688  687  686  685  684  683  682  681  680  679  678  677  676  675  674  673  672  671  670  565  452  331  202   65
 109  242  367  484  593  592  591  590  589  588  587  586  585  584  583  582  581  580  579  578  577  576  575  574  573  572  571  570  569  568  567  566  453  332  203   66
 108  241  366  483  482  481  480  479  478  477  476  475  474  473  472  471  470  469  468  467  466  465  464  463  462  461  460  459  458  457  456  455  454  333  204   67
 107  240  365  364  363  362  361  360  359  358  357  356  355  354  353  352  351  350  349  348  347  346  345  344  343  342  341  340  339  338  337  336  335  334  205   68
 106  239  238  237  236  235  234  233  232  231  230  229  228  227  226  225  224  223  222  221  220  219  218  217  216  215  214  213  212  211  210  209  208  207  206   69
 105  104  103  102  101  100   99   98   97   96   95   94   93   92   91   90   89   88   87   86   85   84   83   82   81   80   79   78   77   76   75   74   73   72   71   70

Ruby

Using the print_matrix method from Reduced row echelon form#Ruby

Translation of: Python

<lang ruby>def spiral(n)

 spiral = Array.new(n) {Array.new(n, nil)}     # n x n array of nils
 runs = n.downto(0).each_cons(2).to_a.flatten  # n==5; [5,4,4,3,3,2,2,1,1,0]
 delta = [[1,0], [0,1], [-1,0], [0,-1]].each
 x, y, value = -1, 0, -1
 for run in runs
   dx,dy = begin
             delta.next
           rescue StopIteration
             delta.rewind
             retry
           end
   run.times do |i|
     x += dx
     y += dy
     value += 1
     spiral[y][x] = value
   end
 end
 spiral

end

print_matrix spiral(5)</lang>

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

Scala

<lang scala> class Folder(){

 var dir = (1,0)
 var pos = (-1,0)
 def apply(l:List[Int], a:Array[Array[Int]]) = {
   var (x,y) = pos  //start position
   var (dx,dy) = dir //direction
   l.foreach {e => x = x + dx; y = y + dy; a(y)(x) = e }  //copy l elements to array using current direction
   pos = (x,y)
   dir = (-dy, dx) //turn
 }

} def spiral(n:Int) = {

 def dup(n:Int) = (1 to n).flatMap(i=>List(i,i)).toList
 val folds = n :: dup(n-1).reverse  //define fold part lengths

 var array = new Array[Array[Int]](n,n)
 val fold = new Folder()

 var seq = (0 until n*n).toList  //sequence to fold
 folds.foreach {len => fold(seq.take(len),array); seq = seq.drop(len)}
 array

} </lang>

Explanation: if you see the sequence of numbers to spiral around as a tape to fold around, you can see this pattern on the lenght of tape segment to fold in each step:
N, N-1, N-1,..., 1, 1
Using this the solution becomes very simple,
1. make the list of lengths to fold
2. create the sequence to fold
3. for each segment call a fold function that keeps track of where it is and knows how to turn around

It's simple to make this generic, changing start position, initial direction, etc.
The code could be more compact, but I'm leaving it like this for clarity.

Tcl

Using print_matrix from Matrix Transpose#Tcl <lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop} proc spiral size {

   set m [lrepeat $size [lrepeat $size .]]
   set x 0; set dx 0
   set y -1; set dy 1
   set i -1
   while {$i < $size ** 2 - 1} {
       if {$dy == 0} {
           incr x $dx
           if {0 <= $x && $x < $size && [lindex $m $x $y] eq "."} {
               lset m $x $y [incr i]
           } else {
               # back up and change direction
               incr x [- $dx]
               set dy [- $dx]
               set dx 0
           }
       } else {
           incr y $dy
           if {0 <= $y && $y < $size && [lindex $m $x $y] eq "."} {
               lset m $x $y [incr i]
           } else {
               # back up and  change direction
               incr y [- $dy]
               set dx $dy
               set dy 0
           }
       }
   }
   return $m

}

print_matrix [spiral 5]</lang>

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

Ursala

Helpful hints from the J example are gratefully acknowledged. The spiral function works for any n, and results are shown for n equal to 5, 6, and 7. The results are represented as lists of lists rather than arrays. <lang Ursala>#import std

import nat
import int

spiral =

^H/block nleq-<lS&r+ -+

  num@NiC+ sum:-0*yK33x+ (|\LL negation**)+ rlc ~&lh==1,
  ~&rNNXNXSPlrDlSPK32^lrtxiiNCCSLhiC5D/~& iota*+ iota+-

cast %nLLL

examples = spiral* <5,6,7></lang> output:

<
   <
      <0,1,2,3,4>,
      <15,16,17,18,5>,
      <14,23,24,19,6>,
      <13,22,21,20,7>,
      <12,11,10,9,8>>,
   <
      <0,1,2,3,4,5>,
      <19,20,21,22,23,6>,
      <18,31,32,33,24,7>,
      <17,30,35,34,25,8>,
      <16,29,28,27,26,9>,
      <15,14,13,12,11,10>>,
   <
      <0,1,2,3,4,5,6>,
      <23,24,25,26,27,28,7>,
      <22,39,40,41,42,29,8>,
      <21,38,47,48,43,30,9>,
      <20,37,46,45,44,31,10>,
      <19,36,35,34,33,32,11>,
      <18,17,16,15,14,13,12>>>

Visual Basic

Translation of: Java

This requires VB6.

<lang vb>Option Explicit

Sub Main()

   print2dArray getSpiralArray(5)

End Sub

Function getSpiralArray(dimension As Integer) As Integer()

   ReDim spiralArray(dimension - 1, dimension - 1) As Integer

   Dim numConcentricSquares As Integer
   numConcentricSquares = dimension \ 2
   If (dimension Mod 2) Then numConcentricSquares = numConcentricSquares + 1

   Dim j As Integer, sideLen As Integer, currNum As Integer
   sideLen = dimension

   Dim i As Integer
   For i = 0 To numConcentricSquares - 1
       ' do top side
       For j = 0 To sideLen - 1
           spiralArray(i, i + j) = currNum
           currNum = currNum + 1
       Next

       ' do right side
       For j = 1 To sideLen - 1
           spiralArray(i + j, dimension - 1 - i) = currNum
           currNum = currNum + 1
       Next

       ' do bottom side
       For j = sideLen - 2 To 0 Step -1
           spiralArray(dimension - 1 - i, i + j) = currNum
           currNum = currNum + 1
       Next

       ' do left side
       For j = sideLen - 2 To 1 Step -1
           spiralArray(i + j, i) = currNum
           currNum = currNum + 1
       Next

       sideLen = sideLen - 2
   Next

   getSpiralArray = spiralArray()

End Function

Sub print2dArray(arr() As Integer)

   Dim row As Integer, col As Integer
   For row = 0 To UBound(arr, 1)
       For col = 0 To UBound(arr, 2) - 1
           Debug.Print arr(row, col),
       Next
       Debug.Print arr(row, UBound(arr, 2))
   Next

End Sub</lang>

VBA

Translation of: Java

Works with: VBA/Excel

<lang vb>Sub spiral()

   Dim n As Integer, a As Integer, b As Integer
   Dim numCsquares As Integer, sideLen As Integer, currNum As Integer
   Dim j As Integer, i As Integer
   Dim j1 As Integer, j2 As Integer, j3 As Integer

   n = 5

   Dim spiralArr(9, 9) As Integer
   numCsquares = CInt(Application.WorksheetFunction.Ceiling(n / 2, 1))
   sideLen = n
   currNum = 0
   For i = 0 To numCsquares - 1
       'do top side
       For j = 0 To sideLen - 1
           currNum = currNum + 1
           spiralArr(i, i + j) = currNum
       Next j

       'do right side
       For j1 = 1 To sideLen - 1
           currNum = currNum + 1
           spiralArr(i + j1, n - 1 - i) = currNum
       Next j1

       'do bottom side
       j2 = sideLen - 2
       Do While j2 > -1
           currNum = currNum + 1
           spiralArr(n - 1 - i, i + j2) = currNum
           j2 = j2 - 1
       Loop

       'do left side
       j3 = sideLen - 2
       Do While j3 > 0
           currNum = currNum + 1
           spiralArr(i + j3, i) = currNum
           j3 = j3 - 1
       Loop

       sideLen = sideLen - 2
   Next i

   For a = 0 To n - 1
       For b = 0 To n - 1
       Cells(a + 1, b + 1).Select
           ActiveCell.Value = spiralArr(a, b)
       Next b
   Next a

End Sub</lang>

Spiral matrix: Difference between revisions

Revision as of 04:09, 16 November 2010

Ada

ALGOL 68

AutoHotkey

C

C++

C#

Common Lisp

D

E

Fortran

F#

Haskell

J

Java

JavaScript

Lua

Mathematica

MATLAB

OCaml

Octave

Oz

Perl

Perl 6

PL/I

PicoLisp

PureBasic

Python

Recursive Solution

Functional Solution

R

REXX

Ruby

Scala

Tcl

Ursala

Visual Basic

VBA