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()
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.