Spiral matrix: Difference between revisions
No edit summary |
(Added Ada) |
||
Line 11: | Line 11: | ||
12 11 10 9 8 |
12 11 10 9 8 |
||
</pre> |
</pre> |
||
=={{header|Ada}}== |
|||
<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; |
|||
</Ada> |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 05:00, 7 August 2008
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
<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; </Ada>
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).
Python
<python> def spiral(n):
dx,dy = 1,0 # Starting increments x,y = 0,0 # Starting location i = 0 # starting value myarray = [[None]* n for j in range(n)] while i < n**2: myarray[x][y] = i i += 1 nx,ny = x+dx, y+dy if 0<=nx<n and 0<=ny<n and myarray[nx][ny] == None: x,y = nx,ny continue else: dx,dy = (-dy,dx) if dy else (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)) </python> 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
<python> 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
def spiral(n):
array = [[None]*n for j in range(n)] for x in range(n): for y in range(n): array[x][y] = spiral_part(x,y,n) return array
</python>
Adding a cache for the spiral_part function it could be quite efficient.
Another way, based on preparing lists ahead
<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 != range(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)
</Python>