Euler Problem 11

In the 20×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 × 63 × 78 × 14 = 1788696.

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

Problem 11 is another exercise in map-reduce, though the diagonal option adds an interesting twist to mapping all the combinations. First parse the input into two dimensional array:

s = <large string of numbers>
 
a = s.split("\n").map{|s| s.split(" ")}
a = a.map{ |r| r.map{ |s| s.to_i } }

Horizontal and vertical groups of 4 can be constructed with each_cons. Horizontal groups are constructed by calling each_cons on every row, and concat each rows list of lists. Vertical groups are
constructed by calling each_cons on the rows and zipping the rows in each group together.

row_groups = a.map{ |r| r.each_cons(4).to_a }.reduce(:+)
col_groups = a.each_cons(4).map{ |g| g[0].zip(*g[1..-1]) }.reduce(:+)

Diagonal groups can be constructed in a similar fashion to the vertical groups, but require an extra step to shift the rows in each group so zip will construct a diagonal. Using each_with_index, I modified the rows in each group so that the fist row was complete, the second row skipped the first number, the third row skipped the first two numbers and the fourth row skipped the first three numbers. Zipping them together creates down-left diagonal groups. The down-right diagonal groups are similar, but drop three numbers from the first row, two from the second etc.

diag_groups1 = a.each_cons(4).map{ |g|
    g2 = g.each_with_index.map{|r,i| r[i..-1] }
    g2[-1].zip(*g2[0..-2])
}.reduce(:+)
 
diag_groups2 = a.each_cons(4).map{ |g|
    g2 = g.each_with_index.map{|r,i| r[(3-i)..-1] }
    g2[0].zip(*g2[1..-1])
}.reduce(:+)

Finally, finding the largest product is a simple matter of mapping the “*” operator across all the groups and reducing with max:

groups = row_groups + col_groups + diag_groups1 + diag_groups2
puts groups.map{|g| g.reduce(:*)}.max

Putting it all together:

s = "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"
 
a = s.split("\n").map{|s| s.split(" ")}
a = a.map{ |r| r.map{ |s| s.to_i } }
 
row_groups = a.map{ |r| r.each_cons(4).to_a }.reduce(:+)
col_groups = a.each_cons(4).map{ |g| g[0].zip(*g[1..-1]) }.reduce(:+)
 
diag_groups1 = a.each_cons(4).map{ |g|
    g2 = g.each_with_index.map{|r,i| r[i..-1] }
    g2[-1].zip(*g2[0..-2])
}.reduce(:+)
 
diag_groups2 = a.each_cons(4).map{ |g|
    g2 = g.each_with_index.map{|r,i| r[(3-i)..-1] }
    g2[0].zip(*g2[1..-1])
}.reduce(:+)
 
groups = row_groups + col_groups + diag_groups1 + diag_groups2
puts groups.map{|g| g.reduce(:*)}.max

About this entry