It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!
Day 03 - Rucksack Reorganization
Find the problem description HERE.
The Input - A Bit of This, A Bit of That
Time to pack the rucksacks! Today’s puzzle has us keeping up with which items are in two different compartments of a rucksack. These sound suspiciously like_sets_ of items, and since we know exactly how many different possible items there are, we can use a bit of (somewhat) clever bit manipulation to store our set as a single integer, where each different set bit indicates the presence of an individual type of item.
use anyhow::{anyhow, bail, Error, Result};
const INPUT: &str = include_str!("../../input/03/input.txt");
// Today we'll do a bit of math converting ASCII characters to numbers.
// These constants are used in that math. For references, ASCII 'a' corresponds
// to a value of 97, and ASCII 'A' corresponds to a value of 65.
const LOWERCASE_OFFSET: u32 = 96; // 'a' -> 97 - 1 (priority of 'a') = 96
const CAPITAL_OFFSET: u32 = 38; // 'A' -> 65 - 26 (priority of 'A') = 38
/// A `Rucksack` represents a pack carried by an elf with two different,
/// separated sets of `Item`s.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Rucksack(ItemSet, ItemSet);
/// Attempt to convert a line from the input into a `Rucksack`
impl TryFrom<&str> for Rucksack {
type Error = Error;
fn try_from(s: &str) -> Result<Self, Self::Error> {
// Because the input lines contain two equal-length strings of
// characters representing `Item`s, we need the length of each
// half.
let compartment_len = s.len() / 2;
// Split the line into two equal-length strings
let (str1, str2) = s.split_at(compartment_len);
// Convert each string into a set of `Item`s
let compartment1 = ItemSet::try_from(str1)?;
let compartment2 = ItemSet::try_from(str2)?;
// Return a `Rucksack` with two sets of items
Ok(Rucksack(compartment1, compartment2))
}
}
/// An `ItemSet` represents the unique items held in each compartment of a
/// `Rucksack`. The goal is to provide functionality equivalent to a
/// `HashSet<Item>` (at least as much as we need) without the overhead
/// of an actual `HashSet`. This is accomplished by assigning each type of
/// `Item` to a particular bit in the inner `u64`.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
pub struct ItemSet(u64);
impl ItemSet {
/// Insert an `Item` into an `ItemSet`.
fn insert(&mut self, item: Item) {
// Set the bit in the `ItemSet` that corresponds to the particular type
// of `Item`.
self.0 |= item.0;
}
}
/// Attempt to convert a string slice into a set of `Item`s.
impl TryFrom<&str> for ItemSet {
type Error = Error;
fn try_from(value: &str) -> Result<Self, Self::Error> {
// Start with an empty item set
let mut item_set = ItemSet::default();
// Convert each character in the input string into an `Item` and
// insert each `Item` into the set
for ch in value.chars() {
let item = Item::try_from(ch)?;
item_set.insert(item);
}
Ok(item_set)
}
}
/// An `Item` represents a particular item carried by the elves. Because the puzzle
/// specifies that there are only 52 possible item types, each item can be uniquely
/// represented by a single set bit in a `u64` with 6 extra bits to spare. We'll set
/// bits in order of increasing priority, starting with 'a' at 2^1. This way, the
/// number of trailing zeros will be equal to priority. So, 'a' will be stored as
/// 2u64 with 1 trailing zero, and 'A' will be stored as 134217728u64 with 27 trailing
/// zeros.
///
/// Just for excessive clarity, 2u64 is represented in bits as:
/// 0b00000000000000000000000000000000000000000000000000000000000010
///
/// 134217728u64 is represented in bits as:
/// 0b00000000000000000000000000000000001000000000000000000000000000
#[derive(Debug, Clone, Copy)]
pub struct Item(u64);
/// Attempt to convert a single character into an `Item`
impl TryFrom<char> for Item {
type Error = Error;
fn try_from(value: char) -> Result<Self, Self::Error> {
// Error if trying to make an `Item` out of any character that's not a letter
if !value.is_alphabetic() { bail!("Cannot convert {value} to an Item!") }
// Offset for ASCII range starts and priority offset.
let offset = if value > 'Z' { LOWERCASE_OFFSET } else { CAPITAL_OFFSET };
let priority = value as u32 - offset;
let set_bit = 1 << priority; // One bit, shifted left by priority
Ok(Item(set_bit))
}
}
/// Read and parse the input
pub fn read() -> Vec<Rucksack> {
// Attempt to convert each line into a `Rucksack` and return the
// list of successful results.
INPUT.lines().flat_map(Rucksack::try_from).collect()
}
Lots of abstraction here, but hopefully it flows nicely and makes it clear what we’re doing. Essentially an ItemSet serves the same purpose for us as aHashSet<Item> and a Rucksack contains two of them.
Part One - Organized Chaos
Looks like one of the elf AI’s glitched and dropped an extra item into one of each rucksack’s compartments. I was worried that we were going to need to figure out which compartment had the extra item in it, which would have been a bit on the steep side for a Day 3 puzzle, but no, we just need to figure out which item in each rucksack is in both compartments. Given that we’re representing each compartment as a set of items, that’s just an intersect operation! We can do that.
use anyhow::{bail, Error, Result};
/// Solve Day 3, Part 1
pub fn solve(input: &Input) -> u32 {
// For each `Rucksack`, identify the one item in common between the
// compartments, calculate that item's priority, and return the sum
// of all unique item priorities.
input
.iter()
.flat_map(|r| r.one_in_common())
.map(|i| i.priority())
.sum::<u32>()
}
impl Rucksack {
/// Attempt to identify the one `Item` in common between both compartments.
fn one_in_common(&self) -> Result<Item> {
self.0.intersect(self.1).try_into()
}
}
impl ItemSet {
/// Construct an `ItemSet` that contains only items in common between
/// `self` and `other`. Just a bitwise _and_ on the underlying integers.
fn intersect(&self, other: ItemSet) -> ItemSet {
ItemSet(self.0 & other.0)
}
}
/// Attempt to convert an `ItemSet` into a single `Item`.
/// Fails and returns an Error if the `ItemSet` contains more than one item.
impl TryFrom<ItemSet> for Item {
type Error = Error;
fn try_from(set: ItemSet) -> Result<Self, Self::Error> {
if set.0.count_ones() > 1 {
bail!("{set:?} contains more than one item!")
}
Ok(Item(set.0))
}
}
impl Item {
/// Calculate the priority of the `Item`. Recall each `Item` is represented
/// by a single bit shifted left by priority, so priority is just the
/// number of trailing zeros.
fn priority(&self) -> u32 {
self.0.trailing_zeros()
}
}
Good thing that there really is only one item in common between the compartments, otherwise we’d be in a pickle. That elf glitch was oddly… specific…
Part Two - We Don’t Need No Stinkin’ Badges
Ok, so this flub is understandable. Some elf just didn’t do their job. It happens. Maybe they were busy compiling a Rock, Paper, Scissors strategy guide or something. Can’t say for sure. All we know, is we need to identify which item in each group is the badge. Not that that saves anyone from having to go and manually collect each badge from each rucksack to apply these stickers, making our identification seem a bit unnecessary, but hey, we’re better at coding than manual labor anyway.
use anyhow::Result;
use itertools::Itertools;
pub fn solve(input: &Input) -> u32 {
let mut total = 0; // The sum of badge priorities
// Convert each `Rucksack` to an `ItemSet` consisting of all its unique
// `Item`s, as an iterator.
let rucksack_sets = input.iter().map(|r| r.all_items());
// For each chunk of three rucksack_sets in sequence...
for chunk in &rucksack_sets.chunks(3) {
// Produce an `ItemSet` that is the intersection of all three sets
// in the chunk. If the chunk is empty, we get an empty `ItemSet` back.
let intersect = chunk
.reduce(|acc, i| acc.intersect(i))
.unwrap_or(ItemSet(0));
// Attempt to convert the `ItemSet` into a single Item. Panic if
// the chunk contains more than one common item. The puzzle text
// assures us this won't happen.
let badge = Item::try_from(intersect).expect("{intersect:?} contains multiple Items!");
// Add the priority of the badge to the total
total += badge.priority();
}
total
}
impl Rucksack {
/// Return an `ItemSet` comprised of the items in both compartments of
/// the `Rucksack`. Recall that this is a set, so duplicates aren't counted.
fn all_items(&self) -> ItemSet {
ItemSet(self.0 .0 | self.1 .0)
}
}
Got it. Now we’re prepared to organize the sticker application effort in a _much_more reasonable way than just by one group at a time. Maybe the stickers can only go on specific badges or something…
Wrap Up
Well, no major text parsing today, so we skipped using nom. Using integers instead of actual HashSets spiced things up a bit, though! Plus, this is a much more performant solution than using actual HashSets, which is a nice repeatable process for situations with a known constraint on the number of possible value types, as long as they can be mapped to a particular bit. This could get a bit tricky if you’ve got more than 128 items since the largest Rust integer type is u128, but you could get there with multiple integers if need be. May be something to keep in mind for future days. Stay tuned!
Top comments (0)