It’s that time of the year again! Head for Advent of Code 2021. This year’s theme is also Clojure.
It’s important to break down a task into sub-problems and solve each with a function. There is a reason it’s called functional programming.
First is the function to check if a board’s condition is enough to win. Additional tranpose functionality is added to deal with the 2d matrix.
(defn transpose [m]
(apply mapv vector m))
(defn win?
[board]
(or
(some true? (map #(every? true? %) board))
(some true? (map #(every? true? %) (transpose board)))))My first thought when approaching the problem was:
(for [guess guesses]
(for [board boards]
(for [row board]
(for [num row]
;; ...
))))As you see I was trying to code into a triangular shape.
Inside nested loop I was trying to check winning condition and complicated modification logic.
To break the loop when the winning condition is met is also a big problem.
I even thought of modifying the variable boards by assoc-in. That’s not an idiom of functional programming.
This is a sign to break down the problems. I have to make the code as flat as possible.
So I divided into sub-problems to deal with individual board, and then individual row:
(defn mark-row
"Mark a row with all the numbers equal the guess to true."
[row guess]
(map
#(if (= % guess) true %)
row))
(defn mark-board
"Mark a board with all the numbers equal the guess to true."
[board guess]
(map
#(mark-row % guess)
board))To solve early break problem I use loop:
(loop [boards boards
guesses guesses]
(let [guess (first guesses)
boards (map #(mark-board % guess) boards)
win-board (some #(if (win? %) %) boards)]
(if win-board
;; break here
[win-board guess]
(recur boards (rest guesses)))))Generate a 2d diagram:
(def diagram
(into [] (repeat n
(into [] (repeat n 0)))))It’s necessary to use (into [] ...) since I can only modify elements in a vector using update-in.
Since x1 can be larger than x2 (so does y1 and y2) so I wrote a helper to generate a range which does not care about the direction:
(defn gen-range
"Helper to generate a range, either from smaller number to larger number
or from larger number to smaller number."
[a b]
(if (< a b)
(range a (inc b))
(range a (dec b) -1)))Again, I broke down the problem into a sub-problem of marking a diagram with a list of coordinates [x y]:
(defn mark-diagram-with-coords
"Mark diagram from a list of coords [x y]"
[diagram coords]
(reduce
(fn [res [x y]]
(update-in res [y x] inc))
diagram
coords))So I can concentrate on the logic of making the slice of coordinates:
(defn mark-diagram
"Mark diagram derived from a couple of coord [x1 y1 x2 y2]"
[diagram couple-coord]
(let [[x1 y1 x2 y2] couple-coord]
(if (= y1 y2)
;; horizontally
(mark-diagram-with-coords
diagram
(map #(vector % y1) (gen-range x1 x2)))
;; vertically
(mark-diagram-with-coords
diagram
(map #(vector x1 %) (gen-range y1 y2))))))Part 2 is just a piece of cake by building up from the solution of part 1:
(defn mark-diagram-2
[diagram couple-coord]
(let [[x1 y1 x2 y2] couple-coord]
(if (or (= x1 x2)
(= y1 y2))
(mark-diagram diagram couple-coord)
;; diagonally
(mark-diagram-with-coords
diagram
(zipmap (gen-range x1 x2) (gen-range y1 y2))))))In part 1, by using loop I can filter from the start:
(loop [diagram diagram
couple-coords (filter (fn [couple-coord]
(let [[x1 y1 x2 y2] couple-coord]
(or (= x1 x2)
(= y1 y2))))
couple-coords)]
;; ...
)My initial brute force solution is to store all the fishes, and then count!
(def fishes
(reverse (map
#(Integer/parseInt %)
(str/split input #"[,|\n]"))))
(defn tick-one-day
"What will happen to the fish after one day?"
[fishes]
(let [dec-fishes (map dec fishes)
n-new-fishes (count (filter #(= -1 %) dec-fishes))
new-fishes (reduce
#(cons %2 %1)
dec-fishes
(repeat n-new-fishes 8))]
(map #(if (= -1 %) 6 %)
new-fishes)))I learned a tip for repeatedly applying one function to the fishes each day (using iterate):
(defn fishes-after-n-day
[fishes n]
(first
(drop n
(take (inc n) (iterate tick-one-day fishes)))))
(count (fishes-after-n-day fishes 80))80 days are fine, but the memory grew very quickly for 256 days in the problem 2. And it would take ages (e.g. 26984457539 fishes in the result) to count.
So I have to change the strategy. Instead of storing the fishes, I store the frequencies of the timers from 0 to 8.
(def timers
(reduce
(fn [res i]
(update res i inc))
(into [] (repeat 9 0))
fishes))
;; => 0 1 1 2 1 0 0 0 0After each day, we shift the timers vector to the left position (i.e. each timer’s value decreases by 1). Note that 0 turns to 6, and the new number of 8 are added equal the number of 0.
(defn shift-left
"Shift the timers to the 'left', corresponding to one day,
Increase in the new timers: #6 and #8 by the original #0.
e.g. 1 1 2 1 0 0 0 0 0 => 1 2 1 0 0 0 1 0 1"
[orig]
(let [n-0 (first orig)
new (conj (into [] (rest orig)) n-0)]
(update new 6 + n-0)))We simply sum all the numbers in the internal timers to get the number of fishes:
(defn timers-after-n-days
[timers n]
(first
(drop n (take (inc n)
(iterate shift-left timers)))))
(apply + (timers-after-n-days timers 80))Problem 2 is now so easy, with no additional space:
(apply + (timers-after-n-days timers 256))Space: O(1)
Time: O(n)
No special trick needed, I brute force to calculate the fuels needed for each position. Time: O(n^2).
Part 1 is easy since you only care about the length of each output values that would match 2, 3, 4, 7 (which would render 1, 7, 4, 8).
(count
(filter (fn [num]
(some #{num} #{2 3 4 7}))
;; ...
))On part 2, there are 3 possibilities for each of 5-segments and 6-segments. To deduce the correct number, we have minus the set difference between the current string and one of 1, 7, 4, 8 (which have the corresponding length of 2, 3, 4, 7).
0: 1: 2: 3: 4: aaaa .... aaaa aaaa .... b c . c . c . c b c b c . c . c . c b c .... .... dddd dddd dddd e f . f e . . f . f e f . f e . . f . f gggg .... gggg gggg .... 5: 6: 7: 8: 9: aaaa aaaa aaaa aaaa aaaa b . b . . c b c b c b . b . . c b c b c dddd dddd .... dddd dddd . f e f . f e f . f . f e f . f e f . f gggg gggg .... gggg gggg
First, we have to deduce 1, 7, 4, 8.
- How to deduce 0, 6, 9 from the strings which have the same lengths of 6?
Minus 1-string:
- Length 5: 6
- Length 4: 0 or 9. Minus 4-string:
- Length 3: 0
- Length 2: 9
- How to deduce 2, 3, 5 from the strings which have the same lengths of 5?
Minus 1-string:
- Length 3: 3
- Length 4: 2 or 5. Minus 4-string:
- Length 3: 2
- Length 2: 5
Some lessons learned from Clojure:
zipmapreturns a map, so the order would be different.- Equivalence to
zip(inPython) is:
(map vector patterns outputs)Finding low points in part 1 is straightforward. Breaking down to subproblems, again, is a huge help for part 2.
- Function to support find all adjacent coorindates:
(defn adjacent-coords
"Given a (y, x) coordinate, return list of current coordinate and
4 adjacent coordinates: u, d, l, r"
[coord]
(let [[y x] coord]
(filter
#(not (= coord %))
[[(max 0 (dec y)) x]
[(min (dec limy) (inc y)) x]
[y (max 0 (dec x))]
[y (min (dec limx) (inc x))]])))- Function to get the value given the coordinate:
(defn cell-value
"Return the cell value from [y x] coord"
[coord]
(let [[y x] coord]
(nth (nth locations y) x)))In problem 2, from the low points found in part 1, we can expand them outward and then count all the coordinates to get the size of basins. This is a typical DFS problem.
(defn dfs
"Expand the basin from a [y x] coord."
[coord]
(loop [stack (list coord)
visited #{}]
(if (empty? stack)
visited
(let [cur-coord (peek stack)
new-stack (pop stack)]
(if (contains? visited cur-coord)
(recur new-stack visited)
(let [new-visited (conj visited cur-coord)
cur-value (cell-value cur-coord)
adjacent-pos (filter
#(and (< (cell-value %) 9)
(not (contains? visited %)))
(adjacent-coords cur-coord))]
(recur (apply conj new-stack adjacent-pos)
new-visited)))))))At first, I misunderstood the problem’s constraints:
- Value including in one basin must < 9
- Value doesn’t have to be difference by 1
And I have to refer to one solution on Reddit to find out my mistakes.