year2016/
day16.rs

1use utils::prelude::*;
2
3/// Calculating a dragon curve checksum.
4///
5/// The checksum is based on the parity of each chunk, and each chunk is the length of the largest
6/// power of 2 that divides the checksum's length.
7///
8/// Using the dragon bit parity function from
9/// [/u/askalski's post "How to tame your dragon in under a millisecond"](https://www.reddit.com/r/adventofcode/comments/5ititq/2016_day_16_c_how_to_tame_your_dragon_in_under_a/)
10/// we can calculate the parity of any length of the sequence:
11/// - Calculate how many full repeats of the pattern
12///   \[Original data]\[Dragon bit]\[Reversed & inverted data]\[Dragon bit] there are, and how
13///   far through the pattern the final truncated repeat was.
14/// - Calculate the parity of the full repeats of the original and the reversed & inverted data.
15/// - Calculate the parity of the original data in the truncated repeat, if any.
16/// - Calculate the parity of the reversed & inverted data in the truncated repeat, if any.
17/// - Calculate the parity of all the dragon bits.
18/// - XOR the four calculated parity values together.
19///
20/// This allows computing the parity from the start of the sequence to the end of each chunk, which
21/// then can be used to find each chunk's parity by XORing each parity with the previous one.
22#[derive(Clone, Debug)]
23pub struct Day16<'a> {
24    input: &'a str,
25    input_type: InputType,
26}
27
28impl<'a> Day16<'a> {
29    pub fn new(input: &'a str, input_type: InputType) -> Result<Self, InputError> {
30        if let Some(index) = input.find(|c| c != '0' && c != '1') {
31            return Err(InputError::new(input, index, "expected 0 or 1"));
32        }
33
34        Ok(Self { input, input_type })
35    }
36
37    #[must_use]
38    pub fn part1(&self) -> String {
39        self.checksum(match self.input_type {
40            InputType::Example => 20,
41            InputType::Real => 272,
42        })
43    }
44
45    #[must_use]
46    pub fn part2(&self) -> String {
47        self.checksum(35651584)
48    }
49
50    fn checksum(&self, length: u32) -> String {
51        let chunk_length = 1 << length.trailing_zeros();
52        let input_length = self.input.len() as u32;
53
54        // Expanded data repeats the following pattern:
55        // [Original data][Dragon bit][Reversed & inverted data][Dragon bit]
56        let pattern_length = 2 * (input_length + 1);
57
58        let mut previous = false;
59        let mut output = String::with_capacity((length / chunk_length) as usize);
60        for i in (chunk_length..=length).step_by(chunk_length as usize) {
61            let mut parity = false;
62
63            // Work out how many complete pattern repeats there are up until this point, and how
64            // far through the pattern the final truncated repeat is
65            let complete_repeats = i / pattern_length;
66            let mut truncated = i % pattern_length;
67            let mut dragon_bits = 2 * complete_repeats;
68
69            // Calculate parity of all the repeated original + reversed & inverted sections
70            parity ^= (complete_repeats * input_length) % 2 == 1;
71
72            // Calculate parity of original data in the final truncated repeat
73            if truncated > 0 {
74                let original_length = truncated.min(input_length);
75                let ones = self
76                    .input
77                    .bytes()
78                    .take(original_length as usize)
79                    .filter(|&b| b == b'1')
80                    .count();
81                parity ^= ones % 2 == 1;
82                truncated -= original_length;
83            }
84
85            // Extra dragon bit in final truncated repeat
86            if truncated > 0 {
87                dragon_bits += 1;
88                truncated -= 1;
89            }
90
91            // Calculate parity of the reversed & inverted data in the final truncated repeat
92            if truncated > 0 {
93                let mirrored_inverted_length = truncated.min(input_length);
94                let ones = self
95                    .input
96                    .bytes()
97                    .rev()
98                    .take(mirrored_inverted_length as usize)
99                    .filter(|&b| b == b'0')
100                    .count();
101                parity ^= ones % 2 == 1;
102            }
103
104            // Truncated repeat can't have a final dragon bit (otherwise it wouldn't be incomplete)
105
106            // Calculate parity of all the dragon bits
107            parity ^= Self::dragon_parity(dragon_bits);
108
109            if parity ^ previous {
110                output.push('0');
111            } else {
112                output.push('1');
113            }
114            previous = parity;
115        }
116
117        output
118    }
119
120    /// See https://www.reddit.com/r/adventofcode/comments/5ititq/2016_day_16_c_how_to_tame_your_dragon_in_under_a/
121    fn dragon_parity(n: u32) -> bool {
122        let gray = n ^ (n >> 1);
123        ((n & gray).count_ones() ^ gray) & 1 != 0
124    }
125}
126
127examples!(Day16<'_> -> (&'static str, &'static str) [
128    {input: "10000", part1: "01100"},
129]);
year2016/day16.rs

year2016/
day16.rs
