CODEWITHSUNDEEP
java
Niklas Torwald
Niklas Torwald

Reputation: 41

Project Euler #11 java. Not getting the right answer

I have some problems with Problem 11 on Project Euler. I manage to get an answer, but it's not the right one. I'm getting 51267216. This is found by the greatestVert method. I think the problem is located in the greatestDiaglonal method, but I'm not quite sure. Can somebody check if my algorithm is correct?

The task is to find out what the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) is in the 20x20 grid.

package euler;

public class Problem11 {

int num1, num2, num3, num4;
int highestNum1, highestNum2, highestNum3, highestNum4;

private int sum = 0;

String[] l = {
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08",
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00",
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65",
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91",
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80",
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50",
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70",
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21",
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72",
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95",
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92",
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57",
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58",
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40",
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66",
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69",
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36",
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16",
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54",
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"
};

int greatestSide() {
    for(int i = 0;i<=19;i++) {
        for(int n = 0;n<=l[i].length()-12;n+=3) {
            num1 = Integer.parseInt(l[i].substring(0+n,3+n).trim());
            num2 = Integer.parseInt(l[i].substring(3+n,6+n).trim());
            num3 = Integer.parseInt(l[i].substring(6+n,9+n).trim());
            num4 = Integer.parseInt(l[i].substring(9+n,12+n).trim());

            if(num1*num2*num3*num4 > sum) {
                sum = num1*num2*num3*num4;
                highestNum1 = num1;
                highestNum2 = num2;
                highestNum3 = num3;
                highestNum4 = num4;
            }   
        }
    }
    return sum;
}

int greatestVert() {
    for(int i = 0; i<=16; i++) {
        for(int n = 0; n<=l[i].length()-3; n+=3) {
            num1 = Integer.parseInt(l[i].substring(0+n,3+n).trim());
            num2 = Integer.parseInt(l[i+1].substring(0+n,3+n).trim());
            num3 = Integer.parseInt(l[i+2].substring(0+n,3+n).trim());
            num4 = Integer.parseInt(l[i+3].substring(0+n,3+n).trim());

            if(num1*num2*num3*num4 > sum) {
                sum = num1*num2*num3*num4;
                highestNum1 = num1;
                highestNum2 = num2;
                highestNum3 = num3;
                highestNum4 = num4;
            }   
        }
    }
    return sum;
}

int greatestDiagonal() {
    for(int i = 19; i>=3; i--) {
        for(int n = 0; n<=l[i].length()-12; n+=3) {
            num4 = Integer.parseInt(l[i].substring(9+n,12+n).trim());
            num3 = Integer.parseInt(l[i-1].substring(6+n,9+n).trim());
            num2 = Integer.parseInt(l[i-2].substring(3+n,6+n).trim());
            num1 = Integer.parseInt(l[i-3].substring(0+n,3+n).trim());

            if(num1*num2*num3*num4 > sum) {
                sum = num1*num2*num3*num4;
                highestNum1 = num1;
                highestNum2 = num2;
                highestNum3 = num3;
                highestNum4 = num4;
            }   
        }
    }

    for(int i = 0; i>=16; i++) {
        for(int n = 0; n<=l[i].length()-12; n+=3) {
            num4 = Integer.parseInt(l[i].substring(9+n,12+n).trim());
            num3 = Integer.parseInt(l[i+1].substring(6+n,9+n).trim());
            num2 = Integer.parseInt(l[i+2].substring(3+n,6+n).trim());
            num1 = Integer.parseInt(l[i+3].substring(0+n,3+n).trim());

            if(num1*num2*num3*num4 > sum) {
                sum = num1*num2*num3*num4;
                highestNum1 = num1;
                highestNum2 = num2;
                highestNum3 = num3;
                highestNum4 = num4;
            }   
        }
    }
    return sum;
}

public static void main(String[] args) {
    Problem11 prog = new Problem11();

    prog.greatestSide();
    prog.greatestVert();
    prog.greatestDiagonal();
    System.out.println(prog.sum);
    System.out.println(prog.highestNum1);
    System.out.println(prog.highestNum2);
    System.out.println(prog.highestNum3);
    System.out.println(prog.highestNum4);
}
}

Upvotes: 2

Views: 1435

Answers (2)

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56666

Here is another solution that firstly converts the String to a 2D array:

public class P11 {

    public static void main(String[] args) throws Exception {
        String input = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
        int n = 20;
        int a[][] = getMatrixOfIntegers(input, n);
        System.out.println(maxProduct(a));
    }

    private static long maxProduct(int a[][]) {
        int size = a.length - 4;
        int l = a.length - 1;
        long pMax = 1;
        for ( int i = 0 ; i < size ; i++ ) {
            for ( int j = 0 ; j < size ; j++ ) {
                int prodDiag1 = a[i][j]*a[i+1][j+1]*a[i+2][j+2]*a[i+3][j+3];
                if ( pMax < prodDiag1 ) {
                    pMax = prodDiag1;
                }
                int prodCol = a[i][j]*a[i+1][j]*a[i+2][j]*a[i+3][j];
                if ( pMax < prodCol ) {
                    pMax = prodCol;
                }
                int prodRow = a[i][j]*a[i][j+1]*a[i][j+2]*a[i][j+3];
                if ( pMax < prodRow ) {
                    pMax = prodRow;
                }
                int prodDiag2 = a[i][l-j]*a[i+1][l-j-1]*a[i+2][l-j-2]*a[i+3][l-j-3];
                if ( pMax < prodDiag2 ) {
                    pMax = prodDiag2;
                }               
            }
        }
        return pMax;
    }

    private static int[][] getMatrixOfIntegers(String input, int n) {
        String m[] = input.split(" ");
        int a[][] = new int[n][n];      
        for ( int i = 0 ; i < n*n ; i++ ) {
            a[i/n][i%n] = Integer.parseInt(m[i]);
        }
        return a;
    }

}

Time for maxProduct: 0.2 ms

Upvotes: 0

Daniel Fischer
Daniel Fischer

Reputation: 183888

You are omitting to scan one direction of diagonals:

for(int i = 0; i>=16; i++) {

doesn't run at all. You meant i <= 16 there.

Upvotes: 1

Related Questions