I’m particularly fond of using threading macros in Clojure, as they make it easy to follow and express input transformations step by step. It’s interesting how this preference can sometimes lead to tunnel vision, preventing me from noticing simpler solutions.
For example, consider this implementation:
(->> lists
(map sort)
(apply map list)
(reduce (fn [s p] (+ s (abs (apply - p)))) 0))Here, there’s a transposing step to create a list of pairs from two lists
((apply map list)), but it’s somewhat redundant since the operations in
reduce can be performed directly without transposing:
(->> lists
(map sort)
(apply #(mapv (comp abs -) %1 %2))
(apply +))Finally, stepping away from the threading mindset and flipping the logic upside down reduces this to a one-liner:
(reduce + (mapv (comp abs -) (map sort lists)))Now – I like it because it’s consise and I already know the logic, but is it more readable?
I completely forgot about frequencies – honestly, I was surprised such an obvious utility hadn’t already been implemented… Naturally, this:
(->> right (reduce (fn [m e] (update m e (fnil inc 0))) {}))can be replaced with the much simpler:
(frequencies right)and then redundant threading becomes:
(reduce (fn [s n] (+ (* n (fqs n 0)) s)) 0 left)Initial 0 in reduce can be eliminated by using transducer that maps
over the first list:
(transduce (map #(abs (* % (fqs % 0)))) + left)Once again, I like the transducer version when I see it – no need for a redundant initial step, and no need for an explicit fn declaration. That said, “transductions” still bend my mind a bit!
P.S. I’m still glad I wrote my version of frequencies. It gave me the
opportunity to discover fnil which combined with update, provides
functionality similar to Python’s defaultdict: (update MAP key (fnil inc 0)).
In my first approach, I used a straightforward loop:
(loop [[op & xs] ops, enabled true, sum 0]
(if (nil? op) sum
(condp = op
"do()" (recur xs true sum)
"don't()" (recur xs false sum)
(recur xs enabled (cond-> sum (or enabled (= part 1)) (+ (mul op)))))))Here, ops is a list of all occurrences of “muls”, “dos”, and
“don’ts”. It’s still quite verbose with three recur calls. The mul
function computes the product of integers extracted from the matching
strings.
Wanting a more concise solution, I initially tried to write smarter regexes. However, this quickly led to the classic “now you have two problems” scenario. As it turns out, the simpler solution wasn’t about designing a better regex to catch what I needed but to remove irrelevant parts of the input using one.
So the trick fo part 2 is (str/replace s #"(?s)don't\(\).*?(do\(\)|\Z)" "").
Here’s how it works:
(?s)enables dot-matches-all mode, allowing.to match any character, including newlines (\n)..*?matches zero or more of any character, non-greedily.(do\(\)|\Z)matchesdo()or the end of input (\Z).
Using this cleanup step, the revised solution looks like this:
(defn clear-donts [s] (str/replace s #"(?s)don't\(\).*?(do\(\)|\Z)" ""))
(defn solve [input part]
(let [ops (re-seq #"mul\(\d+,\d+\)" (cond-> input (= part 2) clear-donts))
mul #(apply * (map read-string (re-seq #"\d+" %)))]
(->> ops (map mul) (apply +))))For now I keep ugly notes with a working solution… Would like to
refactor the diag(onal) transposition function and use it in the part
2, along with juxt.
That was fun! I got to a working solution pretty quickly with loops
and checking pages ordering by using set/intersection of rules for
given page and pages preceding it. But then, after staring at both
parts for a while, I’ve just realized that the only thing I need is
actually the simple comparator used to sort the pages #(not (contains? (RUL %2) %1))
– by comparing sorted pages to original pages I know
which should go to which part of the solution, the rest is simple
reduction.
Dijkstra is faster here (0.1 sec vs 0.15 using only bfs for both
parts), but after all I decided to refactor using only bfs for
simplicity. Also it looks like second part can be brute-forced, but
due to some typos in my initial implementation I thought it would be
running forever, hence implemented binary search…
(defn shortest-path [bytes [X Y :as exit] cut]
(let [BYT (set (take cut bytes))]
(loop [Q (priority-map [[0 0] #{[0 0]}] 0), best Integer/MAX_VALUE, score-map {}]
(if (empty? Q) (dec best)
(let [[[pos seen] _] (peek Q)]
(if (= pos exit) (recur (pop Q), (min (count seen) best), score-map)
(let [[mvs scs]
(reduce
(fn [[mv bs] [x y :as pos]]
(let [s (count seen)]
(if (and (<= 0 x X) (<= 0 y Y)
(not (contains? BYT pos)) (not (contains? seen pos))
(< s (score-map pos Integer/MAX_VALUE)))
[(conj mv [[pos (conj seen pos)] s]) (assoc bs pos s)]
[mv bs])))
[[] score-map] (t/moves pos))])))))))Another memo day. I got an over-complicated solution for part one (priority maps fixation after previous days, I guess…) – it was giving the right answer, however the run was not finishing due all possible combinations:
(fn [init]
(loop [Q (into (priority-map) (map (fn [n] [[(subs init 0 n) 0] (- (count init) n)]) pos)),
steps 0]
(cond
(= steps 120) false ; 120 was enough for me, but this should've been
; an indicator than I should be looking for something better...
(empty? Q) false
:else
(let [[[s idx] left] (peek Q)
c (count s)]
(if (contains? (px c) s)
(if (zero? left) true
(recur
(into (pop Q)
(map (fn [n]
[[(subs init (+ idx c) (+ idx c n)) (+ idx c)]
(- left n)])
(remove #(> % left) pos))),
(inc steps)))
(recur (pop Q) (inc steps)))))))Obviously it wasn’t working for part 2. Wanted to refactor the above
to use “keep state” map, but it was, again, over complicated. Finally
started from scratch with memoize and more elegant string processing
using starts-with? instead of a set lookup for a slice. Code for part 2 was
basically the same (instead of getting “some”, i. e. any, we need to
get “all”), I used the final version to solve both parts.
(def p1
(memoize
(fn [cur pats]
(if (empty? cur) 1
(some
(fn [s]
(when (starts-with? cur s)
(p1 (subs cur (count s)) pats))) pats)))))