Advent of Code 2018  Day 2
Christopher Kruse Dec 2 '18 Updated on Dec 03, 2018 γ»5 min read
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 longandshort 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:

abcdef
contains no letters that appear exactly two or three times. 
bababc
contains two a and three b, so it counts for both. 
abbcde
contains two b, but no letter appears exactly three times. 
abcccd
contains three c, but no letter appears exactly two times. 
aabcdd
contains two a and two d, but it only counts once. 
abcdee
contains two e. 
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 rabbitholed 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.aoc2test
(:require [aoc.aoc2 :as sut]
[clojure.test :refer [deftest testing is]]))
(deftest aoc2part1
(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 reducetwosthrees
"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 [tmemo (transient memo)]
(if (some (fn [[k v]] (= v 2)) n) (assoc! tmemo :twos (inc (:twos tmemo))))
(if (some (fn [[k v]] (= v 3)) n) (assoc! tmemo :threes (inc (:threes tmemo))))
(persistent! tmemo)))
(defn checksum [input]
(let [summaps (map frequencies input)
twosthrees (reduce reducetwosthrees {:twos 0 :threes 0} summaps)]
(* (:twos twosthrees) (:threes twosthrees))))
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:
abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz
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]
(ifnot (= (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 tailrecursive optimizing functions loop
and recur
to compare the strings onebyone, 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 twoitem sequence, one for each swap of matching (there's probably an optimization there to not go through the entire list):
(defn findchristmasboxes [input]
(keep identity (map (fn [basestr]
(let [targetbox (filter #(= 1 (hamming % basestr)) input)]
(ifnot (empty? targetbox)
[basestr (first targetbox)]))) 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 nonClojurists 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 removeuncommonletter [s1 s2]
(apply str (keepindexed #(if (= (get s2 %1) %2) %2) s1)))
;; To execute everything:
;; (apply removeuncommonletter (first findchristmasboxes 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 [numberstoadd [1 2 3 4 5 6]]
(apply + numberstoadd)) => 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.