What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 x 20 grid?
Permalink: http://projecteuler.net/problem=11
In the 20 x 20 grid below, four numbers along a diagonal line have been enclosed into square brackets
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 the same direction (up, down, left, right, or diagonally) in the 20 x 20 grid?
First step is pretty routine, we need to create such grid representation in our program from file. For the way how we read files refer Clojure Euler: Problem 008, we have similar problem there.
(defn get-matrix []
(map #(Integer/parseInt (apply str %))
(partition 2 2 (remove #(or (= \newline %) (= \ %))
(seq (slurp "res/problem011.txt"))))))
Idea is following: read the file, drop the garbage, take all two-digit combinations, concat each and transform to the integer.
To make things simple we reading the numbers in one-dimensional list of size 20 x 20 = 400. We always can use formula to represent two dimensional indexing for one-dimensional array and vice versa.
Example: suppose you need a 3 x 3 matrix A
9 2 4
6 1 7
5 3 8
You can flat it into 1D array B
9 2 4 6 1 7 5 3 8
Now, when you want A[i][j] use the formula i * size_j + j, where size_j
is second matrix dimension. Therefore A[1][2] = B[1 * 3 + 2] = B[5] = 7, what is correct.
Implementing that in clojure gives one indexing function
(defn get-at [i j matrix]
(if (and (>= i 0) (< i 20) (>= j 0) (< j 20))
(nth matrix (+ j (* i 20))) 0))
We check the boundaries of array inside this function, which can be inappropriate in many cases, but it is good as we use it in one place.
Ok. We have data, we have methods operate this data, now let’s code logic. Our good friend - bruteforce.
(let [matrix (get-matrix)
ways (for [i (range 20) j (range 20)]
[(map #(get-at i (+ % j) matrix) (range 4))
(map #(get-at (+ % i) j matrix) (range 4))
(map #(get-at (+ % i) (+ % j) matrix) (range 4))
(map #(get-at (+ % i) (- j %) matrix) (range 4))])]
(reduce max (map #(reduce * %) (reduce concat ways))))
We iterate on all matrix elements as start of 4-element range.
We have 4 conditions, each of them represents some direction. All these 4 directions represent all possible direction in grid.
S S * * * S S
* * *
* * *
* * *
S is for start
If we obtain all possible 4-element ranges for matrix, just find maximum of product.
Problem solved!
P.S. Boring problem. I think it just for introducing matrices computation.
mishadoff 18 January 2013