aoc/year2015/
day05.rs

1//! # Doesn't He Have Intern-Elves For This?
2//!
3//! [Regular expressions](https://en.wikipedia.org/wiki/Regular_expression) are a good fit for this
4//! problem. However in the interest of speed we'll take a different approach for both parts.
5//!
6//! ## Part One
7//! Each string consists only of lowercase ASCII characters so the cardinality is 26. We can
8//! test for vowels and invalid characters more quickly by converting each character into a bitmask
9//! that fits into a `i32`. For example `a` becomes `1`, b becomes `10` and so on.
10//!
11//! To check if a character is a vowel we logically `AND` against `100000100000100010001` which is
12//! "aeiou" converted to a bitmask. Similarly to check for the invalid sequence "ab" we `AND`
13//! against a mask that has `b` set and notice the previous character is always one less, so we
14//! can left shift to reuse the same mask.
15//!
16//! ## Part Two
17//! We can check for non-overlapping pairs in `O(n)` complexity by storing the last seen index of
18//! each pair in the string. If the difference is more than one, then we know that the pairs are
19//! non-overlapping.
20//!
21//! Instead of using a `HashMap` we rely on the fact there at most 26² possible combinations
22//! in order to use a fixed size array as an implicit data structure. Using zero as a special
23//! starting value gives 27² or 729 possibilities. To avoid having to clear the array for each
24//! string, we bump the index by 1000 (any value larger than the length of the string would do).
25//! This means that if the difference is greater than the current position in the string we can be
26//! sure that we haven't encountered this pair in this particular string before.
27pub fn parse(input: &str) -> Vec<&[u8]> {
28    input.lines().map(str::as_bytes).collect()
29}
30
31pub fn part1(input: &[&[u8]]) -> usize {
32    // Bitmask for vowels (a, e, i, o, u)
33    const VOWEL_MASK: u32 = 0x0104111;
34    // Bitmask for forbidden pairs
35    const FORBIDDEN_MASK: u32 = 0x101000a;
36
37    input
38        .iter()
39        .filter(|line| {
40            let mut vowels = 0;
41            let mut pairs = 0;
42            let mut previous = 0;
43
44            for &c in line.iter() {
45                let current = 1 << (c - b'a');
46
47                if FORBIDDEN_MASK & current & (previous << 1) != 0 {
48                    return false;
49                }
50                if VOWEL_MASK & current != 0 {
51                    vowels += 1;
52                }
53                if previous == current {
54                    pairs += 1;
55                }
56
57                previous = current;
58            }
59
60            vowels >= 3 && pairs >= 1
61        })
62        .count()
63}
64
65pub fn part2(input: &[&[u8]]) -> usize {
66    let mut pairs = [0; 729];
67
68    input
69        .iter()
70        .enumerate()
71        .filter(|(base, line)| {
72            let mut first = 0;
73            let mut second = 0;
74
75            let mut two_pair = false;
76            let mut split_pair = false;
77
78            for (offset, &c) in line.iter().enumerate() {
79                let third = (c - b'a' + 1) as usize;
80                let index = 27 * second + third;
81
82                let position = base * 1000 + offset;
83                let delta = position - pairs[index];
84
85                if delta > offset {
86                    // This is the first time we've seen the pair for this string.
87                    pairs[index] = position;
88                } else if delta > 1 {
89                    // No overlapping means that the distance must be at least two.
90                    two_pair = true;
91                }
92                if first == third {
93                    split_pair = true;
94                }
95
96                first = second;
97                second = third;
98            }
99
100            two_pair && split_pair
101        })
102        .count()
103}
aoc/year2015/day05.rs

aoc/year2015/
day05.rs
