This is my solution to Problem 11 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 11 of Project Euler is described as:

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 any direction (up, down, left, right, or diagonally) in the 2020 grid?

I looked into using Incanter but didn’t get it setup as I am using Clojure 1.4, and had some issues getting the dependencies resolved. No big deal though, as I just used a vector of vectors to represent a matrix. I created a new file matrix.clj, which got the namespace definition for project-euler.matrix.

(ns project-euler.matrix)

The first function I defined was `transpose`

, since I am going to want to work against the columns, but rows are easier to think about and work with.

(defn transpose [m] (vec (apply map vector m)))

Since I am going to need to find groups of four numbers in the matrix, I defined the following to functions to get all possible groups of four in the rows, and in the columns.

(defn partition-rows [m n step] (if (= (count m) 0) [] (concat (partition n step (first m)) (partition-rows (rest m) n step)))) (defn partition-columns [m n step] (partition-rows (transpose m) n step))

The `partition-rows`

function just concats the results of calling partition on each row with the group size, `n`

, and the step, by calling partition on the first row of the matrix `(first m)`

, and then calling `partition-rows`

again with the remaining rows in the matrix given `(rest m)`

. The function `partition-columns`

simply transposes the matrix `m`

and then calls `partition-rows`

with that matrix.

The next two functions are two helper functions, which were defined after writing some of the following functions, and exist to better express intent.

(defn matrix-get [m r c] (nth (nth m r) c)) (defn row [m n] (nth m n))

The function `matrix-get`

gets the `r`

th row from the matrix `m`

and then gets the `c`

th item in that row. The function `row`

gets the row for a matrix. Again nothing special about these functions except that they help to communicate the intent, and give the concept a name. These were littered around the code so the functions were created as part of tidying up. In looking at it as I was writing up this post, I realized I still didn’t pull out the concept of row in the function `matrix-get`

, and the two functions should probably be defined as follows instead:

(defn row [m n] (nth m n)) (defn matrix-get [m r c] (nth (row m r) c))

Working through getting the diagonals, I posted a call for help about a clean way to get the diagonals for a matrix in the post Smelly matrix diagonals. I got some good comments, and after taking a bit to pick apart the functions, I went with the following from the comments, thanks to Mark.

(defn diagonals [m] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(+ r (- cdim c)) [(matrix-get m r c)]}) (apply merge-with into) vals)))

This worked great, but I also needed to get the diagonals going from the bottom left to the top right, which resulted in the function `reverse-diagonals`

.

(defn reverse-diagonals [m] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(+ r c) [(matrix-get m r c)]}) (apply merge-with into) vals)))

As this was almost the same function as diagonals, with just a different function for getting the key, so I extracted a function `matrix-lines`

which resulted in:

(defn matrix-lines [m f] (let [rdim (count m) cdim (count (first m))] (->> (for [r (range rdim), c (range cdim)] {(f rdim cdim r c) [(matrix-get m r c)]}) (apply merge-with into) vals))) (defn diagonals [m] (matrix-lines m (fn [rdim cdim r c] (+ r (- cdim c))))) (defn reverse-diagonals [m] (matrix-lines m (fn [rdim cdim r c] (+ r c))))

Where the function `matrix-lines`

will generate the lines based off of a function to generate a key for a given cell.

I have seen that it is idiomatic Clojure code to use `_`

s to signify function variables that are not used, so looking at this with some fresh eyes, should those variables defined in the functions `diagonals`

and `reverse-diagonals`

be an `_`

instead, even though they are the first bindings to the function?

The last part of working with the matrix that I needed were functions to partition the diagonals, and get all the partitioned diagonals in both directions.

(defn partition-diagonals [m n diagonals-fn] (apply concat (map #(partition n 1 %) (diagonals-fn m)))) (defn partition-every-diagonal [m n] (concat (partition-diagonals m n diagonals) (partition-diagonals m n reverse-diagonals)))

The function `partition-diagonals`

returns the result of `concat`

ing every resulting seq from calling `partition`

on every result of call the `diagonals-fn`

which is the function to get the diagonals that was passed in as the second parameter. The function `partition-every-diagonal`

simply `concat`

s the results of calling `partition-diagonals`

with the functions `diagonals`

and `reverse-diagonals`

.

(defn problem11 [] (let [m [[ 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 4 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]]] (apply max (map multiply (concat (partition-rows m 4 1) (partition-columns m 4 1) (partition-every-diagonal m 4))))))

The function `problem11`

applys the function `max`

to the result of calling `multiply`

on every possible partition of the matrix m, to get largest multiple of ‘four adjacent numbers in any direction’.

So far, this has been the Project Euler problem with the most code that was needed to solve the problem, including the ones I have solved but not posted answers to yet. While overall this is still not a great deal of code, I am wondering if there are any things that I am missing that might make this even more concise and expressive.

Is there anything that I have missed? Anything interesting in my approach? Again, I thank you in advance for any comments that you might have on this.

Thanks again,

–Proctor

Pingback: Project Euler in Clojure – Problem 10 « Proctor It