year2019/
day16.rs

1use utils::number::lcm;
2use utils::prelude::*;
3
4/// Transforming digits with a repeating block pattern.
5///
6/// This implementation is based on the following:
7/// - [Advent of Code 2019 in 130 ms: day 16](https://emlun.se/advent-of-code-2019/2020/08/26/day-16.html)
8/// - [/u/ephemient's post "Let's combinatorics"](https://www.reddit.com/r/adventofcode/comments/ebqgdu/2019_day_16_part_2_lets_combinatorics/)
9/// - [Voltara's C++ implementation](https://github.com/Voltara/advent2019-fast/blob/5a35123d4113d63cf2bc0d59edb1e0a6d5d67d0c/src/day16.cpp)
10///   and [README explanation](https://github.com/Voltara/advent2019-fast/blob/5a35123d4113d63cf2bc0d59edb1e0a6d5d67d0c/README.md#day-16)
11#[derive(Clone, Debug)]
12pub struct Day16 {
13    digits: Vec<u8>,
14    offset: usize,
15}
16
17const PHASES: usize = 100;
18const PART2_REPEAT: usize = 10_000;
19
20// After 100 suffix-sum phases, the kth digit after the offset is multiplied by C(99 + k, k) mod 10.
21// Instead of calculating every value of C(99 + k, k), part 2 keeps only the positions where the
22// coefficient is non-zero mod 2 or mod 5, combining the results to sum the matching input digits.
23//
24// Mod 2: by Lucas' theorem in base 2, C(n, k) is odd iff every 1 bit in k is also a 1 bit in n
25// (k & !n == 0). Here n = 99 + k, so C(99 + k, k) is odd iff k & 99 == 0.
26// Since 99 = 0b1100011, one mod 128 cycle leaves only k mod 128 in {0, 4, ..., 28}, which use
27// only the bit positions where 99 has 0s.
28// The second tuple element is the mod 10 value to add for the mod 2 component.
29// 5 is used for all the terms as it is 1 mod 2 and 0 mod 5.
30const BINOMIAL_MOD2_TERMS: [(usize, u32); 8] = [
31    (0, 5),
32    (4, 5),
33    (8, 5),
34    (12, 5),
35    (16, 5),
36    (20, 5),
37    (24, 5),
38    (28, 5),
39];
40const BINOMIAL_MOD2_PERIOD: usize = 128;
41
42// Mod 5: by Lucas' theorem in base 5, C(n, k) is non-zero mod 5 iff every base 5 digit in k is at
43// most the matching digit in n.
44// Here n = 99 + k and 99 = 344 in base 5, so the 1s and 5s digits in k must be 0 and the 25s digit
45// can be 0 or 1, giving k mod 125 = 0 or 25.
46//
47// The second tuple element is the mod 10 value to add for the mod 5 component.
48// For k = 0, 6 is used as C(99, 0) = 1 mod 5, and 6 is 1 mod 5 and 0 mod 2.
49// For k = 25, 4 is used as C(124, 25) = 4 mod 5, and 4 is already 0 mod 2.
50const BINOMIAL_MOD5_TERMS: [(usize, u32); 2] = [(0, 6), (25, 4)];
51const BINOMIAL_MOD5_PERIOD: usize = 125;
52
53impl Day16 {
54    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
55        if let Some(index) = input.bytes().position(|b| !b.is_ascii_digit()) {
56            return Err(InputError::new(input, index, "expected digit"));
57        }
58        if input.len() < 8 {
59            return Err(InputError::new(
60                input,
61                input.len(),
62                "expected at least 8 digits",
63            ));
64        }
65
66        let digits = input.bytes().map(|b| b - b'0').collect::<Vec<_>>();
67        let offset = digits[..7]
68            .iter()
69            .fold(0usize, |acc, &digit| 10 * acc + digit as usize);
70
71        Ok(Self { digits, offset })
72    }
73
74    #[must_use]
75    pub fn part1(&self) -> u32 {
76        let mut digits = self.digits.clone();
77        let mut next = vec![0; digits.len()];
78        let mut prefix = vec![0i32; digits.len() + 1];
79
80        let len = digits.len();
81        let quarter = len / 4;
82        let third = len / 3;
83        let half = len / 2;
84
85        for _ in 0..PHASES {
86            prefix[0] = 0;
87            let mut total = 0;
88            for (&digit, prefix) in digits.iter().zip(prefix.iter_mut().skip(1)) {
89                total += i32::from(digit);
90                *prefix = total;
91            }
92
93            let block_sum = |start: usize, width: usize| {
94                prefix[(start + width).min(len)] - prefix[start.min(len)]
95            };
96
97            // Before len/4, rows can still contain multiple +1 and -1 blocks.
98            for (index, out) in next.iter_mut().enumerate().take(quarter) {
99                let width = index + 1;
100                let mut total = 0i32;
101                let mut start = index;
102
103                while start < len {
104                    total += block_sum(start, width);
105                    start += 2 * width;
106
107                    if start >= len {
108                        break;
109                    }
110
111                    total -= block_sum(start, width);
112                    start += 2 * width;
113                }
114
115                *out = (total.abs() % 10) as u8;
116            }
117
118            // Between len/4 and len/3, the row has exactly one +1 block and one -1 block.
119            for (index, out) in next.iter_mut().enumerate().take(third).skip(quarter) {
120                let width = index + 1;
121                let total = block_sum(index, width) - block_sum(index + 2 * width, width);
122                *out = (total.abs() % 10) as u8;
123            }
124
125            // Between len/3 and len/2, the row has exactly one +1 block.
126            for (index, out) in next.iter_mut().enumerate().take(half).skip(third) {
127                let width = index + 1;
128                *out = (block_sum(index, width) % 10) as u8;
129            }
130
131            // From len/2 onward, the row is just a suffix sum.
132            let mut suffix = 0u8;
133            for i in (half..len).rev() {
134                suffix += digits[i];
135                suffix = suffix.wrapping_sub(10 * u8::from(suffix >= 10));
136                next[i] = suffix;
137            }
138
139            (digits, next) = (next, digits);
140        }
141
142        digits
143            .iter()
144            .take(8)
145            .fold(0, |acc, &digit| 10 * acc + u32::from(digit))
146    }
147
148    #[must_use]
149    pub fn part2(&self) -> u32 {
150        let len = self.digits.len();
151        let total_len = len * PART2_REPEAT;
152        assert!(
153            self.offset + 8 <= total_len,
154            "expected message offset within repeated signal"
155        );
156        assert!(
157            self.offset >= total_len / 2,
158            "expected message offset in second half of repeated signal"
159        );
160
161        // Coefficients repeat every 128 / 125 terms, and the repeated input repeats every `len`, so
162        // the product repeats every `lcm(len, period)` terms.
163        // For mod 2, each term adds 0 or 5 and each cycle sums to a multiple of 5, so 2 cycles sum
164        // to 0 mod 10 and can be skipped.
165        // For mod 5, each term adds 4*d or 6*d and one cycle sums to a multiple of 2, so 5 cycles
166        // sum to 0 mod 10 and can be skipped.
167        let mod2_skip_period = 2 * lcm(len, BINOMIAL_MOD2_PERIOD);
168        let mod5_skip_period = 5 * lcm(len, BINOMIAL_MOD5_PERIOD);
169        let mut result = 0;
170
171        for i in 0..8 {
172            let tail_len = total_len - self.offset - i;
173            let start_index = (self.offset + i) % len;
174
175            let sparse_sum = |step: usize, skip_period: usize, terms: &[(usize, u32)], mask: u8| {
176                let mut total = 0;
177                for &(residue, coefficient) in terms {
178                    if residue >= tail_len {
179                        break;
180                    }
181
182                    let remainder = tail_len - residue;
183                    let skip = remainder - remainder % skip_period;
184                    let mut position = residue + skip;
185                    let mut index = (start_index + residue) % len;
186
187                    while position < tail_len {
188                        total += coefficient * u32::from(self.digits[index] & mask);
189                        position += step;
190                        index += step;
191                        if index >= len {
192                            index %= len;
193                        }
194                    }
195                }
196                total
197            };
198
199            let mod2_total = sparse_sum(
200                BINOMIAL_MOD2_PERIOD,
201                mod2_skip_period,
202                &BINOMIAL_MOD2_TERMS,
203                1,
204            );
205            let mod5_total = sparse_sum(
206                BINOMIAL_MOD5_PERIOD,
207                mod5_skip_period,
208                &BINOMIAL_MOD5_TERMS,
209                u8::MAX,
210            );
211            let total = mod2_total + mod5_total;
212            result = 10 * result + total % 10;
213        }
214
215        result
216    }
217}
218
219examples!(Day16 -> (u32, u32) [
220    {input: "80871224585914546619083218645595", part1: 24176176},
221    {input: "19617804207202209144916044189917", part1: 73745418},
222    {input: "69317163492948606335995924319873", part1: 52432133},
223    {input: "03036732577212944063491565474664", part2: 84462026},
224    {input: "02935109699940807407585447034323", part2: 78725270},
225    {input: "03081770884921959731165446850517", part2: 53553731},
226]);
year2019/day16.rs

year2019/
day16.rs
