Eccoci.

Largest Product in a Grid

ℹ️Published on Friday, 22nd February 2002, 06:00 pm; Solved by 251941;
Difficulty rating: 5%

Problem 11

In the $20 \times 20$ grid below, four numbers along a diagonal line have been marked in red.

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 \times 63 \times 78 \times 14 = 1788696$.

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

Soluzione

Questo è semplice ma interessante da programmare perché occorre stare bene attenti a tutti i casi possibili (righe, colonne, diagonali) e ai casi limite (siamo vicino a un bordo?).

M =
[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]

function maxp4_over_rows(M::Matrix; verbose=false)
	cur_max = 0
	R, C = size(M)
	for i in 1:R
		for j in 1:(C-3)
			if prod(@view M[i,j:j+3]) > cur_max
				cur_max = prod(@view M[i,j:j+3])
				println("Lungo le righe: i=$i, j=$j, cur_max=$cur_max")
			end
		end
	end
	return cur_max
end

function maxp4_over_cols(M::Matrix; verbose=false)
	cur_max = 0
	R, C = size(M)
	for j in 1:C
		for i in 1:(R-3)
			if prod(@view M[i:i+3,j]) > cur_max
				cur_max = prod(@view M[i:i+3,j])
				println("Lungo le colonne: i=$i, j=$j, cur_max=$cur_max")
			end
		end
	end
	return cur_max
end

function maxp4_over_diag(M::Matrix; verbose=false)
	cur_max = 0
	R, C = size(M)
	# direzione ↘
	for i in 1:(R-3)
		for j in 1:(C-3)
			idxs = i .+ [0,1,2,3]
			jdxs = j .+ [0,1,2,3]
			# shortcut se carichiamo LinearAlgebra (using LinearAlgebra)
			# max_here = tr(M[idxs,jdxs]))
			max_here = 1
			for k in 1:4
				max_here *= M[idxs[k],jdxs[k]]
			end
			if max_here > cur_max
				cur_max = max_here
				println("Lungo le diagonali ↘: i=$i, j=$j, cur_max=$cur_max")
			end
		end
	end
	# direzione ↙
	for i in 1:(R-4)
		for j in 4:C
			idxs = i .+ [0,1,2,3]
			jdxs = j .- [0,1,2,3]
			# shortcut se carichiamo LinearAlgebra (using LinearAlgebra)
			# max_here = tr(M[idxs,jdxs]))
			max_here = 1
			for k in 1:4
				max_here *= M[idxs[k],jdxs[k]]
			end
			if max_here > cur_max
				cur_max = max_here
				println("Lungo le diagonali ↙: i=$i, j=$j, cur_max=$cur_max")
			end
		end
	end
	return cur_max
end

@show maximum([maxp4_over_rows(M),maxp4_over_cols(M),maxp4_over_diag(M)])

Lungo le righe: i=1, j=1, cur_max=34144
Lungo le righe: i=1, j=2, cur_max=162184
Lungo le righe: i=1, j=3, cur_max=1216380
Lungo le righe: i=1, j=14, cur_max=2433600
Lungo le righe: i=1, j=16, cur_max=4204200
Lungo le righe: i=2, j=1, cur_max=9507960
Lungo le righe: i=2, j=12, cur_max=11630640
Lungo le righe: i=2, j=13, cur_max=13956768
Lungo le righe: i=3, j=9, cur_max=17696040
Lungo le righe: i=5, j=5, cur_max=19159119
Lungo le righe: i=5, j=7, cur_max=21149604
Lungo le righe: i=8, j=9, cur_max=21941010
Lungo le righe: i=8, j=16, cur_max=27663636
Lungo le righe: i=9, j=11, cur_max=48477312
Lungo le colonne: i=1, j=1, cur_max=1651104
Lungo le colonne: i=2, j=1, cur_max=4540536
Lungo le colonne: i=2, j=2, cur_max=5210170
Lungo le colonne: i=4, j=2, cur_max=9995020
Lungo le colonne: i=17, j=2, cur_max=14808780
Lungo le colonne: i=13, j=4, cur_max=23569344
Lungo le colonne: i=14, j=4, cur_max=35845044
Lungo le colonne: i=7, j=16, cur_max=51267216
Lungo le diagonali ↘: i=1, j=1, cur_max=279496
Lungo le diagonali ↘: i=1, j=3, cur_max=2904000
Lungo le diagonali ↘: i=1, j=8, cur_max=11587200
Lungo le diagonali ↘: i=2, j=1, cur_max=16194745
Lungo le diagonali ↘: i=3, j=2, cur_max=32719995
Lungo le diagonali ↘: i=17, j=10, cur_max=40304286
Lungo le diagonali ↙: i=2, j=13, cur_max=41076896
Lungo le diagonali ↙: i=13, j=7, cur_max=70600674
maximum([maxp4_over_rows(M), maxp4_over_cols(M), maxp4_over_diag(M)]) = 70600674