# Day 10

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

## Section

<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiIxMCIsInNlc3Npb25fc2VjcmV0IjoiQURWRU5UX09GX0NPREVfU0VTU0lPTiIsInllYXIiOiIyMDI1In0","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->

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

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

  def decode("(" <> rest) do
    <<seq::binary-size(byte_size(rest) - 1), ")">> = rest

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

  def decode("{" <> rest) do
    <<seq::binary-size(byte_size(rest) - 1), "}">> = rest

    seq
    |> String.split(",")
    |> Enum.map(&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
```

```elixir
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)
```

<!-- livebook:{"branch_parent_index":0} -->

## 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
$$

```elixir
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
```

```elixir
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)
```

<!-- livebook:{"branch_parent_index":0} -->

## Part 2

```elixir
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
```

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

<!-- livebook:{"offset":4336,"stamp":{"token":"XCP.sfoBGIHkFvWbEHVrY-dL-QiEcwRz_ZCIjn3lQ0RFHActIOwEapmOPBt0ygbQAmrnEjYPlFm5KrcWx4LfIPbSznxxcea0fYORG9GbBBpRCm-tYbGXYTCGgqgTvOsifyWDNg","version":2}} -->