It has been a while since previous writeup, and even longer since the code was written, thankfully the code was not difficult to decipher.

My thoughts after reviewing them are as follows:

• it is possible to archieve adequate readability and efficienty when writing algorithmic codes in Clojure
• recursion can be beautiful(day 9)
• CSP should be added to more languages!

### Day 7: Recursive Circus

Given a k-way tree: nodes with weights, node’s children list. Which node is the root?

The edges are given in `parent -> [child1, child2, ...]` form, the root node is the only parent that is not at the same time a child, use clojure.set/difference:

``````(let [ls (->> i7 (clojure.string/split-lines) (filter #(clojure.string/includes? % "->")))]
(loop [[line & r] ls
lt #{} rt #{}]
(if (nil? line)
(first (clojure.set/difference lt rt))
(let [[p _ & c] (re-seq #"\w+" line)] ;; parent and children
(recur r (conj lt p) (into rt c))))))
``````

Part 2: only one node has a wrong weight, what’s its correct weight to make the tree balanced?

Definition of “balance tree”:

• if the tree’s root is a leaf node, it’s balanced
• else all child nodes should have the same weight: child node’s own weight, plus all its children’s weight recursively

Typical recursion problem:

• spot the “outstanding” child node `C` by counting weights: if weight W2 occurs more times than W1, then W2 is the correct weight, let the difference `D` be `W1-W2` for now
• then we need to know if `C` itself has wrong weight or one of `C`’s children has
• if all children of `C` share the same weight, then `C`’s weight is wrong, find the correct weight of `C` by applying the difference `D`: `C.weight - D`
• else recur into the outstanding child node of `C`, with the new weight difference `D2` of current level

But code looks different than typical OO languages here, since every object is either a list or a map, I used a string of the root node’s name and a flat map to represent the k-way tree, `node-name -> [weight, [children-names]]`:

``````(defn map7
[ls]
(into {} (for [l ls
:let [[l1 d & r] (re-seq #"\w+" l)]]
[l1 [(bigdec d) r]])))

;; recursion
(let [ls (clojure.string/split-lines i7)
root (find-7root ls) w (map7 ls)] ;; root name and weight map
(loop [node root
d  0] ;; safe to init with arbitrary number
(let [[v children] (w node)
;; build children weight map, find less frequent one
ws (into {} (map #(vector % (sum-weights w %)) children))
fs (frequencies (vals ws))
[[k1 v1] [k2 v2]] (sort-by second fs) ;; sum weight k1 less frequent
wr (first (for [[k v] ws :when (= v k1)] k))] ;; less frequent node name
(if (nil? k2)
;; children are balanced, current node's weight should change by d
(- v d)
;; else k1 be wrong one(less frequent), find its children
(recur wr (- k1 k2))))))
``````

### Day 8: I Heard You Like Registers

No! Not when writing Lisp.

### Day 9: Stream Processing

The recursion code was written by A.I., solves two parts in one pass:

``````(defn score-9
[s ops e l g] ;; e for score, l for level, g for garbage count
(let [[c & r] s
[o & -ops] ops]
(match
[c o]
[nil _]   [e g]
["!" _]   (recur (rest r) ops e l g)  ;; skip next as well
[">" "<"] (recur r -ops e l g)        ;; close garbage
[_ "<"]   (recur r ops e l (inc g))   ;; inside garbage, +g
["{" _]   (recur r (cons c ops) e (inc l) g) ;; out garbage, nest group
["<" _]   (recur r (cons c ops) e l g)      ;; out garbage
["}" "{"] (recur r -ops (+ e l) (dec l) g) ;; close group
:else     (recur r ops e l g)))) ;; between { and < nonsense
``````

### Day 12: Digital Plumber

Given a list of edges(denoted by numbers from 0 to N) in an undirected and possibly cyclic graph, what is the size of the group that contains `0`? How many groups, or connected components, are there?

A graph problem that is typically solved recursively, here’s some efficiency improvements compared with my previous solution, part 1:

``````;; "Elapsed time: 413.881246 msecs"
(defn find-group
[m k]
(loop [q [k]
seen #{k}]
(if (empty? q)
seen
(let [b (peek q) ;; peak vector's back
n (filter #(not (seen %)) (m b))] ;; unvisited neighbours
(recur (into (pop q) n) (into seen n))))))
;; "Elapsed time: 2779.375395 msecs"
(defn find-group-old
[m k]
(loop [s #{k}]
(let [n (into s (mapcat m s))]
(if (= n s)
s
(recur n)))))
``````

Then sacrifice more readability for part 2:

``````;; "Elapsed time: 413.881246 msecs"
(->> (for [n (keys m)] (find-group m n))
(into #{})
(count))

;; "Elapsed time: 40.457927 msecs"
(let [seen (atom #{}) ;; all keys visited
cnt  (atom 0)]
(doseq [k (keys m)
:when (not (@seen k))
:let  [g (find-group m k)]]
(swap! seen into g)
(swap! cnt inc))
@cnt)

;; "Elapsed time: 34.171986 msecs"
(loop [[k & rs] (keys m)
cnt      1
seen     (into #{} (find-group m k))]
(if (nil? rs)
cnt
(if (seen k)
(recur rs cnt seen)
(recur rs (inc cnt) (into seen (find-group m k))))))
``````

I found the sacrifice to be reasonable.

### Day 18: Duet

This is when CSP comes into play:

• 2 workers share the same logic and a atomic counter
• workers are initialized with different args: PID, 2 channels for write-to and read-from
• workers communicate with each other using channels: `write` to a buffered one, `read` blockingly using an unbuffered one
• use another `core.async/loop` as “supervisor” to detect deadlock
``````(let [ops (read-lines "resources/2017/i18.txt")
m1 (atom 0) m2 (atom 0) ;; queue max size counter, debug purpose

;; nearest "integer" larger than max queue size is 128 for my input
;; queues for 2 programs
ch1r (a/chan) ch1w (a/chan 128)
ch2r (a/chan) ch2w (a/chan 128)

;; running state atom, counter for send
r1 (atom true) r2 (atom true)
cnt (atom {0M 0 1M 0})]

;; this dispatchs message and records maximum write buffer size
(a/go-loop []
(when (or @r1 @r2)
(a/alt!
ch2w ([v]
(when-let [c (.count (.buf ch2w))]
(if (> c @m2) (reset! m2 c)))
(a/>! ch1r v))
ch1w ([v]
(when-let [c (.count (.buf ch1w))]
(if (> c @m1) (reset! m1 c)))
(a/>! ch2r v)))
(recur)))
;; start worker with their own id and queues
(op18-loop! ops 0M r1 cnt ch1r ch1w)
(op18-loop! ops 1M r2 cnt ch2r ch2w)

;; wait for block for 3 seconds
(loop [i 0
rt 3]
(a/<!! (a/timeout 1000))
(infof "queue 1 %s, queue 2 %s, sent counts %s"
(.count (.buf ch1w)) (.count (.buf ch2w)) @c)
(infof "queue 1 max len %s, queue 2 max len %s"
(inc @m1) (inc @m2))
(when (= i rt) ;; close workers' loop and dispatch loop
(reset! r1 false)
(reset! r2 false))
(if (< i rt)
(recur (inc i) rt))))

;; 2nd line explains 128
2022-05-25T05:13:30.253Z DESKTOP-AE88V45 INFO [advent.2017:664] - queue 1 91, queue 2 31, sent counts {0M 6344, 1M 6250}
2022-05-25T05:13:30.255Z DESKTOP-AE88V45 INFO [advent.2017:666] - queue 1 max len 124, queue 2 max len 104
2022-05-25T05:13:31.256Z DESKTOP-AE88V45 INFO [advent.2017:664] - queue 1 0, queue 2 0, sent counts {0M 6985, 1M 6858}
``````