The Mystery Spiral
First Things first. There is no “mystery” behind this spiral. (as in NO HIDDEN MYSTERY MSGS etc.) The “mystery” part is the fact that the solution (C-code) has eluded me all these years.
>>FLASHBACK (Sometime around FEB 2006)…
I was first posed this problem by a senior friend of mine. Then i was in my 2nd Semester of B.E and knee-deep into C. I just casually glanced at it and thought it too easy and forgot all about it in no time. I mean after all its just printing numbers in a properly formatted way. How tough could it be after all!!…
And boy, was i more wrong!!
>>Now FAST-FORWARD to MAR-2010…
I recently saw this problem posed in an online C-forum. What amazed me was that no-one had posted any solution. People had tackled more intriguing problems and founds very elegant solutions. I kept wondering was it unsolvable?… or maybe not interesting enough… or was there no elegant solution to it at all…
And thus began my 8 hour ordeal in tackling this problem.
( …hey i got a solution, didn’t I… 🙂 🙂 )
The Mystery Spiral :
Write a program that accepts a integer N
and displays a “spiral” of NxN numbers.
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 04 03 02 11 28 53 86
68 39 18 05 00 01 10 27 52 85
69 40 19 06 07 08 09 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
Here’s another example spiral for N=3:
8 7 6
1 0 5
2 3 4
The aim is to print no.s in the following order:-
“Starting from the Green square and continuing in a spiral manner to the center of the NxN matrix and finishing at the RED square”.NOTE: The Spiral shown is for odd NxN matrix. In case N is an even number, the spiral would look slightly different with no single “Central-square”.
UPDATE :
People who solved the Puzzle.Checkout the Hall-of-FAME.
THE MYSTERY SPIRAL SOLVED
https://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/
Algorithm:
1. Set the starting number Num = Square(N) – 1
2. For a Spiral of NxN matrix, there will be ceil(N/2) number of enclosing squares; one inside another and the top-left number of each such internal square will be a perfect square number.
3. The only problem would be to fill the numbers along each row after each enclosing-square length ends, which needs a bit complicated method. Here, for each internal square, say of size m=N-2, we would compute the element as 2(m+1)+2m to trace back the exceeding element of the internal square on that row. Repeat this until m=N by incrementing each time. This would fill the entire row.
4. Repeat the above steps 2 and 3, by decrementing until the row number turns zero.
Manjunath said this on Tue, 23 Mar, 2010 at 2:06 PM |
Good Observation about the top-left corner elements being perfect squares.
(or maybe PerfectSquares – 1 in this case; 99,63,35 etc.)
That makes a very good place to start indeed. 🙂
hey but i couldn’t follow STEP3.
do u hav a code-snippet that illustrates it maybe…
cvs268 said this on Tue, 23 Mar, 2010 at 4:24 PM |
Prashant D Bloggleminds.co.cc
My code Speaks For Itself 😉
#include “stdio.h”
#include “conio.h”
#define rows 8
#define cols 8
int mystery(int,int);
int i,j;
int row=rows;
int col=cols;
int count=row*col;
int num=row*col-1;
int matrix[rows][cols], spiral[rows][cols];
int no=row*col;
int r=1,c=0;
int row_count=row;
int col_count=col;
int a=1,b=1;
int num1=num;
int main()
{
do{
mystery(1,col_count);
mystery(2,row_count);
mystery(3,col_count);
mystery(4,row_count);
}while(count!=0);
for(i=1;i<=row;i++)
{
for(j=1;j<=col;j++)
printf("%d\t",spiral[i][j]);
printf("\n");
}
getchar();
return 0;
}
int mystery(int x,int n)
{
switch(x)
{
case 1: for(i=1;i<=n;i++)
{
// printf("11\t");
spiral[r][++c]=num1–;//matrix[a++][b++];
count–;
}
// printf("\n");
row_count–;
break;
case 2: for(i=1;i<=n;i++)
{
// printf("22\t");
spiral[++r][c]=num1–;
count–;}
printf("\n");
col_count–;
break;
case 3: for(i=1;i<=n;i++)
{
// printf("33\t");
spiral[r][–c]=num1–;//matrix[a++][b++];
count–;
}
printf("\n");
row_count–;
break;
case 4:for(i=1;i<=n;i++)
{
// printf("44\t");
spiral[–r][c]=num1–;//matrix[a++][b++];
count–;
}
printf("\n");
col_count–;
break;
default: return 0;
}
return 0;
}
Prashanth said this on Tue, 23 Mar, 2010 at 8:30 PM |
http://codepad.org/L0c3HgKv
This will print line-by-line without storing anything.
#include
void printRow(int N, int row)
{
int Nsquared = N*N;
if (N==0) return;
if (row == 0)
{
int i;
for (i=0; i<N; ++i)
{
printf("%4d", Nsquared-i-1);
}
}
else if (row == N-1)
{
int i;
for (i=0; i<N; ++i)
{
printf("%4d", Nsquared-3*(N-1)+i-1);
}
}
else
{
printf("%4d", Nsquared-4*(N-1)+row-1);
printRow(N-2, row-1);
printf("%4d", Nsquared-(N-1)-row-1);
}
}
int main()
{
int N = 10;
int row;
for (row=0; row<N; ++row)
{
printRow(N, row);
printf("\n");
}
return 0;
}
Aeth said this on Sat, 17 Apr, 2010 at 7:22 PM |
Here is almost the same thing used as D1 easy: http://www.topcoder.com/stat?c=problem_statement&pm=6093 so it requires nowhere near 8 hours to solve 🙂
Ps. This is not the correct forum for posting this, try Educational discussion next time.
From Topcoder said this on Mon, 03 May, 2010 at 4:19 PM |
Sure. Thank You.
CVS268 said this on Mon, 03 May, 2010 at 5:10 PM |