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 rth row from the matrix m and then gets the cth 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 concating 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 concats 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