# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Tuesday, August 05, 2008

### Spiral

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 N2 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

### TheAlgorithm

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
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.

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/\(&nbsp;&nbsp;\)\?  / color="#6a5acd">\1\&nbsp;\&nbsp;/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))`

#### Sampleoutput:

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;">>>>

1. Now a Rosetta Code entry.

2. A new recursive solution in:

http://www.rosettacode.org/wiki/Spiral