year2015/
day11.rs

1use utils::prelude::*;
2
3/// Password rules.
4#[derive(Clone, Debug)]
5pub struct Day11 {
6    part1: [u8; 8],
7    part2: [u8; 8],
8}
9
10impl Day11 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        if input.len() != 8 || input.bytes().any(|x| !x.is_ascii_lowercase()) {
13            return Err(InputError::new(input, 0, "expected 8 lowercase letters"));
14        }
15
16        let input = input.as_bytes().as_array().copied().unwrap();
17        let part1 = Self::next_password(input);
18        let part2 = Self::next_password(part1);
19        Ok(Self { part1, part2 })
20    }
21
22    #[must_use]
23    pub fn part1(&self) -> &str {
24        std::str::from_utf8(&self.part1).unwrap()
25    }
26
27    #[must_use]
28    pub fn part2(&self) -> &str {
29        std::str::from_utf8(&self.part2).unwrap()
30    }
31
32    fn next_password(mut pass: [u8; 8]) -> [u8; 8] {
33        loop {
34            if pass[0] != pass[1]
35                && pass[1] != pass[2]
36                && pass[2] != pass[3]
37                && pass[1] + 1 != pass[2]
38                && pass[2] + 1 != pass[3]
39            {
40                // If in the first 4 characters, there are no pairs, no increasing runs, and the
41                // third and forth characters can't start an increasing run, skip ahead.
42                if pass[3] <= b'x' && &pass[4..] < &[pass[3], pass[3] + 1, pass[3] + 2, pass[3] + 2]
43                {
44                    // The final 4 characters must be "aabcc", "bbcdd", ... to contain 2 pairs and
45                    // an increasing sequence.
46                    pass[4] = pass[3];
47                    pass[5] = pass[3] + 1;
48                    pass[6] = pass[3] + 2;
49                    pass[7] = pass[3] + 2;
50                } else {
51                    // There are no other possible matches for the current first 4 characters, so
52                    // increment the first characters and reset the last 4. Setting the last 4
53                    // characters to the above pattern immediately after incrementing isn't safe as
54                    // the first 4 characters may now contain a pair or increasing run.
55                    Self::increment(&mut pass, 3);
56                    pass[4] = b'a';
57                    pass[5] = b'a';
58                    pass[6] = b'a';
59                    pass[7] = b'a';
60                }
61            } else {
62                Self::increment(&mut pass, 7);
63            }
64
65            if Self::valid(&pass) {
66                return pass;
67            }
68        }
69    }
70
71    fn increment(pass: &mut [u8; 8], from: usize) {
72        for i in (0..=from).rev() {
73            if pass[i] == b'z' {
74                pass[i] = b'a';
75                // Continue to next position
76            } else if pass[i] == b'h' || pass[i] == b'k' || pass[i] == b'n' {
77                pass[i] += 2; // Skip confusing letters ('i', 'l', 'o')
78                break;
79            } else {
80                pass[i] += 1;
81                break;
82            }
83        }
84    }
85
86    #[cfg_attr(
87        target_pointer_width = "64",
88        expect(clippy::trivially_copy_pass_by_ref)
89    )]
90    fn valid(pass: &[u8; 8]) -> bool {
91        Self::has_two_pairs(pass)
92            && Self::has_three_run(pass)
93            && Self::has_no_confusing_letters(pass)
94    }
95
96    #[cfg_attr(
97        target_pointer_width = "64",
98        expect(clippy::trivially_copy_pass_by_ref)
99    )]
100    fn has_two_pairs(x: &[u8; 8]) -> bool {
101        for i in 0..7 {
102            if x[i] == x[i + 1] {
103                for j in i + 2..7 {
104                    if x[j] == x[j + 1] {
105                        return true;
106                    }
107                }
108            }
109        }
110        false
111    }
112
113    #[cfg_attr(
114        target_pointer_width = "64",
115        expect(clippy::trivially_copy_pass_by_ref)
116    )]
117    fn has_three_run(x: &[u8; 8]) -> bool {
118        x.array_windows().any(|&[a, b, c]| a + 1 == b && a + 2 == c)
119    }
120
121    #[cfg_attr(
122        target_pointer_width = "64",
123        expect(clippy::trivially_copy_pass_by_ref)
124    )]
125    fn has_no_confusing_letters(x: &[u8; 8]) -> bool {
126        x.iter().all(|&x| x != b'i' && x != b'o' && x != b'l')
127    }
128}
129
130examples!(Day11 -> (&'static str, &'static str) [
131    {input: "abcdefgh", part1: "abcdffaa"},
132    {input: "ghijklmn", part1: "ghjaabcc"},
133]);
year2015/day11.rs

year2015/
day11.rs
