Day 20

d20.livemd

Dmitry Slutsky ‮ ‮

@Lakret

aoc2023

More notebooks

Day 20

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

Solution

defmodule State do
  defstruct [:low, :high, :on_flips, :conj_memory]

  def new(input) do
    conj_memory = init_conj_memory(input)

    %__MODULE__{
      low: 0,
      high: 0,
      on_flips: MapSet.new(),
      conj_memory: conj_memory
    }
  end

  def count_pulse(state, :low), do: %__MODULE__{state | low: state.low + 1}
  def count_pulse(state, :high), do: %__MODULE__{state | high: state.high + 1}

  def on?(state, module_name), do: MapSet.member?(state.on_flips, module_name)

  def flip_on(state, module_name) do
    %__MODULE__{state | on_flips: MapSet.put(state.on_flips, module_name)}
  end

  def flip_off(state, module_name) do
    %__MODULE__{state | on_flips: MapSet.delete(state.on_flips, module_name)}
  end

  def remember_conj_input(state, conj_module, pulse_from, pulse_kind) do
    conj_memory = put_in(state.conj_memory, [conj_module, pulse_from], pulse_kind)
    %__MODULE__{state | conj_memory: conj_memory}
  end

  def all_high?(state, conj_module) do
    state.conj_memory[conj_module]
    |> Map.values()
    |> Enum.all?(fn pulse_kind -> pulse_kind == :high end)
  end

  @doc false
  def init_conj_memory(input) do
    input.conj_inputs
    |> Enum.map(fn {conj_module, inputs} ->
      states = Enum.map(inputs, fn input -> {input, :low} end) |> Enum.into(%{})
      {conj_module, states}
    end)
    |> Enum.into(%{})
  end
end

{:module, State, <<70, 79, 82, 49, 0, 0, 22, ...>>, {:init_conj_memory, 1}}

defmodule D20 do
  def parse_input(input) do
    {conns, kinds} =
      input
      |> String.trim()
      |> String.split("\n")
      |> Enum.map(fn line ->
        [src, dst] = String.split(line, " -> ")
        dst = String.split(dst, ", ")

        {kind, src} =
          cond do
            src == "broadcaster" -> {:broadcaster, :broadcaster}
            String.starts_with?(src, "%") -> {:flip, String.trim_leading(src, "%")}
            String.starts_with?(src, "&") -> {:conj, String.trim_leading(src, "&")}
            true -> raise "Unknown: #{src}"
          end

        {{src, dst}, {src, kind}}
      end)
      |> Enum.unzip()

    conns = Enum.into(conns, %{})
    kinds = Enum.into(kinds, %{})

    conj_modules =
      kinds
      |> Enum.map(fn
        {name, :conj} -> name
        _ -> nil
      end)
      |> Enum.reject(&amp;is_nil/1)
      |> MapSet.new()

    conj_inputs =
      Enum.reduce(conns, %{}, fn {src, dst}, inputs ->
        dst
        |> Enum.filter(&amp;MapSet.member?(conj_modules, &amp;1))
        |> Enum.reduce(inputs, fn conj_module, inputs ->
          module_inputs =
            Map.get(inputs, conj_module, MapSet.new())
            |> MapSet.put(src)

          Map.put(inputs, conj_module, module_inputs)
        end)
      end)

    %{conns: conns, kinds: kinds, conj_inputs: conj_inputs}
  end

  def press_button(input) do
    press_button(input, State.new(input), [{:button, :low, :broadcaster}])
  end

  def press_button(_input, state, []), do: state

  def press_button(
        %{conns: conns, kinds: kinds} = input,
        %State{} = state,
        [{src, signal_kind, dst} | rest]
      ) do
    state = State.count_pulse(state, signal_kind)

    {state, pulses} =
      case kinds[dst] do
        :broadcaster ->
          pulses =
            conns[:broadcaster]
            |> Enum.map(fn dst -> {:broadcaster, signal_kind, dst} end)

          {state, pulses}

        :flip ->
          case signal_kind do
            :high ->
              {state, []}

            :low ->
              if State.on?(state, dst) do
                state = State.flip_off(state, dst)
                pulses = Enum.map(conns[dst], fn next_dst -> {dst, :low, next_dst} end)
                {state, pulses}
              else
                state = State.flip_on(state, dst)
                pulses = Enum.map(conns[dst], fn next_dst -> {dst, :high, next_dst} end)
                {state, pulses}
              end
          end

        :conj ->
          state = State.remember_conj_input(state, dst, src, signal_kind)
          pulse_kind = if State.all_high?(state, dst), do: :low, else: :high
          pulses = Enum.map(conns[dst], fn next_dst -> {dst, pulse_kind, next_dst} end)
          {state, pulses}

        nil ->
          {state, []}
      end

    press_button(input, state, rest ++ pulses)
  end

  def p1(input) do
    state =
      Enum.reduce(1..1000, State.new(input), fn _, state ->
        press_button(input, state, [{:button, :low, :broadcaster}])
      end)

    state.low * state.high
  end
end

{:module, D20, <<70, 79, 82, 49, 0, 0, 30, ...>>, {:p1, 1}}

input = Path.join(__DIR__, "inputs/d20") |> File.read!() |> D20.parse_input()

%{
  kinds: %{
    "bm" => :conj,
    "qb" => :flip,
    "lh" => :flip,
    "xz" => :flip,
    "dx" => :flip,
    "lm" => :flip,
    "kn" => :flip,
    "cj" => :flip,
    "fj" => :flip,
    "ng" => :flip,
    "ds" => :conj,
    "qm" => :flip,
    "ft" => :flip,
    "df" => :flip,
    "zf" => :flip,
    "gz" => :flip,
    "bs" => :flip,
    "fp" => :flip,
    "cs" => :conj,
    "vr" => :conj,
    "ll" => :flip,
    "bx" => :flip,
    "pz" => :flip,
    "bv" => :flip,
    "qr" => :flip,
    "dc" => :flip,
    "sb" => :flip,
    "pg" => :flip,
    "jc" => :flip,
    "rv" => :flip,
    "mg" => :flip,
    "dt" => :conj,
    "dr" => :conj,
    "fg" => :flip,
    "zb" => :flip,
    "qs" => :flip,
    "tn" => :conj,
    "db" => :flip,
    "sx" => :flip,
    "nx" => :flip,
    "mp" => :flip,
    "vx" => :flip,
    "ls" => :flip,
    "dz" => :flip,
    "kd" => :flip,
    "tr" => :flip,
    "bk" => :flip,
    "rs" => :flip,
    "bj" => :flip,
    ...
  },
  conns: %{
    "bm" => ["vr"],
    "qb" => ["qm"],
    "lh" => ["cs", "kd"],
    "xz" => ["sx", "ds"],
    "dx" => ["bv", "dt"],
    "lm" => ["ds"],
    "kn" => ["jc", "cs"],
    "cj" => ["pg"],
    "fj" => ["dt", "tr"],
    "ng" => ["ft", "ds"],
    "ds" => ["qg", "db", "bm", "ft", "jk", "qs", "dz"],
    "qm" => ["dt", "ll"],
    "ft" => ["dz"],
    "df" => ["rs"],
    "zf" => ["lh", "cs"],
    "gz" => ["dt", "dx"],
    "bs" => ["dt"],
    "fp" => ["bk", "cs"],
    "cs" => ["lp", "jg", "sb", "jc", "dr"],
    "vr" => ["rx"],
    "ll" => ["zb", "dt"],
    "bx" => ["qb"],
    "pz" => ["rv"],
    "bv" => ["bs", "dt"],
    "qr" => ["pz"],
    "dc" => ["bd", "nx"],
    "sb" => ["lp", "cs"],
    "pg" => ["df", "bd"],
    "jc" => ["zf"],
    "rv" => ["bd", "mp"],
    "mg" => ["fj", "dt"],
    "dt" => ["bx", "mg", "qb", "cl", "zb"],
    "dr" => ["vr"],
    "fg" => ["ds", "xz"],
    "zb" => ["gz"],
    "qs" => ["db"],
    "tn" => ["vr"],
    "db" => ["qg"],
    "sx" => ["ds", "lm"],
    "nx" => ["qr"],
    "mp" => ["cj", "bd"],
    "vx" => ["bd"],
    "ls" => ["ds", "ng"],
    "dz" => ["fg"],
    "kd" => ["cs", "jg"],
    "tr" => ["bx", "dt"],
    "bk" => ["cs"],
    "rs" => [...],
    ...
  },
  conj_inputs: %{
    "bd" => MapSet.new(["dc", "gq", "mp", "pg", "rs", "rv", "vx"]),
    "bm" => MapSet.new(["ds"]),
    "cl" => MapSet.new(["dt"]),
    "cs" => MapSet.new(["bj", "bk", "fp", "kd", "kn", "lh", "sb", "sh", "zf"]),
    "dr" => MapSet.new(["cs"]),
    "ds" => MapSet.new(["fg", "jk", "lm", "ls", "ng", "sx", "xz"]),
    "dt" => MapSet.new(["bs", "bv", "dx", "fj", "gz", "ll", "mg", "qm", "tr"]),
    "tn" => MapSet.new(["bd"]),
    "vr" => MapSet.new(["bm", "cl", "dr", "tn"])
  }
}

Let’s look at our graph to figure out how to solve this.

input.conns
|> Enum.filter(fn {_src, dst} -> "rx" in dst end)

[{"vr", ["rx"]}]

input.conns
|> Enum.filter(fn {_src, dst} -> "vr" in dst end)

[{"cl", ["vr"]}, {"tn", ["vr"]}, {"dr", ["vr"]}, {"bm", ["vr"]}]

input.kinds["vr"]

:conj

This means that we need to make vr send a :low pulse to rx. Since vr is a conjunction module, we need to find a state where each of its inputs is set to :high.

If there’s some kind of a cyclical behaviour as in the test example #2 we will probably need to do least common multiple trick again to find the number of button presses.

conns_graph =
  input.conns
  |> Enum.flat_map(fn {src, dst} ->
    Enum.map(dst, fn dst -> "  #{src}-->#{dst}" end)
  end)
  |> Enum.join("\n")

"  qg-->ls\n  gq-->bd\n  gq-->vx\n  sh-->kn\n  sh-->cs\n  cl-->vr\n  broadcaster-->sb\n  broadcaster-->dc\n  broadcaster-->jk\n  broadcaster-->mg\n  jk-->ds\n  jk-->qs\n  lp-->sh\n  bd-->nx\n  bd-->pz\n  bd-->dc\n  bd-->qr\n  bd-->cj\n  bd-->df\n  bd-->tn\n  jg-->bj\n  bj-->cs\n  bj-->fp\n  rs-->gq\n  rs-->bd\n  bk-->cs\n  tr-->bx\n  tr-->dt\n  kd-->cs\n  kd-->jg\n  dz-->fg\n  ls-->ds\n  ls-->ng\n  vx-->bd\n  mp-->cj\n  mp-->bd\n  nx-->qr\n  sx-->ds\n  sx-->lm\n  db-->qg\n  tn-->vr\n  qs-->db\n  zb-->gz\n  fg-->ds\n  fg-->xz\n  dr-->vr\n  dt-->bx\n  dt-->mg\n  dt-->qb\n  dt-->cl\n  dt-->zb\n  mg-->fj\n  mg-->dt\n  rv-->bd\n  rv-->mp\n  jc-->zf\n  pg-->df\n  pg-->bd\n  sb-->lp\n  sb-->cs\n  dc-->bd\n  dc-->nx\n  qr-->pz\n  bv-->bs\n  bv-->dt\n  pz-->rv\n  bx-->qb\n  ll-->zb\n  ll-->dt\n  vr-->rx\n  cs-->lp\n  cs-->jg\n  cs-->sb\n  cs-->jc\n  cs-->dr\n  fp-->bk\n  fp-->cs\n  bs-->dt\n  gz-->dt\n  gz-->dx\n  zf-->lh\n  zf-->cs\n  df-->rs\n  ft-->dz\n  qm-->dt\n  qm-->ll\n  ds-->qg\n  ds-->db\n  ds-->bm\n  ds-->ft\n  ds-->jk\n  ds-->qs\n  ds-->dz\n  ng-->ft\n  ng-->ds\n  fj-->dt\n  fj-->tr\n  cj-->pg\n  kn-->jc\n  kn-->cs\n  lm-->ds\n  dx-->bv\n  dx-->dt\n  xz-->sx\n  xz-->ds\n  lh-->cs\n  lh-->kd\n  qb-->qm\n  bm-->vr"

Kino.Mermaid.new("""
graph TD;
#{conns_graph}
""")

graph TD;
  qg-->ls
  gq-->bd
  gq-->vx
  sh-->kn
  sh-->cs
  cl-->vr
  broadcaster-->sb
  broadcaster-->dc
  broadcaster-->jk
  broadcaster-->mg
  jk-->ds
  jk-->qs
  lp-->sh
  bd-->nx
  bd-->pz
  bd-->dc
  bd-->qr
  bd-->cj
  bd-->df
  bd-->tn
  jg-->bj
  bj-->cs
  bj-->fp
  rs-->gq
  rs-->bd
  bk-->cs
  tr-->bx
  tr-->dt
  kd-->cs
  kd-->jg
  dz-->fg
  ls-->ds
  ls-->ng
  vx-->bd
  mp-->cj
  mp-->bd
  nx-->qr
  sx-->ds
  sx-->lm
  db-->qg
  tn-->vr
  qs-->db
  zb-->gz
  fg-->ds
  fg-->xz
  dr-->vr
  dt-->bx
  dt-->mg
  dt-->qb
  dt-->cl
  dt-->zb
  mg-->fj
  mg-->dt
  rv-->bd
  rv-->mp
  jc-->zf
  pg-->df
  pg-->bd
  sb-->lp
  sb-->cs
  dc-->bd
  dc-->nx
  qr-->pz
  bv-->bs
  bv-->dt
  pz-->rv
  bx-->qb
  ll-->zb
  ll-->dt
  vr-->rx
  cs-->lp
  cs-->jg
  cs-->sb
  cs-->jc
  cs-->dr
  fp-->bk
  fp-->cs
  bs-->dt
  gz-->dt
  gz-->dx
  zf-->lh
  zf-->cs
  df-->rs
  ft-->dz
  qm-->dt
  qm-->ll
  ds-->qg
  ds-->db
  ds-->bm
  ds-->ft
  ds-->jk
  ds-->qs
  ds-->dz
  ng-->ft
  ng-->ds
  fj-->dt
  fj-->tr
  cj-->pg
  kn-->jc
  kn-->cs
  lm-->ds
  dx-->bv
  dx-->dt
  xz-->sx
  xz-->ds
  lh-->cs
  lh-->kd
  qb-->qm
  bm-->vr

It seems that each of the inputs of vr has their own independent connected component in the graph and only one input!

Plan to solve part 2:

figure out length of cycles for each of the bm, dr, tn, and cl
see if they are primes
find their LCM

# D20.p1(input)

nil

Tests

ExUnit.start(autorun: false)

defmodule D20Test do
  use ExUnit.Case, async: true

  @test_input D20.parse_input("""
              broadcaster -> a, b, c
              %a -> b
              %b -> c
              %c -> inv
              &inv -> a
              """)

  @test_input2 D20.parse_input("""
               broadcaster -> a
               %a -> inv, con
               &inv -> b
               %b -> con
               &con -> output
               """)

  @input Path.join(__DIR__, "inputs/d20") |> File.read!() |> D20.parse_input()

  test "part 1 works" do
    assert D20.p1(@test_input) == 32_000_000
    assert D20.p1(@test_input2) == 11_687_500
    assert D20.p1(@input) == 747_304_011
  end

  # test "part 2 works" do
  #   assert D12.p2(@test_input) == 525_152
  #   assert D12.p2(@input) == 11_607_695_322_318
  # end
end

ExUnit.run()

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

Randomized with seed 86317

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

Other notebooks:

@TomBers

livebookNotes

Attractors

attractors.livemd

decimal vega_lite kino

2022-8-18
Kevin Pan
@feng19

spider_man

ElixirJobs

elixirjobs.livemd

spider_man floki nimble_csv kino

2022-8-18
@TomBers

livebookNotes

Fun with Graphs

graphs.livemd

vega_lite kino math

2022-8-18
@TomBers

livebookNotes

Epicycloid - draw Curves with Straight Lines

Epicycloid.livemd

vega_lite kino math

2022-8-18
Aslak Johansen
@aslakjohansen

livebook-demos

MQTT

mqtt.livemd

vega_lite kino_vega_lite kino tortoise jason

2024-1-23
Ameen Ahmed
@zakia98

elixir-bootcamp

Data Traversal

data_traversal.livemd

jason kino youtube hidden_cell

2024-10-17
Ameen Ahmed
@zakia98

elixir-bootcamp

Portfolio: Blog Live Search

deprecated_portfolio_blog_live_search.livemd

jason kino youtube hidden_cell

2024-10-17

Back