day20.livemd

Day 20: Pulse Propagation

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

Input

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

defmodule Day20Shared do
  def parse(input) do
    modules =
      input
      |> Kino.Input.read()
      |> String.split("\n")
      |> Enum.map(fn module_raw ->
        [type_raw, name, outs_raw] =
          Regex.run(~r/([%&]*)(\w+) -> ([\w, ]+)$/, module_raw, capture: :all_but_first)

        outs = String.split(outs_raw, ~r/[,\s+]/, trim: true)

        config =
          case type_raw do
            "" -> %{type: :cast, outs: outs}
            "%" -> %{type: :flip, outs: outs, state: :off}
            "&" -> %{type: :conj, outs: outs, state: %{}}
          end

        {name, config}
      end)

    {machinezy(modules), graphy(modules)}
  end

  # Sets inputs and initial state for the conjuction modules, but leaves the rest of
  # configuration the same as parsed
  defp machinezy(modules) do
    modules
    |> Enum.map(fn
      {name, %{type: :conj} = config} ->
        inputs =
          modules
          |> Enum.filter(fn {_, %{outs: outs}} -> Enum.member?(outs, name) end)
          |> Enum.map(fn {out_name, _} -> out_name end)

        state =
          inputs
          |> Enum.map(fn inp -> {inp, :low} end)
          |> Map.new()

        {name, %{config | state: state}}

      otherwise ->
        otherwise
    end)
    |> Map.new()
  end

  # Generates a graph with the vertices and edges for the given machine (not sure if needed)
  defp graphy(modules) do
    module_names = Enum.map(modules, &elem(&1, 0))
    graph = Graph.new() |> Graph.add_vertices(module_names)

    Enum.reduce(modules, graph, fn {name, %{outs: outs}}, graph ->
      Enum.reduce(outs, graph, fn out, graph ->
        Graph.add_edge(graph, name, out)
      end)
    end)
  end
end

Day20Shared.parse(input)

Part 1

defmodule Day20Part1 do
  @init_pulses [{"button", :low, "broadcaster"}]
  @init_counts {0, 0}
  @steps 1000

  def solve({machine, _graph}) do
    1..@steps
    |> Enum.reduce({machine, @init_counts}, fn _step, {machine, counts} ->
      process(@init_pulses, machine, counts)
    end)
    # |> IO.inspect()
    |> then(fn {_machine, {low_n, high_n}} ->
      low_n * high_n
    end)
  end

  defp process([], machine, counts), do: {machine, counts}

  defp process([pulse | queue], machine, {low_n, high_n}) do
    {new_machine, new_pulses} = update_machine(pulse, machine)
    # IO.inspect(pulse, label: "pulse")

    new_counts =
      if elem(pulse, 1) == :low do
        {low_n + 1, high_n}
      else
        {low_n, high_n + 1}
      end

    process(queue ++ new_pulses, new_machine, new_counts)
  end

  defp update_machine({from_module, pulse_type, to_module}, machine) do
    case Map.get(machine, to_module) do
      %{type: :cast} = module ->
        next_pulses = Enum.map(module[:outs], fn out -> {to_module, pulse_type, out} end)

        {machine, next_pulses}

      %{type: :flip} = module ->
        # Flip-flop modules (prefix %) are either on or off; they are initially off.
        # If a flip-flop module receives a high pulse, it is ignored and nothing happens.
        # However, if a flip-flop module receives a low pulse, it flips between on and off.
        # If it was off, it turns on and sends a high pulse.
        # If it was on, it turns off and sends a low pulse.

        if pulse_type == :high do
          {machine, []}
        else
          module = flip(module)

          next_pulses =
            Enum.map(module[:outs], fn out ->
              if module[:state] == :on do
                {to_module, :high, out}
              else
                {to_module, :low, out}
              end
            end)

          {%{machine | to_module => module}, next_pulses}
        end

      %{type: :conj, state: state} = module ->
        # Conjunction modules (prefix &) remember the type of the most recent pulse received
        # from each of their connected input modules; they initially default to remembering
        # a low pulse for each input.
        # When a pulse is received, the conjunction module first updates its memory for
        # that input. Then, if it remembers high pulses for all inputs, it sends a low pulse;
        # otherwise, it sends a high pulse.

        state = %{state | from_module => pulse_type}
        module = %{module | state: state}
        signal = invertor_will_send(state)

        next_pulses = Enum.map(module[:outs], fn out -> {to_module, signal, out} end)

        {%{machine | to_module => module}, next_pulses}

      nil ->
        {machine, []}
    end
  end

  defp flip(%{state: :off} = module), do: %{module | state: :on}
  defp flip(%{state: :on} = module), do: %{module | state: :off}

  defp invertor_will_send(state) do
    if Enum.all?(state, fn {_, type} -> type == :high end) do
      :low
    else
      :high
    end
  end
end

input
|> Day20Shared.parse()
|> Day20Part1.solve()

# 743871576 is the right answer

Part 2

defmodule Day20Part2 do
  # See https://elixirforum.com/t/advent-of-code-2023-day-20/60474 for solution ideas
  # Maybe use https://csacademy.com/app/graph_editor/ to find cycles in the input
  # Kostya's result: 243_221_023_462_303
end

# input
# |> Day20Shared.parse()
# |> Day20Part2.solve()