All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Spirals (Posted on 2003-08-21) Difficulty: 3 of 5
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

See The Solution Submitted by DJ    
Rating: 4.4167 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution, parameters slightly modified Comment 11 of 11 |
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information