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

aoc/year2022/
day06.rs
