Advent of Code, in Erlang: Day 16

The storm I was worried about mainly went south of me. The local airport weather records say our winds topped out at a brief 35mph sustained, and one 40mph gust. Starlink kept right on shuttling bits the whole time, so I was able to check out Advent of Code 2021, Day 16 right away.

When today's puzzle started talking about packet parsing, I knew this was going to be some fun Erlang code. The language is made for it.

BinData = << <<(binary_to_integer(B, 16))>>
             || <<B:2/binary>> <= HexData >>.

This is all the code that is required to convert the hexidecimal message representation to binary. That says, "take every two bytes from HexData, parse it as a base-16 integer, and write that integer as a byte in a new binary." I added some extra code after it to check whether any of the inputs included half-bytes ("nibbles") via an odd number of hex digits, but none did. On to parsing the binary data!

-record(packet, {ver, type, value, subs}).

parse_packet(<<Ver:3, 4:3, Rest/bitstring>>) ->
    {Literal, RestB} = parse_literal(Rest),
    {#packet{ver=Ver, type=literal, value=Literal}, RestB};
parse_packet(<<Ver:3, Type:3, 0:1, BitLength:15, Rest/bitstring>>) ->
    <<SubPacketData:BitLength/bitstring, RestB/bitstring>> = Rest,
    Packets = parse_all_packets(SubPacketData),
    {#packet{ver=Ver, type=Type, subs=Packets}, RestB};
parse_packet(<<Ver:3, Type:3, 1:1, SubCount:11, Rest/bitstring>>) ->
    {Packets, RestB} = parse_n_packets(SubCount, Rest),
    {#packet{ver=Ver, type=Type, subs=Packets}, RestB};
parse_packet(Rest) ->
    {'end', Rest}.

Here is where Erlang's bit-match syntax shines. I've written code that does something similar to this in Java and C. In each of those, I would be using a bunch of bitwise operations to mask and shift parts of bytes into the right place (and complaining yet again that Java's byte type is signed). But here, I write just exactly what the description says: the version is the first three bits (Ver:3), the type is the next three bits (Type:3), and so on. I'm even able to directly match things like, if the type of the packet is "4" (4:3), it means the packet contains a literal. Or for the other types, I can choose to read fifteen or eleven more bits based on the single bit following the type. It even automatically gives me an unsigned integer of an appropriate width! This makes decoding so much less error-prone, while also being quicker to write. The final clause, with the 'end' isn't needed, but I missed the sentence saying there would be only one packet (not including subpackets) per message, and was preparing to parse a stream.

parse_literal(<<0:1, N:4, Rest/bitstring>>) -> {N, Rest};
parse_literal(Extended) -> parse_literal(Extended, 0).

parse_literal(<<1:1, N:4, Rest/bitstring>>, Acc) ->
    parse_literal(Rest, (Acc bsl 4) + N);
parse_literal(<<0:1, N:4, Rest/bitstring>>, Acc) ->
    {(Acc bsl 4) + N, Rest}.

I do finally use a bit-shift-left (bsl) operation when parsing a literal value. They're encoded as variable-length numbers, with the first bit being 1 or 0 depending on whether there are more nibbles following that are part of the literal or not. Most real-world versions of this I have seen would align the indicator bit and the literal data on byte boundaries. It would be basically the same idea, but it would be the high bit of the byte would be the indicator, and the other seven bits would be part of the literal. That's not the case here, as this encoding is five bits total. This would make the C/Java code I would have written far more complex - tracking which part of which byte or two I was getting each bit from. Here, I just say I want 1+4 of them, and tell Erlang that the Rest of the bitstring is where I'll start next. (Even Erlang differentiates between a byte-aligned binary and an unaligned bitstring.)

Parsing sub-packets is straightforward recursion, as I've shown many times in this series. I'll skip over discussing it here, in favor of getting on with the two analysis tasks we're supposed to do with the parsed packet data.

sum_versions(#packet{ver=V, type=literal}) ->
    V;
sum_versions(#packet{ver=V, subs=Subs}) ->
    V + lists:sum([sum_versions(S) || S <- Subs]).

Part 1 asked for the sum of the version fields. This is a nice check for whether your code recovered all sub-packets from the message correctly. My solution is a recursive tree walk. Literals are leaf nodes that just return their version. Operator packets are internal tree nodes that add their version to the sum of their subpacket versions.

Part1 = fun(Hex) -> puzzle16:sum_versions(element(1, puzzle16:parse_packet(puzzle16:hex_to_bin(Hex)))) end.
16 = Part1(<<"8A004A801A8002F478">>).
12 = Part1(<<"620080001611562C8802118E34">>).
23 = Part1(<<"C0015000016115A2E0802F182340">>).
31 = Part1(<<"A0016C880162017C3686B18A3D4780">>).

All packets recovered. Excellent. Part 2 taught us what the operators are.

calculate(#packet{type=literal, value=V}) ->
    V;
calculate(#packet{type=Operator, subs=Subs}) ->
    case {Operator, [calculate(S) || S <- Subs]} of
        {0, Calc} ->
            lists:sum(Calc);
        {1, Calc} ->
            lists:foldl(fun erlang:'*'/2, 1, Calc);
        {2, Calc} ->
            lists:min(Calc);
        {3, Calc} ->
            lists:max(Calc);
        {5, [A,B]} ->
            compare(fun erlang:'>'/2, A, B);
        {6, [A,B]} ->
            compare(fun erlang:'<'/2, A, B);
        {7, [A,B]} ->
            compare(fun erlang:'=='/2, A, B)
    end.

compare(Fun, A, B) ->
    case Fun(A,B) of true -> 1; false -> 0 end.

The calculate clause for literals is nearly the same as it was in sum_versions, just extracting the value instead of the version. For the Operators, though, we first calculate the value of all Sub packets, and then pattern-match on the Operator to apply the right one to the calculated values. I couldn't resist tossing in a little extra-fancy use of functions that Erlang exports from an erlang module, that mimic the language operators sharing their names. I think it's neat how the bulleted list in the puzzle description maps so cleanly to the case branching here.

Part2 = fun(Hex) -> puzzle16:calculate(element(1, puzzle16:parse_packet(puzzle16:hex_to_bin(Hex)))) end.
3 = Part2(<<"C200B40A82">>).
54 = Part2(<<"04005AC33890">>).
7 = Part2(<<"880086C3E88112">>).
9 = Part2(<<"CE00C43D881120">>).
1 = Part2(<<"D8005AC2A8F0">>).
0 = Part2(<<"F600BC2D8F">>).
0 = Part2(<<"9C005AC2F8F0">>).
1 = Part2(<<"9C0141080250320F1802104A08">>).

And even with such a straightforward mapping, I still didn't beat the 100th fastest solver. There was so much problem description to read! But when I see leaderboard times double from day 15 to day 16, when my own day 16 time was a quarter of my day 15 time, I'm still amazed. Clearly being familiar with the domain, and being able to use tools well-matched to the domain, make a difference.

What did you use to solve today's puzzle? If there's another language or library that makes packet parsing this easy, let me know on Twitter (@hobbyist). Have a way to make this Erlang even clearer? Tell me about it on Github (beerriot). What awaits us in Day 17?

Categories: Development AdventOfCode