Advent of Code 2023 - Day 20

I used dot from graphviz to plot the input graph, and I noticed that there are 4 distinct components: branching directly from the broadcaster, and merging into a single “conjunction” vertex than then feeds into rx. Each of the components by themselves can be processed by just running the same thing as in part 1 - for me they produce the desired signal as their output in about ~3900 steps. Then the desired number is just the least common multiple of those (curiously, all 4 were primes in my case, so I could just multiply them).

defmodule Main do
  def run() do
    get_input()
    |> parse() |> add_sinks() |> calc_incoming()
    # |> solve1()
    # |> solve2()
    |> mess_around()
	end

  def get_input() do
    # "testinput20.1"
    # "testinput20.2"
    "input20"
    |> File.read!() |> String.trim() |> String.split("\n")
  end

 # parse input into %{}, a "graph"
  def parse(ls) do
    for l <- ls, into: %{} do
      [labl,tos] = String.split(l," -> ")
      case labl |> String.to_charlist() |> Enum.at(0) do
        ?b -> {"B", {nil, tos |> String.split(", ")} }
        c  -> {String.slice(labl,1..-1), {c, tos |> String.split(", ")} }
      end
    end
  end

  # prep: for each "vertex", remember also the ones that point to it
  def calc_incoming(gr) do
    edges = for {l,{_,outedges}} <- gr, e <- outedges, into: [], do: {l,e}
    for {l,{t,outs}} <- gr, into: %{}, do: {l,{t,outs, Enum.filter(edges,&(elem(&1,1)==l))|>Enum.map(&elem(&1,0))}}
  end

  # prep: add vertices that have no outgoing arrows
  def add_sinks(gr) do
    incs = gr |> Map.values() |> Enum.map(&elem(&1,1)) |> Enum.concat()
    missing = MapSet.difference(MapSet.new(incs), MapSet.new(Map.keys(gr)))
    for m <- missing, into: gr, do: {m,{nil,[]}}
  end

  # generate %{} representing the "base" state before anything happens
  def base_state(gr) do
    for {l,{t,_,incs}} <- gr, into: %{} do
      case t do
        ?% -> {l, false}
        ?& -> {l, incs |> Enum.map(fn i -> {i,false} end) |> Enum.into(%{}) }
        _  -> {l, nil}
      end
    end
  end

  # implementing the pulse rules (single pulse)
  def send(lvl,from,outs), do: outs |> Enum.map(fn oo -> {lvl,from,oo} end)
  def do_one_node({nil,outs,_},{lvl,_,"B"},   _), do: {nil,send(lvl,"B",outs)}
  def do_one_node({nil, _ ,_}, {_  ,_, _ },   _), do: {nil,[]}
  def do_one_node({?%,  _ ,_}, {true, _,_}, stt), do: {stt,[]}
  def do_one_node({?%,outs,_}, {false,_,i}, stt), do: {not stt,send(not stt,i,outs)}
  def do_one_node({?&,outs,_}, {lvl,  o,i}, stt) do
    nstt = Map.put(stt,o,lvl)
    if Map.values(nstt)|>Enum.all?, do: {nstt,send(false,i,outs)}, else: {nstt,send(true,i,outs)}
  end

  # implementing pulse rules (one whole "push button" run)
  def run_pulses(st, [], _, {hs,ls}), do: {st, hs, ls}
  def run_pulses(st, [p|ps], gr, {hs,ls}) do
    {lvl,_,i} = p
    {nlst, nps} = do_one_node(gr[i],p,st[i])
    run_pulses(Map.put(st,i,nlst), ps++nps, gr, (if lvl, do: {hs+1,ls}, else: {hs,ls+1}))
  end

  def solve1(gr) do
    bst = gr |> base_state()
    res = 1..1000 |> Enum.reduce({bst,0,0}, fn _,{st,hs,ls} ->
                run_pulses(st,[{false,nil,"B"}],gr,{hs,ls}) end)
    elem(res,1)*elem(res,2)
  end

  def run_pulses2(st, [], _, _, f), do: {st, f}
  def run_pulses2(st, [p|ps], gr, tst, f) do
    {lvl,_,i} = p
    {nlst, nps} = do_one_node(gr[i],p,st[i])
    nf = if {lvl,i} == tst, do: f+1, else: f
    run_pulses2(Map.put(st,i,nlst), ps++nps, gr, tst, nf)
  end

  def solve2(_) do
    "sorry, no general solution"
  end
  
  def find_first(cond,gr) do
    bst = gr |> base_state()
    1..100_000 |> Enum.reduce_while({bst,0}, fn i, {st,f} ->
                    {nst,nf} = run_pulses2(st,[{false,nil,"B"}],gr,cond,f)
                    if nf>0, do: {:halt, i}, else: {:cont, {nst,nf}}
                  end)
  end

  def lcm(ls), do: Enum.reduce(ls, Enum.at(ls,0), fn n, lcm -> div(n*lcm, Integer.gcd(n,lcm)) end)

  def mess_around(gr) do
    # OK so the way I did this is that I used "dot" to draw the graph, and noticed
    # a structure: the vtx just before rx (&vd) has 4 inputs, and each of those come
    # from independent components, branched right from the broadcaster.
    # So: did each of the components separately. and then did lcm of them
    # (interestingly, each of them 4 were primes, in the range of ~3900.)

    watchers = for vtx1 <- elem(gr["rx"],2), vtx2 <- elem(gr[vtx1],2), into: [], do: vtx2
    watchers |> Enum.map(&find_first({false,&1},gr)) |> lcm()
  end
 
end

:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)

1. There exists only one conjunction connected to rx
2. For this conjunction &c, it has inputs from m other conjunctions
3. To find when &c sends a low pulse to rx, we need to find the LCM of the first times that every connected conjunction sends a high pulse to &c since that means all of them sent a high pulse at once, causing &c to send a low pulse to rx

defmodule Part1 do
  def parse(input) do
    for line <- String.split(input, "\n", trim: true),
        reduce: {%{}, %{}} do
      {inputs, outputs} ->
        [input, output] = String.split(line, " -> ")
        output = String.split(output, ", ")

        {type, input} =
          case input do
            "broadcaster" -> {:broadcast, input}
            <<"%", name::binary>> -> {:flip_flop, name}
            <<"&", name::binary>> -> {:conjunction, name}
          end

        inputs =
          output
          |> Enum.reduce(inputs, fn output, inputs ->
            Map.update(inputs, output, [input], fn existing -> [input | existing] end)
          end)

        outputs = Map.put(outputs, input, {type, output})
        {inputs, outputs}
    end
  end

  def graph(inputs, outputs, state \\ %{}) do
    outputs = Map.put(outputs, "button", {:button, ["broadcaster"]})
    graph(inputs, outputs, state, ["button"], MapSet.new(), [])
  end

  def graph(_, outputs, state, [], _, edges) do
    meta =
      Enum.map(outputs, fn {sender, {type, _}} ->
        "    #{sender}[\"#{sender} (#{type})\"]"
      end)

    styles =
      Enum.flat_map(outputs, fn {name, {type, _}} ->
        case type do
          :flip_flop ->
            internal = Map.get(state, name, 0)
            fill = if internal == 1, do: "#0f0", else: "#f00"
            ["    style #{name} fill:#{fill}"]

          _ ->
            []
        end
      end)

    lines = ["graph LR"] ++ meta ++ edges ++ styles

    graph =
      lines
      |> Enum.uniq()
      |> Enum.join("\n")

    Kino.Mermaid.new(graph)
  end

  def graph(inputs, outputs, state, [sender | rest], seen, acc) do
    {_, receivers} = Map.get(outputs, sender, {nil, []})
    seen = MapSet.put(seen, sender)

    edges =
      receivers
      |> Enum.map(fn receiver ->
        "    #{sender} --> #{receiver}"
      end)

    next =
      receivers
      |> Enum.reject(fn receiver -> MapSet.member?(seen, receiver) end)

    acc = acc ++ edges
    rest = rest ++ next
    graph(inputs, outputs, state, rest, seen, acc)
  end

  def run(inputs, outputs, opts \\ []) do
    initial = Keyword.get(opts, :initial, %{})
    debug = Keyword.get(opts, :debug, false)
    render = Keyword.get(opts, :render, false)
    frame = if render, do: Kino.Frame.new() |> Kino.render(), else: nil

    run(%{
      inputs: inputs,
      outputs: outputs,
      state: initial,
      debug: debug,
      frame: frame,
      lows: 1,
      highs: 0,
      pulses: [{"button", "broadcaster", 0}]
    })
  end

  def run(%{
        inputs: inputs,
        outputs: outputs,
        state: state,
        lows: lows,
        highs: highs,
        frame: frame,
        pulses: []
      }) do
    if frame do
      term = graph(inputs, outputs, state)
      Kino.Frame.render(frame, term)
    end

    {lows, highs, state}
  end

  def run(
        %{
          inputs: inputs,
          outputs: outputs,
          state: state,
          debug: debug,
          lows: lows,
          highs: highs,
          pulses: [{sender, receiver, pulse} | rest]
        } = proc
      ) do
    {type, receivers} = Map.get(outputs, receiver, {nil, []})

    {pulse, state} =
      recv(%{
        inputs: inputs,
        sender: sender,
        receiver: receiver,
        pulse: pulse,
        type: type,
        state: state
      })

    {lows, highs, pulses} =
      case pulse do
        nil ->
          {lows, highs, []}

        0 ->
          {lows + length(receivers), highs, Enum.map(receivers, &{receiver, &1, 0})}

        1 ->
          {lows, highs + length(receivers), Enum.map(receivers, &{receiver, &1, 1})}
      end

    if debug do
      for {sender, receiver, pulse} <- pulses do
        pulse = if pulse == 0, do: "low", else: "high"
        IO.puts("#{sender} -#{pulse}-> #{receiver}")
      end
    end

    run(%{proc | state: state, pulses: rest ++ pulses, lows: lows, highs: highs})
  end

  def recv(%{type: nil, receiver: receiver, pulse: pulse, state: state}),
    do: {nil, Map.put(state, receiver, pulse)}

  def recv(%{
        type: :broadcast,
        pulse: pulse,
        state: state
      }),
      do: {pulse, state}

  def recv(%{type: :flip_flop, pulse: 1, state: state}), do: {nil, state}

  def recv(%{
        type: :flip_flop,
        receiver: receiver,
        pulse: 0,
        state: state
      }) do
    prev = Map.get(state, receiver, 0)
    next = 1 - prev
    state = Map.put(state, receiver, next)
    {next, state}
  end

  def recv(%{
        type: :conjunction,
        inputs: inputs,
        sender: sender,
        receiver: receiver,
        pulse: pulse,
        state: state
      }) do
    prev = Map.get(state, receiver, %{})
    next = Map.put(prev, sender, pulse)
    pulse = if Enum.all?(inputs[receiver], fn input -> next[input] == 1 end), do: 0, else: 1
    state = Map.put(state, receiver, next)
    {pulse, state}
  end
end

{inputs, outputs} = Part1.parse(input)

{lows, highs, _} =
  for _ <- 1..1000, reduce: {0, 0, %{}} do
    {lows, highs, state} ->
      {new_lows, new_highs, state} = Part1.run(inputs, outputs, initial: state)
      {lows + new_lows, highs + new_highs, state}
  end

lows * highs

You can see I used the for-loop here to explore the graph at different iterations.

state =
  for _ <- 1..0//1, reduce: %{} do
    state ->
      {_, _, state} = Part1.run(inputs, outputs, initial: state)
      state
  end

{_, _, state} = Part1.run(inputs, outputs, initial: state, render: true)