Project Euler #11

Question

I recently started these projects to test my skills with Java. I got to problem 11, getting all the previous ones right. There is something wrong with my code. The answer that is returned seems to be correct, but it isn't when I check it on the official website: The problem is at Project Euler #11.

Here is my code. I have several commented out debugging lines. Just ignore them.

static String source = "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";
//  static String source = "02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00";
static int[] numList = new int[400];
static int answer;

public static void main(String args[]){
    int counter = 1;
    int numListCounter = 0;
    //convert source to array
    for(int x = 0; x < source.length(); x++){
        char[] c = new char[2];
        String s;

        if(counter == 1){
            c[0] = source.charAt(x);
            c[1] = source.charAt(x+1);
            s = new String(c,0,2);
            numList[numListCounter] = Integer.parseInt(s);
        }
        if(counter == 3){
            numListCounter++;
            counter = 0;
        }
        counter++;
    }
    //convert array to grid
    int[][] grid = new int[20][20];
    int c = 0;
    for(int x = 0; x < 20; x++){
        for(int y = 0; y < 20; y++){

            grid[y][x] = numList[c];
            c++;
        }
    }

    //Prints the array. used for testing.
    /*
    for(int y = 0; y < 20; y++){
        for(int x = 0; x < 16; x++){
            System.out.print(grid[x][y] + "\t");
        }
        System.out.println();
    }
    */

    //check horizontal
    int hAnswer = 0;
    for(int y = 0; y < 20; y++){
        for(int x = 0; x < 16; x++){
            if(grid[x][y]*grid[x+1][y]*grid[x+2][y]*grid[x+3][y] > hAnswer){

                hAnswer = grid[x][y]*grid[x+1][y]*grid[x+2][y]*grid[x+3][y];

                //  System.out.println(x + " , " + y);
                //  System.out.println(answer);
            }
        }
    }
    if(hAnswer > answer){
        answer = hAnswer;
    }
    System.out.println(hAnswer + " - Horizontal Answer");

    //check vertical
    int vAnswer = 0;
    for(int x = 0; x < 20; x++){
        for(int y = 0; y < 16; y++){
            if(grid[x][y]*grid[x][y+1]*grid[x][y+2]*grid[x][y+3] > vAnswer){

                vAnswer = grid[x][y]*grid[x][y+1]*grid[x][y+2]*grid[x][y+3];

        //      System.out.println(x + " , " + y);
        //      System.out.println(answer); 
            }
        }
    }
    if(vAnswer > answer){
        answer = vAnswer;
    }
    System.out.println(vAnswer + " - Vertical Answer");

    //check diagonal \
    int d1answer = 0;
    for(int y = 0; y < 16; y++){
        for(int x = 0; x < 16; x++){
            if(grid[x][y]*grid[x+1][y+1]*grid[x+2][y+2]*grid[x+3][y+3] > d1answer){

                d1answer = grid[x][y]*grid[x+1][y+1]*grid[x+2][y+2]*grid[x+3][y+3];

        //      System.out.println(x + " , " + y);
        //      System.out.println(answer);

            }
        }
    }

    if(d1answer > answer){
        answer = d1answer;
    }

    System.out.println(d1answer + " - Diagonal \"\\\" Answer");

    //check diagonal /
    int d2answer = 0;
    for(int y = 3; y < 20; y++){
        for(int x = 3; x < 20; x++){
            if(grid[x][y]*grid[x-1][y-1]*grid[x-2][y-2]*grid[x-3][y-3] > d2answer){

                d2answer = grid[x][y]*grid[x-1][y-1]*grid[x-2][y-2]*grid[x-3][y-3];

        //      System.out.println(x + " , " + y);
        //      System.out.println(answer);
            }
        }
    }
    if(d2answer > answer){
        answer = d2answer;
    }

System.out.println(d2answer + " - Diagonal \"/\" Answer");
System.out.println();
System.out.println(answer + " - Final Answer");
}

This is compile-able if put into a class. I just don't know why it is wrong.

Output:

48477312 - Horizontal Answer
51267216 - Vertical Answer
32719995 - Diagonal "\" Answer
40304286 - Diagonal "/" Answer

51267216 - Final Answer

Answer 1

def LI(): return list(map(int, input().split()))


def horizontal(row,col,a):
    if col <= len(a[0])-4:
        return a[row][col] * a[row][col+1] * a[row][col+2] * a[row][col+3]
    else:
        return 0
def vertical(row,col,a):
    if row <= len(a)-4:
        return a[row][col] * a[row+1][col] * a[row+2][col] * a[row+3][col]
    else:
        return 0
def rd(row,col,a):
    if col <= len(a[0])-4 and row <= len(a)-4:
        ans = 1
        ans *= a[row][col]
        ans *= a[row+1][col+1]
        ans *= a[row+2][col+2]
        ans *= a[row+3][col+3]
        return ans
    else:
        return 0
def ld(row,col,a):
    if col >=3 and row <= len(a)-4:
        ans = 1
        ans *= a[row][col]
        ans *= a[row+1][col-1]
        ans *= a[row+2][col-2]
        ans *= a[row+3][col-3]
        return ans
    else:
        return 0

def main(a):
    maxi = 0
    for row in range(len(a)):
        for col in range(len(a[0])):
            maxi = max(maxi,horizontal(row,col,a))
            maxi = max(maxi,vertical(row,col,a))
            #diagonally right:
            maxi = max(maxi,rd(row,col,a))
            #diagonally left:
            maxi = max(maxi,ld(row,col,a))
    return maxi
a = []
for i in range(20):
    a.append(LI())
print(main(a))

Answer 2

You should use integer array, there are too many type castings in your implementation, also it's much easier to work with array indexes.

I wrote a simple code(in javascript tho) with O(n) complexity using one dimensional array.

var 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];
var start = Date.now();
var max = 0;
var row = 0;
var rowIndex = 0;
for (var i = 0; i < input.length - 3; i++) {
    var tmpProd;
    if(rowIndex < 17) {
        tmpProd = input[i] * input[i+1] * input[i+2] * input[i+3];
        if(tmpProd > max) max = tmpProd;
    }
    if(row < 17) {
        tmpProd = input[i] * input[i+20] * input[i+40] * input[i+60];
        if(tmpProd > max) max = tmpProd;
    }
    if(rowIndex < 17 && row < 17) {
        tmpProd = input[i] * input[i+21] * input[i+42] * input[i+63];
        if(tmpProd > max) max = tmpProd;
    }
    if(rowIndex > 2 && row < 17) {
        tmpProd = input[i] * input[i+19] * input[i+38] * input[i+57];
        if(tmpProd > max) max = tmpProd;
    }
    if(rowIndex < 17 && row > 2) {
        tmpProd = input[i] * input[i-19] * input[i-38] * input[i-57];
        if(tmpProd > max) max = tmpProd;
    }
    if(rowIndex == 19) {
        rowIndex = 0;
        row++;
    } else {
        rowIndex++;
    }
}
console.log('time: ', Date.now() - start);
console.log('max: ', max);

When writing your code you should always have in mind it's complexity and time needed for it's execution. With little code optimization you can improve your solution for several seconds.

Cheers.

Answer 3

Your / diagonal calculation is wrong i guess .. I have solved it in java :

for (i = 0; i < 17; i++) {
    for (j = 3; j < 20; j++) {
      product.add(twoDArray[i][j] * twoDArray[i + 1][j - 1] * twoDArray[i + 2][j - 2] *   twoDArray[i + 3][j - 3]);
        }
    }

Answer 4

I think what is wrong with your code is that you are trying to use strings. Try re-writing it using a 3d array. My solution has about 14 lines of code.

public class P11 {

int max, digits;
int[][] grid = {

P11() {
    max = 0;
    digits = 4;
}

public void run() {
    for (int i=0; i<grid.length-digits+1; i++)
        for (int j=0; j<grid.length-digits+1; j++) {
            //iterate through the grid          }
    System.out.println(max);

}

private int getMaxProduct(int xIndex, int yIndex) {
    int p1=1, p2=1, p3=1, p4=1;
    for (int i=0; i<digits; i++) {
        ///find all the products        }
    return //maximum product    }

Answer 5

You are checking the same diagonal lines both times. Draw the lines you are checking in the grid (on paper), to see this easily.

Change one of them to add from X and subtract from Y (or the other way around).

Answer 6

A few tips :

• You dont need this :

  c[0] = source.charAt(x);
  c[1] = source.charAt(x + 1);
  s = new String(c, 0, 2);
  

  you can just write

  s= source.charAt(x) +""+ source.charAt(x+1);

  or even better use

  s = source.substring(x, x+2);

• Check the diagonals on simpler data

• Don't swap the inner outer for if you really don't need to

• write gird.length instead 20