Advent of Code 2021 - Day 16

This topic is about Day 16 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

1 Like

Finally a puzzle perfectly suited for BEAM languages! :grinning:

3 Likes

@bjorng: right, a natural fit, all the gore of the bit stream fiddling is excellently handled by Elixir! Solution in under 60 lines:

4 Likes

I agree, doing today’s exercise with Elixir felt like cheating :smiley:

Here’s my solution

1 Like

It would be interesting to compare optimised and non-optimised approaches: Erlang -- Constructing and Matching Binaries

To check if an approach is optimised, one can do ERL_COMPILER_OPTIONS=bin_opt_info mix compile --force.

2 Likes

Since I wasn’t feeling comfortable with bit-streams due to being new to this whole elixir thing, I just converted everything to a giant list of 1s and 0s and then did the parsing of that. Even that felt very easy to do in elixir somehow.

anyhow here’s the code: aoc/day-16.ex at 880e2934416746d18d262a09946330ce36c9ee23 · ramuuns/aoc · GitHub

3 Likes

Again LiveBook note:


Day 16

defmodule Day16 do
  defmodule Packet do
    defstruct [:version, :type, :value]
  end

  def decode(<<version::3, 4::3, rest::bitstring>>) do
    {value, rest} = literal(rest, 0)

    {%Packet{type: :literal, version: version, value: value}, rest}
  end

  def decode(<<version::3, type::3, 0::1, length::15, rest::bitstring>>) do
    <<subpackets::bitstring-size(length), rest::bitstring>> = rest

    {%Packet{type: type, version: version, value: decode_all(subpackets)}, rest}
  end

  def decode(<<version::3, type::3, 1::1, length::11, rest::bitstring>>) do
    {value, rest} = Enum.map_reduce(1..length, rest, fn _, acc -> decode(acc) end)

    {%Packet{type: type, version: version, value: value}, rest}
  end

  def decode_all(input) do
    case decode(input) do
      {packet, <<>>} -> [packet]
      {packet, rest} -> [packet | decode_all(rest)]
    end
  end

  defp literal(<<1::1, bits::4, rest::bitstring>>, acc) do
    literal(rest, acc * 0x10 + bits)
  end

  defp literal(<<0::1, bits::4, rest::bitstring>>, acc) do
    {acc * 0x10 + bits, rest}
  end
end

input =
  File.read!("day16.txt")
  |> String.trim()
  |> Base.decode16!()
  |> Day16.decode()
  |> elem(0)
%Day16.Packet{
  type: 0,
  value: [
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 20, version: 6},
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{type: :literal, value: 14747, version: 1},
            %Day16.Packet{type: :literal, value: 14747, version: 6}
          ],
          version: 2
        }
      ],
      version: 1
    },
    %Day16.Packet{
      type: 3,
      value: [
        %Day16.Packet{type: :literal, value: 15, version: 5},
        %Day16.Packet{type: :literal, value: 10, version: 6}
      ],
      version: 7
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 7,
          value: [
            %Day16.Packet{type: :literal, value: 2184, version: 1},
            %Day16.Packet{type: :literal, value: 130250, version: 6}
          ],
          version: 6
        },
        %Day16.Packet{type: :literal, value: 5442981, version: 4}
      ],
      version: 6
    },
    %Day16.Packet{type: :literal, value: 8281083, version: 0},
    %Day16.Packet{
      type: 2,
      value: [
        %Day16.Packet{type: :literal, value: 102, version: 5},
        %Day16.Packet{type: :literal, value: 647125, version: 7}
      ],
      version: 1
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 178, version: 1},
        %Day16.Packet{type: :literal, value: 176, version: 6}
      ],
      version: 0
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{
              type: 0,
              value: [
                %Day16.Packet{type: :literal, value: 13, version: 1},
                %Day16.Packet{type: :literal, value: 8, version: 4},
                %Day16.Packet{type: :literal, value: 4, version: 3}
              ],
              version: 2
            },
            %Day16.Packet{
              type: 0,
              value: [
                %Day16.Packet{type: :literal, value: 7, version: 7},
                %Day16.Packet{type: :literal, value: 11, version: 3},
                %Day16.Packet{type: :literal, value: 14, version: 2}
              ],
              version: 4
            }
          ],
          version: 7
        },
        %Day16.Packet{type: :literal, value: 2724, version: 0}
      ],
      version: 1
    },
    %Day16.Packet{type: :literal, value: 9, version: 4},
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{type: :literal, value: 7240238, version: 2},
            %Day16.Packet{type: :literal, value: 233, version: 7}
          ],
          version: 1
        },
        %Day16.Packet{type: :literal, value: 37, version: 6}
      ],
      version: 4
    },
    %Day16.Packet{type: 2, value: [%Day16.Packet{type: :literal, value: 2, version: 5}], version: 5},
    %Day16.Packet{type: :literal, value: 53749, version: 4},
    %Day16.Packet{type: :literal, value: 11, version: 3},
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 382979, version: 4},
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{
              type: 0,
              value: [
                %Day16.Packet{type: :literal, value: 15, version: 1},
                %Day16.Packet{type: :literal, value: 10, version: 0},
                %Day16.Packet{type: :literal, value: 2, version: 6}
              ],
              version: 5
            },
            %Day16.Packet{
              type: 0,
              value: [
                %Day16.Packet{type: :literal, value: 4, version: 7},
                %Day16.Packet{type: :literal, value: 7, version: 4},
                %Day16.Packet{type: :literal, value: 2, version: 5}
              ],
              version: 1
            }
          ],
          version: 6
        }
      ],
      version: 2
    },
    %Day16.Packet{type: :literal, value: 21251, version: 1},
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 163, version: 6},
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{type: :literal, value: 59, version: 3},
            %Day16.Packet{type: :literal, value: 836848134220, version: 1}
          ],
          version: 6
        }
      ],
      version: 2
    },
    %Day16.Packet{
      type: 2,
      value: [
        %Day16.Packet{
          type: 0,
          value: [
            %Day16.Packet{
              type: 0,
              value: [
                %Day16.Packet{
                  type: 2,
                  value: [
                    %Day16.Packet{
                      type: 2,
                      value: [
                        %Day16.Packet{
                          type: 0,
                          value: [
                            %Day16.Packet{
                              type: 3,
                              value: [
                                %Day16.Packet{
                                  type: 2,
                                  value: [
                                    %Day16.Packet{
                                      type: 2,
                                      value: [
                                        %Day16.Packet{
                                          type: 3,
                                          value: [%Day16.Packet{type: 0, value: [...], ...}],
                                          version: 0
                                        }
                                      ],
                                      version: 1
                                    }
                                  ],
                                  version: 1
                                }
                              ],
                              version: 7
                            }
                          ],
                          version: 0
                        }
                      ],
                      version: 6
                    }
                  ],
                  version: 2
                }
              ],
              version: 2
            }
          ],
          version: 6
        }
      ],
      version: 7
    },
    %Day16.Packet{
      type: 1,
      value: [%Day16.Packet{type: :literal, value: 44, version: 4}],
      version: 7
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 255, version: 2},
        %Day16.Packet{type: :literal, value: 91, version: 5},
        %Day16.Packet{type: :literal, value: 176, version: 5},
        %Day16.Packet{type: :literal, value: 23, version: 1}
      ],
      version: 7
    },
    %Day16.Packet{
      type: 3,
      value: [
        %Day16.Packet{type: :literal, value: 11520, version: 4},
        %Day16.Packet{type: :literal, value: 6069, version: 0},
        %Day16.Packet{type: :literal, value: 1089149511401, version: 4},
        %Day16.Packet{type: :literal, value: 158, version: 2},
        %Day16.Packet{type: :literal, value: 620605, version: 0}
      ],
      version: 2
    },
    %Day16.Packet{
      type: 0,
      value: [
        %Day16.Packet{type: :literal, value: 62788, version: 7},
        %Day16.Packet{type: :literal, value: 9410622, version: 2},
        %Day16.Packet{type: :literal, value: 15912821, version: 4}
      ],
      version: 4
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 22416, version: 5},
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{type: :literal, value: 246, version: 1},
            %Day16.Packet{type: :literal, value: 246, version: 4}
          ],
          version: 2
        }
      ],
      version: 0
    },
    %Day16.Packet{
      type: 3,
      value: [%Day16.Packet{type: :literal, value: 13008601, version: 5}],
      version: 0
    },
    %Day16.Packet{
      type: 0,
      value: [
        %Day16.Packet{
          type: 1,
          value: [
            %Day16.Packet{type: :literal, value: 3, version: 4},
            %Day16.Packet{type: :literal, value: 14, version: 1},
            %Day16.Packet{type: :literal, value: 5, version: 0}
          ],
          version: 5
        },
        %Day16.Packet{
          type: 1,
          value: [
            %Day16.Packet{type: :literal, value: 2, version: 1},
            %Day16.Packet{type: :literal, value: 14, version: 1},
            %Day16.Packet{type: :literal, value: 10, version: 1}
          ],
          version: 6
        },
        %Day16.Packet{
          type: 1,
          value: [
            %Day16.Packet{type: :literal, value: 8, version: 3},
            %Day16.Packet{type: :literal, value: 6, version: 6},
            %Day16.Packet{type: :literal, value: 11, version: 0}
          ],
          version: 1
        }
      ],
      version: 5
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 32940592237, version: 2},
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{type: :literal, value: 100, version: 1},
            %Day16.Packet{type: :literal, value: 1393232728, version: 2}
          ],
          version: 2
        }
      ],
      version: 0
    },
    %Day16.Packet{type: :literal, value: 89, version: 3},
    %Day16.Packet{
      type: 2,
      value: [
        %Day16.Packet{type: :literal, value: 204, version: 6},
        %Day16.Packet{type: :literal, value: 260321821, version: 2},
        %Day16.Packet{type: :literal, value: 225241983, version: 6}
      ],
      version: 0
    },
    %Day16.Packet{
      type: 0,
      value: [
        %Day16.Packet{type: :literal, value: 960899, version: 3},
        %Day16.Packet{type: :literal, value: 58997, version: 5},
        %Day16.Packet{type: :literal, value: 54940, version: 6},
        %Day16.Packet{type: :literal, value: 10974, version: 2},
        %Day16.Packet{type: :literal, value: 882043, version: 2}
      ],
      version: 0
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{type: :literal, value: 35633017255, version: 4},
            %Day16.Packet{type: :literal, value: 35633017255, version: 2}
          ],
          version: 3
        },
        %Day16.Packet{type: :literal, value: 1359, version: 6}
      ],
      version: 6
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 92, version: 4},
        %Day16.Packet{type: :literal, value: 38, version: 3},
        %Day16.Packet{type: :literal, value: 160, version: 5},
        %Day16.Packet{type: :literal, value: 111, version: 1},
        %Day16.Packet{type: :literal, value: 64, version: 4}
      ],
      version: 4
    },
    %Day16.Packet{
      type: 0,
      value: [
        %Day16.Packet{type: :literal, value: 2541, version: 3},
        %Day16.Packet{type: :literal, value: 263947, version: 6},
        %Day16.Packet{type: :literal, value: 7686705, version: 5},
        %Day16.Packet{type: :literal, value: 31, version: 4}
      ],
      version: 2
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{type: :literal, value: 3193865, version: 1},
            %Day16.Packet{type: :literal, value: 20223, version: 7}
          ],
          version: 2
        },
        %Day16.Packet{type: :literal, value: 9328522, version: 5}
      ],
      version: 0
    },
    %Day16.Packet{
      type: 2,
      value: [
        %Day16.Packet{type: :literal, value: 5, version: 4},
        %Day16.Packet{type: :literal, value: 7, version: 3},
        %Day16.Packet{type: :literal, value: 179420284, version: 4},
        %Day16.Packet{type: :literal, value: 19890, version: 1},
        %Day16.Packet{type: :literal, value: 2655, version: 0}
      ],
      version: 7
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 862089, version: 1},
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{type: :literal, value: 248, version: 3},
            %Day16.Packet{type: :literal, value: 3286, version: 5}
          ],
          version: 3
        }
      ],
      version: 3
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 93, version: 6},
        %Day16.Packet{
          type: 5,
          value: [
            %Day16.Packet{type: :literal, value: 4269, version: 6},
            %Day16.Packet{type: :literal, value: 240, version: 3}
          ],
          version: 4
        }
      ],
      version: 5
    },
    %Day16.Packet{
      type: 3,
      value: [
        %Day16.Packet{type: :literal, value: 2938, version: 6},
        %Day16.Packet{type: :literal, value: 3, version: 6},
        %Day16.Packet{type: :literal, value: 211, version: 7}
      ],
      version: 3
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 7,
          value: [
            %Day16.Packet{type: :literal, value: 159, version: 0},
            %Day16.Packet{type: :literal, value: 159, version: 5}
          ],
          version: 0
        },
        %Day16.Packet{type: :literal, value: 28, version: 1}
      ],
      version: 4
    },
    %Day16.Packet{type: :literal, value: 84, version: 4},
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 235, version: 4},
        %Day16.Packet{
          type: 6,
          value: [
            %Day16.Packet{type: 0, value: [%Day16.Packet{...}, ...], version: 4},
            %Day16.Packet{type: 0, value: [...], ...}
          ],
          version: 3
        }
      ],
      version: 6
    },
    %Day16.Packet{type: :literal, value: 1425, version: 4},
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{
          type: 7,
          value: [%Day16.Packet{type: 0, value: [...], ...}, %Day16.Packet{type: 0, ...}],
          version: 5
        },
        %Day16.Packet{type: :literal, value: 13, version: 2}
      ],
      version: 2
    },
    %Day16.Packet{
      type: 0,
      value: [%Day16.Packet{type: :literal, value: 3121, version: 6}],
      version: 5
    },
    %Day16.Packet{
      type: 1,
      value: [
        %Day16.Packet{type: :literal, value: 51, version: 2},
        %Day16.Packet{type: :literal, value: 61, ...},
        %Day16.Packet{type: :literal, ...}
      ],
      version: 4
    },
    %Day16.Packet{
      type: 1,
      value: [%Day16.Packet{type: :literal, value: 1393, ...}, %Day16.Packet{type: 5, ...}],
      version: 3
    },
    %Day16.Packet{type: 1, value: [%Day16.Packet{type: 7, ...}, %Day16.Packet{...}], version: 3},
    %Day16.Packet{type: 1, value: [%Day16.Packet{...}, ...], version: 7},
    %Day16.Packet{type: 3, value: [...], ...},
    %Day16.Packet{type: 2, ...},
    %Day16.Packet{...},
    ...
  ],
  version: 3
}
defmodule Day16.Task1 do
  alias Day16.Packet

  def sum(%Packet{type: :literal, version: version}), do: version

  def sum(%Packet{version: version, value: value}) do
    Enum.reduce(value, version, &(sum(&1) + &2))
  end
end

Day16.Task1.sum(input)
949
defmodule Day16.Task2 do
  alias Day16.Packet

  def evaluate(%Packet{type: :literal, value: value}), do: value

  def evaluate(%Packet{type: 0} = packet), do: reduce(packet, 0, &+/2)
  def evaluate(%Packet{type: 1} = packet), do: reduce(packet, 1, &*/2)
  def evaluate(%Packet{type: 2} = packet), do: reduce(packet, :inf, &min/2)
  def evaluate(%Packet{type: 3} = packet), do: reduce(packet, 0, &max/2)

  def evaluate(%Packet{type: 5} = packet), do: compare(packet, &>/2)
  def evaluate(%Packet{type: 6} = packet), do: compare(packet, &</2)
  def evaluate(%Packet{type: 7} = packet), do: compare(packet, &==/2)

  defp reduce(%Packet{value: value}, initial, op) do
    Enum.reduce(value, initial, &op.(evaluate(&1), &2))
  end

  defp compare(%Packet{value: [a, b]}, op) do
    if op.(evaluate(a), evaluate(b)), do: 1, else: 0
  end
end

Day16.Task2.evaluate(input)
1114600142730
3 Likes

@ramuuns: Woo, working with raw 1s and 0s worked out better then I’d expected. Still a missed chance though, this is an excellent exersize to get acquainted with bit handling :slight_smile:

yeah, I have a plan to rewrite my solution to use binaries, for exactly this reason

ok, the fact that you can take the whole bunch of hex characters, convert it to an integer, and then say “hey, so this giant integer is a bitstream of that’s n chunks of 4 bits” is madness. I am in genuine shock :exploding_head:

Like for a person who’s not used to this sort of stuff this function is crazy:

def prepare_data([input]) do
  len = byte_size(input)
  num = input |> String.to_integer(16)
  <<num::integer-size(len)-unit(4)>>
end

And of course that you then just replace the code where I was doing pattern matching on a list, with pattern matching on bits in this stream and everything just works is just additional crazy talk

2 Likes

It is needlessly complicated way of calling Base.decode16!(input)

1 Like

actually, there is a difference - Base.decode16!/1 expects an even number of “digits” - consider:

iex> "F" |> Base.decode16!()
** (ArgumentError) odd-length string
    (elixir 1.13.0) lib/base.ex:349: Base.decode16!/2

vs

iex> << ("F" |> String.to_integer(16))::integer-size(1)-unit(4) >>
<<15::size(4)>>
2 Likes

I had this error because I did not strip the final "\n" from the input. But once done, Base.decode16!/1 works as expected.

1 Like

Anybody want to help me understand this part of the prompt:

For example, here is an operator packet (hexadecimal string 38006F45291200) with length type ID 0 that contains two sub-packets:

00111000000000000110111101000101001010010001001000000000
VVVTTTILLLLLLLLLLLLLLLAAAAAAAAAAABBBBBBBBBBBBBBBB
  • The three bits labeled V (001) are the packet version, 1.
  • The three bits labeled T (110) are the packet type ID, 6, which means the packet is an operator.
  • The bit labeled I (0) is the length type ID, which indicates that the length is a 15-bit number representing the number of bits in the sub-packets.
  • The 15 bits labeled L (000000000011011) contain the length of the sub-packets in bits, 27.
  • The 11 bits labeled A contain the first sub-packet, a literal value representing the number 10.
  • The 16 bits labeled B contain the second sub-packet, a literal value representing the number 20.

Specifically my understanding from the earlier instructions was that literal values would be 5 bit subunits, with the first bit of each subunit denoting whether it was the last subunit of the literal. So in this case the 11 bits they’ve labeled as A 11010001010 would be divided up as 11010, first bit is 1 so keep going, 00101, first bit is 0 so it’s the last subunit. Why is the next zero tacked on? Then for B, the very first subunit starts with zero so shouldn’t it stop right there?

Each sub packet starts with a 6 bit header. So A would be divided up as:

11010001010
VVVTTTAAAAA
3 Likes
1 Like

Thanks a lot. This was the thing I was missing the whole time.

1 Like

I hope the next day will expand on that new format like intcode in 2019. We were building a VM from for CPU-like instructions.
This time it is basically an AST that we are working with, so we may end up building an interpretor. And if we do, then I we could try to rewrite the binary decoder to output Elixir AST instead of custom packet formats, and eval it with Code.eval_quoted :smiley:

2 Likes

I hadn’t worked with binary pattern matching before. I’m learning so much!

I couldn’t wait; had to try it:

def solve do
  {ast, _} =
    @path
    |> File.read!()
    |> String.trim_trailing()
    |> Base.decode16!()
    |> make_ast()

  Code.eval_quoted(ast)
end

Full solution here

3 Likes