Day 10: Factory

use aoc_2025::timed_run;
use std::collections::HashMap;
use std::fmt::Display;
use std::io;
use std::vec::Vec;

struct Machine {
  lights: u64,
  buttons: Vec<u64>,
  joltages: Vec<u64>,
}

impl Machine {
  fn from_str(l: &str) -> Self {
    let (lights_str, remaining) = l.split_once(' ').unwrap();
    let (buttons_str, joltages_str) = remaining.rsplit_once(' ').unwrap();
    let lights = lights_str
      .strip_prefix('[')
      .unwrap()
      .strip_suffix(']')
      .unwrap()
      .chars()
      .enumerate()
      .fold(0, |lights, (i, c)| match c {
        '#' => lights | (1 << i),
        '.' => lights,
        _ => panic!(),
      });
    let buttons = buttons_str
      .split(' ')
      .map(|b| {
        b.strip_prefix('(')
          .unwrap()
          .strip_suffix(')')
          .unwrap()
          .split(',')
          .map(|i| 1 << i.parse::<u64>().unwrap())
          .reduce(|a, b| a | b)
          .unwrap()
      })
      .collect();
    let joltages = joltages_str
      .strip_prefix('{')
      .unwrap()
      .strip_suffix('}')
      .unwrap()
      .split(',')
      .map(|i| i.parse::<u64>().unwrap())
      .collect();
    Machine {
      lights,
      buttons,
      joltages,
    }
  }

  fn print<T: Display>(&self, label: T) {
    println!("Machine {label}:");
    println!("  Lights: {:b}", self.lights);
    for (j, b) in self.buttons.iter().enumerate() {
      println!("  Button {j}: {b:b}");
    }
    println!("  Joltages: {:?}", self.joltages);
  }
}

struct Input {
  machines: Vec<Machine>,
}

impl Input {
  fn read_from_stdin() -> Input {
    Input {
      machines: io::stdin()
        .lines()
        .map(|l| Machine::from_str(l.unwrap().as_str()))
        .collect(),
    }
  }
}

fn part1(input: &Input) -> u64 {
  let mut ret = 0;
  for m in &input.machines {
    let mut min_found = m.buttons.len() + 1;
    for i in 0..2_u64.pow(m.buttons.len() as u32) {
      let mut lights = 0;
      let mut tmp = i;
      while tmp != 0 {
        let pos = tmp.trailing_zeros();
        lights ^= m.buttons[pos as usize];
        tmp &= !(1 << pos);
      }
      if lights == m.lights {
        min_found = min_found.min(i.count_ones() as usize);
      }
    }
    if min_found > m.buttons.len() {
      m.print("failed machine");
      panic!();
    }
    assert!(min_found < m.buttons.len());
    ret += min_found;
  }
  ret as u64
}

struct SystemEq {
  equations: HashMap<u32, u64>,
  num_presses: u64,
  num_unsolved: u64,
}

#[derive(Debug)]
struct SystemErr;

impl SystemEq {
  #[allow(dead_code)]
  fn print(&self) {
    println!(
      "    num_presses: {}, num_unsolved: {}",
      self.num_presses, self.num_unsolved
    );
    let num_ones = self
      .equations
      .iter()
      .fold(0, |a, (&k, _)| a | k)
      .count_ones() as u64;
    if num_ones != self.num_unsolved {
      println!(
        "!!!!Incorrect num_unsolved: cached {}, actual {}",
        self.num_unsolved, num_ones
      );
    }
    for (k, v) in &self.equations {
      println!("    {k:013b} = {v}");
    }
  }

  fn clone(&self) -> SystemEq {
    SystemEq {
      equations: self.equations.clone(),
      num_presses: self.num_presses,
      num_unsolved: self.num_unsolved,
    }
  }

  fn checked_insert(&mut self, k: u32, v: u64) -> Result<(), SystemErr> {
    if let Some(old_val) = self.equations.insert(k, v) {
      if old_val != v {
        return Err(SystemErr);
      }
    }
    Ok(())
  }

  // Eliminate the given variable using the given value.
  fn eliminate_single(&mut self, single: u32, val: u64) -> Result<(), SystemErr> {
    self.num_presses += val;
    self.num_unsolved = self.num_unsolved.checked_sub(1).unwrap();
    let updated = self
      .equations
      .extract_if(|k, _| k & single != 0)
      .collect::<Vec<_>>();
    for (k, v) in updated {
      if k != single {
        let new_val = v.checked_sub(val).ok_or(SystemErr)?;
        self.checked_insert(k & !single, new_val)?;
      } else if v != val {
        return Err(SystemErr);
      }
    }
    Ok(())
  }

  // Eliminate all variables involved in equations that are sum(xs) = 0.
  fn eliminate_nulls(&mut self) -> Result<(), SystemErr> {
    let mut nulls = self
      .equations
      .extract_if(|k, v| *v == 0 && k.count_ones() > 1)
      .fold(0, |a, (k, _)| a | k);
    while nulls != 0 {
      let pos = nulls.trailing_zeros();
      let single = 1 << pos;
      self.eliminate_single(single, 0)?;
      nulls &= !single;
    }
    Ok(())
  }

  // Eliminate all variables involved in equations with a single variable. Returns true if it
  // eliminated anything.
  fn eliminate_singles(&mut self) -> Result<bool, SystemErr> {
    let singles = self
      .equations
      .extract_if(|k, _| k.count_ones() == 1)
      .collect::<Vec<_>>();
    let has_singles = !singles.is_empty();
    for (single, val) in singles {
      self.eliminate_single(single, val)?;
    }
    Ok(has_singles)
  }

  // Tries to generate equations by substracting one from another. Returns true if it generated
  // anything.
  fn generate_eqs(&mut self) -> Result<bool, SystemErr> {
    let mut added = false;
    let copied_eqs = self
      .equations
      .iter()
      .map(|(k, v)| (*k, *v))
      .collect::<Vec<_>>();
    for (k, v) in copied_eqs {
      let new_eqs = self
        .equations
        .iter()
        .filter(|(nk, _)| **nk != k && *nk & k == k && !self.equations.contains_key(&(*nk & !k)))
        .map(|(nk, nv)| (nk & !k, nv.checked_sub(v)))
        .collect::<Vec<_>>();
      added = added || !new_eqs.is_empty();
      for (nk, nv) in new_eqs {
        self.checked_insert(nk, nv.ok_or(SystemErr)?)?;
      }
    }
    Ok(added)
  }

  // Tries applying all simplification steps until nothing more can be done.
  fn simplify(&mut self) -> Result<(), SystemErr> {
    loop {
      self.eliminate_nulls()?;
      if self.eliminate_singles()? {
        continue;
      }
      if !self.generate_eqs()? {
        break;
      }
    }
    Ok(())
  }

  fn solve(&mut self) -> Result<(), SystemErr> {
    self.simplify()?;
    if self.num_unsolved == 0 {
      return Ok(());
    }
    let mut min_val = u64::MAX;
    let mut key_for_min = None;
    for (&k, &v) in &self.equations {
      if v < min_val {
        min_val = v;
        key_for_min = Some(k);
      }
    }
    let single = 1 << key_for_min.unwrap().trailing_zeros();
    let mut min_found = None;
    for i in 0..=min_val {
      let mut new_sys = self.clone();
      if new_sys.eliminate_single(single, i).is_err() {
        continue;
      }
      if new_sys.solve().is_err() {
        continue;
      }
      min_found =
        Some(min_found.map_or(new_sys.num_presses, |min: u64| min.min(new_sys.num_presses)));
    }
    if let Some(min) = min_found {
      self.num_presses = min;
      self.num_unsolved = 0;
      Ok(())
    } else {
      Err(SystemErr)
    }
  }
}

fn part2(input: &Input) -> u64 {
  let mut ret = 0;
  for (mi, m) in input.machines.iter().enumerate() {
    let mut start_equations = vec![0; m.joltages.len()];
    for (i, b) in m.buttons.iter().enumerate() {
      let mut tmp = *b;
      while tmp != 0 {
        let pos = tmp.trailing_zeros();
        start_equations[pos as usize] |= 1 << i;
        tmp &= !(1 << pos);
      }
    }
    let mut equations = HashMap::<u32, u64>::new();
    for (i, e) in start_equations.into_iter().enumerate() {
      equations.insert(e, m.joltages[i]);
    }
    let mut system = SystemEq {
      equations,
      num_presses: 0,
      num_unsolved: m.buttons.len() as u64,
    };
    system.simplify().unwrap();
    if system.num_unsolved == 0 {
      ret += 1;
    }
    continue;
    if system.solve().is_err() {
      m.print(mi);
      println!("  Current state:");
      for (k, v) in system.equations {
        println!("    {k:013b} = {v}");
      }
      panic!("failed to find a solution");
    }
    ret += system.num_presses;
  }
  ret
}

fn main() {
  let input = Input::read_from_stdin();
  timed_run("Part 1", || part1(&input));
  timed_run("Part 2", || part2(&input));
}

import itertools
import pulp 

BIG_NUMBER = 10000

def parse_input(lines: list[str]) -> tuple[list[str], list[list[list[int]]], list[list[int]]]:
  lights = []
  buttons = []
  joltages = []
  for line in lines:
    light, *button, joltage = line.split()
    lights.append([c == '#' for c in light.strip('[]')])
    buttons.append([list(map(int, b.strip('()').split(','))) for b in button])
    joltages.append(list(map(int, joltage.strip('{}').split(','))))
  return lights, buttons, joltages

def toggle_lights(target: list[bool], button_combos: tuple[list[int]]):
  lights = [False]*len(target)
  for bc in button_combos:
    for b in bc:
      lights[b] ^= True
  
  if target == lights:
    return len(button_combos)
  return BIG_NUMBER

def increase_joltage_ilp(target: list[int], button_list: list[list[int]]) -> int:
  matrix = [[0]*len(button_list) for _ in range(len(target))]
  for j, buttons in enumerate(button_list):
    for i in buttons:
      matrix[i][j] = 1
  problem = pulp.LpProblem("Minimum Button Presses", pulp.LpMinimize)
  vars = [pulp.LpVariable(f'x_{i}', lowBound=0, cat='Integer') for i in range(len(button_list))]
  problem += pulp.lpSum(vars)
  for i in range(len(target)):
    problem += pulp.lpSum(matrix[i][j] * vars[j] for j in range(len(button_list))) == target[i]
  problem.solve()
  return int(sum(v.value() for v in vars))


def part_one(input: tuple[list[str], list[list[list[int]]], list[list[int]]]) -> int:
  target_lights, buttons, _ = input
  presses = 0
  for target, button_list in zip(target_lights, buttons):
    button_combos = []
    for r in range(0, len(button_list)):
      button_combos.extend(itertools.combinations(button_list, r+1))
    presses += min(toggle_lights(target, bc) for bc in button_combos)
  return presses

def part_two(input: tuple[list[str], list[list[list[int]]], list[list[int]]]) -> int:
  _, buttons, joltages = input
  presses = 0
  for i, (button_list, target) in enumerate(zip(buttons, joltages)):
    print(i, target)
    #presses += increase_joltage_dfs(target, [0]*len(target), button_list, 0, {})
    #presses += increase_joltage_bfs(target, button_list)
    presses += increase_joltage_ilp(target, button_list)
  return presses

def main() -> None:
  with open('10.in') as file:
    lines = [line.rstrip() for line in file]

  input = parse_input(lines)
  print('Part 1:', part_one(input))
  print('Part 2:', part_two(input))

if __name__ == '__main__':
  main()

@dataclass(frozen=True)
class Machine:
    lights: int  # Integer bitmap of lights that should be illuminated
    buttons: tuple[int, ...]  # Integer bitmasks of lights toggled when pressed

    def __repr__(self) -> str:
        return (
            "Machine(\n"
            + f"   lights: {self.lights:08b}\n"
            +  "  buttons: "
            +  "           ".join(f"{button:08b}\n" for button in self.buttons)
            +  ")"
        )


def solve(input: str) -> int:
    return sum(minimum_presses(input))


def minimum_presses(input: str) -> Iterator[int]:
    for machine in machines(input):
        lights_after_presses = {0: 0}

        while machine.lights not in lights_after_presses:
            for lights, presses in tuple(lights_after_presses.items()):
                for button in machine.buttons:
                    lights_after_press = lights ^ button
                    if lights_after_press not in lights_after_presses:
                        lights_after_presses[lights_after_press] = presses + 1

        yield lights_after_presses[machine.lights]


def machines(input: str) -> Iterator[Machine]:
    for line in input.strip().splitlines():
        lights_str, *buttons_strs, joltages_str = line.split()
        lights_0b_str = lights_str.strip("[]").replace(".", "0").replace("#", "1")
        buttons = tuple(
            tuple(map(int, button.strip("()").split(",")))
            for button in buttons_strs
        )
        yield Machine(
            lights=int(lights_0b_str, 2),
            buttons=tuple(
                sum(2 ** (len(lights_0b_str) - 1 - digit) for digit in button)
                for button in buttons
            ),
        )

@dataclass(frozen=True)
class Machine:
    joltages: int  # Joltages packed into a single integer to perform SIMD additions
    joltage_limit: int  # Bitmask to check if a machine is overjolted
    buttons: tuple[int, ...]  # Integer bitmasks of joltages incremented when pressed

    def __repr__(self) -> str:
        return (
            "Machine(\n"
            + f"  joltages: {self.joltages:064b}\n"
            + f"     limit: {self.joltage_limit:064b}\n"
            +  "   buttons: "
            +  "            ".join(f"{button:064b}\n" for button in self.buttons)
            +  ")"
        )


def solve(input: str) -> int:
    return sum(minimum_presses(input))


def minimum_presses(input: str) -> Iterator[int]:
    for machine in machines(input):
        joltages_after_presses = {0: 0}

        while machine.joltages not in joltages_after_presses:
            joltages_before_presses = joltages_after_presses
            joltages_after_presses = {}

            for joltages, presses in joltages_before_presses.items():
                for button in machine.buttons:
                    joltages_after_press = joltages + button
                    if joltages_after_press & machine.joltage_limit == 0:
                        joltages_after_presses[joltages_after_press] = presses + 1

        yield joltages_after_presses[machine.joltages]


def machines(input: str) -> Iterator[Machine]:
    for line in input.strip().splitlines():
        lights, *buttons, joltages = line.split()
        yield Machine(
            joltages=sum(
                map(
                    lambda i_j: i_j[1] << (10 * i_j[0]),
                    enumerate(
                        map(
                            int,
                            joltages.strip("{}").split(","),
                        )
                    ),
                )
            ),
            joltage_limit=sum(
                map(
                    lambda i_j: 2 ** int.bit_length(i_j[1]) << (10 * i_j[0]),
                    enumerate(
                        map(
                            int,
                            joltages.strip("{}").split(","),
                        )
                    ),
                )
            ),
            buttons=tuple(
                sum(
                    map(
                        lambda n: 1 << (10 * n),
                        map(int, button.strip("()").split(",")),
                    )
                )
                for button in buttons
            ),
        )

For part 1, I just iterated through all the combinations until I found one that worked. I wanted to iterate through them in ascending order of number of presses, so that I didn't have to go through every combination - after some searching I discovered Gosper's hack, which let me do it with bitsets (which is maybe more efficient than the alternative?).

Part 2 was rough. I realized I needed to solve linear systems almost immediately, but actually doing so was another story. I've never really done linear algebra before, so it took me a while (and a couple hints taken from other people's descriptions of their solutions) to figure out how to even start. What I ended up doing is:

1. Build an augmented matrix for the given machine.
2. Use Gaussian elimination over the matrix, and find the pivot and free columns.
3. Iterate through all possible combinations of values for the free variables and back-substitute. Find the solution with the smallest sum of its coefficients, and add that sum to the total. This is the inefficient part - I know each button can't be pressed any more times than the counter it affects with the lowest required joltage, but those bounds seem to be a little too large, which slows things down a lot. I couldn't figure out how to get the bounds any lower, though.

var total_presses_for_lights = 0
var total_presses_for_joltages = 0

for line in File.read_to_string("inputs/day_10.txt").split("\n"): {
    var parts = line.split(" ")

    var lights: List[Boolean] = []
    parts.shift().slice(1, -1).to_bytestring().each_byte(|char|
        lights.push(char == '#')
    )

    var max_light_index = lights.size() - 1

    var required_state = 0
    for i, light in lights.reverse(): {
        if light: {
            required_state |= 1 << i
        }
    }

    var buttons: List[List[Integer]] = []
    var required_joltages: List[Integer] = []

    for part in parts: {
        var numbers = part
            .slice(1, -1)
            .split(",")
            .map(String.parse_i)
            .map(Option.unwrap)

        if part[0] == '(': {
            buttons.push(numbers)
        else:
            required_joltages = numbers
            break
        }
    }

    var button_count = buttons.size()
    var max_button_index = button_count - 1
    var button_mask_limit = 1 << button_count
    var reached_required_state = false

    for presses in 1...button_count: {
        var button_mask = (1 << presses) - 1
        while button_mask < button_mask_limit: {
            var state = 0

            for button_index in 0...max_button_index: {
                if button_mask & 1 << max_button_index - button_index: {
                    for light_index in buttons[button_index]: {
                        state ^= 1 << max_light_index - light_index
                    }
                }
            }

            if state == required_state: {
                total_presses_for_lights += presses
                reached_required_state = true
                break
            }

            # Use Gosper's hack to find the next combination of presses with the
            # same length. This lets us avoid having to iterate through every
            # combination to find the shortest working one.
            var c = button_mask & -button_mask
            var r = button_mask + c
            button_mask = (((r ^ button_mask) >> 2) / c) | r
        }

        if reached_required_state: {
            break
        }
    }

    var rows = required_joltages.map_with_index(|joltage, index|
        buttons.map(|button| button.any(|i| i == index).to_i()).push(joltage)
    )

    var width = buttons.size()
    var height = rows.size()

    var row = 0
    var pivot_columns: List[Integer] = []
    var free_columns: List[Integer] = []

    for column in 0...width - 1: {
        var pivot = -1

        for i in row...height - 1: {
            if rows[i][column]: {
                pivot = i
                break
            }
        }

        if pivot == -1: {
            free_columns.push(column)
            continue
        }

        var temp = rows[row]
        rows[row] = rows[pivot]
        rows[pivot] = temp

        for i in row + 1...height - 1: {
            var value = rows[i][column]
            if value: {
                var pivot_value = rows[row][column]
                for j in 0...width: {
                    rows[i][j] = rows[i][j] * pivot_value - rows[row][j] * value
                }
            }
        }

        row += 1
        pivot_columns.push(column)
    }

    var free_variable_combinations = 1
    var free_variable_bounds = free_columns.map(|column|
        # Buttons can't possibly be pushed more times than the counter they
        # affect with the lowest required joltage.
        var bound = buttons[column].fold(-1, (|minimum, index|
            var joltage = required_joltages[index]

            if joltage < minimum || minimum == -1: {
                return joltage
            }

            minimum
        )) + 1

        free_variable_combinations *= bound
        bound
    )

    var free_column_count = free_columns.size()
    var free_variables = List.repeat(free_column_count, 0)

    var minimum_presses = -1

    for _ in 1...free_variable_combinations: {
        var solution = List.repeat(width, 0)

        for i, column in free_columns: {
            solution[column] = free_variables[i]
        }

        var valid = true

        for i in pivot_columns.size() - 1...0 by -1: {
            var column = pivot_columns[i]
            var joltage = rows[i][width]

            for j in column + 1...width - 1: {
                joltage -= rows[i][j] * solution[j]
            }

            var value = rows[i][column]

            if joltage % value: {
                valid = false
                break
            }

            joltage /= value

            if joltage < 0: {
                valid = false
                break
            }

            solution[column] = joltage
        }

        for i in 0...free_column_count - 1: {
            free_variables[i] += 1
            if free_variables[i] == free_variable_bounds[i]: {
                free_variables[i] = 0
            else:
                break
            }
        }

        if !valid: {
            continue
        }

        var presses = solution.fold(0, (|sum, value| sum + value))
        if presses < minimum_presses || minimum_presses == -1: {
            minimum_presses = presses
        }
    }

    total_presses_for_joltages += minimum_presses
}

print("Part 1: {}\nPart 2: {}".format(
    total_presses_for_lights, total_presses_for_joltages
))

Like some others, I noticed that the buttons could be represented as bitmasks that are XOR'ed with 0 to try and produce a target integer: the light diagram, also represented as a binary number.

I use an additional "meta-bitmask" for selecting which of the button bitmasks to apply, since we need to check the entire power set of the buttons to find the minimal number of presses. The best way I could think of to generate a power set of S is to iterate through [0, 2^{(cardinality of S)} - 1], using the iterated value as the meta-bitmask.

Some of my code (particularly the comprehensions) looks a bit cursed.
Elixir is a very... punctuation-rich language.

defmodule AdventOfCode.Solution.Year2025.Day10 do
  import Bitwise, only: [&&&: 2, |||: 2, >>>: 2, <<<: 2]

  use AdventOfCode.Solution.SharedParse

  # Bitwise XOR should have an operator too! So let's make one >:]
  defdelegate a <~> b, to: Bitwise, as: :bxor

  @impl true
  def parse(input) do
    for line <- String.split(input, "\n", trim: true) do
      [diagram | others] = line |> String.split() |> Enum.map(&String.slice(&1, 1..-2//1))
      {buttons, [jolts]} = Enum.split(others, -1)
      {goal, bit_width} = parse_goal(diagram)
      {goal, Enum.map(buttons, &parse_mask(&1, bit_width)), jolts}
    end
  end

  def part1(machines) do
    machines
    |> Task.async_stream(&min_button_presses_p1/1, ordered: false)
    |> Enum.sum_by(fn {:ok, min_presses} -> min_presses end)
  end

  defp min_button_presses_p1({goal, masks, _}) do
    bit_flag_to_mask = Enum.with_index(masks, fn mask, i -> {2 ** i, mask} end)

    1..(2 ** length(masks) - 1)//1
    |> Stream.filter(&(apply_masks(bit_flag_to_mask, &1) == goal))
    |> Enum.reduce_while(:infinity, fn
      _, 1 -> {:halt, 1}
      meta_mask, min_acc -> {:cont, min(min_acc, sum_bits(meta_mask))}
    end)
  end

  defp apply_masks(bit_flag_to_mask, meta_mask) do
    for({b, mask} <- bit_flag_to_mask, (b &&& meta_mask) != 0, reduce: 0, do: (n -> n <~> mask))
  end

  defp sum_bits(n, acc \\ 0)
  defp sum_bits(0, acc), do: acc
  defp sum_bits(n, acc), do: sum_bits(n >>> 1, acc + (n &&& 1))

  defp parse_goal(s) do
    {for(<<c <- s>>, reduce: 0, do: (n -> (n <<< 1) + if(c == ?#, do: 1, else: 0))), byte_size(s)}
  end

  defp parse_mask(btn, goal_bit_width) do
    for <<c <- btn>>, c in ?0..?9, reduce: 0, do: (n -> n ||| 2 ** (goal_bit_width - 1 - c + ?0))
  end
end

Name             ips        average  deviation         median         99th %
Parse         765.93        1.31 ms     ±1.94%        1.31 ms        1.36 ms
Part 1        194.67        5.14 ms    ±29.27%        4.38 ms        8.17 ms