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 | Comment 3 of 10 |
To talk about the rows and columns of this layout, let the zero at the center define the origin at row zero column zero, and count the rows positive upward, negative downward, and the columns positive to the right and negative to the left, as in Cartesian coordinates.

The diagonal up and to the left from the origin contains the squares of successive even numbers. The numbers in the rows above the origin to the right of this diagonal and to the left of the major diagonal can be obtained by subtracting from the appropriate square in this row. That is (2r)^2-r-c, where r and c are the row and column as defined above.

The numbers to the left of the origin from the above diagonal of squares down to the major diagonal can be obtained by adding an appropriate amount to the square numbers: (2c)^2-r-c

To the lower right of the 1 that's to the right of the zero origin, there is another diagonal, containing the squares of successive odd natural numbers. The other wedges (right hand and bottom) are calculated similarly, but the offset of 1 column has to be accounted for, and the numbers get higher with higher rows, and less for leftward columns. The adjustment was done in the below program by trying them out and fixing as necessary:

DO
  INPUT "n=", n

  c1 = -INT((n - 1) / 2)
  c2 = INT(n / 2)
  FOR row = INT(n / 2) TO -INT((n - 1) / 2) STEP -1
    FOR col = c1 TO c2
     
      IF row >= col THEN
        IF row >= -col THEN
            v = 4 * row * row - row - col
        ELSE
            v = 4 * col * col - row - col
        END IF
      ELSEIF row <= -col THEN
        v = 4 * row * row - 4 * row + col + row
      ELSE
        v = 4 * (1 - col) * (1 - col) - 4 * (1 - col) + row + col
      END IF
     
      PRINT USING \\\"####\\\"; v;

    NEXT
    PRINT
  NEXT
LOOP

samples are:

n=4
15 14 13 12
4 3 2 11
5 0 1 10
6 7 8 9
n=5
16 15 14 13 12
17 4 3 2 11
18 5 0 1 10
19 6 7 8 9
20 21 22 23 24
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
n=11
100 99 98 97 96 95 94 93 92 91 90
101 64 63 62 61 60 59 58 57 56 89
102 65 36 35 34 33 32 31 30 55 88
103 66 37 16 15 14 13 12 29 54 87
104 67 38 17 4 3 2 11 28 53 86
105 68 39 18 5 0 1 10 27 52 85
106 69 40 19 6 7 8 9 26 51 84
107 70 41 20 21 22 23 24 25 50 83
108 71 42 43 44 45 46 47 48 49 82
109 72 73 74 75 76 77 78 79 80 81
110 111 112 113 114 115 116 117 118 119 120

--------
-----------


Edited on August 26, 2003, 12:31 am
Edited on August 26, 2003, 12:32 am
  Posted by Charlie on 2003-08-21 16:36:43
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


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

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