CODEWITHSUNDEEP
pythonmath
wiknwo
wiknwo

Reputation: 29

What am I doing wrong here? Project Euler Problem 11

This is my first question post on StackOverflow so please pardon any mistakes but let me know about them. I am trying to do problem 11 on project euler in python. I feel like my method is correct but I am not getting the right answer. The answer I am getting is 51267216. Would you please be able to spot where I am going wrong in my code?

def main():
   grid = [[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],
           [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0],
           [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65],
           [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
           [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
           [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
           [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92],
           [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57],
           [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
           [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40], 
           [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
           [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
           [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
           [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
           [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
           [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]]

   greatest_product_four_adjacent_numbers_same_direction = -1
   product = 0

   for i in range(20):
       for j in range(20):
           # Right
           if(i < 20 and j + 1 < 20 and j + 2 < 20 and j + 3 < 20):
               product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product
           
           # Left
           if(i < 20 and j - 1 >= 0 and j - 2 >= 0 and j - 3 >= 0):
               product = grid[i][j] * grid[i][j - 1] * grid[i][j - 2] * grid[i][j - 3]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product
           
           # Down
           if(j < 20 and i + 1 < 20 and i + 2 < 20 and i + 3 < 20):
               product = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product
               
           # Up 
           if(i < 20 and j - 1 >= 0 and j - 2 >= 0 and j - 3 >= 0):
               product = grid[i][j] * grid[i - 1][j] * grid[i - 2][j] * grid[i - 3][j]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product

           # Diagonal right
           if(i + 1 < 20 and j + 1 < 20 and i + 2 < 20 and j + 2 < 20 and i + 3 < 20 and j + 3 < 20):
               product = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product
           
           # Diagonal left
           if(i - 1 >= 0 and j - 1 >= 0 and i - 2 >= 0 and j - 2 >= 0 and i - 3 >= 0 and j - 3 >= 0):
               product = grid[i][j] * grid[i - 1][j - 1] * grid[i - 2][j - 2] * grid[i - 3][j - 3]
               if(product > greatest_product_four_adjacent_numbers_same_direction):
                   greatest_product_four_adjacent_numbers_same_direction = product
   print(greatest_product_four_adjacent_numbers_same_direction)

if __name__ == '__main__':
   main()

Upvotes: 1

Views: 224

Answers (2)

OffHakhol
OffHakhol

Reputation: 101

My solution in python.

Note that previously I copy paste the grid into a text file named "problem11.txt"

# ==== Problem 11 ====
with open('problem11.txt', 'r') as f:
    mat_prb11 = [[int(num) for num in line.split(' ')] for line in f]

tmp = 0
sol = 0

for i in range(len(mat_prb11)):
    for j in range(len(mat_prb11)):

        try:  # 1
            row_right = mat_prb11[i][j] * mat_prb11[i][j + 1] * mat_prb11[i][j + 2] * mat_prb11[i][j + 3]
        except:
            row_right = 1

        try:  # 2
            row_left = mat_prb11[i][j] * mat_prb11[i][j - 1] * mat_prb11[i][j - 2] * mat_prb11[i][j - 3]
        except:
            row_left = 1

        try:  # 3
            col_up = mat_prb11[i][j] * mat_prb11[i - 1][j] * mat_prb11[i - 2][j] * mat_prb11[i - 3][j]
        except:
            col_up = 1

        try:  # 4
            col_dwn = mat_prb11[i][j] * mat_prb11[i + 1][j] * mat_prb11[i + 2][j] * mat_prb11[i + 3][j]
        except:
            col_dwn = 1

        try:  # 5
            diag_right_up = mat_prb11[i][j] * mat_prb11[i + 1][j + 1] * mat_prb11[i + 2][j + 2] * mat_prb11[i + 3][j + 3]
        except:
            diag_right_up = 1

        try:  # 6
            diag_right_dwn = mat_prb11[i][j] * mat_prb11[i - 1][j + 1] * mat_prb11[i - 2][j + 2] * mat_prb11[i - 3][j + 3]
        except:
            diag_right_dwn = 1

        try:  # 7
            diag_left_up = mat_prb11[i][j] * mat_prb11[i + 1][j - 1] * mat_prb11[i + 2][j - 2] * mat_prb11[i + 3][j - 3]
        except:
            diag_left_up = 1

        try:  # 8
            diag_left_dwn = mat_prb11[i][j] * mat_prb11[i - 1][j - 1] * mat_prb11[i - 2][j - 2] * mat_prb11[i - 3][j - 3]
        except:
            diag_left_dwn = 1

        tmp = max(row_right, row_left, col_up, col_dwn, diag_right_up, diag_right_dwn, diag_left_up, diag_left_dwn)
        if tmp > sol:
            sol = tmp

print(mat_prb11)
print(f"The solution is = {sol}")  # solution is = 70600674

Upvotes: 0

khelwood
khelwood

Reputation: 59222

Both your diagonals are checking the same lines.

If fact you're checking each possible line twice: you multiply sequences of numbers going right, and then sequences going left, checking the same numbers again in reverse.

Finally you check the same diagonals twice (both axes increasing, and then both axes decreasing), but you don't check the diagonal that increases in one axis and decreases in the other.

Upvotes: 1

Related Questions