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 upper
5//! case letters) we can instead use a much faster approach of storing each set in a single `u128`
6//! 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 97
10//!
11//! `set | (1 << 97)`
12//!
13//! Set intersection is the logical AND of two integers which compiles to a single machine instruction.
14//!
15//! `a & b`
16//!
17//! To obtain the score we can use the [`trailing_zeroes`] method to find the first set bit. On most
18//! architectures this also compiles down to a single instruction (`LZCNT` on x86 or `CLZ` on ARM)
19//! that is blazing fast.
20//!
21//! Notes:
22//! * We could get away with a `u64` for the set, but by using an `u128` we can shift directly by the
23//!   raw ASCII codes and not bother computing offsets until the very end.
24//!
25//! [`trailing_zeroes`]: u128
26use crate::util::iter::*;
27
28/// Collect each line into a `vec` of string slices.
29pub fn parse(input: &str) -> Vec<&str> {
30    input.lines().collect()
31}
32
33/// Split each line into 2 equal halves, then compute the set intersection.
34pub fn part1(input: &[&str]) -> u32 {
35    input
36        .iter()
37        .map(|rucksack| {
38            let (a, b) = rucksack.split_at(rucksack.len() / 2);
39            priority(mask(a) & mask(b))
40        })
41        .sum()
42}
43
44/// Group lines into chunks of 3, then compute the mutual set intersection.
45pub fn part2(input: &[&str]) -> u32 {
46    input.iter().chunk::<3>().map(|[a, b, c]| priority(mask(a) & mask(b) & mask(c))).sum()
47}
48
49/// Build a set from a slice of ASCII characters, using the `fold` function to repeatedly OR
50/// bit offsets into an accumulator.
51fn mask(s: &str) -> u128 {
52    s.bytes().fold(0, |acc, b| acc | (1 << b))
53}
54
55/// Find the lowest set bit (there should only be one) then convert to priority using the
56/// given rules.
57fn priority(mask: u128) -> u32 {
58    let zeroes = mask.trailing_zeros();
59    match zeroes {
60        65..=90 => zeroes - 38,
61        97..=122 => zeroes - 96,
62        _ => unreachable!(),
63    }
64}
aoc/year2022/day03.rs

aoc/year2022/
day03.rs
