Andrey Listopadov

Advent of Code: Day 16 - Packet Decoder

@aoc2021 @programming clojure ~7 minutes read

We’ve finally left the caves! This is such a relief, no more walls full of Chitons, or volcanic activity. And since we’re out of the caves, we’re able to receive a transmission to our submarine!

The transmission is encoded with the Buoyancy Interchange Transmission System (BITS) and is represented in hexadecimal. It’s a continuous stream of the packets, and each packet has a fixed header format:

  • First three bits encode the packet version
  • Next three bits encode packet ID

Packets with an ID of 4 are value packets and can be processed by checking the 7th bit. If the 7th bit is 1 we read four bits, and check the next bit. If this bit is yet again equal to 1, we read four more bits and check the fifth. This repeats until the fifth bit is equal to 0, meaning that this is the last portion of the packet, so we need to read only 4 more values.

Let’s write function to read a stream using the logic so far:

day15> (ns day16 (:require [clojure.string :as str]))
nil
day16> (def hex-to-binary
         {\0 "0000", \1 "0001", \2 "0010", \3 "0011",
          \4 "0100", \5 "0101", \6 "0110", \7 "0111",
          \8 "1000", \9 "1001", \A "1010", \B "1011",
          \C "1100", \D "1101", \E "1110", \F "1111"})
#'day16/hex-to-binary
day16> (defn parse-binary [b]
         (Long/parseLong (str/join b) 2))
#'day16/parse-binary
day16> (defn read-version-or-id [packet]
         (let [[ver-or-id packet] (split-at 3 packet)]
           [(parse-binary ver-or-id) packet]))
#'day16/read-version-or-id
day16> (defn read-value [packet]
         (loop [[continue? a b c d & packet] packet
                v ""]
           (if (= \1 continue?)
             (recur packet
                    (str v a b c d))
             [(parse-binary (str v a b c d)) packet])))
#'day16/read-value

Now, suppose we have the packet D2FE28. We convert it to the stream of bits first:

day16> (mapcat hex-to-binary "D2FE28")
(\1 \1 \0 \1 \0 \0 \1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)

Next, we can read it’s version and ID:

day16> (read-version-or-id *1)
[6 (\1 \0 \0 \1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)]
day16> (read-version-or-id (second *1))
[4 (\1 \0 \1 \1 \1 \1 \1 \1 \1 \0 \0 \0 \1 \0 \1 \0 \0 \0)]

As can be seen, each function returns the parsed value and the rest of the packet, so we can continue parsing it. Now we can read the value, since this is the package with ID of 4:

day16> (read-value (second *1))
[2021 (\0 \0 \0)]

This returns the value of 2021 and the rest of the packet stream, which we do not care about right now.

There’s a second type of packet, which are operator packets. They’re totally different beasts though. Packets with IDs that are not equal to 4, have the next bit after ID as length ID. The length ID can be either 0, meaning that we need to read the next N bits or 1 meaning that we need to process the next N packets. Let’s implement the function that will read length ID and the length itself:

day16> (defn read-length [packet]
         (let [[type & packet] packet
               id (parse-binary (str type))
               length (case id 0 15 1 11)
               [length packet] (split-at length packet)]
           [id (parse-binary length) packet]))
#'day16/read-length
day16> (mapcat hex-to-binary "38006F45291200")
(\0 \0 \1 \1 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)
day16> (read-version-or-id *1)
[1 (\1 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]
day16> (read-version-or-id (second *1))
[6 (\0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \1 \1 \0 \1 \1 \1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]
day16> (read-length (second *1))
[0 27 (\1 \1 \0 \1 \0 \0 \0 \1 \0 \1 \0 \0 \1 \0 \1 \0 \0 \1 \0 \0 \0 \1 \0 \0 \1 \0 \0 \0 \0 \0 \0 \0 \0 \0)]

Here it correctly reads the length and its type. Now we can implement the function that will process the stream of packets until it finishes. We need to store the packet versions in order to solve the first part:

day16> (defn process-packet-stream [packets]
         (let [[ver packets] (read-version-or-id packets)
               [id packets] (read-version-or-id packets)]
           (if (= id 4)
             (let [[_ packets] (read-value packets)]
               [[ver] packets])
             (let [[length-id length packets] (read-length packets)
                   [vers packets]
                   (loop [length length
                          packets packets
                          inner-vers [ver]]
                     (if (> length 0)
                       (let [len-before (count packets)
                             [vers packets] (process-packet-stream packets)]
                         (recur (case length-id
                                  0 (- length (- len-before (count packets)))
                                  1 (dec length))
                                packets
                                (into inner-vers vers)))
                       [inner-vers packets]))]
               [vers packets]))))
#'day16/process-packet-stream
day16> (process-packet-stream (mapcat hex-to-binary "A0016C880162017C3686B18A3D4780"))
[[5 1 3 7 6 5 2 2] (\0 \0 \0 \0 \0 \0 \0)]

Seems to work so far! This function recursively calls itself when if finds an operator packet. It determines the number of packages it needs to process recursively based on the lendth-id.

We get the list of versions as the first value of the returned vector. Now we just need to reduce it with addition, and we’ll get our answer. This grants us the first gold star, let’s see what’s in part two!

Part two

So now, ununexpectedly we need to actually use values and operators stored in packets. Operators are determined by the packet ID, and are as follows:

  • 0 - summation
  • 1 - product
  • 2 - minimum value
  • 3 - maximum value
  • 5 - greater than
  • 6 - smaller than
  • 7 - equal to

Applied to all the data in the packet. Seems easy to implement, as we just need to store values during recursion similarly to versions, and call some function based on ID when exiting the recursion step:

day16> (defn process-packet-stream [packets]
         (let [[ver packets] (read-version-or-id packets)
               [id packets] (read-version-or-id packets)]
           (if (= id 4)
             (let [[val packets] (read-value packets)]
               [[ver] [val] packets])
             (let [[length-id length packets] (read-length packets)
                   [vers vals packets]
                   (loop [length length
                          packets packets
                          inner-vers [ver]
                          inner-vals []]
                     (if (> length 0)
                       (let [len-before (count packets)
                             [vers vals packets] (process-packet-stream packets)]
                         (recur (case length-id
                                  0 (- length (- len-before (count packets)))
                                  1 (dec length))
                                packets
                                (into inner-vers vers)
                                (into inner-vals vals)))
                       [inner-vers inner-vals packets]))]
               (case id
                 0 [vers [(reduce + vals)] packets]
                 1 [vers [(reduce * vals)] packets]
                 2 [vers [(apply min vals)] packets]
                 3 [vers [(apply max vals)] packets]
                 5 [vers [(if (apply > vals) 1 0)] packets]
                 6 [vers [(if (apply < vals) 1 0)] packets]
                 7 [vers [(if (apply = vals) 1 0)] packets])))))
#'day16/process-packet-stream
day16> (process-packet-stream (mapcat hex-to-binary "A0016C880162017C3686B18A3D4780"))
[[5 1 3 7 6 5 2 2] [54] (\0 \0 \0 \0 \0 \0 \0)]

Checking the second return value grants us the second gold star.

Day 16 thoughts

Today’s task was pretty simple, but the description was very convoluted. I think I’ve spent most of the time figuring out what bits are responsive to what kind of information and so on. So I really have a question. I mean, yes, English is not my first language, but I think I’m pretty decent, as I can write, read and talk freely (albeit with some accent, and grammar issues). But I’ve spent good 20 minutes only to understand the task fully, but the leader board for this day shows people completing both parts in under 10 minutes! I understand, that there are people who compete with others and take it pretty seriously, but how do you read so fast?! I mean, yesterday’s task with pathfinding algorithm and terrain generation was completed in under 4 minutes. Four minutes! This is some serious speed programming.

I’ll try to search for the recording, but I’m generally interested in the thought process of people who’re able to solve these tasks so fast. The tasks are not too complicated, but the speed still amazes me. If you know some of the videos like this feel free to send me a link, I’ll be interested.

On that note, until tomorrow, and I’ll try my best to solve the next task as fast as I can. We’ll see how it goes.