Overcoming heap overflow issues

Question

I tried to solve problems from Project Euler. I know my method would work logically (it returns answers to the small scale problem almost instantly). However, it scales horribly. I already attempted changing the .ini file, but to no avail.

Here's my code:

public class Number28 {

    static int SIZE = 101; //this should be an odd number, i accidentally posted 100
    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        long spiral[][]= new long[size][size];
        if(size == 1){
            spiral[0][0] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= new long[size - 2][size - 2];
            subspiral = spiral(size - 2);
            for(int r = 0; r < size - 2; r++){
                for(int c = 0; c < size - 2; c++){
                    spiral[r + 1][c + 1] = subspiral[r][c];
                }
            }
            long counter = subspiral[0][size - 3];
            for(int r = 1; r < size ; r++){
                counter++;
                spiral[r][size - 1] = counter;
            }
            for(int c = size - 2; c >= 0; c--){
                counter++;
                spiral[size - 1][c] = counter;
            }
            for(int r = size - 2 ; r >= 0 ; r--){
                counter++;
                spiral[r][0] = counter;
            }
            for(int c = 1; c < size ; c++){
                counter++;
                spiral[0][c] = counter;
            }

            return spiral;
        }
    }
}

Here's the edited code, worked like a gem:

public class Number28 {
    static int SIZE = 1001;
    static long spiral[][]= new long[SIZE][SIZE];

    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        if(size == 1){
            spiral[SIZE / 2][SIZE / 2] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= spiral(size - 2);
            int edge = (SIZE - size) / 2;
            long counter = subspiral[edge + 1][edge + size - 2];

              for(int r = 1; r < size ; r++){
                  counter++;
                  spiral[edge + r][edge + size - 1] = counter;
          }
          for(int c = size - 2; c >= 0; c--){
                  counter++;
                  spiral[edge + size - 1][edge + c] = counter;
          }
          for(int r = size - 2 ; r >= 0 ; r--){
                  counter++;
                  spiral[edge + r][edge] = counter;
          }
          for(int c = 1; c < size ; c++){
                  counter++;
                  spiral[edge][edge + c] = counter;
          }
            return spiral;
        }
    }
}

Answer 1

Here is a simplified solution that doesn't store a matrix:

public class P28 {

    private final static int N = 1001;

    public static void main(String[] args) {

        int limit = (N + 1) / 2;
        int sum = -3;
        int first = 4;
        int r = 20;
        for (int i = 1; i <= limit; i++) {
            sum += first;
            first += r;
            r += 32;
        }
        System.out.println(sum);
    }

}

Explanation:

Starting from 1 you can see 4 sums:

• 1 + 3 + 13 + 31 + 57 + ...
• 1 + 5 + 17 + 37 + 65 + ...
• 1 + 7 + 21 + 43 + 73 + ...
• 1 + 9 + 25 + 49 + 81 + ...

1 is added 4 times, this is why the default value for sum is -3.

Let's gather those sums:

• 4 + 24 + 76 + 160 + 276 + ... (this is why first is 4 and r is 20 = 24 - 4)

You can observe that r increases by 32 per step ( 24 - 4 = 32 + 76 - 24 = 32 + 32 + 160 - 76 = ... ) and the actual number (first) increases by r.

Answer 2

The first problem I saw was a NegativeArraySizeException when running your program with SIZE = 100. I guess this has something to do with how each recursive call is decreasing the size by 2.

I believe that Steven's comment is right on the money. You are allocating the size of the array, them making a recursive call. This causes (SIZE - 1) number of arrays to be allocating, eating up all of your memory. Removing that one line should prevent any memory from being allocated until necessary.

Answer 3

Not familiar with the Euler problems, but the horror appears to be your continual allocation and re-allocation of what are basically throwaway intermediate spirals, as you call down recursively to the base case.

Restructure so that you allocate your full spiral up front. Then call your recursive function, passing your full spiral in as a parameter by reference, along with a "level" parameter, which will change with each recursive call. E.g., initial call is with 100x100 spiral and level 100; next (recursive) call is with same spiral, by reference, and level 98. Operations within the function will all be done on the one-and-only-allocated spiral.

In a nutshell: allocate your data structure once, even if you operate on that data structure recursively.

Answer 4

As a general piece of Project Euler advice, if your solution doesn't scale, there's almost certainly a better way to solve it. If you've used the same type of solution on an earlier problem you can go through the posts from other users on the earlier question to get ideas for solving the problem in different ways.