year2025/
day10.rs

1use std::collections::HashMap;
2use utils::array::ArrayVec;
3use utils::bit::BitIterator;
4use utils::prelude::*;
5
6/// Finding the minimum number of operations that sum to a target.
7///
8/// This implementation is based on
9/// [/u/tenthmascot's post "Bifurcate your way to victory!"](https://www.reddit.com/r/adventofcode/comments/1pk87hl/2025_day_10_part_2_bifurcate_your_way_to_victory/).
10#[derive(Clone, Debug)]
11pub struct Day10 {
12    part1: u32,
13    part2: u32,
14}
15
16const MAX_TARGETS: usize = 10;
17const MAX_BUTTONS: usize = 15;
18const MAX_PARITY_OPTIONS: usize = 16;
19
20impl Day10 {
21    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
22        let machine = parser::byte_map!(
23            b'.' => false,
24            b'#' => true,
25        )
26        .repeat_arrayvec::<MAX_TARGETS, _>(parser::noop(), 1)
27        .map(|v| {
28            (
29                v.iter().rfold(0, |acc, &n| (acc << 1) | u32::from(n)),
30                v.len(),
31            )
32        })
33        .with_prefix(b'[')
34        .with_suffix("] ")
35        .then(
36            parser::number_range(0..=MAX_TARGETS - 1)
37                .repeat_arrayvec::<MAX_TARGETS, _>(b',', 1)
38                .map_res(|v| {
39                    let mut mask = 0u32;
40                    for &n in v.iter().rev() {
41                        if mask & (1 << n) != 0 {
42                            return Err("duplicate button within wiring schematic");
43                        }
44                        mask |= 1 << n;
45                    }
46                    Ok(mask)
47                })
48                .with_prefix(b'(')
49                .with_suffix(b')')
50                .repeat_arrayvec::<MAX_BUTTONS, _>(b' ', 1),
51        )
52        .then(
53            parser::u16()
54                .repeat_arrayvec(b',', 1)
55                .with_prefix(" {")
56                .with_suffix(b'}'),
57        )
58        .map_res(|((lights, light_count), buttons, targets)| {
59            let all_buttons = buttons.iter().copied().fold(0, |acc, b| acc | b);
60            if all_buttons.trailing_ones() as usize != light_count
61                || all_buttons.leading_zeros() as usize != 32 - light_count
62            {
63                return Err("wiring schematics do not match light count");
64            }
65            if targets.len() != light_count {
66                return Err("joltage targets do not match light count");
67            }
68            Ok((lights, buttons, targets))
69        })
70        .with_eol();
71
72        let (mut part1, mut part2) = (0, 0);
73        for line in machine.parse_iterator(input) {
74            let (lights, buttons, targets) = line?;
75            let (p1, p2) = Self::calculate(lights, buttons, targets);
76            part1 += p1;
77            part2 += p2;
78        }
79
80        Ok(Self { part1, part2 })
81    }
82
83    #[must_use]
84    pub fn part1(&self) -> u32 {
85        self.part1
86    }
87
88    #[must_use]
89    pub fn part2(&self) -> u32 {
90        self.part2
91    }
92
93    #[inline]
94    fn calculate(
95        lights: u32,
96        buttons: ArrayVec<u32, MAX_BUTTONS>,
97        targets: ArrayVec<u16, MAX_TARGETS>,
98    ) -> (u32, u32) {
99        // Precalculate the results and parity of every button press combination
100        let combination_count = 1usize << buttons.len();
101        let mut combination_results = vec![[0u16; MAX_TARGETS]; combination_count];
102        let mut combination_parity_masks = vec![0u16; combination_count];
103        for i in 0..buttons.len() {
104            let button = buttons[i] as u16;
105            let half = 1usize << i;
106
107            let mut button_result = [0u16; MAX_TARGETS];
108            for (bit_pos, _) in BitIterator::ones(button) {
109                button_result[bit_pos as usize] = 1;
110            }
111
112            let (results_without, results_with) = combination_results.split_at_mut(half);
113            for (without, with) in results_without.iter().zip(results_with) {
114                for i in 0..MAX_TARGETS {
115                    with[i] = without[i] + button_result[i];
116                }
117            }
118
119            let (parity_without, parity_with) = combination_parity_masks.split_at_mut(half);
120            for (&without, with) in parity_without.iter().zip(parity_with) {
121                *with = without ^ button;
122            }
123        }
124
125        // Group combinations by the parity of their results
126        let parity_states = 1usize << targets.len();
127        let mut parity_combinations = vec![ArrayVec::new(); parity_states];
128        for (combination, parity_mask) in combination_parity_masks.into_iter().enumerate() {
129            parity_combinations[parity_mask as usize]
130                .push(combination as u16)
131                .expect("expected less than MAX_PARITY_OPTIONS options per parity mask");
132        }
133
134        // Minimum presses for each light to match its parity
135        let part1 = parity_combinations[lights as usize]
136            .iter()
137            .map(|&combinations| combinations.count_ones())
138            .min()
139            .expect("no solution found");
140
141        // Minimum presses for each counter to match its target
142        let mut cache = HashMap::with_capacity(1024);
143        cache.insert([0; MAX_TARGETS], Some(0));
144        let part2 = Self::target_min_presses(
145            targets.as_array(),
146            &parity_combinations,
147            &combination_results,
148            &mut cache,
149        )
150        .expect("no solution found");
151
152        (part1, part2)
153    }
154
155    fn target_min_presses(
156        targets: &[u16; MAX_TARGETS],
157        parity_combinations: &[ArrayVec<u16, MAX_PARITY_OPTIONS>],
158        combination_results: &[[u16; MAX_TARGETS]],
159        cache: &mut HashMap<[u16; MAX_TARGETS], Option<u32>>,
160    ) -> Option<u32> {
161        if let Some(cached_solution) = cache.get(targets) {
162            return *cached_solution;
163        }
164
165        let parity_mask = targets
166            .iter()
167            .enumerate()
168            .fold(0, |acc, (i, &v)| acc | ((v & 1) as usize) << i);
169
170        let mut best = None;
171        let mut remaining_targets = [0u16; MAX_TARGETS];
172        for &combination in &parity_combinations[parity_mask] {
173            // After pressing the buttons from the combination, the remaining targets must be even.
174            // Any additional presses must be in pairs to preserve this even parity, so it is safe
175            // to divide each remaining target by 2, solve recursively, then double the result.
176            // This limits the recursion depth to O(log(max_target)).
177
178            let mut possible = true;
179            for ((&current, &amount), next) in targets
180                .iter()
181                .zip(&combination_results[combination as usize])
182                .zip(remaining_targets.iter_mut())
183            {
184                possible &= current >= amount;
185                *next = current.wrapping_sub(amount) / 2;
186            }
187
188            if possible
189                && let Some(remaining_solution) = Self::target_min_presses(
190                    &remaining_targets,
191                    parity_combinations,
192                    combination_results,
193                    cache,
194                )
195                && let solution = combination.count_ones() + 2 * remaining_solution
196                && best.is_none_or(|b| b > solution)
197            {
198                best = Some(solution);
199            }
200        }
201
202        cache.insert(*targets, best);
203        best
204    }
205}
206
207examples!(Day10 -> (u32, u32) [
208    {file: "day10_example0.txt", part1: 7, part2: 33},
209]);
year2025/day10.rs

year2025/
day10.rs
