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.

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.

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

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