Day 10

Mix.install([:kino_aoc, {:dantzig, github: "hauleth/dantzig", ref: "use-proper-binary"}],
config: [
  dantzig: [
    highs_binary_path: System.find_executable("highs")
  ]
])

Section

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2025", "10", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))

defmodule Decoder do
  def decode("[" <> pattern), do: do_lights(String.reverse(String.trim_trailing(pattern, "]")), 0)

  def decode("(" <> rest) do
    <> = rest

    seq
    |> String.split(",")
    |> Enum.map(&amp;String.to_integer/1)
  end

  def decode("{" <> rest) do
    <> = rest

    seq
    |> String.split(",")
    |> Enum.map(&amp;String.to_integer/1)
  end
  
  defp do_lights("", num), do: num
  defp do_lights("." <> rest, num), do: do_lights(rest, 2 * num)
  defp do_lights("#" <> rest, num), do: do_lights(rest, 2 * num + 1)
end

indicators =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Enum.map(fn raw ->
    [lights | rest] =
      raw
      |> String.split()
      |> Enum.map(&Decoder.decode/1)

    {buttons, [whatever]} = Enum.split(rest, -1)

    {lights, buttons, whatever}
  end)

Part 1

We are looking for such sequence of buttons that will provide pattern we are looking for. It can be solved by brute force with simple observation that buttons $a_n$ as well as light pattern $p$ can be represented by binary pattern. This allows us to use $\oplus$ (exclusive or, aka XOR) as an operation for pressing button.

Thanks to that observation we can see, that order in which we press buttons doesn’t matter, as $\oplus$ is reflexive, i.e.:

$$ \begin{equation} a \oplus b = b \oplus a \end{equation} $$

Additionally, wrt. $\oplus$ we have identity element $0$ and inverse element is the same as an original element, i.e.

$$ \begin{align} a \oplus 0 = a \ a \oplus a = 0 \end{align} $$

Additionally we can observe that:

$$ \begin{equation} (a \oplus b) \oplus c = a \oplus (b \oplus c) \end{equation} $$

With that observation we can deduce that each button will be pressed at most once and the order in which we press buttons doesn’t matter.

So now we look for set $A = {a_n}$ of buttons that

$$ A \in \mathcal{P}(\text{Buttons}) \ \forall_{i, j} \; i \ne j \implies a_i \ne a_j \ \bigoplus A = p $$

defmodule Comb do
  def all_possible([]), do: [[]]
  def all_possible([a | rest]) do
    sub = all_possible(rest)

    sub ++ Enum.map(sub, &[a | &1])
  end
end

indicators
|> Enum.sum_by(fn {p, a, _} ->
  a
  |> Enum.map(&Enum.sum_by(&1, fn p -> 2 ** p end))
  |> Comb.all_possible()
  |> Enum.sort_by(&length/1)
  |> Enum.find(fn seq ->
    r = Enum.reduce(seq, 0, &Bitwise.bxor/2)

    p == r
  end)
  |> length()
end)

Part 2

defmodule Joltage do
  alias Dantzig.Polynomial
  alias Dantzig.Constraint
  alias Dantzig.Problem

  def solve({_pat, buttons, goal}) do
    p = Problem.new(direction: :minimize)

    {vars, {p, map}} =
      buttons
      |> Enum.with_index()
      |> Enum.map_reduce({p, %{}}, fn {list, idx}, {p, acc} ->
        {p, var} = Problem.new_variable(p, "v#{idx}", min: 0, type: :integer)

        acc =
          Enum.reduce(list, acc, fn key, map ->
            Map.update(map, key, [var], &[var | &1])
          end)

        {var, {p, acc}}
      end)

    p =
      map
      |> Enum.sort()
      |> Enum.map(&elem(&1, 1))
      |> Enum.zip(goal)
      |> Enum.reduce(p, fn {vars, target}, p ->
        poly = Polynomial.sum(vars)
        const = Constraint.new(poly, :==, target)

        Problem.add_constraint(p, const)
      end)

    p = Problem.increment_objective(p, Polynomial.sum(vars))

    {:ok, s} = Dantzig.HiGHS.solve(p)

    Enum.sum_by(vars, &Dantzig.Solution.evaluate(s, &1))
  end
end

indicators
|> Task.async_stream(&Joltage.solve/1, ordered: false)
|> Enum.sum_by(&elem(&1, 1))
|> trunc()