aoc/year2019/
day04.rs

1//! # Secure Container
2//!
3//! We speed things up by only checking numbers that have digits in non-decreasing order for pairs.
4//! These numbers become rapidly less dense as the password value increases and there
5//! are only 3003 total of these numbers with 6 digits.
6use crate::util::iter::*;
7use crate::util::parse::*;
8
9type Input = (u32, u32);
10
11pub fn parse(input: &str) -> Input {
12    let [start, end] = input.iter_unsigned::<u32>().chunk::<2>().next().unwrap();
13
14    let mut digits = to_digits(start);
15    let end = to_digits(end);
16
17    let mut part_one = 0;
18    let mut part_two = 0;
19
20    // Increase the starting number to the next number that has all digits in non-decreasing order
21    // to ensure that the incrementing logic in the search loop works correctly.
22    // For example 223450 => 223455, 120568 => 122222 and 439999 => 444444.
23    if let Some(index) = digits.windows(2).position(|w| w[0] > w[1]) {
24        let next = digits[index];
25        digits[index..].fill(next);
26    }
27
28    while digits <= end {
29        // Build a 5 bit binary mask with a `1` if two adjacent digits are equal.
30        let mask = digits.windows(2).fold(0, |acc, w| (acc << 1) | (w[0] == w[1]) as u32);
31
32        // Password must contain at least one pair.
33        part_one += (mask != 0) as u32;
34        // Password must contain at least one pair that's not part of a larger group.
35        part_two += (mask & !(mask >> 1) & !(mask << 1) != 0) as u32;
36
37        // Find the next number with all digits in non-decreasing order.
38        let index = digits.iter().rposition(|&d| d < b'9').unwrap();
39        let next = digits[index] + 1;
40        digits[index..].fill(next);
41    }
42
43    (part_one, part_two)
44}
45
46pub fn part1(input: &Input) -> u32 {
47    input.0
48}
49
50pub fn part2(input: &Input) -> u32 {
51    input.1
52}
53
54fn to_digits(n: u32) -> [u8; 6] {
55    format!("{n:06}").into_bytes().try_into().unwrap()
56}