<filename>011 - Largest product in a grid.py
"""
Largest product in a grid



In the 20x20 grid below, four numbers along a diagonal line have been marked in red. (26, 63, 78, 14)

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

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20x20 grid?



"""

import time
start_time = time.time()

raw_grid = "\
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 \
"




def format_grid(raw_grid):
	grid_1d = raw_grid.split()
	nums_in_grid = len(grid_1d)
	rows_and_cols = int(nums_in_grid**0.5)
	if rows_and_cols % 1 != 0:
		print "The grid in not in 1:1 ratio"

	# initialize 2D gri
	grid_2d = [[0 for x in xrange(rows_and_cols)] for x in xrange(rows_and_cols)]
	for i in xrange(len(grid_1d) / rows_and_cols):
		for j in xrange(rows_and_cols):
			#print i, j
			grid_2d[i][j] = int(grid_1d[i * rows_and_cols + j])
	

	return (int(nums_in_grid**0.5), grid_2d)




def largest_product(raw_grid):
	rows_and_cols, grid_2d = format_grid(raw_grid)
	max_product = -1
	max_i, max_j, max_start, max_direction= -1, -1, -1, None
	#print grid_2d
	# for rows

	for i in xrange(rows_and_cols):
		for j in xrange(rows_and_cols - 3):
			product = grid_2d[i][j] * grid_2d[i][j+1] * grid_2d[i][j+2] * grid_2d[i][j+3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "right"

	# for cols
	for i in xrange(rows_and_cols - 3):
		for j in xrange(rows_and_cols):
			product = grid_2d[i][j] * grid_2d[i+1][j] * grid_2d[i+2][j] * grid_2d[i+3][j]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "down"

	# for diagonally down right
	for i in xrange(rows_and_cols - 3):
		for j in xrange(rows_and_cols - 3):
			product = grid_2d[i][j] * grid_2d[i+1][j+1] * grid_2d[i+2][j+2] * grid_2d[i+3][j+3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "diagonally down right"

	# for diagonally down left
	for i in xrange(rows_and_cols - 3):
		for j in xrange(3, rows_and_cols):
			product = grid_2d[i][j] * grid_2d[i+1][j-1] * grid_2d[i+2][j-2] * grid_2d[i+3][j-3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "diagonally down left"

	print "start with the number " + str(max_start) + " at " + str(max_i) + ", " + str(max_j) + " and go " + max_direction 
	return max_product


print largest_product(raw_grid)

print "Time elapsed: %5.3f" % (time.time() - start_time)

"""
answer is 70600674
89, 94, 97, 87

"""
<filename>011 - Largest product in a grid.py
"""
Largest product in a grid



In the 20x20 grid below, four numbers along a diagonal line have been marked in red. (26, 63, 78, 14)

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

The product of these numbers is 26 x 63 x 78 x 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20x20 grid?



"""

import time
start_time = time.time()

raw_grid = "\
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 \
"




def format_grid(raw_grid):
	grid_1d = raw_grid.split()
	nums_in_grid = len(grid_1d)
	rows_and_cols = int(nums_in_grid**0.5)
	if rows_and_cols % 1 != 0:
		print "The grid in not in 1:1 ratio"

	# initialize 2D gri
	grid_2d = [[0 for x in xrange(rows_and_cols)] for x in xrange(rows_and_cols)]
	for i in xrange(len(grid_1d) / rows_and_cols):
		for j in xrange(rows_and_cols):
			#print i, j
			grid_2d[i][j] = int(grid_1d[i * rows_and_cols + j])
	

	return (int(nums_in_grid**0.5), grid_2d)




def largest_product(raw_grid):
	rows_and_cols, grid_2d = format_grid(raw_grid)
	max_product = -1
	max_i, max_j, max_start, max_direction= -1, -1, -1, None
	#print grid_2d
	# for rows

	for i in xrange(rows_and_cols):
		for j in xrange(rows_and_cols - 3):
			product = grid_2d[i][j] * grid_2d[i][j+1] * grid_2d[i][j+2] * grid_2d[i][j+3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "right"

	# for cols
	for i in xrange(rows_and_cols - 3):
		for j in xrange(rows_and_cols):
			product = grid_2d[i][j] * grid_2d[i+1][j] * grid_2d[i+2][j] * grid_2d[i+3][j]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "down"

	# for diagonally down right
	for i in xrange(rows_and_cols - 3):
		for j in xrange(rows_and_cols - 3):
			product = grid_2d[i][j] * grid_2d[i+1][j+1] * grid_2d[i+2][j+2] * grid_2d[i+3][j+3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "diagonally down right"

	# for diagonally down left
	for i in xrange(rows_and_cols - 3):
		for j in xrange(3, rows_and_cols):
			product = grid_2d[i][j] * grid_2d[i+1][j-1] * grid_2d[i+2][j-2] * grid_2d[i+3][j-3]
			if max_product < product:
				max_product = product
				max_i, max_j, max_start, max_direction = i, j, grid_2d[i][j], "diagonally down left"

	print "start with the number " + str(max_start) + " at " + str(max_i) + ", " + str(max_j) + " and go " + max_direction 
	return max_product


print largest_product(raw_grid)

print "Time elapsed: %5.3f" % (time.time() - start_time)

"""
answer is 70600674
89, 94, 97, 87

"""
Largest product in a grid    In the 20x20 grid below, four numbers along a diagonal line have been marked in red. (26, 63, 78, 14)  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  The product of these numbers is 26 x 63 x 78 x 14 = 1788696.  What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20x20 grid? # initialize 2D gri #print i, j #print grid_2d # for rows # for cols # for diagonally down right # for diagonally down left answer is 70600674 89, 94, 97, 87