aoc/year2022/
day06.rs

1//! # Tuning Trouble
2//!
3//! One solution to this problem is to use the [`windows`] method to slide over groups of the desired
4//! size, then construct a [`HashSet`] from the characters. If the [`HashSet`] is the same size
5//! as the window then we know that all characters are unique, as sets contain no duplicate elements.
6//!
7//! We'll use a faster approach that minimizes the work needed. Instead of creating a set for each
8//! window, we'll maintain the last position seen of each character. As we advance character by
9//! character we lookup the previous position. If this is within the packet size, then we advance
10//! the start of the packet to exclude that character. Once the packet has reached the desired
11//! size then we return the current index.
12//!
13//! [`windows`]: slice::windows
14//! [`HashSet`]: std::collections::HashSet
15
16/// Return the input directly.
17pub fn parse(input: &str) -> &str {
18    input
19}
20
21/// Find the first unique set of size 4
22pub fn part1(input: &str) -> usize {
23    find(input, 4)
24}
25
26/// Find the first unique set of size 14
27pub fn part2(input: &str) -> usize {
28    find(input, 14)
29}
30
31/// The cardinality of the input is only 26 so a fixed size array can store the last position
32/// of each character.
33fn find(input: &str, marker: usize) -> usize {
34    let mut start = 0;
35    let mut seen = [0; 26];
36
37    for (i, b) in input.bytes().enumerate() {
38        // Use the character as an index into the array.
39        let index = (b - b'a') as usize;
40        let previous = seen[index];
41        // Positions are 1-based.
42        seen[index] = i + 1;
43
44        // There's a duplicate so advance the start of the window one character past it.
45        if previous > start {
46            start = previous;
47        }
48        // We've reached the desired packet size with no duplicates so finish.
49        if i + 1 - start == marker {
50            return i + 1;
51        }
52    }
53
54    unreachable!()
55}
aoc/year2022/day06.rs

aoc/year2022/
day06.rs
