bjorng

bjorng

Erlang Core Team

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

Most Liked

zevv

zevv

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

bjorng

bjorng

Erlang Core Team

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

ramuuns

ramuuns

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

hauleth

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
bjorng

bjorng

Erlang Core Team

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

11010001010
VVVTTTAAAAA

Where Next?

Popular in Challenges Top

sb8244
Note: This topic is to talk about Day 10 of the Advent of Code 2019 . There is a private leaderboard for elixirforum members. You can jo...
New
bjorng
This topic is about Day 17 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/l...
New
sasajuric
Note: This topic is to talk about Day 12 of the Advent of Code. For general discussion about the Advent of Code 2018 and links to topics...
New
sneako
Note by the Moderators: This topic is to talk about the first day of the Advent of Code. For general discussion about the Advent of Code...
New
Aetherus
This topic is about the Advent of Code 2021 - Day 4. Thanks to @bjorng , we now have a new Private Leaderboard. The entry code is: 370...
New
stevensonmt
Trying to get more facility with dynamic programming concepts on Leetcode and having an issue I can’t find a way around. It’s a chutes an...
New
Aetherus
This topic is about Day 16 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/l...
New
bjorng
This topic is about Day 15 of the Advent of Code 2021. We have a private leaderboard (shared with users of Erlang Forums): https://adve...
New
bjorng
Note: This topic is to talk about Day 6 of the Advent of Code 2019. There is a private leaderboard for elixirforum members. You can join...
New
cblavier
Hi, there :wave: Today, I felt it was way more challenging! I went through part2 thanks to Agent based memoization (without memoization ...
New

Other popular topics Top

Brian
What is the proper way to load a module from a file in to IEX? In the python world, doing something like this pretty standard: from ....
New
sorentwo
Hello! tl;dr Announcing Oban, an Ecto based job processing library with a focus on reliability and historical observability. After spen...
977 41022 311
New
sergio
In Ruby, I can go: User.find_by(email: "foobar@email.com").update(email: "hello@email.com") How can I do something similar in Elixir? ...
New
bsollish-terakeet
Credo is smart enough to check for (something like) this: assert length(the_list) == 0 with this response: Checking if an enum is empt...
New
aalberti333
As the title describes, I’m trying to run Enum.map() over a list of key/value pairs, where the value is a map. My data looks like this: ...
New
Jim
As a follow up to my earlier question: I have the code compiling and running but not getting a successful login from the rest server. ...
New
lastday4you
I wanted to check elixir version in phoenix because i found that my elixir is 1.5 but when i use Enum.chunk_by it said the function is un...
New
fireproofsocks
Forgive me if this is obvious, but how does one delete a database record WITHOUT selecting it first? https://hexdocs.pm/ecto/Ecto.Repo.h...
New
Patoshizzle
After calling mix ecto.create I get this error: 17:00:32.162 [error] GenServer #PID&lt;0.412.0&gt; terminating ** (Postgrex.Error) FATAL...
New
magnetic
Hey :wave:t3: Elixir community, I’ve been learning Elixir, and working on some side projects. My editor of choice is VSCode, and althoug...
New

We're in Beta

About us Mission Statement