Advent of Code 2018 - Day 2

Welcome back! Today, we're continuing the Advent of Code challenges. I found these challenges through the awesome people I've found at the dev.to community, which has been embracing these challenges, providing discussion boards, and more.

Day 2, Problem the First

The long-and-short of the second day's problem is thus:

You are given a list of box IDs, which are series of letters. In order to verify the contents of the boxes in total, you count the number of IDs with "exactly two of any letter", and separately count "exactly three of any letter" to make a checksum of the values. Using the example from the problem statement:

For example, if you see the following box IDs:

  1. abcdef contains no letters that appear exactly two or three times.
  2. bababc contains two a and three b, so it counts for both.
  3. abbcde contains two b, but no letter appears exactly three times.
  4. abcccd contains three c, but no letter appears exactly two times.
  5. aabcdd contains two a and two d, but it only counts once.
  6. abcdee contains two e.
  7. ababab contains three a and three b, but it only counts once.

As a result, we have four IDs which contain exactly two repeated letters (2, 3, 5, and 6), and three IDs which contain three repeats (2, 4, 7). If you multiply these values together 4 x 3 = 12, so 12 is your checksum value. You are now asked to calculate the checksum value of the test input.

Not to be bitten by the trouble yesterday, I wanted to set up a full project (with the ability to test). This took a fair bit longer than I had intended, because I rabbit-holed into "how do I get this to provide test results automatically?" (where I spent about 20m), and "Why the hell isn't this test executing correctly?" (which took substantially longer).

Once I finally had my environment up and running correctly, I went about putting some test cases down:

(ns aoc.aoc2-test
  (:require [aoc.aoc2 :as sut]
            [clojure.test :refer [deftest testing is]]))

(deftest aoc2-part1
  (testing "the example statement"
    (let [input ["abcdef" "bababc"
                 "abbcde" "abcccd"
                 "aabcdd" "abcdee"
                 "ababab"]]
      (is (= 12 (sut/checksum input)))))
  (testing "a simple second example"
    (let [input ["abab" "abaa" "aab"
                 "aac" "aaa" "abc"]]
      (is (= 6 (sut/checksum input))))))

This uses the example scenario given in the problem, as well as a small example I cooked up myself. Armed with tests that executed on file save, I was ready to build out the solution.

Once again, this problem lends well to the frequencies function provided by Clojure - it will automatically group the values within the string by how frequent they show up. Since we only care about twos and threes, however, we need to search those results for those values. The reduce function (of "map/reduce" fame) is where we want to be - it gives us an easy way to take a list of things and make a scalar value out of it. In our case, we want to reduce each map to its existence of twos and threes; ideally, {:a 3 :b 1 :c 2} would result in {:threes 1 :twos 1}.

Building out a complicated reduce function generally is painful; because the inner function to a reduce is exactly that (a function), I defined it outside the logic. Because clojure values are generally immutable, I needed an easy way to maintain the state during the loop - transient helped out here, because I treat the map as temporarily mutable, but only within the bounds of the function and the lifetime of the transient binding.

Here's what I ended up with for the part 1 solution:

(ns aoc.aoc2)

(defn reduce-twos-threes
  "check the given frequency map n for twos or threes matches, and update
   the memo map to indicate if the string has a match. Used for a reducer."
  [memo n]
  (let [t-memo (transient memo)]
    (if (some (fn [[k v]] (= v 2)) n) (assoc! t-memo :twos (inc (:twos t-memo))))
    (if (some (fn [[k v]] (= v 3)) n) (assoc! t-memo :threes (inc (:threes t-memo))))
    (persistent! t-memo)))

(defn checksum [input]
  (let [sum-maps (map frequencies input)
        twos-threes (reduce reduce-twos-threes {:twos 0 :threes 0} sum-maps)]
    (* (:twos twos-threes) (:threes twos-threes))))

This makes the checksum function read really straightforward: find the frequencies of each input value, find the numbers of twos and threes (stored in a map), then finally multiply the twos and threes values together.

Day 2 Problem 2 (Electric Boogaloo)

Distilling the problem statement again:

Given your list of IDs, the particular IDs you're searching for differ by just one character; for example, "text" and "tent" fit this requirement, because you only need to replace the "x" and "n" characters. The example given in the problem is this:

where fghij and fguij are "adjacent" boxes. Any problem where you're comparing closeness of matching strings screams Levenshtein Distance. The Levenshtein distance of two strings is a measure of the minimum number of changes required to turn one string into another - this is generally counting insertion, deletion, and substitution, but our needs solely require substitution (better known as Hamming Distance - two separate mathematicians studying the same area of string differences. This is done by comparing values in each string, and adding 1 to each difference you encounter - a pretty simple comparison function.

(defn hamming
  "Compute the Hamming Distance between two equal length
   strings."
  [str1 str2]
  (if-not (= (count str1) (count str2))
    (throw (IllegalArgumentException. "Strings must be equal size.")))
  (loop [s1 str1
         s2 str2
         score 0]
    (if (empty? s1)
      score
      (recur (rest s1) (rest s2)
             (+ score (if (= (first s1) (first s2)) 0 1))))))

This uses Clojure's tail-recursive optimizing functions loop and recur to compare the strings one-by-one, and calculate their Hamming distance (we've got a check in there to make sure they're the same length, and throw an error if not).

Once that was complete, I built out a way to sift through the list of boxes to find just the ones with a Hamming distance of 1. This returns a two-item sequence, one for each swap of matching (there's probably an optimization there to not go through the entire list):

(defn find-christmas-boxes [input]
  (keep identity (map (fn [base-str]
                        (let [target-box (filter #(= 1 (hamming % base-str)) input)]
                          (if-not (empty? target-box)
                            [base-str (first target-box)]))) input)))

There's a couple of cool things to point out here. First, the base map function will return a lot of nil (Clojure's null value). In order to get rid of those, we use the identity function (which basically says "return true if truthy"; it's effectively a cleaner (not (nil? thing))). Another thing to point out for non-Clojurists is that shorthand function declaration used in the filter call:

;; These two are equivalent:
#{+ % 3}

(fn [arg] (+ arg 3))

Finally, the AoC puzzle asks for the common characters between the two strings. This is close to the Hamming Distance function above, but we just need to drop a character if it doesn't match. This got reduced to the following:

(defn remove-uncommon-letter [s1 s2]
  (apply str (keep-indexed #(if (= (get s2 %1) %2) %2) s1)))

;; To execute everything:
;; (apply remove-uncommon-letter (first find-christmas-boxes input))
;; where input is the raw input string from the project.

apply is the cool bit here - using apply allows you to use vector (read: array) entries as arguments to a function:

(let [numbers-to-add [1 2 3 4 5 6]]
 (apply + numbers-to-add)) => 21

And hey - no borrowing from anyone else today, and right before day 3 releases. I'm saving that for tomorrow, though. :D The Github Gist for today's problems is right here.

/Programming/ /AoC2018/ /advent-of-code/