Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Making number spirals

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Question 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.

    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:

    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;
    	}


  2. #2
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default 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

    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.

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default 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.

  4. #4
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Making number spirals

    Quote Originally Posted by aesguitar View Post
    ...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:
    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
    Last edited by Zaphod_b; August 19th, 2012 at 12:16 AM.

  5. #5
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Making number spirals

    Quote Originally Posted by Zaphod_b View Post
    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
        //
        //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():
        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:
    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
    Last edited by Zaphod_b; August 19th, 2012 at 02:37 PM.

Similar Threads

  1. How To Ask the User to Enter Another Number Using the Number 1
    By Pettsa in forum Object Oriented Programming
    Replies: 6
    Last Post: May 3rd, 2012, 03:44 AM
  2. How to returned random number to original number?
    By i4ba1 in forum Algorithms & Recursion
    Replies: 2
    Last Post: March 19th, 2011, 04:35 AM
  3. [SOLVED] Help making a loop please
    By CheekySpoon in forum Loops & Control Statements
    Replies: 10
    Last Post: February 5th, 2011, 08:23 PM
  4. about making .class into .jar
    By sibbe in forum Java Theory & Questions
    Replies: 7
    Last Post: November 13th, 2010, 01:50 PM
  5. Digital map application with Java GUI
    By donjuan in forum AWT / Java Swing
    Replies: 3
    Last Post: May 15th, 2009, 03:32 AM