Skip to main content

year2025/
day10.rs

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