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: [u8; 8] = input.as_bytes().try_into().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    fn valid(pass: &[u8; 8]) -> bool {
87        Self::has_two_pairs(pass)
88            && Self::has_three_run(pass)
89            && Self::has_no_confusing_letters(pass)
90    }
91
92    fn has_two_pairs(x: &[u8; 8]) -> bool {
93        for i in 0..7 {
94            if x[i] == x[i + 1] {
95                for j in i + 2..7 {
96                    if x[j] == x[j + 1] {
97                        return true;
98                    }
99                }
100            }
101        }
102        false
103    }
104
105    fn has_three_run(x: &[u8; 8]) -> bool {
106        x.windows(3).any(|x| x[0] + 1 == x[1] && x[0] + 2 == x[2])
107    }
108
109    fn has_no_confusing_letters(x: &[u8; 8]) -> bool {
110        x.iter().all(|&x| x != b'i' && x != b'o' && x != b'l')
111    }
112}
113
114examples!(Day11 -> (&'static str, &'static str) [
115    {input: "abcdefgh", part1: "abcdffaa"},
116    {input: "ghijklmn", part1: "ghjaabcc"},
117]);
year2015/day11.rs

year2015/
day11.rs
