1use utils::array::ArrayVec;
2use utils::bit::BitIterator;
3use utils::hash::FastMap;
4use utils::prelude::*;
5
6#[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 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 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 let part1 = parity_combinations[lights as usize]
126 .iter()
127 .map(|&combinations| combinations.count_ones())
128 .min()
129 .expect("no solution found");
130
131 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 let mut possible = true;
169 for ((¤t, &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]);