Advent of Code 2021 - Day 16

bjorng · December 16, 2021, 6:07am

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

bjorng · December 16, 2021, 6:10am

Finally a puzzle perfectly suited for BEAM languages!

github.com

bjorng/advent-of-code-2021/blob/daf1e4875a4a61eccc2610406bb08d85f72fa189/day16/lib/day16.ex

defmodule Day16 do
  def part1(input) do
    bin = parse(input)
    {packet, _} = decode_packet(bin)
    version_sum(packet, 0)
  end

  def part2(input) do
    bin = parse(input)
    {packet, _} = decode_packet(bin)
    eval_packet(packet)
  end

  defp version_sum({version, :literal, _}, sum) do
    sum + version
  end
  defp version_sum({version, _, packets}, sum) do
    Enum.reduce(packets, sum + version, &version_sum/2)
  end

This file has been truncated. show original

zevv · December 16, 2021, 8:35am

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

github.com

zevv/aoc2021/blob/master/lib/day16.ex


defmodule Day16 do

  def parse_lit(bits, lit \\ 0) do
    case bits do
      <<1::1, val::4, rest::bits>> -> parse_lit(rest, lit * 16 + val)
      <<0::1, val::4, rest::bits>> -> {rest, 0, lit*16 + val}
    end
  end
  
  def parse_op_bits(bits, vsum, data, n) do
    case n do
      0 -> {bits, vsum, data}
      n ->
        {rest, vsum2, val} = parse_pkt(bits)
        n = n - (bit_size(bits)- bit_size(rest))
        parse_op_bits(rest, vsum + vsum2, [val | data], n)
    end
  end

This file has been truncated. show original

dallagi · December 16, 2021, 8:53am

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

Here’s my solution

github.com

dallagi/aoc2021/blob/main/lib/aoc2021/day16.ex

defmodule Aoc2021.Day16 do
  def part1(input) do
    {decoded, _} = input |> String.trim() |> Base.decode16!() |> decode()
    version_numbers_sum(decoded)
  end

  def part2(input) do
    {decoded, _} = input |> String.trim() |> Base.decode16!() |> decode()
    eval_program(decoded)
  end

  @literal_type 4

  def decode(<<version::size(3), @literal_type::size(3), rest::bits>>) do
    {literal_payload, rest} = decode_literal(rest)
    {{:literal, version, literal_payload}, rest}
  end

  def decode(<<version::size(3), operator_type::size(3), rest::bits>>) do
    {operator_payload, rest} = decode_operator(rest)

This file has been truncated. show original

ruslandoga · December 16, 2021, 9:12am

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.

ramuuns · December 16, 2021, 9:14am

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

hauleth · December 16, 2021, 9:53am

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)

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

zevv · December 16, 2021, 10:35am

@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

ramuuns · December 16, 2021, 11:20am

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

ramuuns · December 16, 2021, 6:54pm

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

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

hauleth · December 16, 2021, 7:23pm

ramuuns:

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

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

ramuuns · December 16, 2021, 8:47pm

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)>>

lud · December 16, 2021, 11:22pm

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

stevensonmt · December 17, 2021, 5:45am

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?

bjorng · December 17, 2021, 6:56am

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

11010001010
VVVTTTAAAAA

princemaple · December 17, 2021, 7:45am

github.com

princemaple/aoc/blob/main/2021/day16.exs

# Title: Day16

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> String.split("", trim: true)
  |> Enum.flat_map(
    &(&1
      |> String.to_integer(16)
      |> Integer.digits(2)
      |> then(fn l -> [0, 0, 0] ++ l end)
      |> Enum.take(-4))
  )

defmodule D16 do
  def parse(data) do
    {data, %{}}

This file has been truncated. show original

github.com

princemaple/aoc/blob/main/2021/day16-bitstring.exs

# Title: Day16 - BitString

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> :binary.decode_hex()

defmodule D16 do
  def parse(data) do
    {data, %{}}
    |> parse_meta(:version)
    |> parse_meta(:type)
    |> parse_by_type()
  end

  def parse_meta({<<meta_value::3, rest::bitstring>>, meta}, meta_key) do
    {rest, Map.put(meta, meta_key, meta_value)}

This file has been truncated. show original

github.com

princemaple/aoc/blob/main/2021/day16ast.exs

# Title: Day16 - BitString+AST

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> :binary.decode_hex()

defmodule D16 do
  def parse(data) do
    {data, %{}}
    |> parse_meta(:version)
    |> parse_meta(:type)
    |> parse_by_type()
  end

  def parse_meta({<<meta_value::3, rest::bitstring>>, meta}, meta_key) do
    {rest, Map.put(meta, meta_key, meta_value)}

This file has been truncated. show original

stefanluptak · December 17, 2021, 1:26pm

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

lud · December 17, 2021, 4:29pm

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

tommyokeefe · December 17, 2021, 5:56pm

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

APB9785 · December 18, 2021, 12:13am

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