Spiral matrix
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
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))
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>
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>
Haskell
Solution based on the J hints:
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)
J
This function is the result of some beautiful insights:
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
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
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:
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>
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>
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>
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
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 rat
spiral =
^H/block -+
nleq-<lS&r+ num@NrlPSC+ sum:-0*@lZrXSK9tLiiDlSxyK9x, ~&hlPxhrPlrTSCPC+ (@DlS ^/(~&NiX\1)* -1/1!*)^*Dt/~& 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>>>