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

LostKobrakai
This topic is about Day 9 of the Advent of Code 2020 . Thanks to @egze, we have a private leaderboard: https://adventofcode.com/2020/le...
New
bjorng
Note: This topic is to talk about Day 1 of the Advent of Code 2019.
New
gangstead
This is my second year doing AoC in Elixir and my first year doing it with Livebook. When I was doing just plain Elixir I usually set up...
New
kwando
Phew, this one took a while to get right. My naive attempts was way to slow so I reached for Dijkstras shortest path algorithm… and that ...
New
New
New
Aetherus
Hello, guys. I’m back again, but only for the weekends, maybe. This topic is about Day 13 of the Advent of Code 2020 . Thanks to @egze,...
New
woolfred
It is that time of the year again: Advent of Code 2022 :christmas_tree: Day 1 Leaderboard:
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
mattbaker
I’m having so much fun working on the “Protohackers” challenges, I never got into Advent of Code much but this has been amazing. The chal...
New

Other popular topics Top

shahryarjb
Hello, I get Persian date from my client and convert it to normal calendar like this: def jalali_string_to_miladi_english_number(persi...
New
chrisalley
ExUnit now has describe blocks which is a welcome addition coming from RSpec. In the docs, it states that nested hierarchies of describe ...
New
JakeBecker
TL;DR: I’ve just released an implementation of Microsoft’s IDE-independent Language Server Protocol for Elixir. It adds language support ...
1140 51847 244
New
JorisKok
I have a server on AWS, and was running a load test using artillery. When looking at the Phoenix dashboard I see the Ports going to 100% ...
New
albydarned
Hello all! I am typing this post from my new MacBook Pro with the M1 chip. I’m loving it so far, and will probably use it as my daily dr...
New
itssasanka
Hi all, Trying to get some more clarity over utc_datetime and naive_datetime for Ecto: https://hexdocs.pm/ecto/Ecto.Schema.html#module-...
New
axelson
This post is a wiki (feel free to hit the edit button near the bottom right of this post to add your own changes!) This post collects co...
239 45766 226
New
AstonJ
You’re a programmer, so you don’t need spoon feeding with the conventional drivel about “this is an integer.” No. You need to know what’s...
New
ycv005
I have followed this StackOverflow post to install the specific version of Erlang. And When I am running mix ecto.setup then getting fol...
New
KronicDeth
Elixir plugin for JetBrain’s IntelliJ Platform (including Rubymine) This is a plugin that adds support for Elixir to JetBrains IntelliJ...
289 35421 110
New

We're in Beta

About us Mission Statement