Making number spirals

• August 18th, 2012, 01:13 PM
aesguitar
Making number spirals
I was working on a problem that involves making number spirals with the middle as 1 and values getting larger clockwise withing the spiral.

Code :

```7 8 9   6 1 2   5 4 3```

I either need a faster method of creating a spiral or some way to make an existing spiral larger. The second way is preferred, however, I can't figure out a way to do it. Here is the code for creating the spirals and a way to print them out:

Code java:

```public static int[][] spiral(int max) throws IllegalArgumentException { int use = (int) Math.sqrt(max);//the size of the array int counter = max;//counter to count down from the max int x = use-1; int y = 0; int left = use; int right = use-1; int up = use-2; int down = use - 1;   if(max%use!=0||max%2==0) throw new IllegalArgumentException("Illegal input. Input must be the square of an odd number.");       spiral = new int[use][use];     while(counter > 0) { for(int i = left; i > 0; i--) { spiral[y][x] = counter; counter--; x--; } left-=2; y++; x++; for(int i = down; i > 0; i--) { spiral[y][x]=counter; counter--; y++; } down-=2; y--; x++; for(int i = right; i > 0; i--) { spiral[y][x]=counter; counter--; x++; } right-=2; y--; x--; for(int i = up; i > 0; i--) { spiral[y][x]=counter; counter--; y--; } up-=2; y++; x--; }   return spiral;   } public static String toString(int[][] sp) { String spiral = ""; for(int i = 0; i <sp.length; i++) { for(int j = 0; j < sp.length; j++) { if(sp[i][j]>=100) spiral+=(sp[i][j]+" "); else if(sp[i][j]>=10) spiral+=(" " + sp[i][j] + " "); else spiral+=(" " + sp[i][j] + " "); } spiral+="\n"; } return spiral; }```
• August 18th, 2012, 06:24 PM
pbrockway2
Re: Making number spirals
Is this a homework problem? If so it's best to state that upfront: In part because the statement of the program helps say what help would be most beneficial, and in part because most would prefer to help without giving the game away. (ie take away the fun)

-----

If I were dealing with a huge number spiral I think I would start with the recognition that there's not much "state" to it: just the width of the square. Once you know the width of the square all the rest just follows. So my class would look like

Code :

```class NumberSpiral { private int size;   NumberSpiral(int size) { this.size = size; } /** Returns the number at a given row and column. */ int get(int row, int col) { // code here }   /** Prints some or all of the sprial. */ void print(int topRow, int leftCol, int width, int height) { // code here }   // etc }```

If you follow this approach (not necessarily the most "efficient") the get() method is pivotal. Everything else useful follows from this calculation. Implementing it is a matter of playing "spot the pattern" - ie seeing what value the spiral has given a certain displacement from the all important middle position.
• August 18th, 2012, 08:44 PM
aesguitar
Re: Making number spirals
No, I'm not doing this as homework. It's Project Euler problem 58. I was trying to speed up the code a bit, I wasn't going to wait 10 minutes to find the solution. Naturally, I thought that there is probably a more efficient way to do it, so I started with the spiral creation algorithm. So far, I have made some modifications to other parts of the algorithm like prime checking. I'd like to see a way of taking a 2-d array, make it bigger (3x3 to 5x5 for example) and expanding the spiral to fit its new array. That's more of what I need.
• August 18th, 2012, 11:37 PM
Zaphod_b
Re: Making number spirals
Quote:

Originally Posted by aesguitar
...a more efficient way to do it...

Well, for starters, you are only going to test elements on the diagonal and antidiagonal for primality, so why bother to wrap yourself around in circles generating entire arrays? Just look at the corners.

The key, to me, would be to spot the pattern in corner elements as you increase the size. Write out some arrays (pencil and paper might even be OK for the first few) and look at the corners.
Here are some corner values, starting with the 3 x 3 array:
Code :

```Size = 3 x 3: Corners: 3 5 7 9 Size = 5 x 5: Corners: 13 17 21 25 Size = 7 x 7: Corners: 31 37 43 49 Size = 9 x 9: Corners: 57 65 73 81 Size = 11 x 11: Corners: 91 101 111 121 Size = 13 x 13: Corners: 133 145 157 169 Size = 15 x 15: Corners: 183 197 211 225 Size = 17 x 17: Corners: 241 257 273 289 Size = 19 x 19: Corners: 307 325 343 361 Size = 21 x 21: Corners: 381 401 421 441 Size = 23 x 23: Corners: 463 485 507 529 Size = 25 x 25: Corners: 553 577 601 625 Size = 27 x 27: Corners: 651 677 703 729 Size = 29 x 29: Corners: 757 785 813 841 Size = 31 x 31: Corners: 871 901 931 961 . . .```

.

See how it goes? The last one in the lists that I showed for each NxN array is just N-squared, right? I mean, you already glommed onto that, right?. So, instead of all of that up-down-left-right stuff, just calculate the other corners by working back from there for each one.

So...

The actual "formulas" for finding corners is quite simple, but of course your prime number checker still should be efficient since that's where the program will be spending most of its time.

Cheers!

Z
• August 19th, 2012, 02:05 PM
Zaphod_b
Re: Making number spirals
Quote:

Originally Posted by Zaphod_b
Well, for starters, you are only going to test elements on the diagonal and antidiagonal for primality, so why bother to wrap yourself around in circles generating entire arrays? Just look at the corners....

On the other hand, if you have some reason to actually generate the spirals incrementally, you could try something like
Code java:

``` // //Direction of the result is clockwise out from the center. // public static int [][] nextCWSpiral(int [][] oldSpiral) throws IllegalArgumentException { int oldsiz = oldSpiral.length; if (oldsiz < 1) { throw new IllegalArgumentException("Illegal input. Old spiral must have size > 0."); }   // Length of rows and columns of new array = oldlengths+2 int newsiz = oldsiz + 2;   // A brand new array int [][] newSpiral = new int[newsiz][newsiz];   // Just for the heck of it make sure no one throws something // at it that won't mean anything. for (int i = 0; i < oldSpiral.length; i++) { if (oldSpiral[i].length != oldsiz) { throw new IllegalArgumentException("Illegal input. Old spiral must be square."); } } // // Write values into new top row: Upper right is length squared, // and that is the largest element of the new array. Working // to the left from there means that the next result will // spiral out from the center in a clockwise direction. // int newValue = newsiz*newsiz;   // Here: I'll do this one. You can do the rest for (int j = newsiz-1; j >= 0; j--) { newSpiral[0][j] = newValue--; }   // Create first column below upper left element for (int i = whatever; condition; i++) { newSpiral[i][0] = newValue--; } // Create bottom row to the right of lower left element for (int j = whatever; condition; j++) { newSpiral[newsiz-1][j] = newValue--; } // Create last column between lower right and upper right elements for (int i = whatever; condition; i--) { newSpiral[i][newsiz-1] = newValue--; }   // Now copy old array to the inner cells of the new for (int i = whatever; condition; i++) { for (int j = whatever; condition; j++) { newSpiral[i][j] = oldSpiral[i-1][j-1]; } } return newSpiral; }```

Then with something like the following in main():
Code java:

``` public static void main(String [] args) { // // Maybe you want to try your old stuff here, for comparison // int [][] array = {{1}}; // A new 1x1 array with array[0][0] = 1   System.out.println("Starting with manually generated array."); System.out.printf("%d x %d:\n", 1, 1); System.out.println(toString(array)); // // Note that i is not used by the function; it's just for reference. // // Starting with 1x1 array whose element value is 1, // each application of the function gives another "layer" of // the spiral array. System.out.println("Loop calls nextCWSpiral() repeatedly...\n"); for (int i = 3; i < 9; i+= 2) { array = nextCWSpiral(array); System.out.printf("%d x %d:\n", i, i); System.out.println(toString(array)); } }```

Output, if implemented with correct values for the "whatevers" and "conditions" in the nextCWSpiral function:
Code :

```Starting with manually generated array. 1 x 1: 1   Loop calls nextCWSpiral() repeatedly...   3 x 3: 7 8 9 6 1 2 5 4 3   5 x 5: 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13   7 x 7: 43 44 45 46 47 48 49 42 21 22 23 24 25 26 41 20 7 8 9 10 27 40 19 6 1 2 11 28 39 18 5 4 3 12 29 38 17 16 15 14 13 30 37 36 35 34 33 32 31```

Of course, if your interest is only in Euler 58, you don't need all of the iterations of the array itself, since you are only going to check the new corner values each time and add the number of primes to a running total. (But I said that already.)

In fact, the Project Euler problem statement shows an array that spirals counterclockwise out from the center with the largest element in the lower right corner of the array instead of the way that your example (and my code, which was based on your example) shows. That would be just as easy if you really wanted it However (and I hate to repeat myself, yet again) the number of primes on the diagonals depends only on the corner values of each new array as you generate it, so the Euler answer would be the same.

Cheers!

Z