Largest product in a grid
- Task
The task description is taken from Project Euler:
(https://projecteuler.net/problem=11)
Given the 20×20 grid below:
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
What is the greatest product of four adjacent numbers in the same direction (down, right) in the 20×20 grid?
11l
F maxproduct(mat, length)
‘ find the largest product of len length horizontal or vertical length in matrix ’
V (nrow, ncol) = (mat.len, mat[0].len)
V (maxprod, maxrow, maxcol, arr) = (Int64(0), [0, 0], [0, 0], [0])
L(row) 0 .< nrow
L(col) 0 .< ncol
V (row2, col2) = (row + length, col + length)
I row < nrow - length
V array = mat[row .< row2].map(r -> r[@col])
V pro = product(array.map(Int64))
I pro > maxprod
(maxprod, maxrow, maxcol, arr) = (pro, [row, row2], [col], array)
I col < ncol - length
V pro = product(mat[row][col .< col2].map(Int64))
I pro > maxprod
(maxprod, maxrow, maxcol, arr) = (pro, [row], [col, col2], mat[row][col .< col2])
print(‘The max ’length‘-product is ’maxprod‘, product of ’arr‘ at row ’maxrow‘, col ’maxcol‘.’)
V MATRIX = [
[ 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]
]
L(n) 2..5
maxproduct(MATRIX, n)
- Output:
The max 2-product is 9215, product of [95, 97] at row [7, 9], col [8]. The max 3-product is 776776, product of [91, 88, 97] at row [7, 10], col [15]. The max 4-product is 51267216, product of [66, 91, 88, 97] at row [6, 10], col [15]. The max 5-product is 2326829868, product of [62, 99, 69, 82, 67] at row [17], col [9, 14].
ALGOL 68
BEGIN # find the maximum product of 4 adjacent numbers in a row or column of a matrix #
[,]INT 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 )
);
INT elements = 4; # number of elements to multiply #
INT max product := - max int; # most negative integer #
INT row := 0, col := 0;
BOOL horizontal := TRUE;
FOR i FROM 1 LWB m TO 1 UPB m DO
FOR j FROM 2 LWB m TO ( 2 UPB m - elements ) + 1 DO
INT ij product := m[ i, j ] * m[ i, j + 1 ] * m[ i, j + 2 ] * m[ i, j + 3 ];
IF ij product > max product THEN
max product := ij product;
row := i;
col := j
FI
OD
OD;
FOR j FROM 2 LWB m TO 2 UPB m DO
FOR i FROM 1 LWB m TO ( 2 UPB m - elements ) + 1 DO
INT ij product := m[ i, j ] * m[ i + 1, j ] * m[ i + 2, j ] * m[ i + 3, j ];
IF ij product > max product THEN
max product := ij product;
row := i;
col := j;
horizontal := FALSE
FI
OD
OD;
print( ( "The maximum product of ", whole( elements, 0 )
, " elements: ", whole( max product, 0 )
, " is the ", IF horizontal THEN "row" ELSE "column" FI
, " of ", whole( elements, 0 )
, " numbers starting at: ", whole( row, 0 ), ", ", whole( col, 0 )
)
)
END
- Output:
The maximum product of 4 elements: 51267216 is the column of 4 numbers starting at: 7, 16
Arturo
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]
]
findLargestProduct: function [g][
dim: size g
maxProd: [[], 0]
loop 0..dec dim 'row [
loop 0..dim-4 'col [
items: @[g\[row]\[col], g\[row]\[col+1], g\[row]\[col+2], g\[row]\[col+3]]
prod: product items
if prod > last maxProd [
maxProd: @[items, prod]
]
]
]
loop 0..dec dim 'col [
loop 0..dim-4 'row [
items: @[g\[row]\[col], g\[row+1]\[col], g\[row+2]\[col], g\[row+3]\[col]]
prod: product items
if prod > last maxProd [
maxProd: @[items, prod]
]
]
]
return maxProd
]
print findLargestProduct grid
- Output:
[66 91 88 97] 51267216
AutoHotkey
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
)
oGrid := []
for r, line in StrSplit(grid, "`n", "`r")
for c, v in StrSplit(line, " ")
oGrid[r, c] := v
n := 4
Steps := []
for r, row in oGrid
{
for c, v in row
{
prodR := prodC := 1
strR := strC := ""
loop % n
{
prodR *= oGrid[r, c + A_Index - 1]
prodC *= oGrid[r + A_Index - 1, C]
strR .= oGrid[r, c + A_Index - 1] "*"
strC .= oGrid[r + A_Index - 1, C] "*"
}
Steps[prodR] .= "`n" Trim(strR, "*") " @ Row " r ", Col " c " - Col " c+n-1
Steps[prodC] .= "`n" Trim(strC, "*") " @ Row " r " - Row " r+n-1 ", Col " c
maxProd := maxProd > prodR ? maxProd : prodR
maxProd := maxProd > prodC ? maxProd : prodC
}
}
MsgBox, 262144, ,% result := "Max Product = " maxProd . Steps[maxProd]
- Output:
Max Product = 51267216 66*91*88*97 @ Row 7 - Row 10, Col 16
AWK
# syntax: GAWK -f LARGEST_PRODUCT_IN_A_GRID.AWK
BEGIN {
grid[++row] = "08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08"
grid[++row] = "49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00"
grid[++row] = "81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65"
grid[++row] = "52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91"
grid[++row] = "22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80"
grid[++row] = "24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50"
grid[++row] = "32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70"
grid[++row] = "67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21"
grid[++row] = "24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72"
grid[++row] = "21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95"
grid[++row] = "78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92"
grid[++row] = "16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57"
grid[++row] = "86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58"
grid[++row] = "19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40"
grid[++row] = "04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66"
grid[++row] = "88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69"
grid[++row] = "04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36"
grid[++row] = "20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16"
grid[++row] = "20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54"
grid[++row] = "01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48"
for (r=1; r<=row; r++) { # build 2-dimensional array
col = split(grid[r],tmp_arr,",")
width_arr[col] = ""
for (c=1; c<=col; c++) {
arr[r][c] = tmp_arr[c]
}
}
if (length(width_arr) != 1) {
print("error: arrays must be same length")
exit(1)
}
delete grid
delete tmp_arr
delete width_arr
for (r=1; r<=row-3; r++) { # top-bottom / down
for (c=1; c<=col; c++) {
product = (p0=arr[r][c]) * (p1=arr[r+1][c]) * (p2=arr[r+2][c]) * (p3=arr[r+3][c])
if (product > ans) {
ans = product
cell_info = sprintf("%d*%d*%d*%d in column %d rows %d-%d",p0,p1,p2,p3,c,r,r+3)
}
}
}
for (c=1; c<=col-3; c++) { # left-right / across
for (r=1; r<=row; r++) {
product = (p0=arr[r][c]) * (p1=arr[r][c+1]) * (p2=arr[r][c+2]) * (p3=arr[r][c+3])
if (product > ans) {
ans = product
cell_info = sprintf("%d*%d*%d*%d in row %d columns %d-%d",p0,p1,p2,p3,r,c,c+3)
}
}
}
printf("%d = %s\n",ans,cell_info)
exit(0)
}
- Output:
51267216 = 66*91*88*97 in column 16 rows 7-10
BASIC
ANSI BASIC
100 REM Largest product in a grid
110 DATA 08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08
120 DATA 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00
130 DATA 81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65
140 DATA 52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91
150 DATA 22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80
160 DATA 24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50
170 DATA 32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70
180 DATA 67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21
190 DATA 24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72
200 DATA 21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95
210 DATA 78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92
220 DATA 16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57
230 DATA 86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58
240 DATA 19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40
250 DATA 04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66
260 DATA 88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69
270 DATA 04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36
280 DATA 20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16
290 DATA 20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54
300 DATA 01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48
310 REM
320 DIM Grid(1 TO 20, 1 TO 20)
330 LET Champ = 0
340 LET Across = 0
350 FOR Row = 1 TO 20
360 FOR Col = 1 TO 20
370 READ Grid(Row, Col)
380 NEXT Col
390 NEXT Row
400 REM ** Search down
410 FOR Row = 1 TO 17
420 FOR Col = 1 TO 20
430 LET Prod = Grid(Row, Col) * Grid(Row + 1, Col) * Grid(Row + 2, Col) * Grid(Row + 3, Col)
440 IF Prod > Champ THEN
450 LET CR = Row
460 LET CC = Col
470 LET Champ = Prod
480 end IF
490 NEXT Col
500 NEXT Row
510 REM ** Search across
520 FOR Row = 1 TO 20
530 FOR Col = 1 TO 17
540 LET Prod = Grid(Row, Col) * Grid(Row, Col + 1) * Grid(Row, Col + 2) * Grid(Row, Col + 3)
550 IF Prod > Champ THEN
560 LET CR = Row
570 LET CC = Col
580 LET Champ = Prod
590 LET Across = 1
600 END IF
610 NEXT Col
620 NEXT Row
630 REM **
640 PRINT "The largest product was"; Champ; "at row"; CR; "and column"; CC; "(reading ";
650 IF Across = 0 THEN PRINT "down)." ELSE PRINT "across)."
660 END
- Output:
The largest product was 51267216 at row 7 and column 16 (reading down).
FreeBASIC
data 08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08
data 49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00
data 81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65
data 52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91
data 22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80
data 24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50
data 32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70
data 67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21
data 24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72
data 21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95
data 78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92
data 16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57
data 86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58
data 19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40
data 04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66
data 88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69
data 04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36
data 20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16
data 20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54
data 01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48
dim as integer grid(1 to 20, 1 to 20), row, col, prod
dim as integer champ = 0, cr, cc
dim as boolean across = false
for row = 1 to 20
for col = 1 to 20
read grid(row, col)
next col
next row
'search down
for row = 1 to 17
for col = 1 to 20
prod = grid(row, col)*grid(row + 1, col)*grid(row + 2, col)*grid(row + 3, col)
if prod > champ then
cr = row
cc = col
champ = prod
end if
next col
next row
'search across
for row = 1 to 20
for col = 1 to 17
prod = grid(row, col)*grid(row, col + 1)*grid(row, col + 2)*grid(row, col + 3)
if prod > champ then
cr = row
cc = col
champ = prod
across = true
end if
next col
next row
print "The largest product was ";champ;" at row ";cr;" and column ";cc;" (reading ";
if across then print "across)." else print "down)."
- Output:
The largest product was 51267216 at row 7 and column 16 (reading down).
Minimal BASIC
10 REM Largest product in a grid
20 REM 2 lines of DATA fill 1 row
30 DATA 08, 02, 22, 97, 38, 15, 00, 40, 00, 75
40 DATA 04, 05, 07, 78, 52, 12, 50, 77, 91, 08
50 DATA 49, 49, 99, 40, 17, 81, 18, 57, 60, 87
60 DATA 17, 40, 98, 43, 69, 48, 04, 56, 62, 00
70 DATA 81, 49, 31, 73, 55, 79, 14, 29, 93, 71
80 DATA 40, 67, 53, 88, 30, 03, 49, 13, 36, 65
90 DATA 52, 70, 95, 23, 04, 60, 11, 42, 69, 24
100 DATA 68, 56, 01, 32, 56, 71, 37, 02, 36, 91
110 DATA 22, 31, 16, 71, 51, 67, 63, 89, 41, 92
120 DATA 36, 54, 22, 40, 40, 28, 66, 33, 13, 80
130 DATA 24, 47, 32, 60, 99, 03, 45, 02, 44, 75
140 DATA 33, 53, 78, 36, 84, 20, 35, 17, 12, 50
150 DATA 32, 98, 81, 28, 64, 23, 67, 10, 26, 38
160 DATA 40, 67, 59, 54, 70, 66, 18, 38, 64, 70
170 DATA 67, 26, 20, 68, 02, 62, 12, 20, 95, 63
180 DATA 94, 39, 63, 08, 40, 91, 66, 49, 94, 21
190 DATA 24, 55, 58, 05, 66, 73, 99, 26, 97, 17
200 DATA 78, 78, 96, 83, 14, 88, 34, 89, 63, 72
210 DATA 21, 36, 23, 09, 75, 00, 76, 44, 20, 45
220 DATA 35, 14, 00, 61, 33, 97, 34, 31, 33, 95
230 DATA 78, 17, 53, 28, 22, 75, 31, 67, 15, 94
240 DATA 03, 80, 04, 62, 16, 14, 09, 53, 56, 92
250 DATA 16, 39, 05, 42, 96, 35, 31, 47, 55, 58
260 DATA 88, 24, 00, 17, 54, 24, 36, 29, 85, 57
270 DATA 86, 56, 00, 48, 35, 71, 89, 07, 05, 44
280 DATA 44, 37, 44, 60, 21, 58, 51, 54, 17, 58
290 DATA 19, 80, 81, 68, 05, 94, 47, 69, 28, 73
300 DATA 92, 13, 86, 52, 17, 77, 04, 89, 55, 40
310 DATA 04, 52, 08, 83, 97, 35, 99, 16, 07, 97
320 DATA 57, 32, 16, 26, 26, 79, 33, 27, 98, 66
330 DATA 88, 36, 68, 87, 57, 62, 20, 72, 03, 46
340 DATA 33, 67, 46, 55, 12, 32, 63, 93, 53, 69
350 DATA 04, 42, 16, 73, 38, 25, 39, 11, 24, 94
360 DATA 72, 18, 08, 46, 29, 32, 40, 62, 76, 36
370 DATA 20, 69, 36, 41, 72, 30, 23, 88, 34, 62
380 DATA 99, 69, 82, 67, 59, 85, 74, 04, 36, 16
390 DATA 20, 73, 35, 29, 78, 31, 90, 01, 74, 31
400 DATA 49, 71, 48, 86, 81, 16, 23, 57, 05, 54
410 DATA 01, 70, 54, 71, 83, 51, 54, 69, 16, 92
420 DATA 33, 48, 61, 43, 52, 01, 89, 19, 67, 48
430 REM
440 OPTION BASE 1
450 DIM G(20,20)
460 LET X = 0
470 LET A = 0
480 FOR R = 1 TO 20
490 FOR C = 1 TO 20
500 READ G(R,C)
510 NEXT C
520 NEXT R
530 REM ** Search down
540 FOR R = 1 TO 17
550 FOR C = 1 TO 20
560 LET P = G(R,C)*G(R+1,C)*G(R+2,C)*G(R+3,C)
570 IF P <= X THEN 610
580 LET R0 = R
590 LET C0 = C
600 LET X = P
610 NEXT C
620 NEXT R
630 REM ** Search across
640 FOR R = 1 TO 20
650 FOR C = 1 TO 17
660 LET P = G(R,C)*G(R,C+1)*G(R,C+2)*G(R,C+3)
670 IF P <= X THEN 720
680 LET R0 = R
690 LET C0 = C
700 LET X = P
710 LET A = 1
720 NEXT C
730 NEXT R
740 REM **
750 PRINT "The largest product was"; X
760 PRINT "at row"; R0; "and column"; C0
770 IF A = 0 THEN 800
780 PRINT "(reading across)."
790 GOTO 810
800 PRINT "(reading down)."
810 END
- Output:
The largest product was 5.126722E+07 at row 7 and column 16 (reading down).
C
/* Largest product in a grid */
#include<stdio.h>
#define PROD_LEN 4
#define GRID_SIZE 20
int main()
{
long int max, prod;
int i, j, k, k_max, j_max = GRID_SIZE - PROD_LEN;
int grid[GRID_SIZE][GRID_SIZE] =
{
{ 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}
};
max = 0;
for (j = 0; j < GRID_SIZE; j++)
for (i = 0; i <= j_max; i++)
for (k = i, prod = 1, k_max = PROD_LEN + i - 1; k <= k_max; k++)
{
prod *= grid[j][k];
if (prod > max)
max = prod;
}
for (j = 0; j <= j_max; j++)
for (i = 0; i < GRID_SIZE; i++)
for (k = j, prod = 1, k_max = PROD_LEN + j - 1; k <= k_max; k++)
{
prod *= grid[k][i];
if (prod > max)
max = prod;
}
printf("%d\n", max);
}
- Output:
51267216
C#
// Largest product in a grid
using System;
class Program
{
const int prodLen = 4;
const int gridSize = 20;
public static void Main()
{
int jMax = gridSize - prodLen;
int[ , ] grid = new int[gridSize, gridSize]
{
{ 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}
};
long max = 0;
for (int j = 0; j < gridSize; j++)
for (int i = 0; i <= jMax; i++)
{
long prod = 1;
for (int k = i, kMax = prodLen + i - 1; k <= kMax; k++)
{
prod *= grid[j, k];
if (prod > max)
max = prod;
}
}
for (int j = 0; j <= jMax; j++)
for (int i = 0; i < gridSize; i++)
{
long prod = 1;
for (int k = j, kMax = prodLen + j - 1; k <= kMax; k++)
{
prod *= grid[k, i];
if (prod > max)
max = prod;
}
}
Console.WriteLine(max);
}
}
- Output:
51267216
C++
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
struct Coordinate {
uint32_t x;
int32_t y;
std::string to_string() {
if ( y == -1 ) {
return std::to_string(x);
}
return "(" + std::to_string(x) + ", " + std::to_string(y) + ")";
}
};
template <typename T>
void print_vector(const std::vector<T>& vec) {
std::cout << "[";
for ( uint32_t i = 0; i < vec.size() - 1; ++i ) {
std::cout << vec[i] << ", ";
}
std::cout << vec.back() << "]";
}
void max_product(const std::vector<std::vector<uint64_t>>& grid, const uint32_t& product_length) {
const uint32_t row_count = grid.size();
const uint32_t col_count = grid[0].size();
uint64_t max_product = 0;
Coordinate max_row(0, 0);
Coordinate max_col(0, 0);
std::vector<uint64_t> numbers{};
for ( uint32_t row = 0; row < row_count; ++row ) {
for ( uint32_t col = 0; col < col_count; ++col ) {
const uint32_t row2 = row + product_length;
const uint32_t col2 = col + product_length;
if ( row < row_count - product_length ) {
uint64_t product = 1;
for ( uint32_t r = row; r < row2; ++r ) {
product *= grid[r][col];
}
if ( product > max_product ) {
max_product = product;
max_row = Coordinate(row, row2);
max_col = Coordinate(col, -1);
numbers.clear();
for ( uint32_t r = row; r < row2; ++r ) {
numbers.emplace_back(grid[r][col]);
}
}
}
if ( col < col_count - product_length ) {
uint64_t product = 1;
for ( uint32_t c = col; c < col2; ++c ) {
product *= grid[row][c];
}
if ( product > max_product ) {
max_product = product;
max_row = Coordinate(row, -1);
max_col = Coordinate(col, col2);
numbers.clear();
for ( uint32_t c = col; c < col2; ++c ) {
numbers.emplace_back(grid[row][c]);
}
}
}
}
}
std::cout << "The maximum " << product_length << "-product is " << max_product << ", product of ";
print_vector(numbers);
std::cout << " at row " + max_row.to_string() << ", col " << max_col.to_string() << std::endl;
}
int main() {
const std::vector<std::vector<uint64_t>> 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 }
};
for ( uint32_t n = 2; n <= 5; ++n ) {
max_product(grid, n);
}
}
- Output:
The maximum 2-product is 9215, product of [95, 97] at row (7, 9), col 8 The maximum 3-product is 776776, product of [91, 88, 97] at row (7, 10), col 15 The maximum 4-product is 51267216, product of [66, 91, 88, 97] at row (6, 10), col 15 The maximum 5-product is 2326829868, product of [62, 99, 69, 82, 67] at row 17, col (9, 14)
Delphi
type T2DGrid = array [0..19,0..19] of integer;
const PGrid: T2DGrid =(
(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 GetAdjacentProduct(Grid: T2DGrid; P: TPoint): integer;
{Get adjacent products from Point P}
var X,Y,Best1,Best2: integer;
var P2: TPoint;
begin
{Get the value at the target point}
Best1:=Grid[P.X,P.Y];
Best2:=Grid[P.X,P.Y];
{Multiply by next 3 elements to the right}
for X:=1 to 3 do
if (P.X+X)<High(Grid) then
Best1:=Best1 * Grid[P.X+X,P.Y];
{Multiply by next 3 elements down}
for Y:=1 to 3 do
if (P.Y+Y)<High(Grid) then
Best2:=Best2 * Grid[P.X,P.Y+Y];
{Return the best one}
if Best1>Best2 then Result:=Best1
else Result:=Best2;
end;
function GetBestGridProduct(Grid: T2DGrid): integer;
{Look at all positions in the grid and find largest product}
var P: integer;
var X,Y: integer;
begin
Result:=0;
for Y:=0 to High(Grid) do
for X:=0 to High(Grid[0]) do
begin
P:=GetAdjacentProduct(Grid,Point(X,Y));
if P>Result then Result:=P;
end;
end;
procedure TestGridProduct(Memo: TMemo);
{Run test problem}
var Best: integer;
begin
Best:=GetBestGridProduct(PGrid);
Memo.Lines.Add(IntToStr(Best));
end;
- Output:
51267216
EasyLang
repeat
s$ = input
until s$ = ""
m[][] &= number strsplit s$ " "
.
for i to 20
for j to 16
p = 1
p2 = 1
for k to 4
p *= m[i][j + k]
p2 *= m[j + k][i]
.
max = higher max p
max = higher max p2
.
.
print max
#
input_data
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
- Output:
51267216
F#
// Largest product in a grid. Nigel Galloway: December 30th., 2021
let N=[|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|]
printfn "%d" (seq{for n in 0..19 do for g in 0..16 do let n=n*20 in yield N.[n+g]*N.[n+g+1]*N.[n+g+2]*N.[n+g+3]; for n in 0..19 do for g in 0..16 do let g=g*20 in yield N.[n+g]*N.[n+g+20]*N.[n+g+40]*N.[n+g+60]}|>Seq.max)
- Output:
51267216
Factor
USING: grouping kernel math.matrices math.order prettyprint
sequences ;
: max-horizontal ( matrix m -- n )
[ <clumps> ] curry map [ product ] matrix-map mmax ;
: max-product ( matrix m -- n )
[ dup flip ] dip [ max-horizontal ] curry bi@ max ;
{
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
} 20 group
4 max-product .
- Output:
51267216
Go
package main
import (
"fmt"
"rcu"
"strings"
)
var grid = [][]int {
{ 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},
}
func main() {
maxProd, maxR1, maxR2, maxC1, maxC2 := 0, 0, 0, 0, 0
var maxNums [4]int
h, w := len(grid), len(grid[0])
// right
for r := 0; r < h; r++ {
for c := 0; c < w-4; c++ {
prod := 1
for i := c; i < c+4; i++ {
prod *= grid[r][i]
}
if prod > maxProd {
maxProd = prod
for n := 0; n < 4; n++ {
maxNums[n] = grid[r][c+n]
}
maxR1, maxR2 = r, r
maxC1, maxC2 = c, c+3
}
}
}
// down
for c := 0; c < w; c++ {
for r := 0; r < h-4; r++ {
prod := 1
for i := r; i < r+4; i++ {
prod *= grid[i][c]
}
if prod > maxProd {
maxProd = prod
for n := 0; n < 4; n++ {
maxNums[n] = grid[r+n][c]
}
maxR1, maxR2 = r, r+3
maxC1, maxC2 = c, c
}
}
}
fmt.Println("The greatest product of four adjacent numbers in the same direction (down or right) in the grid is:")
var maxNumStrs [4]string
for i := 0; i < 4; i++ {
maxNumStrs[i] = fmt.Sprintf("%d", maxNums[i])
}
fmt.Printf(" %s = %s\n", strings.Join(maxNumStrs[:], " x "), rcu.Commatize(maxProd))
fmt.Print(" at indices (one based): ")
for r := maxR1; r <= maxR2; r++ {
for c := maxC1; c <= maxC2; c++ {
fmt.Printf("(%d, %d) ", r+1, c+1)
}
}
fmt.Println()
}
- Output:
The greatest product of four adjacent numbers in the same direction (down or right) in the grid is: 66 x 91 x 88 x 97 = 51,267,216 at indices (one based): (7, 16) (8, 16) (9, 16) (10, 16)
Haskell
import Data.List.Split ( divvy )
import Data.List ( transpose )
grid :: [String]
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 9",
"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"]
toMatrix :: [String] -> [[Int]]
toMatrix = map ( map read . words )
maxHorizontal :: [[Int]] -> Int
maxHorizontal = maximum . map product . divvy 4 1 . concat
maxTotal :: [[Int]] -> Int
maxTotal matrix = max ( maxHorizontal matrix ) ( maxHorizontal $ transpose
matrix )
main :: IO ( )
main = do
print $ maxTotal $ toMatrix grid
- Output:
51267216
J
First, the "hard part" -- represent the grid itself:
grid=: ".>cutLF{{)n
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
}}
With that out of the way, we find all products of four numbers and then find the largest of those:
>./,4 */\ (,.|:)grid
51267216
If we wanted to find which four numbers formed this product, we could do a little more work:
($ #: I.@,) (= >./@,)4 */\ (,.|:)grid
6 15
This tells us that the four number sequence started at row 6 (row 0 is the first row) and column 15. This also means that the numbers extend downwards from there. (If the column index had been 20 or higher, the number sequence would have come from the transposed copy of the array, so they would have been arranged left to right in the original 'grid'.)
In other words:
(6 7 8 9 ,&.> 15) { grid
66 91 88 97
*/66 91 88 97
51267216
Java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.LongStream;
public final class LargestProductInAGrid {
public static void main(String[] args) {
final long[][] grid = new long[][] {
{ 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 }
};
for ( int n = 2; n <= 5; n++ ) {
maxProduct(grid, n);
}
}
private static void maxProduct(long[][] grid, int productLength) {
final int rowCount = grid.length;
final int colCount = grid[0].length;
long maxProduct = 0;
Coordinate maxRow = new Coordinate(0, 0);
Coordinate maxCol = new Coordinate(0, 0);
List<Long> numbers = new ArrayList<Long>();
for ( int row = 0; row < rowCount; row++ ) {
for ( int col = 0; col < colCount; col++ ) {
final int row2 = row + productLength;
final int col2 = col + productLength;
if ( row < rowCount - productLength ) {
final int colFixed = col;
final long product = LongStream.range(row, row2).map( r -> grid[(int) r][colFixed] )
.reduce(1, Math::multiplyExact);
if ( product > maxProduct ) {
maxProduct = product;
maxRow = new Coordinate(row, row2);
maxCol = new Coordinate(col, -1);
numbers = LongStream.range(row, row2).map( r -> grid[(int) r][colFixed] ).boxed().toList();
}
}
if ( col < colCount - productLength ) {
final int rowFixed = row;
final long product = LongStream.range(col, col2).map( c -> grid[rowFixed][(int) c] )
.reduce(1, Math::multiplyExact);
if ( product > maxProduct ) {
maxProduct = product;
maxRow = new Coordinate(row, -1);
maxCol = new Coordinate(col, col2);
numbers = LongStream.range(col, col2).map( c -> grid[rowFixed][(int) c] ).boxed().toList();
}
}
}
}
System.out.println("The maximum " + productLength + "-product is " + maxProduct
+ ", product of " + numbers + " at row " + maxRow + ", col " + maxCol);
}
private static record Coordinate(int x, int y) {
public String toString() {
if ( y == -1 ) {
return String.valueOf(x);
}
return "(" + x + ", " + y + ")";
}
}
}
- Output:
The maximum 2-product is 9215, product of [95, 97] at row (7, 9), col 8 The maximum 3-product is 776776, product of [91, 88, 97] at row (7, 10), col 15 The maximum 4-product is 51267216, product of [66, 91, 88, 97] at row (6, 10), col 15 The maximum 5-product is 2326829868, product of [62, 99, 69, 82, 67] at row 17, col (9, 14)
JavaScript
ES5
// Largest product in a grid
const prodLen = 4;
const gridSize = 20;
const jMax = gridSize - prodLen;
const 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] ];
let max = 0;
for (let j = 0; j < gridSize; j++)
for (let i = 0; i <= jMax; i++)
for (let k = i, prod = 1, kMax = prodLen + i - 1; k <= kMax; k++) {
prod *= grid[j][k];
if (prod > max)
max = prod;
}
for (let j = 0; j <= jMax; j++)
for (let i = 0; i < gridSize; i++)
for (let k = j, prod = 1, kMax = prodLen + j - 1; k <= kMax; k++) {
prod *= grid[k][i];
if (prod > max)
max = prod;
}
console.log(max);
- Output:
51267216
jq
Works with both jq and gojq, the C and Go implementations of jq
In Part 1 below, a simple solution to the basic problem, namely finding the maximum value, is presented.
In Part 2, the focus shifts to reporting the location and direction of the elements with the maximal product. Arrays are indexed from 0.
In both cases, it is assumed that `grid` has been defined as a function returning the grid as an array of arrays as presented, for example, in the Wren entry.
Generic Utilities
def prod(s): reduce s as $x (1; . * $x);
def prod: prod(.[]);
# Input: an array
# Output: a stream of arrays
def windows($size): range(0; 1+length-$size) as $i | .[$i:$i+$size];
Part 1
# Input: a matrix
def largest_product($size):
([.[] | (windows($size) | prod)] | max) as $rowmax
| ([transpose[] | (windows($size) | prod)] | max) as $colmax
| [$rowmax, $colmax]|max,
if ($rowmax > $colmax) then "The rows have it." else "The columns
have it." end ;
grid | largest_product(4)
- Output:
51267216 The columns have it.
Part 2
# Input: a row
# Output: [$i, $maxproduct]
def largest_product_of_row($size):
[range(0; 1 + length - $size) as $i
| [$i, (.[$i:$i+$size] | prod)] ] | max_by(.[1]);
# Input: a matrix
def largest_product_of_rows($size):
[range(0; length) as $row
| [$row, (.[$row] | largest_product_of_row($size)) ]] | max_by(.[1][1])
| [ .[0], .[1][]] ;
# Input: a matrix
def largest_product_with_details($size):
largest_product_of_rows($size) as [$row, $rowcol, $rmax]
| (transpose | largest_product_of_rows($size)) as [$col, $colrow, $cmax]
| if $rmax == $cmax
then "row-wise at \([$row, $rowcol]) equals col-wise at \([$col, $colrow]): \($cmax)"
elif $rmax > $cmax then "The rows have it at \([$row, $rowcol]): \($rmax)"
else "The columns have it at \([$colrow, $col]): \($cmax)"
end ;
grid | largest_product_with_details(4)
- Output:
The columns have it at [6,15]: 51267216
Julia
First, a quick method, which does not reveal the product locations:
mat = [
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
]
x = max(maximum([prod(mat[j, i:i+3]) for i in 1:17, j in 1:20]),
maximum([prod(mat[i:i+3, j]) for i in 1:17, j in 1:20]))
println("The maximum product of 4 adjacent horizontal or vertical in the matrix is: $x")
- Output:
The maximum product of 4 adjacent horizontal or vertical in the matrix is: 51267216
Alternatively, to get the position of the maximum product:
function maxprod(mat, len)
nrow, ncol = size(mat)
maxprod, maxrow, maxcol, arr = 0, 0:0, 0:0, [0]
for row in 1:nrow, col in 1:ncol
if row < nrow - len + 2
pro = prod(mat[row:row+len-1, col])
if pro > maxprod
maxprod, maxrow, maxcol, arr = pro, row:row+len-1, col:col, mat[row:row+len-1, col]
end
end
if col < ncol - len + 2
pro = prod(mat[row, col:col+len-1])
if pro > maxprod
maxprod, maxrow, maxcol, arr = pro, row:row, col:col+len-1, mat[row, col:col+len-1]
end
end
end
println("The maximum product is $maxprod, product of $arr at row $maxrow, col $maxcol")
end
maxprod(mat, 4)
- Output:
The maximum product is 51267216, product of [66, 91, 88, 97] at row 7:10, col 16:16
Mathematica / Wolfram Language
array = {
{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}
};
maxProduct[x_List, n_] := Max[Times @@@ Partition[x, n, 1]]
Max@Join[maxProduct[#, 4] & /@ array,
maxProduct[#, 4] & /@ Transpose[array]]
- Output:
51267216
Modula-2
MODULE LargProdGrid;
(* Largest product in a grid *)
FROM SWholeIO IMPORT
WriteInt;
FROM STextIO IMPORT
WriteLn;
CONST
ProdLen = 4;
GridSize = 20;
JMax = GridSize - ProdLen;
TYPE
TGrid = ARRAY [0 .. GridSize - 1], [0 .. GridSize - 1] OF INTEGER;
VAR
Grid: TGrid;
I, J, K, KMax: CARDINAL;
Max, Prod: INTEGER;
BEGIN
Grid := TGrid{
{ 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} };
Max := 0;
FOR J := 0 TO GridSize - 1 DO
FOR I := 0 TO JMax DO
Prod := 1;
KMax := ProdLen + I - 1;
FOR K := I TO KMax DO
Prod := Prod * Grid[J, K];
IF Prod > Max THEN
Max := Prod
END
END
END
END;
FOR J := 0 TO JMax DO
FOR I := 0 TO GridSize - 1 DO
Prod := 1;
KMax := ProdLen + J - 1;
FOR K := J TO KMax DO
Prod := Prod * Grid[K, I];
IF Prod > Max THEN
Max := Prod
END
END;
END;
END;
WriteInt(Max, 1);
WriteLn
END LargProdGrid.
- Output:
51267216
ooRexx
/* REXX */
a.1=.array~of(08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08)
a.2=.array~of(49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00)
a.3=.array~of(81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65)
a.4=.array~of(52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91)
a.5=.array~of(22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80)
a.6=.array~of(24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50)
a.7=.array~of(32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70)
a.8=.array~of(67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21)
a.9=.array~of(24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72)
a.10=.array~of(21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95)
a.11=.array~of(78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92)
a.12=.array~of(16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57)
a.13=.array~of(86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58)
a.14=.array~of(19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40)
a.15=.array~of(04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66)
a.16=.array~of(88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69)
a.17=.array~of(04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36)
a.18=.array~of(20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16)
a.19=.array~of(20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54)
a.20=.array~of(01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48)
max=0
Do row=1 To 20
Do col=1 To 17
ar=a.row
prod=ar[col]*ar[col+1]*ar[col+2]*ar[col+3]
If prod>max Then Do
max=prod
rc=row col
l=ar[col]'*'ar[col+1]'*'ar[col+2]'*'ar[col+3]'='prod
End
End
End
Parse Var rc row col
Say 'Maximum in row' row 'columns' col '...' (col+3) ':' l
Do i=1 To 20
b.i=.array~of(a.1[i],a.2[i],a.3[i],a.4[i],a.5[i],a.6[i],a.7[i],a.8[i],a.9[i],a.10[i],,
a.11[i],a.12[i],a.13[i],a.14[i],a.15[i],a.16[i],a.17[i],a.18[i],a.19[i],a.20[i])
End
Do col=1 to 20
Do row=1 To 17
bc=b.col
prod=bc[row]*bc[row+1]*bc[row+2]*bc[row+3]
If prod>max Then Do
max=prod
rc=row col
l=bc[row]'*'bc[row+1]'*'bc[row+2]'*'bc[row+3]'='prod
End
End
End
Parse Var rc row col
Say 'Maximum in column' col 'rows' row '...' (row+3)
Say l
- Output:
Maximum in row 9 columns 11 ... 14 : 78*78*96*83=48477312 Maximum in column 16 rows 7 ... 10 : 66*91*88*97=51267216
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Largest_product_in_a_grid
use warnings;
use List::Util qw( max );
$_ = <<END;
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
END
my $score = 0;
for my $gap ( qr/ /, qr/.{58}/s )
{
$score = max $score, $1 * $2 * $3 * $4
while /(?=(\d\d)$gap(\d\d)$gap(\d\d)$gap(\d\d))/g;
}
print "max is $score\n";
- Output:
max is 51267216
Generalized
Handles non-square input (both narrow and wide).
use strict;
use warnings;
use feature 'say';
use List::AllUtils <max reduce>;
my $input = <<~END;
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
END
my(@m,@mt);
push @m, [ split /\s+/, s/\b0//gr ] for split "\n", $input;
for my $j (0..$#{$m[0]}) { push @mt, [ map $_->[$j], @m ] } # transpose
sub max_products {
my($terms,@matrix) = @_;
my @products;
my $columns = 1 + $#{$matrix[0]};
for my $row (@matrix) {
map { push @products, reduce { $a * $b } @$row[ $_ .. $_+$terms-1 ] } 0 .. $columns-$terms;
}
max @products
}
say "Largest product of $_ adjacent elements: " . max max_products($_,@m), max_products($_,@mt) for 1..6;
- Output:
Largest product of 1 adjacent elements: 99 Largest product of 2 adjacent elements: 9215 Largest product of 3 adjacent elements: 776776 Largest product of 4 adjacent elements: 51267216 Largest product of 5 adjacent elements: 2326829868 Largest product of 6 adjacent elements: 188210512710
Phix
with javascript_semantics function splint(string s) return apply(split(s),to_integer) end function constant grid = apply(split(""" 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 ""","\n"),splint) function gridmax(integer len) sequence gmax = {0,"???",0,0} integer height = length(grid), width = length(grid[1]) atom prod for row=1 to height do integer rmax = row+len-1 for col=1 to width do integer cmax = col+len-1 if cmax<=width then prod = product(grid[row][col..cmax]) gmax = max(gmax,{prod,"row",row,col}) end if if rmax<=height then prod = product(vslice(grid,col)[row..rmax]) gmax = max(gmax,{prod,"column",row,col}) end if end for end for return gmax end function for i=1 to 6 do printf(1,"The largest product of length %d is %,d in %s starting at %d,%d\n",i&gridmax(i)) end for
- Output:
The largest product of length 1 is 99 in row starting at 18,11 The largest product of length 2 is 9,215 in column starting at 8,9 The largest product of length 3 is 776,776 in column starting at 8,16 The largest product of length 4 is 51,267,216 in column starting at 7,16 The largest product of length 5 is 2,326,829,868 in row starting at 18,10 The largest product of length 6 is 188,210,512,710 in row starting at 18,11
PHP
<?php
// Largest product in a grid
const PROD_LEN = 4;
const GRID_SIZE = 20;
const J_MAX = GRID_SIZE - PROD_LEN;
$grid =
array(
array( 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8),
array(49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0),
array(81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65),
array(52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91),
array(22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80),
array(24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50),
array(32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70),
array(67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21),
array(24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72),
array(21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95),
array(78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92),
array(16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57),
array(86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58),
array(19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40),
array( 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66),
array(88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69),
array( 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36),
array(20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16),
array(20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54),
array( 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48)
);
$max = 0;
for ($j = 0; $j < GRID_SIZE; $j++)
for ($i = 0; $i <= J_MAX; $i++)
for ($k = $i, $prod = 1, $k_max = PROD_LEN + $i - 1; $k <= $k_max; $k++) {
$prod *= $grid[$j][$k];
if ($prod > $max)
$max = $prod;
}
for ($j = 0; $j <= J_MAX; $j++)
for ($i = 0; $i < GRID_SIZE; $i++)
for ($k = $j, $prod = 1, $k_max = PROD_LEN + $j - 1; $k <= $k_max; $k++) {
$prod *= $grid[$k][$i];
if ($prod > $max)
$max = $prod;
}
echo($max);
echo("\n");
?>
- Output:
51267216
Python
""" Rosetta code task: Largest_product_in_a_grid """
from math import prod
def maxproduct(mat, length):
""" find the largest product of len length horizontal or vertical length in matrix """
nrow, ncol = len(mat), len(mat[0])
maxprod, maxrow, maxcol, arr = 0, [0, 0], [0, 0], [0]
for row in range(nrow):
for col in range(ncol):
row2, col2 = row + length, col + length
if row < nrow - length:
array = [r[col] for r in mat[row:row2]]
pro = prod(array)
if pro > maxprod:
maxprod, maxrow, maxcol, arr = pro, [row, row2], col, array
if col < ncol - length:
pro = prod(mat[row][col:col2])
if pro > maxprod:
maxprod, maxrow, maxcol, arr = pro, row, [col, col2], mat[row][col:col2]
print(f"The max {length}-product is {maxprod}, product of {arr} at row {maxrow}, col {maxcol}.")
MATRIX = [
[ 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]
]
for n in range(2, 6):
maxproduct(MATRIX, n)
- Output:
The max 2-product is 9215, product of [95, 97] at row [7, 9], col 8. The max 3-product is 776776, product of [91, 88, 97] at row [7, 10], col 15. The max 4-product is 51267216, product of [66, 91, 88, 97] at row [6, 10], col 15. The max 5-product is 2326829868, product of [62, 99, 69, 82, 67] at row 17, col [9, 14].
Quackery
transpose
is defined at Matrix transposition#Quackery.
[ 1 swap witheach * ] is product ( [ --> n )
[ 4 split
over product
unrot witheach
[ join behead drop
tuck product
max swap ]
drop ] is 4*max ( [ --> n )
' [ [ 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 ] ]
0 over
witheach [ 4*max max ]
swap transpose
witheach [ 4*max max ]
echo
- Output:
51267216
Raku
General solution. No hard coded values. Works with any size matrix, configurable number of terms.
my @matrix = q:to/END/.lines».words;
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
END
my $terms = 4;
say "Largest product of $terms adjacent elements: " ~ max flat (^@matrix).map: {
@matrix.rotor($terms => -$terms+1).flat»[$_].batch($terms)».reduce(&[*]), # vertical
@matrix[$_].rotor($terms => -$terms+1)».reduce(&[*]); # horizontal
}
- Output:
Largest product of 4 adjacent elements: 51267216
REXX
/* REXX */
Call mk_a 1,08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08
Call mk_a 2,49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00
Call mk_a 3,81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65
Call mk_a 4,52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91
Call mk_a 5,22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80
Call mk_a 6,24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50
Call mk_a 7,32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70
Call mk_a 8,67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21
Call mk_a 9,24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72
Call mk_a 10,21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95
Call mk_a 11,78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92
Call mk_a 12,16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57
Call mk_a 13,86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58
Call mk_a 14,19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40
Call mk_a 15,04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66
Call mk_a 16,88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69
Call mk_a 17,04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36
Call mk_a 18,20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16
Call mk_a 19,20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54
Call mk_a 20,01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48
max=0
Do row=1 To 20
Do col=1 To 17
Parse Value (col+1) (col+2) (col+3) With col1 col2 col3
prod=a.row.col*a.row.col1*a.row.col2*a.row.col3
If prod>max Then Do
max=prod
rc=row col
l=a.row.col'*'a.row.col1'*'a.row.col2'*'a.row.col3'='prod
End
End
End
Parse Var rc row col
Say 'Maximum in row' row 'columns' col '...' (col+3) ':' ö
Do col=1 to 20
Do row=1 To 17
Parse Value (row+1) (row+2) (row+3) With row1 row2 row3
prod=a.row.col*a.row1.col*a.row2.col*a.row3.col
If prod>max Then Do
max=prod
rc=row col
l=a.row.col'*'a.row1.col'*'a.row2.col'*'a.row3.col'='prod
End
End
End
Parse Var rc row col
Say 'Maximum in row' row 'columns' col '...' (col+3) ':' l
mk_a:
row=arg(1)
Do col=1 To 20
a.row.col=arg(col+1)
End
Return
- Output:
Maximum in row 9 columns 11 ... 14 : 78*78*96*83=48477312 Maximum in column 16 rows 7 ... 10 : 66*91*88*97=51267216
Ring
see "working..." + nl
see "Largest product is:" + nl
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]]
Index = []
resTemp = []
prodNew = 0
for n = 1 to 17
prod = 0
for m = 1 to 20
prod = Grid[n][m] * Grid[n+1][m] * Grid[n+2][m] * Grid[n+3][m]
if prod > prodNew
prodNew = prod
res = 1000*Grid[n][m] + 100*Grid[n+1][m] + 10*Grid[n+2][m] + Grid[n+3][m]
resTemp = []
Index = []
add(Index,[n,m])
add(Index,[n+1,m])
add(Index,[n+2,m])
add(Index,[n+3,m])
add(resTemp,Grid[n][m])
add(resTemp,Grid[n+1][m])
add(resTemp,Grid[n+2][m])
add(resTemp,Grid[n+3][m])
ok
next
next
for n = 20 to 1 step -1
prod = 0
for m = 1 to 17
prod = Grid[n][m] * Grid[n][m+1] * Grid[n][m+2] * Grid[n][m+3]
if prod > prodNew
prodNew = prod
res = 1000*Grid[n][m] + 100*Grid[n][m+1] + 10*Grid[n][m+2] + Grid[n][m+3]
resTemp = []
Index = []
add(Index,[n,m])
add(Index,[n,m+1])
add(Index,[n,m+2])
add(Index,[n,m+3])
resTemp = []
add(resTemp,Grid[n][m])
add(resTemp,Grid[n][m+1])
add(resTemp,Grid[n+2][m+2])
add(resTemp,Grid[n][m+3])
ok
next
next
for n = 1 to len(resTemp)-1
see "" + resTemp[n] + " * "
next
see "" + resTemp[len(resTemp)] + " = " + prodNew + nl
see "Indices = "
for n = 1 to len(Index)
see "(" + Index[n][1] + "," + Index[n][2] + ")"
next
see nl + "done..." + nl
- Output:
working... Largest product is: 66 * 91 * 88 * 97 = 51267216 Indices = (7,16)(8,16)(9,16)(10,16) done...
Ruby
gridstr =
"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"
grid = gridstr.lines.map{|line| line.split.map(&:to_i) }
hor_ver = grid.each + grid.transpose.each
puts hor_ver.map{|line| line.each_cons(4).map{|slice| slice.inject(&:*) }.max}.max
- Output:
51267216
Sidef
var text = <<'EOT'
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
EOT
func horizontal(N, i, j, matrix) {
N.of {|k| matrix[i][j+k] }
}
func diagonal(N, i, j, matrix) {
N.of {|k| matrix[i+k][j+k] }
}
var matrix = Matrix(text.lines.map{ .nums }...)
var reversed_matrix = matrix.horizontal_flip
var transposed_matrix = matrix.transpose
define (
CHECK_DIAGONALS = false # true to also check diagonals
)
const e = matrix.end
for N in (1..6) {
var products = gather {
for i in (0..e), j in (0..e) {
(j+N < e) || next
# Horizontal and vertical
take(horizontal(N, i, j, matrix))
take(horizontal(N, i, j, transposed_matrix))
CHECK_DIAGONALS || next
(i+N < e) || next
# Left-to-right and right-to-left diagonals
take(diagonal(N, i, j, matrix))
take(diagonal(N, i, j, reversed_matrix))
}
}
var nums = products.max_by { .prod }
say "Largest product of #{N} adjacent elements: prod(#{nums}) = #{nums.prod}"
}
- Output:
Largest product of 1 adjacent elements: prod([99]) = 99 Largest product of 2 adjacent elements: prod([95, 97]) = 9215 Largest product of 3 adjacent elements: prod([91, 88, 97]) = 776776 Largest product of 4 adjacent elements: prod([66, 91, 88, 97]) = 51267216 Largest product of 5 adjacent elements: prod([62, 99, 69, 82, 67]) = 2326829868 Largest product of 6 adjacent elements: prod([99, 69, 82, 67, 59, 85]) = 188210512710
Wren
import "./fmt" for Fmt
var 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]
]
var maxProd = 0
var maxNums = [0, 0, 0, 0]
var maxR1 = 0
var maxR2 = 0
var maxC1 = 0
var maxC2 = 0
var h = grid.count
var w = grid[0].count
// right
for (r in 0...h) {
for (c in 0..w-5) {
var prod = 1
for (i in c..c+3) prod = prod * grid[r][i]
if (prod > maxProd) {
maxProd = prod
for (n in 0..3) maxNums[n] = grid[r][c+n]
maxR1 = maxR2 = r
maxC1 = c
maxC2 = c + 3
}
}
}
// down
for (c in 0...w) {
for (r in 0..h-5) {
var prod = 1
for (i in r..r+3) prod = prod * grid[i][c]
if (prod > maxProd) {
maxProd = prod
for (n in 0..3) maxNums[n] = grid[r+n][c]
maxR1 = r
maxR2 = r + 3
maxC1 = maxC2 = c
}
}
}
System.print("The greatest product of four adjacent numbers in the same direction (down or right) in the grid is:")
Fmt.print(" $s = $,d", maxNums.map{ |n| n.toString }.join(" x "), maxProd)
System.write(" at indices (one based): ")
for (r in maxR1..maxR2) {
for (c in maxC1..maxC2) Fmt.write("($d, $d) ", r+1, c+1)
}
System.print()
- Output:
The greatest product of four adjacent numbers in the same direction (down or right) in the grid is: 66 x 91 x 88 x 97 = 51,267,216 at indices (one based): (7, 16) (8, 16) (9, 16) (10, 16)
XPL0
int Grid, Max, Prod, I, J, K;
[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]];
Max:= 0;
for J:= 0 to 20-1 do
for I:= 0 to 20-4 do
[Prod:= 1;
for K:= 0 to 4-1 do
[Prod:= Prod * Grid(J,I+K);
if Prod > Max then Max:= Prod;
];
];
for J:= 0 to 20-4 do
for I:= 0 to 20-1 do
[Prod:= 1;
for K:= 0 to 4-1 do
[Prod:= Prod * Grid(J+K,I);
if Prod > Max then Max:= Prod;
];
];
IntOut(0, Max);
]
- Output:
51267216