Write a program (or explain how to do it) that will display a descending "spiral" of NxN numbers, using constant space (no arrays allowed). For example, here's what the spiral looks like for N=10:
99 98 97 96 95 94 93 92 91 90
64 63 62 61 60 59 58 57 56 89
65 36 35 34 33 32 31 30 55 88
66 37 16 15 14 13 12 29 54 87
67 38 17 4 3 2 11 28 53 86
68 39 18 5 0 1 10 27 52 85
69 40 19 6 7 8 9 26 51 84
70 41 20 21 22 23 24 25 50 83
71 42 43 44 45 46 47 48 49 82
72 73 74 75 76 77 78 79 80 81
Back in the mid to late 80s, I had an IBM XT clone, and Microsoft Fortran. I made a program to calculate this identical square spiral (always going counterclockwise), and then write directly to the video RAM. Each square of the pattern was one pixel. At the time, the algorithm I used was similar to what others used here, essentially calculating the locations of each number algebraically.
For this problem, I cheated a little, using the equivalent of arrays (lists in Python), and I chose to keep it always starting with 1 to the right of the 0.
Algorithm. Consider an automaton which begins at (x,y) = (0,0), pointing South. It knows its x and y coordinates and its direction. It marks the current cell with an integer (first 0, then 1 etc). If the cell to the left is empty, it makes a left turn then moves one cell . If cell to left is occupied, it moves straight ahead. In the first move, after marking the location (0,0) with a "0", finding an empty cell to the left, the automaton moves one cell to the East so it's location is then (1,0) and direction is East.
This is recorded as an indexed list, coord[i] where the index is the integer being "marked" and each element is a 2-element list [x,y] of coordinates.
When that is complteted, re-calculate all the coordinates to put (0,0) at the top left, "x" still increases left to right but "y" increases downward: this is to make printing easier.
Next make a new list of lists, grid[x][y] indexed according to the coordinate system, and with the element equal to the integer to be printed.
Then print with constant width so the columns line up.
----- code follows -----
<pre>
size = 10
x = 0
y = 0
minX = maxX = minY = maxY = 0
#initialize list of [x,y] for each integer
coord = [[0,0] for i in range(size**2)]
coordP = [[0,0] for i in range(size**2)]
direction = 3 # 0,1,2,3 equals East, North, West, South
# dictionary where key is direction and value is a list of x,y RELATIVE
# coordinates of the cell to the left AND the cell straight ahead
mapDict = {0:[0,1,1,0], 1:[-1,0,0,1], 2:[0,-1,-1,0], 3:[1,0,0,-1]}
for i in range(0, len(coord)):
coord[i] = [x,y]
cellToLeft = [x + mapDict[direction][0] , \
y + mapDict[direction][1]]
if cellToLeft in coord: # go straight
x = x + mapDict[direction][2]
y = y + mapDict[direction][3]
else: #if not then turn left
x = cellToLeft[0]
y = cellToLeft[1]
direction = (direction + 1)%4
if x < minX:
minX = x
if x > maxX:
maxX = x
if y < minY:
minY = y
if y > maxY:
maxY = y
for i in range(len(coord)): # redefine coord so [0,0] at top left
coordP[i] = [coord[i][0] - minX - 1 + size%2 , maxY - (coord[i][1])]
grid = [[0 for j in range(size)] for i in range(size)] #initialize
for i in range(len(coord)):
grid[coordP[i][1]][coordP[i][0]] = i
for i in range(size):
if i > 0:
print('\n')
for j in range(size):
print('{:3d}'.format(grid[i][j]), end = ' ')
</pre>
|
|
Posted by Larry
on 2019-11-24 11:49:49 |
solution, parameters slightly modified
