This
exercise I thought up myself after doing
href="http://paddy3118.blogspot.com/2008/08/zig-zag.html">ZigZag.
"
Produce a spiral array.. A spiral array is a square arrangement of the
first N
2 integers, where the numbers increase
sequentially as you go around the edges of the array
spiralling inwards.
For example, given 5, produce
this array:
style="font-family: monospace;"> 0
1 2 3 4 style="font-family: monospace;"> style="font-family: monospace;">15 16 17 18 5 style="font-family: monospace;"> style="font-family: monospace;">14 23 24 19 6 style="font-family: monospace;"> style="font-family: monospace;">13 22 21 20 7 style="font-family: monospace;"> style="font-family: monospace;">12 11 10
9 8
The
Algorithm
Again I choose to define the x axis as the column
numbers increasing linearly left to right; and the y axis being the row
numbers increasing linearly top to bottom; and with the top left corner
being (0,0).
If you think of the outer part of the spiral, it
can be defined as how x and y change, i.e. deltas. First along the top
row
dx,dy =
(1,0) meaning that for successive places x changes by 1
and y does not.
Similarly
for the next straight run , down the RHS: style="font-family: monospace;"> dx,dy = (0,1).
Along
the bottom: dx,dy =
(-1,0).
And back to the top along the LHS: style="font-family: monospace;">dx,dy = (0,-1).
The
next time around the loop, dx,dy take on those same values.
When
to stop going in a straight line and change direction?
style="margin-left: 40px;">
- When you
would go off the edge of the array - If you are about
to 'step' on a position that is already filled.
When
to stop?
- When
you have placed the last integer.
The Program
I have two ways of generating successive dx,dy
values; a formula in lines 19 and 34, and a commented out use of
itertools.cycle in lines 14,17,18 and 33 which could be used instead.
They generate the same sequence.
When to change direction is
done by initializing myarray with None values in line 22 and the
conditional statement at line 29
When to stop is handled by
the outer while loop at line 24.
I added a flag at
line 15 that allows you to trace the calculation
1 '''
color="#804040"> 2 Author: Donald 'Paddy' McCarthy
color="#804040"> 3 Email: paddy3118@gmail.com
color="#804040"> 4 File: spiral.py
color="#804040"> 5
color="#804040"> 6 Routine creates a square array filled with numbers that increase
color="#804040"> 7 in a spiral pattern into the center.
color="#804040"> 8
color="#804040"> 9 Note: for spiralling out just swap array[x,y] for n**2-1-array[x,y]
color="#804040">10 Note: Vim colourizing plus
color="#804040">11 :%s/\( \)\? / color="#6a5acd">\1\ \ /g
color="#804040">12 '''
color="#804040">13
color="#804040">14 #from itertools import cycle
color="#804040">15 explain = True
color="#804040">16 def color="#008080">spiral(n):
color="#804040">17 color="#0000ff">#deltas = cycle( ((1,0),(0,1),(-1,0),(0,-1)) )
color="#804040">18 color="#0000ff">#dx,dy = deltas.next() # Starting increments
color="#804040">19 dx,dy = 1,0 color="#0000ff"># Starting increments
color="#804040">20 x,y = 0,0 color="#0000ff"># Starting location
color="#804040">21 i = 0 color="#0000ff"># starting value
color="#804040">22 myarray = [[None]* n color="#804040">for j color="#804040">in range(n)]
color="#804040">23 color="#804040">if explain: color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy
color="#804040">24 color="#804040">while i < n**2:
color="#804040">25 myarray[x][y] = i
color="#804040">26 color="#804040">if explain: color="#804040">print " color="#ff00ff">x,y->[x,y]", x,y, myarray[x][y]
color="#804040">27 i += 1
color="#804040">28 nx,ny = x+dx, y+dy
color="#804040">29 color="#804040">if 0<=nx<n color="#804040">and 0<=ny<n color="#804040">and myarray[nx][ny] == None:
color="#804040">30 x,y = nx,ny
color="#804040">31 color="#804040">continue
color="#804040">32 color="#804040">else:
color="#804040">33 color="#0000ff">#dx,dy = deltas.next()
color="#804040">34 dx,dy = (-dy,dx) color="#804040">if dy color="#804040">else (dy,dx)
color="#804040">35 color="#804040">if explain: color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy
color="#804040">36 x,y = x+dx, y+dy
color="#804040">37 color="#804040">return myarray
color="#804040">38 def color="#008080">printspiral(myarray):
color="#804040">39 n = range(len(myarray))
color="#804040">40 color="#804040">for y color="#804040">in n:
color="#804040">41 color="#804040">for x color="#804040">in n:
color="#804040">42 color="#804040">print " color="#ff00ff">%2i" % myarray[x][y],
color="#804040">43 color="#804040">print
color="#804040">44
color="#804040">45 printspiral(spiral(6))
Sample
output:
style="font-family: monospace;">>>>
printspiral(spiral(4)) style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 0 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 0 2 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 0 3 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 1 4 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 2 5 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 3 6 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 3 7 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 3 8 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 3 9 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 2 10 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 1 11 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 1 12 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 1 13 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 2 14 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 2 15 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;"> 0
1 2 3 style="font-family: monospace;"> style="font-family: monospace;">11 12 13 4 style="font-family: monospace;"> style="font-family: monospace;">10 15 14 5 style="font-family: monospace;"> style="font-family: monospace;"> 9
8 7 6 style="font-family: monospace;"> style="font-family: monospace;">>>>
Now a Rosetta Code entry.
ReplyDeleteA new recursive solution in:
ReplyDeletehttp://www.rosettacode.org/wiki/Spiral