aoc/year2022/
day03.rs

1//! # Rucksack Reorganization
2//!
3//! The core idea of this puzzle is computing set intersection. We could use the built-in `HashSet`
4//! but as the cardinality of the set is so small (52 maximum including both lowercase and
5//! uppercase letters) we can instead use a much faster approach of storing each set in a single
6//! `u64` integer and using bit manipulation.
7//!
8//! If a letter is present in the set then the corresponding bit will be `1` otherwise `0`.
9//! For example, to add the letter "a", logical OR the set with 1 shifted left by 33.
10//!
11//! `set | (1 << (b'a' & 0x3f))`
12//!
13//! Set intersection is the logical AND of two integers which compiles to a single machine
14//! instruction.
15//!
16//! `a & b`
17//!
18//! To obtain the score we can use the [`trailing_zeros`] method to find the first set bit. On most
19//! architectures this also compiles down to a single instruction (`LZCNT` on x86 or `CLZ` on ARM)
20//! that is blazing fast.
21//!
22//! Notes:
23//! * We could use a `u128` to use raw ASCII codes, but it performs less efficiently than a `u64`
24//!   combined with masked ASCII bytes. We can still not bother with computing offsets until the
25//!   very end.
26//!
27//! [`trailing_zeros`]: u64::trailing_zeros
28use crate::util::iter::*;
29
30/// Collect each line into a `vec` of string slices.
31pub fn parse(input: &str) -> Vec<&str> {
32    input.lines().collect()
33}
34
35/// Split each line into 2 equal halves, then compute the set intersection.
36pub fn part1(input: &[&str]) -> u32 {
37    input
38        .iter()
39        .map(|&rucksack| {
40            let (a, b) = rucksack.split_at(rucksack.len() / 2);
41            priority(mask(a) & mask(b))
42        })
43        .sum()
44}
45
46/// Group lines into chunks of 3, then compute the mutual set intersection.
47pub fn part2(input: &[&str]) -> u32 {
48    input.iter().chunk::<3>().map(|[a, b, c]| priority(mask(a) & mask(b) & mask(c))).sum()
49}
50
51/// Build a set from a slice of ASCII characters, using the `fold` function to repeatedly OR
52/// bit offsets into an accumulator.
53fn mask(s: &str) -> u64 {
54    s.bytes().fold(0, |acc, b| acc | (1 << (b & 0x3f)))
55}
56
57/// Find the lowest set bit (there should only be one) then convert to priority using the
58/// given rules.
59fn priority(mask: u64) -> u32 {
60    let bit = mask.trailing_zeros();
61    if bit > 32 { bit - 32 } else { bit + 26 }
62}
aoc/year2022/day03.rs

aoc/year2022/
day03.rs
