Andrey Listopadov

Advent of Code: Day 3

@aoc2021 @programming clojure ~7 minutes read

So far the event went pretty straightforward! The tasks were simple but interesting. Looking at other people’s solutions, I’m starting to feel that I’m overgeneralizing things quite often. But I think it’s a good thing, as I can see and highlight the points I need to improve!

Binary Diagnostic

Today’s task is once again themed around the submarine, we’re using to find the keys. But today we need to perform diagnostics of the submarine systems. The diagnostics came as the following example input:

00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010

It’s a list of binary numbers, and we need to work with those via a specific set of rules.

First, we need to take only the first column of each row, and count how many zeroes and ones are there to compute the most common bit. In the case of the first column, there are seven ones, and five zeroes, and the most common bit is 1. We need to repeat that for each column, and the resulting bits will be the number we’re looking for. Let’s prepare the data.

For the data format, I think a sequence of vectors of integers will do. We can transform the test input string to such format as follows:

day2> (ns day3)
nil
day3> (require '[aoc-commons :refer [parse-long]]
               '[clojure.string :as str])
nil
day3> (->> "00100\n11110\n10110\n10111\n10101\n01111\n00111\n11100\n10000\n11001\n00010\n01010"
           str/split-lines
           (map seq)
           (map #(mapv (fn [c] (parse-long (str c))) %)))
([0 0 1 0 0]
 [1 1 1 1 0]
 [1 0 1 1 0]
 [1 0 1 1 1]
 [1 0 1 0 1]
 [0 1 1 1 1]
 [0 0 1 1 1]
 [1 1 1 0 0]
 [1 0 0 0 0]
 [1 1 0 0 1]
 [0 0 0 1 0]
 [0 1 0 1 0])
day3> (def test-data *1)
#'day3/test-data

OK, this appears to look correct. Now, we need to write an algorithm that will count bits in the given column:

day3> (->> test-data
           (map #(get % 0))
           sort
           (split-with (partial = 0))
           (map count))
(5 7)

This should do it. We map the get function over each of the vectors to get the 0th bit. Then, we sort the result, so all zeroes go before all ones, and split it with the (partial = 0) function, which gives us the result of [(0 0 0 0 0) (1 1 1 1 1 1 1)]. Finally, we map the count function, to compute the amount of each bit, producing the final result of (5 7).

But it’s hard to remember what these numbers are, e.g. you can’t say if there’s 5 zeroes of 5 ones, by looking at the code. Your only hint is a call to sort, which sorts zeroes before ones, but it’s hard to grasp at a glance, so let’s put this into a table. We also need to make 0 argument to get a parameter, so here’s our function:

day3> (defn count-bits [bit-n input]
        (->> input
             (map #(get % bit-n))
             sort
             (split-with (partial = 0))
             (map count)
             (zipmap [:ones :zeroes])))
#'day3/count-bits

Finally, to get the most common bit we need to map this function for every index in our vectors. To obtain the size of the vector we can count the first vector from the input, and use it to create a range, that we will map over:

day3> (defn most-common-bits [input]
        (->> input
             first
             count
             range
             (map #(count-bits % input))))
#'day3/most-common-bits

Calling this function with our test input produces the following sequence of maps:

day3> (most-common-bits test-data)
({:ones 5, :zeroes 7}
 {:ones 7, :zeroes 5}
 {:ones 4, :zeroes 8}
 {:ones 5, :zeroes 7}
 {:ones 7, :zeroes 5})

This appears to be correct, but we’re missing the final step of converting this to a vector of the most common bits. To do this, we just need one extra map over this list, that compares ones and zeroes, and chooses the most common one:

day3> (defn most-common-bits [input]
        (->> input
             first
             count
             range
             (map #(count-bits % input))
             (map (fn [{:keys [zeroes ones]}]
                    (if (> zeroes ones) 1 0)))))
#'day3/most-common-bits
day3> (most-common-bits test-data)
(1 0 1 1 0)

This number is the correct one for the given example input. But it’s not it yet.

We need to compute another number, which consists of the lest common bits. We could change the predicate in the most-common-bits function, and create the least-common-bits function, but it would be a waste. All we need is to flip all bits in the number we got:

day3> (defn flip-bit [b]
        (if (= b 0) 1 0))
#'day3/flip-bit
day3> (map flip-bit *2)
(0 1 0 0 1)

And this is indeed the correct number.

Finally, we need to compute their product. To do so, we need to parse the binary representation into a decimal first. Let’s concatenate our lists to string and use default Java method for parsing:

day3> (* (Long/parseLong (str/join '(1 0 1 1 0)) 2)
         (Long/parseLong (str/join '(0 1 0 0 1)) 2))
198

This is the correct result. Let’s just wrap the whole thing into a function, and test with the real input:

day3> (defn read-input []
        (->> "inputs/day3"
             slurp
             str/split-lines
             (map seq)
             (map #(mapv (fn [c] (parse-long (str c))) %))))
#'day3/read-input
day3> (defn part-1 [input]
        (let [gamma (most-common-bits input)
              epsilon (map flip-bit gamma)]
          (* (Long/parseLong (str/join gamma) 2)
             (Long/parseLong (str/join epsilon) 2))))
#'day3/part-1
day3> (part-1 (read-input))
3885894

And we got the correct result! Time for part two.

Part two

Whoa.. that’s a lot of text! And numbers… Anyway, let’s see what’s up with all of this new information.

The idea is that we need to compute two more numbers, but now, we need to filter out some numbers based on a condition. To get the first number, we need to determine the most common bit for the given position and keep only such rows, that contain that number in the same position. The second number is exactly the same, except we need to use the least common bit. Should be pretty easy. Let’s start by writing a function, that determines which bit we need to use as criteria for filtering:

day3> (defn bit-criteria [type {:keys [ones zeroes]}]
        (case type
          :oxygen (if (< zeroes ones) 0 1)
          :CO2 (if (< zeroes ones) 1 0)))
#'day3/bit-criteria

Interestingly enough, the task explicitly mentions, that if we got the same amount of ones and zeroes, we need to choose 1 for oxygen, and 0 for CO2. I haven’t accounted for this case in the first part, and I haven’t even thought about it, to be frank. And even though the logic above doesn’t have an explicit check for this case as well, it works perfectly along with the rules:

day3> (bit-criteria :oxygen {:zeroes 4 :ones 4})
1
day3> (bit-criteria :CO2 {:zeroes 4 :ones 4})
0

I’m using the same format as returned by the count-bits function here. Now, all we need is to implement the algorithm:

day3> (defn calculate [type input]
        (let [total (count (first input))] ; ①
          (loop [n 0
                 numbers input]
            (let [bits (count-bits n numbers)
                  criteria (bit-criteria type bits)             ; ②
                  res (filter #(= (get % n) criteria) numbers)] ; ③
              (if (= 1 (count res))
                (first res)
                (when (< n total)
                  (recur (inc n) res)))))))
#'day3/calculate

That’s a lot of code, but the job this function does is pretty simple. We compute the total amount of bits we need to check at ①. Then we go into the loop, where we will check each bit n, starting from 0. We count all bits in a given position and compute the criteria ②. Finally, we filter only those rows, that have the same bit as the criteria bit in the position of n ③.

At this point, we have all rows that match the criteria. If we only got 1 row, that’s the result we need. If not, we go into the next iteration with the current amount of rows and check the next bit.

Let’s plug this into a function, and see if it’s correct for the test input:

day3> (defn part-2 [input]
        (let [oxygen (calculate :oxygen input)
              co2 (calculate :CO2 input)]
          (* (Long/parseLong (str/join oxygen) 2)
             (Long/parseLong (str/join co2) 2))))
#'day3/part-2
day3> (part-2 test-data)
230

And it is correct! Now we can check this with the real input:

day3> (part-2 (read-input))
4375225

And we get another gold star, as this is the right answer for my input!

Day 3 thoughts

Definitively was a bit harder than the previous day, but still a lot of fun! After I looked at my solution at the end of the day, I’ve realized that it wasn’t necessary to convert strings to numbers, as I could compare everything that way. But it wasn’t too much extra works, so that’s that.

Overall, I think my code is a bit complex, but I’m not sure how to improve it. Funnily enough, while writing this I’ve noticed that the implementation of most-common-bits was wrong, as I’ve used < instead of >, but the resulting answer was still correct, as the second number is just the inverse of the first one. That’s all for now, and see you the next day!