As I am working on Problem 11 in Project Euler, I am trying to use a matrix and some functions against that matrix to help me solve the problem. I spent a bit of time browsing incanter and its documentation, but did not see anything that would give me what I was looking for.
The particularly nasty function I am encountering is finding all of the diagonals in a matrix. Given a matrix of
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
I am would expect the following sequence of vectors:
[1 6 11 16] [2 7 12] [3 8] [4] [5 10 15] [9 14] [13]
Where I think the nasty-ness is coming from is that function is seeming very imperative, and it seems like there should be a much more elegant solution to this, but I am currently not seeing it. In addition to what seems to be a large smell in the code, what makes me think I am doing something “wrong” for Clojure is having seen the elegant solution to Conway’s Game of Life in Programming Clojure which can be found at Github. In the book they take an imperative implementation from another language into Clojure, and then they show a functional solution which turns the imperative version on its head and spins it like a top.
Here is what I came up with, and I can only assume that others would think there is a large smell to this as well.
(defn diagonals [m]
(let [rdim (count m)
cdim (count (first m))]
(loop [diags []
roff 0
coff 0]
(cond (>= coff cdim) (recur diags (inc roff) 0)
(>= roff rdim) diags
:else (recur
(concat diags
(conj []
(for [i (range 0 (min (- rdim roff) (- cdim coff)))]
(matrix-get m (+ roff i) (+ coff i)))))
roff
(if (zero? roff) (inc coff) cdim))))))
Even as I was writing this function, I could tell that it is doing way to much work in it, and that it is not very composable, nor does it seem to take advantage of much composability. As a side note, one of the things that was also a large sign that I was doing something “wrong” for Clojure, was that it was difficult to incrementally develop, modify, and debug in the REPL.
I would love some suggestions on how to give this code a good scrubbing, and clean up this function.
Thanks in advance,
–Proctor
I would write it like this:
(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 should work:
(defn diagonals [m]
(let [rdim (count m)
cdim (count (first m))]
(for [x (range (- 1 rdim) cdim)]
(for [y (range (max 0 (- x)) (min rdim (- rdim x)))]
(matrix-get m y (+ x y))))))
I would solve this specific problem by setting up a lazy sequence where all the possible 4-rows where sort of “enumerated”. This would mean all horizonal 4-rows concated with the vertical and then the diagonal ones in each direction.
Then the task would be just to identify the largest product of these 4-rows.
The diagonal 4-rows could be indexed by taking a suitable submatrix (ie one that were 3 of the rows and 3 of the cols was not looped through) and read the values in (0,0), (1,1), (2,2), (3,3) relative to the current (x,y)-coordinate.
There are some 2d primitives in clojure, but it’s quite easy to construct a possibly low performant one yourself out of nested vectors. I don’t see that incanters matrix library would be especially suitable for this task – it’s no certainly complex math involved, really. Hope this doesn’t spoil the fun! glhf!
Here’s my take on it. Basically, you want to shift left each vector inside the matrix by it’s matrix index, padding with nils. Then you want to transpose it.
(def matrix
(partition 4 (range 1 17)))
(defn rotate
“Rotates sequence with wrap-around”
[n seq]
(let [l (count seq)]
(take l (drop (mod n l) (cycle seq)))))
(defn diagonals
“Returns a sequence of diagonals of square matrix”
[m]
(let [l (count (first m))
pad (partial concat (repeat (dec l) nil))]
(apply map
vector
(map #(rotate %1 (pad %2)) (range l) m))))
(diagonals matrix)
The rotate sequence can be useful on it’s own, so I pulled it out of the main function.
Pingback: Project Euler in Clojure – Problem 11 « Proctor It