aoc/year2025/
day10.rs

1//! # Factory
2use std::array::from_fn;
3
4use crate::util::bitset::*;
5use crate::util::math::*;
6use crate::util::parse::*;
7
8const MAX_BUTTONS: usize = 14;
9const MAX_JOLTAGES: usize = 11;
10
11type Column = [i32; MAX_JOLTAGES];
12
13pub struct Machine {
14    lights: u32,
15    buttons: Vec<u32>,
16    joltages: Vec<i32>,
17}
18
19struct Subspace {
20    rank: usize,
21    nullity: usize,
22    lcm: i32,
23    rhs: Column,
24    basis: Vec<Basis>,
25}
26
27#[derive(Clone, Copy)]
28struct Basis {
29    limit: i32,
30    cost: i32,
31    vs: Column,
32}
33
34pub fn parse(input: &str) -> Vec<Machine> {
35    input.lines().map(parse_machine).collect()
36}
37
38pub fn part1(input: &[Machine]) -> u32 {
39    input.iter().map(configure_lights).sum()
40}
41
42pub fn part2(input: &[Machine]) -> i32 {
43    input.iter().map(configure_joltages).sum()
44}
45
46/// Convert light patterns and buttons to bitmasks to speed up part one.
47fn parse_machine(line: &str) -> Machine {
48    let tokens: Vec<_> = line.split_ascii_whitespace().collect();
49    let last = tokens.len() - 1;
50
51    let lights = tokens[0][1..]
52        .bytes()
53        .enumerate()
54        .fold(0, |light, (i, b)| light | (u32::from(b == b'#') << i));
55    let buttons = tokens[1..last]
56        .iter()
57        .map(|token| token.iter_unsigned().fold(0, |button, i: u32| button | (1 << i)))
58        .collect();
59    let joltages = tokens[last].iter_signed().collect();
60
61    Machine { lights, buttons, joltages }
62}
63
64/// Check all patterns with one set bit, then patterns with two set bits, and so on,
65/// returning early as soon as we find a match without checking all possible combinations.
66fn configure_lights(machine: &Machine) -> u32 {
67    let Machine { lights, buttons, joltages } = machine;
68    let width = joltages.len();
69    let height = buttons.len();
70
71    let mut rank = 0;
72    let mut h = [0; MAX_BUTTONS];
73    let mut u: [u32; MAX_BUTTONS] = from_fn(|row| 1 << row);
74
75    h[..height].copy_from_slice(buttons);
76
77    for col in 0..width {
78        let mask = 1 << col;
79        let Some(found) = (rank..height).find(|&row| h[row] & mask != 0) else {
80            continue;
81        };
82
83        h.swap(rank, found);
84        u.swap(rank, found);
85
86        for row in 0..height {
87            if row != rank && h[row] & mask != 0 {
88                h[row] ^= h[rank];
89                u[row] ^= u[rank];
90            }
91        }
92
93        rank += 1;
94    }
95
96    let nullity = height - rank;
97    let particular_solution = (0..rank).fold(0, |particular_solution, row| {
98        let mask = h[row].isolate_lowest_one();
99        particular_solution ^ if lights & mask == 0 { 0 } else { u[row] }
100    });
101
102    (0..1 << nullity)
103        .map(|i| {
104            i.biterator().fold(particular_solution, |presses, j| presses ^ u[rank + j]).count_ones()
105        })
106        .min()
107        .unwrap()
108}
109
110/// Convert the buttons and joltages to simultaneous equations,
111/// then use [Gaussian Elimination](https://en.wikipedia.org/wiki/Gaussian_elimination)
112/// to reduce (the up to 13) dimensions of the full solution space to a (between 0 and 3)
113/// dimensional subspace of only the free variables.
114fn configure_joltages(machine: &Machine) -> i32 {
115    let subspace @ Subspace { rank, nullity, lcm, rhs, .. } = gaussian_elimination(machine);
116    let particular_solution = rhs[..rank].iter().sum();
117
118    if nullity == 0 {
119        particular_solution / lcm
120    } else {
121        let remaining = (1 << subspace.basis.len()) - 1;
122        recurse(&subspace, rhs, remaining, particular_solution).unwrap()
123    }
124}
125
126fn gaussian_elimination(machine: &Machine) -> Subspace {
127    let Machine { buttons, joltages, .. } = machine;
128    let width = buttons.len();
129    let height = joltages.len();
130
131    assert!(width < MAX_BUTTONS);
132    assert!(height < MAX_JOLTAGES);
133    let mut equations = [[0; MAX_BUTTONS]; MAX_JOLTAGES];
134
135    for row in 0..height {
136        equations[row][width] = joltages[row];
137    }
138
139    for col in 0..width {
140        let mut limit = i32::MAX;
141
142        for row in buttons[col].biterator() {
143            equations[row][col] = 1;
144            limit = limit.min(joltages[row]);
145        }
146
147        equations[height][col] = limit;
148    }
149
150    let mut rank = 0;
151    let mut last = width;
152
153    while rank < height && rank < last {
154        if let Some(found) = (rank..height)
155            .filter(|&row| equations[row][rank] != 0)
156            .min_by_key(|&row| equations[row][rank].abs())
157        {
158            equations.swap(rank, found);
159            let mut pivot = equations[rank][rank];
160
161            if pivot < 0 {
162                pivot *= -1;
163                equations[rank][rank..=width].iter_mut().for_each(|c| *c *= -1);
164            }
165
166            for row in 0..height {
167                let coefficient = equations[row][rank];
168                if row != rank && coefficient != 0 {
169                    for col in 0..equations[row].len() {
170                        equations[row][col] =
171                            pivot * equations[row][col] - coefficient * equations[rank][col];
172                    }
173                }
174            }
175
176            rank += 1;
177        } else {
178            last -= 1;
179            equations[..=height].iter_mut().for_each(|row| row.swap(rank, last));
180        }
181    }
182
183    let lcm = (0..rank).fold(1, |lcm, pivot| lcm.lcm(equations[pivot][pivot]));
184
185    for (pivot, equation) in equations[..rank].iter_mut().enumerate() {
186        let q = lcm / equation[pivot];
187        equation[rank..=width].iter_mut().for_each(|c| *c *= q);
188    }
189
190    let nullity = width - rank;
191    let rhs = from_fn(|row| equations[row][width]);
192    let basis: Vec<_> = (0..nullity)
193        .map(|col| {
194            let limit = equations[height][col + rank];
195            let vs = from_fn(|row| equations[row][rank + col]);
196            let cost = lcm - vs[..rank].iter().sum::<i32>();
197            Basis { limit, cost, vs }
198        })
199        .collect();
200
201    Subspace { rank, nullity, lcm, rhs, basis }
202}
203
204fn recurse(subspace: &Subspace, mut rhs: Column, remaining: u32, presses: i32) -> Option<i32> {
205    let rank = subspace.rank;
206    let mut temp = rhs;
207
208    for i in remaining.biterator() {
209        let free = &subspace.basis[i];
210        for (row, &v) in free.vs[..rank].iter().enumerate() {
211            if v < 0 {
212                temp[row] -= v * free.limit;
213            }
214        }
215    }
216
217    let mut min_value = i32::MAX;
218    let mut min_index = usize::MAX;
219    let mut global_lower = 0;
220    let mut global_upper = 0;
221
222    for i in remaining.biterator() {
223        let free = &subspace.basis[i];
224        let mut lower = 0;
225        let mut upper = free.limit;
226
227        for (&v, &rhs) in free.vs[..rank].iter().zip(&temp) {
228            if v > 0 {
229                upper = upper.min(rhs / v);
230            }
231            if v < 0 {
232                let rhs = rhs + v * free.limit;
233                lower = lower.max((rhs + v + 1) / v);
234            }
235        }
236
237        let size = upper - lower + 1;
238        if size > 0 && size < min_value {
239            min_value = size;
240            min_index = i;
241            global_lower = lower;
242            global_upper = upper;
243        }
244    }
245
246    if min_index == usize::MAX {
247        return None;
248    }
249
250    let remaining = remaining ^ (1 << min_index);
251    let lower = global_lower;
252    let upper = global_upper;
253    let Basis { cost, vs, .. } = &subspace.basis[min_index];
254    let cost = *cost;
255    let lcm = subspace.lcm;
256
257    if remaining != 0 {
258        rhs[..rank].iter_mut().zip(vs).for_each(|(rhs, v)| *rhs -= (lower - 1) * v);
259
260        (lower..upper + 1)
261            .filter_map(|n| {
262                rhs[..rank].iter_mut().zip(vs).for_each(|(rhs, v)| *rhs -= v);
263                recurse(subspace, rhs, remaining, presses + n * cost)
264            })
265            .min()
266    } else if cost >= 0 {
267        (lower..upper + 1).find_map(|n| {
268            let total = (presses + n * cost) / lcm;
269            rhs[..rank].iter().zip(vs).all(|(rhs, v)| (rhs - n * v) % lcm == 0).then_some(total)
270        })
271    } else {
272        (lower..upper + 1).rev().find_map(|n| {
273            let total = (presses + n * cost) / lcm;
274            rhs[..rank].iter().zip(vs).all(|(rhs, v)| (rhs - n * v) % lcm == 0).then_some(total)
275        })
276    }
277}
aoc/year2025/day10.rs

aoc/year2025/
day10.rs
