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}