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
11//!   to `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    // No pairs in the first 4 characters
25    let pair = |i, j| password[i] == password[j];
26    assert!(!(pair(0, 1) | pair(1, 2) | pair(2, 3)));
27
28    // No straights in the first 4 characters
29    let sequence = |i, j| password[j] > password[i] && password[j] - password[i] == 1;
30    assert!(!(sequence(1, 2) && (sequence(0, 1) || sequence(2, 3))));
31
32    // No potential carry in the third character
33    assert_ne!(password[2], b'z');
34
35    let first = next_password(password);
36    let second = next_password(first);
37    [first, second]
38}
39
40pub fn part1(input: &Input) -> &str {
41    from_utf8(&input[0]).unwrap()
42}
43
44pub fn part2(input: &Input) -> &str {
45    from_utf8(&input[1]).unwrap()
46}
47
48/// Sanitize the input to make sure it has no invalid characters. We increment the first invalid
49/// character found, for example `abcixyz` becomes `abcjaaa`.
50fn clean(mut password: Password) -> Password {
51    let mut reset = false;
52
53    for digit in &mut password {
54        if reset {
55            *digit = b'a';
56        } else if matches!(digit, b'i' | b'o' | b'l') {
57            *digit += 1;
58            reset = true;
59        }
60    }
61
62    password
63}
64
65/// Find the next valid 5 digit sequence of form `aabcc`.
66fn next_password(mut password: Password) -> Password {
67    // If the sequence would contain any illegal character, then skip to the next possible
68    // valid sequence starting with `p`.
69    if (b'g'..b'o').contains(&password[3]) {
70        return fill(password, b'p');
71    }
72
73    // If there's room then check if a sequence starting with the current character is
74    // higher than the current password.
75    if password[3] <= b'x' {
76        let candidate = fill(password, password[3]);
77        if candidate > password {
78            return candidate;
79        }
80    }
81
82    // Otherwise we need to increment the first digit of the sequence.
83    if password[3] == b'x' {
84        // If it starts with `x` then increment the third digit and wrap around.
85        password[2] += if matches!(password[2], b'h' | b'n' | b'k') { 2 } else { 1 };
86        fill(password, b'a')
87    } else if password[3] == b'f' {
88        // If it would enter the invalid range from `g` to `o` then take the next valid start `p`.
89        fill(password, b'p')
90    } else {
91        // Otherwise increment the first digit.
92        fill(password, password[3] + 1)
93    }
94}
95
96/// Creates a sequence of form `aabcc` from an arbitrary starting character.
97fn fill(mut password: Password, start: u8) -> Password {
98    password[3] = start;
99    password[4] = start;
100    password[5] = start + 1;
101    password[6] = start + 2;
102    password[7] = start + 2;
103    password
104}
aoc/year2015/day11.rs

aoc/year2015/
day11.rs
