aoc/year2016/
day16.rs

1//! # Dragon Checksum
2//!
3//! We solve efficiently with a key insight that the checksum is simply the
4//! [odd parity bit](https://en.wikipedia.org/wiki/Parity_bit) for each block. If the total number
5//! of ones is even then the result is one, if the total is odd then the result is zero.
6//!
7//! This means that only the *total number of ones is important* not the pattern itself. Each
8//! checksum bit is computed over the largest power of two divisible into the output size. For part
9//! one this is 2⁴ or 16 and for part this is 2²¹ or 2097152. If we can calculate the number of
10//! ones for any arbitrary length then we can find the number at the start and end of each block,
11//! subtract from each other to get the total in the range then find the checksum bit.
12//!
13//! We find the number of ones for a pattern of length `n` in `log(n)` complexity as follows:
14//! * Start with a known pattern `abcde` and let the reversed bit inverse of this pattern be
15//!   `EDCBA`.
16//! * Caculate the [prefix sum](https://en.wikipedia.org/wiki/Prefix_sum) of the known sequence.
17//! * If the requested length is within the known sequence (in this example from 0 to 5 inclusive)
18//!   then we're done, return the number of ones directly.
19//! * Else after one repetition this becomes `abcde0EDCBA`.
20//! * If the length is at or to the right of the middle `0`,
21//!   for example `length` is 8 then the number of ones is:
22//!    * Let `half` = 5 the length of the left hand known sequence.
23//!    * Let `full` = 11 the length of the entire sequence.
24//!    * Ones in `abcde` => x
25//!    * Ones in `EDCBA` => the number of zeroes in `abcde`
26//!      => 5 - x => half - x
27//!    * Ones in `abc` => y
28//!    * Ones in `CBA` => the number of zeroes in `abc`
29//!      => 3 - y => 11 - 8 - y => full - length - y => next - y
30//!    * The total number of ones in `abcde0ED` is
31//!      x + (half - x) - (next - y) => half - next + y
32//!
33//! Now for the really neat part. We can recursively find the number of ones in `y` by repeating
34//! the same process by setting the new `length` to `next`. We keep recursing until the length
35//! is less the size of the inital input and we can lookup the final count from the prefix sum.
36use crate::util::parse::*;
37
38/// Build a prefix sum of the number of ones at each length in the pattern
39/// including zero at the start.
40pub fn parse(input: &str) -> Vec<usize> {
41    let mut sum = 0;
42    let mut ones = vec![0];
43
44    for b in input.trim().bytes() {
45        sum += b.to_decimal() as usize;
46        ones.push(sum);
47    }
48
49    ones
50}
51
52/// 272 is 17 * 2⁴
53pub fn part1(input: &[usize]) -> String {
54    checksum(input, 1 << 4)
55}
56
57/// 35651584 is 17 * 2²¹
58pub fn part2(input: &[usize]) -> String {
59    checksum(input, 1 << 21)
60}
61
62/// Collect the ones count at each `step_size` then subtract in pairs to calculate the number of
63/// ones in each interval to give the checksum.
64fn checksum(input: &[usize], step_size: usize) -> String {
65    (0..18)
66        .map(|i| count(input, i * step_size))
67        .collect::<Vec<_>>()
68        .windows(2)
69        .map(|w| if (w[1] - w[0]).is_multiple_of(2) { '1' } else { '0' })
70        .collect()
71}
72
73/// Counts the number of ones from the start to the index (inclusive).
74fn count(ones: &[usize], mut length: usize) -> usize {
75    let mut half = ones.len() - 1;
76    let mut full = 2 * half + 1;
77
78    // Find the smallest pattern size such that the index is on the right hand side
79    // (greater than or to) the middle `0` character.
80    while full < length {
81        half = full;
82        full = 2 * half + 1;
83    }
84
85    let mut result = 0;
86
87    while length >= ones.len() {
88        // Shrink the pattern size until the index is on the right side once more.
89        while length <= half {
90            half /= 2;
91            full /= 2;
92        }
93
94        // "Reflect" the index then add the extra number of ones to the running total.
95        let next = full - length;
96        result += half - next;
97        length = next;
98    }
99
100    result + ones[length]
101}
aoc/year2016/day16.rs

aoc/year2016/
day16.rs
