year2019/
day04.rs

1use utils::prelude::*;
2
3/// Counting non-decreasing numbers containing pairs.
4#[derive(Clone, Debug)]
5pub struct Day04 {
6    part1: u32,
7    part2: u32,
8}
9
10impl Day04 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        let [start, end] = parser::digit()
13            .repeat_n::<6, _>(parser::noop())
14            .map_res(|x| {
15                if x[0] == 0 {
16                    Err("expected six digit number not starting with zero")
17                } else {
18                    Ok(x)
19                }
20            })
21            .repeat_n(b'-')
22            .parse_complete(input)?;
23
24        let (mut part1, mut part2) = (0, 0);
25        for password in Self::packed_passwords(start, end) {
26            // e.g. password  = 0x0000_0101_0202_0203
27
28            // adjacent_xor   = 0x0000_0100_0300_0001
29            let adjacent_xor = password ^ (password >> 8);
30            // different_mask = 0x0000_1000_1000_0010
31            let different_mask = (adjacent_xor + 0x0f0f_0f0f_0f0f) & 0x1010_1010_1010;
32
33            // pair           = 0x0000_0010_0010_1000
34            let pair = !different_mask & 0x1010_1010_1010;
35            part1 += u32::from(pair != 0);
36
37            // padded_mask    = 0x1010_0010_0000_1010
38            let padded_mask = (different_mask << 8) | 0x1000_0000_0000_0010;
39            // exact_pair     = 0x0000_1000_0000_0000
40            let exact_pair = !padded_mask & (padded_mask << 8) & (padded_mask >> 8);
41            part2 += u32::from(exact_pair != 0);
42        }
43
44        Ok(Self { part1, part2 })
45    }
46
47    #[must_use]
48    pub fn part1(&self) -> u32 {
49        self.part1
50    }
51
52    #[must_use]
53    pub fn part2(&self) -> u32 {
54        self.part2
55    }
56
57    fn packed_passwords(mut start: [u8; 6], end: [u8; 6]) -> impl Iterator<Item = u64> {
58        // Ensure the start is non-decreasing
59        if let Some(i) = start.array_windows().position(|&[a, b]| a > b) {
60            let digit = start[i];
61            start[i + 1..].fill(digit);
62        }
63
64        let mut password = u64::from_be_bytes([
65            0, 0, start[0], start[1], start[2], start[3], start[4], start[5],
66        ]);
67        let end = u64::from_be_bytes([0, 0, end[0], end[1], end[2], end[3], end[4], end[5]]);
68
69        std::iter::from_fn(move || {
70            if password > end {
71                return None;
72            }
73            let current = password;
74
75            if password & 0xF != 9 {
76                // The final digit isn't a nine, the next password is simply current + 1
77                password += 1;
78                return Some(current);
79            }
80
81            // Advance the packed password to the next non-decreasing password
82            // e.g. password              = 0x0000_0102_0303_0909
83
84            // nine_mask                  = 0x0000_0000_0000_1010
85            let nine_mask = (password + 0x0707_0707_0707) & 0x1010_1010_1010;
86            // (nine_mask << 16 | 0xFFFF) = 0x0000_0000_1010_FFFF
87            // leading_less_than_nine     = 4
88            let leading_less_than_nine = (nine_mask << 16 | 0xFFFF).leading_zeros() / 8;
89
90            if leading_less_than_nine == 0 {
91                // All nines, return current then stop
92                password = u64::MAX;
93                return Some(current);
94            }
95
96            // trailing_nine_count        = 2
97            let trailing_nine_count = 6 - leading_less_than_nine;
98            // last_non_nine_digit        = 0x0000_0000_0000_0003
99            let last_non_nine_digit = (password >> (trailing_nine_count * 8)) & 0xf;
100            // next_digit                 = 0x0000_0000_0000_0004
101            let next_digit = last_non_nine_digit + 1;
102            // next_fill                  = 0x0000_0404_0404_0404
103            let next_fill = 0x0101_0101_0101 * next_digit;
104
105            // replace_count              = 3
106            let replace_count = trailing_nine_count + 1;
107            // keep_mask                  = 0xFFFF_FFFF_FF00_0000
108            let keep_mask = u64::MAX << (replace_count * 8);
109
110            // password                   = 0x0000_0102_0304_0404
111            password = (password & keep_mask) | (next_fill & !keep_mask);
112
113            Some(current)
114        })
115    }
116}
117
118examples!(Day04 -> (u32, u32) []);
year2019/day04.rs

year2019/
day04.rs
