Advent of code day 10

Mix.install(
  [
    {:kino, "~> 0.5.0"},
    {:dantzig, github: "hauleth/dantzig", ref: "use-proper-binary"}
  ],
  config: [
    # we can always use the original branch if we apply this patch https://github.com/tmbb/dantzig/pull/4
    # might be needed to use the previous hack in my commits to override the path.
    dantzig: [
      highs_binary_path:  "/usr/local/bin/highs" # this branch has fixes for integers. Original one
      # fails to round it correct and since we cannot have 0.5 buttons we must use it. 
    ]
  ]
)

Setup input

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

defmodule Combinations do
  def combinations(_, 0), do: [[]]
  def combinations([], _), do: []
  
  def combinations([h | t], r) do
    (for combo <- combinations(t, r - 1), do: [h | combo]) ++ combinations(t, r)
  end
end

lines =
  example
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.map(fn line ->
    [target | rest] = String.split(line, " ", trim: true)
    [j | buttons] = Enum.reverse(rest)

    j =
      String.trim(j, "{")
      |> String.trim("}")
      |> String.split(",", trim: true)
      |> Enum.map(&String.to_integer/1)

    buttons =
      Enum.reverse(buttons)
      |> Enum.map(fn button ->
        button
        |> String.trim_leading("(")
        |> String.trim_trailing(")")
        |> String.split(",")
        |> Enum.map(&String.to_integer/1)
        |> Enum.into(MapSet.new())
      end)

    target =
      target
      |> String.trim_leading("[")
      |> String.trim_trailing("]")
      |> String.split("", trim: true)
      |> Enum.with_index()
      |> Enum.filter(fn {v, _i} -> v == "#" end)
      |> Enum.map(fn {_, i} -> i end)
      |> Enum.into(MapSet.new())

    {target, buttons, j}
  end)

Part 01

total =
  Enum.reduce(lines, 0, fn {target, buttons, _}, acc ->
    result = Enum.reduce_while(1..length(buttons), 0, fn count, _inner_acc ->
      found = Enum.reduce_while(Combinations.combinations(buttons, count), nil, fn attempt, _light ->
        lights = Enum.reduce(attempt, MapSet.new(), fn button, lights ->
          MapSet.symmetric_difference(lights, button)
        end)
        
        if MapSet.equal?(lights, target) do
          {:halt, count}
        else
          {:cont, nil}
        end
      end)
      
      if found != nil do
        {:halt, found}
      else
        {:cont, 0}
      end
    end)
    
    acc + result
  end)

Part 02

defmodule JoltageOptimizer do
  alias Dantzig.Polynomial
  alias Dantzig.Constraint
  alias Dantzig.Problem
  alias Dantzig.Solution

  def solve_machine(buttons, targets) do
    p = Problem.new(direction: :minimize)

    # Create one variable per button
    {p, vars} =
      Enum.reduce(0..(length(buttons) - 1), {p, []}, fn i, {prob, vars_acc} ->
        {prob, var} = Problem.new_variable(prob, "v#{i}", min: 0, type: :integer)
        {prob, vars_acc ++ [var]}
      end)

    # For each counter (joltage requirement), add constraint
    p =
      targets
      |> Enum.with_index()
      |> Enum.reduce(p, fn {target, counter_idx}, prob ->
        # Find which buttons affect this counter
        affecting_button_indices =
          buttons
          |> Enum.with_index()
          |> Enum.filter(fn {button, _} -> counter_idx in button end)
          |> Enum.map(fn {_, button_idx} -> button_idx end)

        case affecting_button_indices do
          [] ->
            prob

          indices ->
            # Sum the variables for buttons that affect this counter
            button_vars = Enum.map(indices, fn idx -> Enum.at(vars, idx) end)
            poly = Polynomial.sum(button_vars)
            Problem.add_constraint(prob, Constraint.new(poly, :==, target))
        end
      end)

    # Minimize sum of all button presses
    p = Problem.increment_objective(p, Polynomial.sum(vars))

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

    # Return total button presses
    Enum.sum_by(vars, &Solution.evaluate(s, &1)) |> round()
  end
end

lines =
  Enum.map(lines, fn {_, buttons, joltages} ->
    buttons = buttons |> Enum.map(fn b -> MapSet.to_list(b) end)

    {buttons, joltages}
  end)

total =
  lines
  |> Enum.reduce(0, fn {buttons, targets}, acc ->
    result = JoltageOptimizer.solve_machine(buttons, targets)
    acc + result
  end)

total