Discussion on: AoC Day 2: Inventory Management System

I did my solutions at midnight last night, but I was surviving on very little sleep at the time, so the resulting code was below standard. I tried again this morning and felt better about it.

For anyone reading this, I'm still using the simple lines function from Day 1 which reads a file into a sequence of strings.

Part 1

This was my solution last night:

(defn nums [s]
  (let [cs (->> s
                (group-by identity)
                vals
                (map count))]
    [(some #(= 2 %) cs) (some #(= 3 %) cs)]))

(defn star
  [input-file]
  (let [tt (->> (lines input-file)
                (map nums))]
    (* (count (filter first tt)) (count (filter second tt)))))

This is embarrassing code. I totally forgot about the frequencies function, which is why I used group-by followed by count. But the 2 filter operations in the final calculation meant that the results of the map get processed twice.

My morning attempt fixed these:

(defn counts [[two-count three-count] s]
  (let [cs (-> s frequencies vals)]
    [(if (some #(= 2 %) cs) (inc two-count) two-count)
     (if (some #(= 3 %) cs) (inc three-count) three-count)]))

(defn star
  [input-file]
  (let [[two-count three-count] (->> (lines input-file) (reduce counts [0 0]))]
    (* two-count three-count)))

This time I accumulated the 2/3 count values while processing the list, so it only goes through it once.

Part 2

Since each element needs to be compared to every other element, I can't see any way around the O(n² ) complexity. Of course, each element should only be compared to the ones after it, so as to avoid comparing each one twice (since comparing A/B has the same result as comparing B/A).

When doing list processing, the only ways I know to refer to everything following an element are by using indexes (yuck) or with a loop. Unfortunately, I got fixated on the loop construct, and nested it:

(defn close [a b]
  (let [sim (filter identity (map #(when (= %1 %2) %1) a b))]
    (when (= (count sim) (dec (count a))) sim)))

(defn cmp-close [ll]
  (loop [[f & fr] ll]
    (when (seq fr)
      (or
        (loop [[s & sr] fr]
          (when s
            (or (close f s)
                (recur sr))))
        (recur fr)))))

(defn star2
  [input-file]
  (let [ll (lines input-file)]
    (apply str (cmp-close ll))))

The other way you can tell that I wrote this on very little sleep was the use of ridiculously terse var names.

On reflection this morning, I realized that the inner loop should have been a some operation. This does a predicate test and terminates processing early, which is what I was doing manually with the inner loop.

Also, my close function has several issues. First is the name! I was thinking of "A is close to B", but when I saw it again this morning I realized that it's the same function name for closing a resource. Something else that bothers me is that it processes the entirety of each string before returning, when a false result can usuall terminate early. Finally, a minor issue is that the anonymous function #(when (= %1 %2) %1) would be more idiomatic to use a singleton set on %1 to compare to %2.

(defn nearly= [left right]
  (let [same (filter identity (map #(#{%1} %2) left right))]
    (when (= (count same) (dec (count left))) (apply str same))))

(defn compare-lines [ll]
  (loop [[line & xlines] ll]
    (when (seq line)
      (or
       (some (partial nearly= line) xlines)
       (recur xlines)))))

(defn star2
  [input-file]
  (compare-lines (lines input-file)))

The nearly= function now returns a string, rather than the array of characters, but hasn't changed much. I was still unsatisfied with it not terminating the test early, so I rewrote it to be faster. However, the resulting code lacks any kind of elegance, and I'm not convinced that it's worth the effort:

(defn nearly= [left right]
  (loop [[l & xl] left [r & xr] right diffs 0]
    (if (nil? l)
      (apply str (filter identity (map #(#{%1} %2) left right)))
      (if (not= l r)
        (when (zero? diffs)
          (recur xl xr 1))
        (recur xl xr diffs)))))

Hopefully I'll get some sleep before attempting day 3. 😊