Day 16

Mix.install([
  {:kino, "~> 0.7.0"}
])

Part 1

input = """
E0529D18025800ABCA6996534CB22E4C00FB48E233BAEC947A8AA010CE1249DB51A02CC7DB67EF33D4002AE6ACDC40101CF0449AE4D9E4C071802D400F84BD21CAF3C8F2C35295EF3E0A600848F77893360066C200F476841040401C88908A19B001FD35CCF0B40012992AC81E3B980553659366736653A931018027C87332011E2771FFC3CEEC0630A80126007B0152E2005280186004101060C03C0200DA66006B8018200538012C01F3300660401433801A6007380132DD993100A4DC01AB0803B1FE2343500042E24C338B33F5852C3E002749803B0422EC782004221A41A8CE600EC2F8F11FD0037196CF19A67AA926892D2C643675A0C013C00CC0401F82F1BA168803510E3942E969C389C40193CFD27C32E005F271CE4B95906C151003A7BD229300362D1802727056C00556769101921F200AC74015960E97EC3F2D03C2430046C0119A3E9A3F95FD3AFE40132CEC52F4017995D9993A90060729EFCA52D3168021223F2236600ECC874E10CC1F9802F3A71C00964EC46E6580402291FE59E0FCF2B4EC31C9C7A6860094B2C4D2E880592F1AD7782992D204A82C954EA5A52E8030064D02A6C1E4EA852FE83D49CB4AE4020CD80272D3B4AA552D3B4AA5B356F77BF1630056C0119FF16C5192901CEDFB77A200E9E65EAC01693C0BCA76FEBE73487CC64DEC804659274A00CDC401F8B51CE3F8803B05217C2E40041A72E2516A663F119AC72250A00F44A98893C453005E57415A00BCD5F1DD66F3448D2600AC66F005246500C9194039C01986B317CDB10890C94BF68E6DF950C0802B09496E8A3600BCB15CA44425279539B089EB7774DDA33642012DA6B1E15B005C0010C8C917A2B880391160944D30074401D845172180803D1AA3045F00042630C5B866200CC2A9A5091C43BBD964D7F5D8914B46F040
"""

defmodule PacketDecoder do
  def decode(packet) do
    metadata = %{
      version_sum: 0
    }

    packet
    |> String.trim()
    |> hex_to_bin()
    |> parse_packet(metadata)
  end

  # when converting to binary
  # we also need to pad leading 0s
  def hex_to_bin(hex) do
    n_chars = hex |> String.length()
    pad_to = n_chars * 4

    hex
    |> String.to_integer(16)
    |> Integer.to_string(2)
    |> String.pad_leading(pad_to, "0")
  end

  def parse_packet(
        <<version::binary-size(3), type_id::binary-size(3), rest::binary>>,
        metadata
      ) do
    version = version |> String.to_integer(2)
    type_id = type_id |> String.to_integer(2)

    metadata = Map.update!(metadata, :version_sum, &(&1 + version))

    case type_id do
      4 ->
        # literal
        {literal, rest, metadata} = parse_literal(rest, metadata)
        {{version, "literal", literal}, rest, metadata}

      _ ->
        # operator
        {sub_packets, rest, metadata} = parse_operator(rest, metadata)
        {{version, type_id, sub_packets}, rest, metadata}
    end
  end

  def parse_literal(bin, metadata) do
    parse_literal("", bin, metadata)
  end

  defp parse_literal(acc, <<"1", bits::binary-size(4), rest::binary>>, metadata) do
    parse_literal(acc <> bits, rest, metadata)
  end

  defp parse_literal(acc, <<"0", bits::binary-size(4), rest::binary>>, metadata) do
    literal = (acc <> bits) |> String.to_integer(2)
    {literal, rest, metadata}
  end

  def parse_operator(<<"0", n::binary-size(15), rest::binary>>, metadata) do
    s = n |> String.to_integer(2)

    <<sub_packets_bin::binary-size(s), rest::binary>> = rest

    Stream.iterate(0, &(&1 + 1))
    |> Enum.reduce_while({[], sub_packets_bin, metadata}, fn
      _, {packets, "", metadata} ->
        {:halt, {packets, rest, metadata}}

      _, {packets, rest, metadata} ->
        {packet, rest, metadata} = parse_packet(rest, metadata)
        {:cont, {[packet | packets], rest, metadata}}
    end)
  end

  def parse_operator(<<"1", n::binary-size(11), rest::binary>>, metadata) do
    s = n |> String.to_integer(2)

    Stream.iterate(0, &(&1 + 1))
    |> Enum.reduce_while({[], rest, metadata}, fn
      ^s, {packets, rest, metadata} ->
        {:halt, {packets, rest, metadata}}

      _s, {packets, rest, metadata} ->
        {packet, rest, metadata} = parse_packet(rest, metadata)
        {:cont, {[packet | packets], rest, metadata}}
    end)
  end

  def resolve(tree) do
    tree |> resolve_value()
  end

  defp resolve_value({_version, "literal", value}) when is_integer(value) do
    value
  end

  defp resolve_value({_version, 0, nodes}) when is_list(nodes) do
    nodes
    |> Enum.map(&resolve_value/1)
    |> Enum.sum()
  end

  defp resolve_value({_version, 1, nodes}) when is_list(nodes) do
    nodes
    |> Enum.map(&resolve_value/1)
    |> Enum.product()
  end

  defp resolve_value({_version, 2, nodes}) when is_list(nodes) do
    nodes
    |> Enum.map(&resolve_value/1)
    |> Enum.min()
  end

  defp resolve_value({_version, 3, nodes}) when is_list(nodes) do
    nodes
    |> Enum.map(&resolve_value/1)
    |> Enum.max()
  end

  defp resolve_value({_version, 5, [a, b] = nodes}) when is_list(nodes) do
    if resolve_value(a) < resolve_value(b) do
      1
    else
      0
    end
  end

  defp resolve_value({_version, 6, [a, b] = nodes}) when is_list(nodes) do
    if resolve_value(a) > resolve_value(b) do
      1
    else
      0
    end
  end

  defp resolve_value({_version, 7, [a, b] = nodes}) when is_list(nodes) do
    if resolve_value(a) == resolve_value(b) do
      1
    else
      0
    end
  end
end

{_tree, _rest, metadata} = input |> PacketDecoder.decode()
metadata.version_sum

Part 2

"""
C200B40A82 finds the sum of 1 and 2, resulting in the value 3.
04005AC33890 finds the product of 6 and 9, resulting in the value 54.
880086C3E88112 finds the minimum of 7, 8, and 9, resulting in the value 7.
CE00C43D881120 finds the maximum of 7, 8, and 9, resulting in the value 9.
D8005AC2A8F0 produces 1, because 5 is less than 15.
F600BC2D8F produces 0, because 5 is not greater than 15.
9C005AC2F8F0 produces 0, because 5 is not equal to 15.
9C0141080250320F1802104A08 produces 1, because 1 + 3 = 2 * 2.
"""
|> String.split("\n", trim: true)
|> Enum.map(&String.split(&1, " "))
|> Enum.map(&Enum.at(&1, 0))
|> Enum.map(&PacketDecoder.decode(&1))
|> Enum.map(&elem(&1, 0))
|> Enum.map(&PacketDecoder.resolve(&1))

{tree, _, _} =
  input
  |> PacketDecoder.decode()

tree

PacketDecoder.resolve(tree)

Visual

defmodule TreeRenderer do
  def render(tree) do
    tree
    |> to_markdown(0, ["flowchart TB", "```mermaid"])
    |> elem(2)
    |> then(fn lines -> ["```" | lines] end)
    |> Enum.reverse()
    |> Enum.join("\n")
    |> Kino.Markdown.new()
  end

  defp to_markdown({_version, "literal", value}, c, lines) when is_integer(value) do
    line = "node_#{c}[#{value}]"

    {%{id: c, value: value}, c + 1, [line | lines]}
  end

  defp to_markdown({_version, type_id, sub_nodes}, c, lines) when is_list(sub_nodes) do
    node = %{id: c, value: type_id_to_value(type_id)}

    line = "node_#{node.id}[#{node.value}]"
    lines = [line | lines]

    {c, lines} =
      sub_nodes
      |> Enum.reduce({c, lines}, fn sub_node, {c, lines} ->
        {sub_node, c, lines} = to_markdown(sub_node, c + 1, lines)
        line = "node_#{node.id} --> node_#{sub_node.id}"
        lines = [line | lines]
        {c, lines}
      end)

    {node, c + 1, lines}
  end

  defp type_id_to_value(0), do: "+"
  defp type_id_to_value(1), do: "*"
  defp type_id_to_value(2), do: "min"
  defp type_id_to_value(3), do: "max"
  defp type_id_to_value(5), do: "lt"
  defp type_id_to_value(6), do: "gt"
  defp type_id_to_value(7), do: "eq"
end

input
# "9C0141080250320F1802104A08"
|> PacketDecoder.decode()
|> elem(0)
|> TreeRenderer.render()