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

  Submitted by DJ    
Rating: 4.4167 (12 votes)
Solution: (Hide)
I did this by numbering the rows going down and the columns across, from 0 to n-1.
The square can be divided into four sections along the diagonals.
Also, the NW-SE diagonals are composed of perfect squares, if you include the n² term 'hidden' to the left of (0, 0).

Without going into much detail, I used these squares and the offsets along each row or column to come up with four if statements to define the value in terms of r and c.

Here a small C++ program, that takes as input the value for n, then loops through to draw the spiral for that n:

#include <iostream>
#include <iomanip>
using namespace std;
void main() {
   int n, r, c, x;
   cout << "n=";
   cin >> n;
   cout << endl;
   for (r=0; r<n; r++) {
      for (c=0; c<n; c++) {
         if ((c-r>=-1) && (c+r+1<=n))
            x=(n-2*r)*(n-2*r)-1-c+r;
         else if ((c-r>-1) && (c+r+1>n))
            x=(2*c-n+1)*(2*c-n+1)+c-r;
         else if ((c-r<=-1) && (c+r+1>=n))
            x=(2*r-n+1)*(2*r-n+1)+c-r;
         else
            x=(n-2*c-2)*(n-2*c-2)-1-c+r;
         cout << setw(n<11 ? 3 : 4) << x;
      }
      cout << endl;
   }
}
Some sample outputs:
n=5

 24 23 22 21 20
  9  8  7  6 19
 10  1  0  5 18
 11  2  3  4 17
 12 13 14 15 16

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=15

 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210
 169 168 167 166 165 164 163 162 161 160 159 158 157 156 209
 170 121 120 119 118 117 116 115 114 113 112 111 110 155 208
 171 122  81  80  79  78  77  76  75  74  73  72 109 154 207
 172 123  82  49  48  47  46  45  44  43  42  71 108 153 206
 173 124  83  50  25  24  23  22  21  20  41  70 107 152 205
 174 125  84  51  26   9   8   7   6  19  40  69 106 151 204
 175 126  85  52  27  10   1   0   5  18  39  68 105 150 203
 176 127  86  53  28  11   2   3   4  17  38  67 104 149 202
 177 128  87  54  29  12  13  14  15  16  37  66 103 148 201
 178 129  88  55  30  31  32  33  34  35  36  65 102 147 200
 179 130  89  56  57  58  59  60  61  62  63  64 101 146 199
 180 131  90  91  92  93  94  95  96  97  98  99 100 145 198
 181 132 133 134 135 136 137 138 139 140 141 142 143 144 197
 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
Also, Your Buddy and Charlie offered alternate algorithms in the problem comments.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
SolutionAnother solution!!phenomenon2004-02-21 02:53:41
SolutionRecursiveAJ2003-09-05 01:02:47
NeatAdam Sisco2003-08-23 10:13:16
re(3): solutionYour buddy2003-08-21 17:28:26
re(2): solutionCharlie2003-08-21 16:54:31
re(2): FULL SOLUTION (in C)Charlie2003-08-21 16:51:49
re: solutionCharlie2003-08-21 16:39:35
SolutionsolutionCharlie2003-08-21 16:36:43
Solutionre: FULL SOLUTION (in C)Your buddy2003-08-21 15:55:56
SolutionFULL SOLUTION (in C)Your buddy2003-08-21 15:50:00
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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