Looking back, I think I misinterpreted this problem but accidentally get the right answer anyway.
Rather than treat the numbers as a 2D grid, I treated them as long 1D vector. My thought was that I could then write a very simple definition for runs of numbers in each of the directions (up, down, left, right, and the two diagonals), and leverage clojure’s sequence libraries to easily achieve my task. Yes, it would mean that numbers could ‘wrap’ around the left/right edges, but I thought that might be tolerably within bounds of the problem’s definition.
(defn euler-11 [run grid]
"Returns the product of largest 'run' of numbers (in any direction) of
length run in square matrix 'grid'."
(let [take-em (fn [every qty coll]
(for [start (range (count coll))]
(take qty (take-nth every (drop start coll)))))
len (int (Math/sqrt (count grid)))
updn (take-em len run grid)
ltrt (take-em 1 run grid)
ldiag (take-em (- len 1) run grid)
rdiag (take-em (+ len 1) run grid)]
(reduce max (map #(reduce * %) (concat updn ltrt ldiag rdiag)))))
(euler-11 4 [ 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 40 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])Looking back, I can see that my assumption about ‘wrapping’ was incorrect: left-to-right runs of numbers do not wrap properly around the left/right boundary and will be split across two different rows. This is bad enough and can not really be argued to be ‘wrapping’ in the sense that most people would mean. Worse, none of the vertical numbers wrap from top to bottom, either. So not only is the left-right wrapping incorrect, it’s inconsistent with the top-bottom wrapping!
To fix the above definition, I see a few ways to go about building those runs of 4 numbers.
- Allow wrapping around the edges of the graph
- Exclude solutions that wrap around the edges
- Expand the graph by padding all sides with zeros
I’ll go with option #3.
(def *grid* [ 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 40 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])
(defn euler-11b [m n grid rl]
"Returns the product of largest 'run' of runlength 'rl' numbers,
starting at each element and going in any direction,
in the m rows by n cols matrix 'grid'."
(let [at (fn [r c] (if (and (< r m) (< c n) (>= r 0) (>= c 0))
(nth grid (+ c (* n r)))
0))
runs (for [r (range n)
c (range m)]
[(map #(at r (+ % c)) (range rl)) ; rightward
(map #(at (+ % r) c) (range rl)) ; downward
(map #(at (+ % r) (+ % c)) (range rl)) ; right diag
(map #(at (+ % r) (- c %)) (range rl))])] ; left diag
(reduce max (map #(reduce * %) (reduce concat runs)))))
(euler-11b 20 20 *grid* 4)As for other people’s solutions, I see that my solution was fairly close to Chouser’s, albeit without the string to integer conversion that he performed. It’s interesting to see that some people chose to immediately perform the multiplication on the runs of four numbers, while other people (like me) chose to keep them around and perform the (reduce * ...) in the final step. For performance the former is doubtless superior, but for re-usability the latter will probably be more advantageous.