Day 20 - Advent of Code 2023

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

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Livebook

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()

"%gv -> lq, pm\n%rv -> jd, nh\n%nh -> rs, jd\n&vt -> tj\n%zv -> pm, gv\n%gh -> jd, vd\n%hh -> bf, qm\n%kx -> nf\n%st -> pm, zc\n%bh -> qm, pv\n&sk -> tj\n%hl -> nf, pn\n%mt -> st, pm\n&jd -> ts, gh, vd, dc, xc\n%zm -> hm\n%pv -> vv\n%zf -> nf, cz\n&xc -> tj\n%bf -> qm\n%ts -> sg\n%ht -> ch, nf\n%pb -> rv, jd\n%nx -> fc\n%mb -> mt\n%mh -> jd, pb\n%lc -> bh\n%xg -> mb, pm\n%vd -> dc\nbroadcaster -> gh, dl, xg, fb\n%sg -> mh, jd\n%qq -> ts, jd\n%dl -> nf, sv\n%vv -> sm, qm\n%zc -> tb\n%sr -> zv, pm\n%dc -> gb\n%cz -> nf, zm\n%rs -> jd\n%hm -> nf, hl\n%gd -> sr\n&qm -> lc, pv, nx, fb, kk\n&tj -> rx\n%gb -> qq, jd\n%xf -> zf\n%tb -> lg\n%sm -> qm, hh\n%fb -> dr, qm\n%lq -> pm\n&nf -> zm, dl, ch, xf, vt\n&pm -> sk, zc, tb, gd, mb, xg\n%pn -> nf, kx\n%fc -> xb, qm\n%ch -> xf\n&kk -> tj\n%lg -> pm, gd\n%sv -> nf, ht\n%xb -> qm, lc\n%dr -> nx, qm"

Solution

defmodule Day20 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input) do
    input
    |> parse()
    |> press_button(1000)
    |> then(fn %{high: high, low: low} -> high * low end)
  end

  def part2(input) do
    state = parse(input)
    high_cycles = for k <- get_sources(state, "rx"), into: %{}, do: {k, nil}

    state
    |> Map.merge(%{high_cycles: high_cycles, button_count: 0})
    |> find_high_cycle_counts()
    |> Map.values()
    |> Enum.reduce(1, &amp;Math.lcm/2)
  end

  defp get_sources(state, dest_key) do
    Enum.find_value(state, fn
      {_, {:conj, dests, sources_memory}} ->
        if dest_key in dests, do: Map.keys(sources_memory)

      _ ->
        nil
    end)
  end

  defp find_high_cycle_counts(state) do
    if Enum.all?(state.high_cycles, fn {_, v} -> v end) do
      state.high_cycles
    else
      state
      |> press_button(1)
      |> Map.update!(:button_count, &amp;(&amp;1 + 1))
      |> find_high_cycle_counts()
    end
  end

  defp press_button(state, count \\ 0, max_count)

  defp press_button(state, count, max_count) when count < max_count do
    [{:low, "button", "broadcaster"}]
    |> send_pulses(state)
    |> press_button(count + 1, max_count)
  end

  defp press_button(state, _, _), do: state

  defp send_pulses([], state), do: state

  defp send_pulses([h | tail], state) do
    {new_pulses, new_state} = send_pulse(h, state)

    send_pulses(tail ++ new_pulses, new_state)
  end

  defp send_pulse({pulse, source_module, module}, state) do
    new_state = Map.update(state, pulse, 1, &amp;(&amp;1 + 1))
    do_send_pulse(pulse, source_module, module, state[module], new_state)
  end

  # 'output' for example testing
  defp do_send_pulse(_pulse, _source, _module, nil, state) do
    {[], state}
  end

  defp do_send_pulse(pulse, _source, module, {:broadcast, dests}, state) do
    {
      Enum.map(dests, &amp;{pulse, module, &amp;1}),
      state
    }
  end

  defp do_send_pulse(:high, _source, _module, {:flip, _, _}, state) do
    {[], state}
  end

  defp do_send_pulse(:low, _source, module, {:flip, dests, :off}, state) do
    new_state = Map.put(state, module, {:flip, dests, :on})

    {
      Enum.map(dests, &amp;{:high, module, &amp;1}),
      new_state
    }
  end

  defp do_send_pulse(:low, _source, module, {:flip, dests, :on}, state) do
    new_state = Map.put(state, module, {:flip, dests, :off})

    {
      Enum.map(dests, &amp;{:low, module, &amp;1}),
      new_state
    }
  end

  defp do_send_pulse(pulse, source, module, {:conj, dests, memory}, state) do
    state =
      case state do
        %{high_cycles: %{^source => nil}} when pulse == :high ->
          Map.update!(state, :high_cycles, fn cycles ->
            Map.put(cycles, source, state.button_count + 1)
          end)

        state ->
          state
      end

    new_memory = Map.put(memory, source, pulse)
    new_state = Map.put(state, module, {:conj, dests, new_memory})
    next_pulse = if Enum.all?(new_memory, &amp;(elem(&amp;1, 1) == :high)), do: :low, else: :high

    {
      Enum.map(dests, &amp;{next_pulse, module, &amp;1}),
      new_state
    }
  end

  defmodule Input do
    def parse(input) do
      input
      |> String.splitter("\n", trim: true)
      |> Enum.map(&amp;parse_line/1)
      |> Enum.into(%{})
      |> setup_conjunctions()
    end

    defp setup_conjunctions(modules) do
      for {k, {_, dests, _}} <- modules, reduce: %{} do
        acc ->
          Enum.reduce(dests, acc, fn d, acc ->
            case modules[d] do
              {:conj, _, _} -> Map.update(acc, d, [k], &amp;[k | &amp;1])
              _ -> acc
            end
          end)
      end
      |> Enum.reduce(modules, fn {k, sources}, acc ->
        Map.update!(acc, k, fn
          {:conj, d, %{}} ->
            {:conj, d, sources |> Enum.map(&amp;{&amp;1, :low}) |> Enum.into(%{})}

          v ->
            v
        end)
      end)
    end

    def parse_line(line) do
      dest = &amp;String.split(&amp;1, ", ")

      case String.split(line, " -> ") do
        ["%" <> module, d] ->
          {module, {:flip, dest.(d), :off}}

        ["&" <> module, d] ->
          {module, {:conj, dest.(d), %{}}}

        [module, d] ->
          {module, {:broadcast, dest.(d)}}
      end
    end
  end
end

{:module, Day20, <<70, 79, 82, 49, 0, 0, 28, ...>>,
 {:module, Day20.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

Part 1:

Consult your module configuration; determine the number of low pulses and high pulses that would be sent after pushing the button 1000 times, waiting for all pulses to be fully handled after each push of the button. What do you get if you multiply the total number of low pulses sent by the total number of high pulses sent?

Your puzzle answer was 818649769.

Day20.part1(input)

818649769

Part 2:

The final machine responsible for moving the sand down to Island Island has a module attached named rx. The machine turns on when a single low pulse is sent to rx.

Reset all modules to their default states. Waiting for all pulses to be fully handled after each button press, what is the fewest number of button presses required to deliver a single low pulse to the module named rx?

Your puzzle answer was 246313604784977.

Day20.part2(input)

246313604784977

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, you should return to your Advent calendar and try another puzzle.

If you still want to see it, you can get your puzzle input.

Tests

ExUnit.start(auto_run: false)

defmodule Day20Test do
  use ExUnit.Case, async: false

  setup_all do
    [
      input1: "broadcaster -> a, b, c\n%a -> b\n%b -> c\n%c -> inv\n&inv -> a",
      input2: "broadcaster -> a\n%a -> inv, con\n&inv -> b\n%b -> con\n&con -> output"
    ]
  end

  describe "part1/1" do
    test "returns expected value", %{input1: input1, input2: input2} do
      assert Day20.part1(input1) == 32_000_000
      assert Day20.part1(input2) == 11_687_500
    end
  end
end

ExUnit.run()

.
Finished in 0.00 seconds (0.00s async, 0.00s sync)
1 test, 0 failures

Randomized with seed 432984

%{total: 1, failures: 0, excluded: 0, skipped: 0}

Benchmarking

defmodule Benchmarking do
  # https://github.com/bencheeorg/benchee
  def run(input) do
    Benchee.run(
      %{
        "Part 1" => fn -> Day20.part1(input) end,
        "Part 2" => fn -> Day20.part2(input) end
      },
      memory_time: 2,
      reduction_time: 2
    )

    nil
  end
end

{:module, Benchmarking, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:run, 1}}

Benchmarking.run(input)

Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.15.7
Erlang 26.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s

Benchmarking Part 1 ...
Benchmarking Part 2 ...

Name             ips        average  deviation         median         99th %
Part 1         74.99       13.34 ms     ±1.39%       13.35 ms       13.98 ms
Part 2         17.15       58.32 ms     ±2.99%       57.91 ms       67.32 ms

Comparison: 
Part 1         74.99
Part 2         17.15 - 4.37x slower +44.98 ms

Memory usage statistics:

Name           average  deviation         median         99th %
Part 1        41.53 MB     ±0.01%       41.53 MB       41.53 MB
Part 2       170.40 MB     ±0.01%      170.40 MB      170.42 MB

Comparison: 
Part 1        41.53 MB
Part 2       170.40 MB - 4.10x memory usage +128.87 MB

Reduction count statistics:

Name   Reduction count
Part 1          1.51 M
Part 2          6.32 M - 4.18x reduction count +4.81 M

**All measurements for reduction count were the same**

nil