aoc/year2025/
day10.rs

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

aoc/year2025/
day10.rs
