Spiral matrix: Difference between revisions
(→{{header|Perl 6}}: make turtle more abstract) |
|||
Line 916: | Line 916: | ||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
⚫ | |||
my @m = 0 xx (my $v = $n * $n); |
|||
Suppose we set up a Turtle class like this: |
|||
# start from the middle |
|||
<lang perl6>enum Dir < north northeast east southeast south southwest west northwest >; |
|||
my ($r, $c, $d) = $n div 2, $n div 2 - $n %% 2, ($n %% 2 ?? 2 !! 4); |
|||
my $debug = 0; |
|||
class Turtle { |
|||
# turn the turtle to face left of current direction |
|||
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; |
|||
sub f {if $d %% 2 {$r += $d == 4 ?? -1 !! 1} else {$c += $d == 3 ?? -1 !! 1}}; |
|||
my $points = +Dir; |
|||
my %world; |
|||
# look whether we've been left |
|||
my $maxegg; |
|||
sub l {t; f; my $x = @m[$r * $n + $c]; t; t; f; t; $x}; |
|||
my $range-x; |
|||
my $range-y; |
|||
method turn-left ($angle = 90) { $!dir -= $angle / 45; $!dir %= $points; } |
|||
# write; turn left if it's empty; move forward |
|||
method turn-right($angle = 90) { $!dir += $angle / 45; $!dir %= $points; } |
|||
method lay-egg($egg) { |
|||
# output matrix, padding entries based on the string length of biggest. |
|||
%world{~@!loc} = $egg; |
|||
say ~@m.splice(0, $n).fmt('%' ~ ($n * $n - 1).Str.chars ~ 'd') for ^$n; |
|||
$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: |
|||
⚫ | |||
my $t = Turtle.new(dir => east); |
|||
my $counter = 0; |
|||
⚫ | |||
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> |
}</lang> |
||
Note that with these "turtle graphics" we don't actually have to care about the coordinate system, since the <code>showmap</code> 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. |
|||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
Revision as of 16:43, 29 August 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Produce a spiral array. A spiral array is a square arrangement of the first N2 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
Ada
<lang ada>-- Spiral Square with Ada.Text_Io; use Ada.Text_Io; with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;
procedure Spiral_Square is
type Array_Type is array(Positive range <>, Positive range <>) of Natural; function Spiral (N : Positive) return Array_Type is Result : Array_Type(1..N, 1..N); Row : Natural := 1; Col : Natural := 1; Max_Row : Natural := N; Max_Col : Natural := N; Min_Row : Natural := 1; Min_Col : Natural := 1; begin for I in 0..N**2 - 1 loop Result(Row, Col) := I; if Row = Min_Row then Col := Col + 1; if Col > Max_Col then Col := Max_Col; Row := Row + 1; end if; elsif Col = Max_Col then Row := Row + 1; if Row > Max_Row then Row := Max_Row; Col := Col - 1; end if; elsif Row = Max_Row then Col := Col - 1; if Col < Min_Col then Col := Min_Col; Row := Row - 1; end if; elsif Col = Min_Col then Row := Row - 1; if Row = Min_Row then -- Reduce spiral Min_Row := Min_Row + 1; Max_Row := Max_Row - 1; Row := Min_Row; Min_Col := Min_Col + 1; Max_Col := Max_Col - 1; Col := Min_Col; end if; end if; end loop; return Result; end Spiral; procedure Print(Item : Array_Type) is Num_Digits : constant Float := Log(X => Float(Item'Length(1)**2), Base => 10.0); Spacing : constant Positive := Integer(Num_Digits) + 2; begin for I in Item'range(1) loop for J in Item'range(2) loop Put(Item => Item(I,J), Width => Spacing); end loop; New_Line; end loop; end Print;
begin
Print(Spiral(5));
end Spiral_Square;</lang> The following is a variant using a different algorithm (which can also be used recursively): <lang ada>function Spiral (N : Positive) return Array_Type is
Result : Array_Type (1..N, 1..N); Left : Positive := 1; Right : Positive := N; Top : Positive := 1; Bottom : Positive := N; Index : Natural := 0;
begin
while Left < Right loop for I in Left..Right - 1 loop Result (Top, I) := Index; Index := Index + 1; end loop; for J in Top..Bottom - 1 loop Result (J, Right) := Index; Index := Index + 1; end loop; for I in reverse Left + 1..Right loop Result (Bottom, I) := Index; Index := Index + 1; end loop; for J in reverse Top + 1..Bottom loop Result (J, Left) := Index; Index := Index + 1; end loop; Left := Left + 1; Right := Right - 1; Top := Top + 1; Bottom := Bottom - 1; end loop; Result (Top, Left) := Index; return Result;
end Spiral;</lang>
ALGOL 68
<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
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
(First code)
<lang c>#include <stdio.h>
- include <stdlib.h>
- define SPIADDR(baseptr,x,y,dim) (&((baseptr)[(y)*(dim)+(x)]))
- define None -1
int *spiral(int n) {
int dx,dy,x,y,i,nx,ny; x=y=0; dx=1; dy=0; int *buf = malloc(n*n*sizeof(int)); if (buf==NULL) return NULL; for(i=0;i<(n*n);i++) buf[i] = None; for(i=0;i<(n*n);i++) { *SPIADDR(buf,x,y,n) = i; nx = x + dx; ny = y + dy; if ( (nx<n) && (0<=nx) && (ny<n) && (0<=ny) && (*SPIADDR(buf,nx,ny,n) == None) ) { x=nx; y=ny; } else { int t = dx; dx=-dy; dy=t; x+=dx; y+=dy; } } return buf;
}
void printspiral(int *spi, int n) {
int x,y; if ( spi==NULL ) return; for(y=0; y<n; y++) { for(x=0; x<n; x++) { printf("%2d ", *SPIADDR(spi,x,y,n)); } printf("\n"); }
}
int main() {
int *the_spiral = NULL; the_spiral = spiral(5); printspiral(the_spiral, 5); if (the_spiral!=NULL) free(the_spiral); return 0;
}</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>
C#
Solution based on the J hints:
<lang csharp>public int[,] Spiral(int n) {
int[,] result = new int[n, n];
int pos = 0; int count = n; int value = -n; int sum = -1;
do { value = -1 * value / n; for (int i = 0; i < count; i++) { sum += value; result[sum / n, sum % n] = pos++; } value *= n; count--; for (int i = 0; i < count; i++) { sum += value; result[sum / n, sum % n] = pos++; } } while (count > 0);
return result;
}
// Method to print arrays, pads numbers so they line up in columns
public void PrintArray(int[,] array) {
int n = (array.GetLength(0) * array.GetLength(1) - 1).ToString().Length + 1;
for (int i = 0; i < array.GetLength(0); i++) { for (int j = 0; j < array.GetLength(1); j++) { Console.Write(array[i, j].ToString().PadLeft(n, ' ')); } Console.WriteLine(); }
}</lang>
Common Lisp
<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))
D
(Second code) (D V.1 code)
<lang d>import std.stdio: writef, writefln;
int[][] spiral(int n) {
int spiral_part(int x, int y, int n) { if (x == -1 && y == 0) return -1; if (y == (x+1) && x < (n/2)) return spiral_part(x-1, y-1, n-1) + 4 * (n-y); if (x < (n-y) && y <= x) return spiral_part(y-1, y, n) + (x-y) + 1; if (x >= (n-y) && y <= x) return spiral_part(x, y-1, n) + 1; if (x >= (n-y) && y > x) return spiral_part(x+1, y, n) + 1; if (x < (n-y) && y > x) return spiral_part(x, y-1, n) - 1; }
auto array = new int[][](n, n); foreach (r, ref row; array) foreach (c, ref el; row) array[r][c] = spiral_part(c, r, n); return array;
}
void main() {
foreach (row; spiral(5)) { foreach (el; row) writef("%3d", el); writefln(); }
}</lang>
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>
Fortran
<lang fortran>PROGRAM SPIRAL
IMPLICIT NONE INTEGER, PARAMETER :: size = 5 INTEGER :: i, x = 0, y = 1, count = size, n = 0 INTEGER :: array(size,size)
DO i = 1, count x = x + 1 array(x,y) = n n = n + 1 END DO
DO count = count - 1 DO i = 1, count y = y + 1 array(x,y) = n n = n + 1 END DO DO i = 1, count x = x - 1 array(x,y) = n n = n + 1 END DO IF (n > size*size-1) EXIT count = count - 1 DO i = 1, count y = y - 1 array(x,y) = n n = n + 1 END DO DO i = 1, count x = x + 1 array(x,y) = n n = n + 1 END DO IF (n > size*size-1) EXIT END DO DO y = 1, size DO x = 1, size WRITE (*, "(I4)", ADVANCE="NO") array (x, y) END DO WRITE (*,*) END DO
END PROGRAM SPIRAL</lang>
F#
No fancy schmancy elegance here, just putting the numbers in the right place (though I commend the elegance)... <lang fsharp>let Spiral n =
let sq = Array2D.create n n 0 // Set up an output array let nCur = ref -1 // Current value being inserted let NextN() = nCur := (!nCur+1) ; !nCur // Inc current value and return new value let Frame inset = // Create the "frame" at an offset from the outside let rangeF = [inset..(n - inset - 2)] // Range we use going forward let rangeR = [(n - inset - 1)..(-1)..(inset + 1)] // Range we use going backward rangeF |> Seq.iter (fun i -> sq.[inset,i] <- NextN()) // Top of frame rangeF |> Seq.iter (fun i -> sq.[i,n-inset-1] <- NextN()) // Right side of frame rangeR |> Seq.iter (fun i -> sq.[n-inset-1,i] <- NextN()) // Bottom of frame rangeR |> Seq.iter (fun i -> sq.[i,inset] <- NextN()) // Left side of frame [0..(n/2 - 1)] |> Seq.iter (fun i -> Frame i) // Fill in all frames if n &&& 1 = 1 then sq.[n/2,n/2] <- n*n - 1 // If n is odd, fill in the last single value sq // Return our output array
</lang>
Haskell
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
<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
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:
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: 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
<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
<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
<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>
Ruby
Using the print_matrix method from Reduced row echelon form#Ruby
<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>>>