# Clojure Euler: Problem 011

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?

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.

1. NORTH -> SOUTH (Up & Down covered)
2. WEST -> EAST (Left & Right covered)
3. NW -> SE (backslash diagonals covered)
4. NE -> SW (slash diagonals covered)
``````    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!

github

P.S. Boring problem. I think it just for introducing matrices computation.

18 January 2013