I became obsessed with this problem after it took me a whole day to get a solution to Part 2. I have now implemented three different solutions: one, an exceedingly clever one (I can say this, because I didn’t think of the algorithm) which extends the Part 1 solution by finding all of the ways (with 0 or 1 presses of each button) to match the least significant bits of the desired joltages, and then recursing on the now-even joltages divided by two, until the desired joltages are all zero. I’ll post that one here, because it is the shortest self-contained solution (the other two are a long self-contained Elixir solution which implements Bareiss’s algorithm for reduction of integer matrices and then searches values of the remaining free variables for solutions, and another one that composes Prolog code that invokes SWI Prolog’s CLPQ solver).

defmodule Machine do
  defstruct target: 0, buttons: %{}, joltages: %{}, parity_map: %{}

  def parse_target(target_str) do
    to_charlist(target_str)
      |> Enum.with_index()
      |> Enum.reduce(0, fn {ch, i}, t ->
        case ch do
          ?. -> 
            t
          ?# ->
            Bitwise.bor(t, Bitwise.bsl(1, i))
        end
      end)
  end

  def parse_buttons(buttons_str) do
    Regex.scan(~r"\(([\d,]+)\)\s*", buttons_str)
      |> Enum.map(fn [_match, button_str] ->
        String.split(button_str, ",")
          |> Enum.map(&String.to_integer/1)
        end)
      |> Enum.with_index(fn l, i -> {i, MapSet.new(l)} end)
      |> Map.new()
  end

  def parse_joltages(joltages_str) do
    String.split(joltages_str, ",")
      |> Enum.map(&String.to_integer/1)
      |> Enum.with_index(fn jolt, i -> {i, jolt} end)
      |> Map.new()
  end
  
  def parse_line(line) do
    case Regex.run(~r"\[([.#]+)\]\s*([^{]+)\s*{([^}]+)}", line) do
      [_match, target_str, buttons_str, joltages_str] ->
        %__MODULE__{
          target: parse_target(target_str),
          buttons: parse_buttons(String.trim(buttons_str)),
          joltages: parse_joltages(joltages_str)
        }
    end
  end

  def parse(lines) do
    Enum.map(lines, &parse_line/1)
      |> Enum.map(&compute_parity_map/1)
  end

  def joltage_parity(joltages) do
    Enum.reduce(joltages, 0, fn {j, v}, parity ->
      Bitwise.bor(parity, Bitwise.bsl(Bitwise.band(v, 1), j))
    end)
  end
  
  def count_bpushes(bpushed, acc \\ 0) do
    if bpushed == 0 do
      acc
    else
      bpushed = Bitwise.band(bpushed, bpushed - 1)
      count_bpushes(bpushed, acc + 1)
    end
  end

  def compute_parity_map(machine = %__MODULE__{buttons: buttons}) do
    bpush_options = 0..(Bitwise.bsl(1, map_size(buttons)) - 1)
    parity_map = Enum.reduce(bpush_options, %{}, fn bpushed, map ->
      delta_jolts = Enum.reduce(buttons, %{}, fn {i, set}, djolts ->
        if Bitwise.band(1, Bitwise.bsr(bpushed, i)) == 1 do
          Enum.reduce(set, djolts, fn j, djolts ->
            Map.update(djolts, j, 1, fn v -> v + 1 end)
          end)
        else
          djolts
        end
      end)
      parity = joltage_parity(delta_jolts)
      push_count = count_bpushes(bpushed)
      push = {push_count, bpushed, delta_jolts}
      Map.update(map, parity, [push], fn pushes -> [push | pushes] end)
    end)
    %__MODULE__{machine | parity_map: parity_map}
  end

  def solve1(%__MODULE__{target: target, parity_map: parity_map}) do
    parity_map[target]
      |> Enum.map(fn {push_count, _bpushed, _delta_jolts} -> push_count end)
      |> Enum.min()
  end

  def reduced_joltages(joltages, delta_jolts) do
    Enum.reduce(delta_jolts, joltages, fn {j, dv}, joltages ->
      Map.update!(joltages, j, fn v -> v - dv end)
    end)
  end

  def solve2(mach = %__MODULE__{joltages: joltages, parity_map: parity_map}) do
    if Enum.all?(joltages, fn {_j, v} -> v == 0 end) do
      0
    else
      target = joltage_parity(joltages)
      push_options = Map.get(parity_map, target, [])
      Enum.map(push_options, fn {push_count, _bpushed, delta_jolts} ->
        rjoltages = reduced_joltages(joltages, delta_jolts)
        {push_count, rjoltages}
      end)
        |> Enum.reject(fn {_count, rjoltages} ->
            Enum.any?(rjoltages, fn {j, v} ->
              if Bitwise.band(v, 1) == 1, do: raise("odd joltage #{v} at #{j}")
              v < 0
            end)
          end)
        |> Enum.map(fn {count, rjoltages} ->
            rjoltages = Enum.map(rjoltages, fn {j, v} -> {j, Bitwise.bsr(v, 1)} end)
              |> Map.new()
            count2 = solve2(%__MODULE__{mach | joltages: rjoltages})
            if count2 != nil do
              count + Bitwise.bsl(count2, 1)
            end
          end)
        |> Enum.min(fn -> nil end)
    end
  end
end