Learning Resources>Coding Challenges

Advent of Code 2021 - Day 16

#advent-of-code
bjorng

bjorng

Erlang Core Team

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

21 comments
#advent-of-code
2233 21

Showing Posts 1 to 10

bjorng

bjorng OP

Erlang Core Team

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

https://github.com/bjorng/advent-of-code-2021/blob/daf1e4875a4a61eccc2610406bb08d85f72fa189/day16/lib/day16.ex

3
Post #1
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:

https://github.com/zevv/aoc2021/blob/master/lib/day16.ex

5
Post #2
dallagi

dallagi

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

Here’s my solution

https://github.com/dallagi/aoc2021/blob/main/lib/aoc2021/day16.ex

1
Post #3
ruslandoga

ruslandoga

It would be interesting to compare optimised and non-optimised approaches: Constructing and Matching Binaries — Erlang System Documentation v29.0.2

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

2
Post #4
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/2021/day-16.ex at 880e2934416746d18d262a09946330ce36c9ee23 · ramuuns/aoc · GitHub

3
Post #5
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
3
Post #6
zevv

zevv

@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:

0
Post #7
ramuuns

ramuuns

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

0
Post #8
ramuuns

ramuuns

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
Post #9
hauleth

hauleth

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

1
Post #10

Where Next? Top

View thread on forum (has 21 replies!)
advent-of-code
Home Learning Resources>Coding Challenges
37 2168 21
Last post
REPLY VIEW THREAD WITH 21 POSTS

Trending in Challenges Top

Other Trending Topics Top

mudasobwa
Chat & Discussions>Discussions

Cure - a new language compiled to BEAM
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
#static-types#type-checking#types#fsm
168 5507 69
New
marciok
News>Announcing

Gust - A task orchestration system built in Elixir
Hi there! We created Gust: A task orchestrator inspired by Airflow. For those who have never heard about Aiflow, it’s a Python-based wor...
/phoenix/oban#library#workflow#background_job#reactor
111 4469 40
New
jimsynz
News>Announcing

Beam Bots - Resilient Robotics on the BEAM
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
/beam-bots#library#robotics#bb
119 2916 28
New
Dmk
News>Announcing

Xamal - Deploy Elixir releases to bare metal servers via SSH
Xamal is a deployment tool for Elixir apps that deploys native releases to bare metal servers over SSH. It’s a port of GitHub - basecamp/...
#library#deployment#deploy#deployments#xamal
75 2512 33
New
netoum
News>Announcing

Corex - Accessible and unstyled UI Phoenix components
Corex is an accessible, unstyled UI component library for Phoenix that integrates Zag.js state machines using Vanilla JavaScript and Live...
/phoenix#library#ui#liveview#hooks#accessibility#component#tableau
63 2662 20
New
webofbits
Chat & Discussions>AI / LLMs

How much do you still code yourself?
With AI doing more of the implementation work, I’ve been wondering how much coding I should deliberately keep doing myself. My main conc...
#ai
202 1525 85
New
Back to top

Learning Resources>Coding Challenges

Resources Challenges ❯

Latest on Elixir Forum

Elixir Forum ❯

Sponsor Spotlight

AppSignal

Catch errors, track performance, monitor hosts and more.

Our Sponsors

Dashbit

Build Elixir applications with speed and confidence.

EEF

Supporting innovation across the BEAM ecosystem.

AppSignal

Catch errors, track performance, monitor hosts and more.

Honeybadger

Error tracking, logs, uptime, and Just Enough APM. Built for developers.

Code Sync

Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Manning

Master modern tools, write cleaner code, and tackle real-world challenges.

ElixirCasts

Producing high quality Elixir screencasts since 2017.

Software Mansion

The team behind Membrane, Popcorn, LiveDebugger. Available for hire.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

Categories:

Sub Categories:

Forums

Popular Tags

Our Sponsors

Dashbit

Build Elixir applications with speed and confidence.

EEF

Supporting innovation across the BEAM ecosystem.

AppSignal

Catch errors, track performance, monitor hosts and more.

Honeybadger

Error tracking, logs, uptime, and Just Enough APM. Built for developers.

Code Sync

Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Manning

Master modern tools, write cleaner code, and tackle real-world challenges.

ElixirCasts

Producing high quality Elixir screencasts since 2017.

Software Mansion

The team behind Membrane, Popcorn, LiveDebugger. Available for hire.

Pragmatic Studio

Courses that'll move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews