aoc/year2015/
day11.rs

1//! # Corporate Policy
2//!
3//! Like the [previous day], we rely on the special structure of the input to solve
4//! more efficiently than the general case.
5//!
6//! The key observation is that if there are no straights or pairs in the first 4 digits then the
7//! next lowest valid sequence will end in a string of the form `aabcc`,
8//! compressing 2 pairs and a straight into 5 digits.
9//!
10//! * If the current string ends with `xxyzz` then increment the third digit and wrap around to
11//!   `aabcc`.
12//! * The 5 digit sequence cannot start with any letter from `g` to `o` inclusive or it would
13//!   contain an invalid character somewhere in the sequence.
14//!
15//! [previous day]: crate::year2015::day10
16use std::str::from_utf8;
17
18type Password = [u8; 8];
19type Input = [Password; 2];
20
21pub fn parse(input: &str) -> Input {
22    let password = clean(input.trim().as_bytes().try_into().unwrap());
23
24    assert!(
25        !password[..4].array_windows().any(|&[a, b]| a == b),
26        "No pairs in the first 4 characters"
27    );
28    assert!(
29        !password[..4].array_windows().any(|&[a, b, c]| a + 1 == b && b + 1 == c),
30        "No straights in the first 4 characters"
31    );
32    assert_ne!(password[2], b'z', "No potential carry in the third character");
33
34    let first = next_password(password);
35    let second = next_password(first);
36    [first, second]
37}
38
39pub fn part1(input: &Input) -> &str {
40    from_utf8(&input[0]).unwrap()
41}
42
43pub fn part2(input: &Input) -> &str {
44    from_utf8(&input[1]).unwrap()
45}
46
47/// Sanitize the input to make sure it has no invalid characters. We increment the first invalid
48/// character found, for example `abcixyz` becomes `abcjaaa`.
49fn clean(mut password: Password) -> Password {
50    if let Some(index) = password.iter().position(|&d| matches!(d, b'i' | b'o' | b'l')) {
51        password[index] += 1;
52        password[index + 1..].fill(b'a');
53    }
54    password
55}
56
57/// Find the next valid 5 digit sequence of form `aabcc`.
58fn next_password(mut password: Password) -> Password {
59    // If the sequence would contain any illegal character, then skip to the next possible
60    // valid sequence starting with `p`.
61    if (b'g'..b'o').contains(&password[3]) {
62        return fill(password, b'p');
63    }
64
65    // If there's room then check if a sequence starting with the current character is
66    // higher than the current password.
67    if password[3] <= b'x' {
68        let candidate = fill(password, password[3]);
69        if candidate > password {
70            return candidate;
71        }
72    }
73
74    // Otherwise, we need to increment the first digit of the sequence.
75    if password[3] == b'x' {
76        // If it starts with `x` then increment the third digit and wrap around.
77        password[2] += if matches!(password[2], b'h' | b'n' | b'k') { 2 } else { 1 };
78        fill(password, b'a')
79    } else if password[3] == b'f' {
80        // If it would enter the invalid range from `g` to `o` then take the next valid start `p`.
81        fill(password, b'p')
82    } else {
83        // Otherwise, increment the first digit.
84        fill(password, password[3] + 1)
85    }
86}
87
88/// Creates a sequence of form `aabcc` from an arbitrary starting character.
89fn fill(mut password: Password, start: u8) -> Password {
90    let (a, b, c) = (start, start + 1, start + 2);
91    password[3..].copy_from_slice(&[a, a, b, c, c]);
92    password
93}
aoc/year2015/day11.rs

aoc/year2015/
day11.rs
