Thanks to my sponsors: Daniel Papp, Alejandro Angulo, Kai Kaufman, Senyo Simpson, Zachary Thomas, Romain Ruetschi, traxys, Yuriy Taraday, Mikkel Rasmussen, Kristoffer Winther Balling, Sawyer Knoblich, Tabitha, Zoran Zaric, Vincent, Daniel Wagner-Hall, Ross Williams, Marco Carmosino, Moritz Lammerich, Zaki, Scott Sanderson and 250 more
Day 3 (Advent of Code 2022)
👋 This page was last updated ~2 years ago. Just so you know.
Part 1
I'm not sure where the day 3 challenge is going, because the problem statement for the first part is kinda convoluted.
As usual we have an input, like this:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
Each line represents the contents of a "rucksack", divided in two halves (which are called "compartments"), so for line 1:
vJrwpWtwJgWr
is the first halfhcsFMMfFFhFp
is the second half
Each letter denotes a given item type, there's item types, for lowercase letters and uppercase letters, and, because we must somehow give the answer as a number, we can convert letters to numbers:
- 'a' through 'z' is 1 through 26
- 'A' through 'Z' is 27 through 52
In our little elf story, the elf in charge of packing the rucksacks made exactly one mistake per rucksack, and that's they put one item type in both compartments.
In the first rucksack, it's lowercase p
:
1st comp 2nd comp
vJrwpWtwJgWr hcsFMMfFFhFp
^ ^
Since I have no idea what part 2 is going to be about (it's talking about "fixing mistakes"), I'll just do whatever comes naturally.
I'd like to do an Item
type, that's really just a byte (u8
) with added
guarantees: that it's an ASCII letter.
We want to be able to convert from u8
to Item
, but it's fallible: if we pass
the '!' (exclamation mark) character for example, it should fail:
#[repr(transparent)]
struct Item(u8);
impl TryFrom<u8> for Item {
type Error = color_eyre::Report;
fn try_from(value: u8) -> Result<Self, Self::Error> {
match value {
b'a'..=b'z' | b'A'..=b'Z' => Ok(Item(value)),
_ => Err(color_eyre::eyre::eyre!(
"{} is not a valid item",
value as char
)),
}
}
}
fn main() -> color_eyre::Result<()> {
let _a = Item::try_from(b'a')?;
let _exclaim = Item::try_from(b'!')?;
Ok(())
}
$ cargo run
Finished dev [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/day3`
Error: ! is not a valid item
Location:
src/main.rs:10:22
Modules and visibility rules
However, that's not good enough.
Isn't it? Seems to work okay.
No, it's not. Because Item
is declared in the same module where we use it
from, so we can bypass validation and just do this:
fn main() -> color_eyre::Result<()> {
let _a = Item(b'a');
let _exclaim = Item(b'!');
Ok(())
}
And that compiles. Which we specifically do not want.
Oh, wait, I know this. Rust has visibility rules, like pub
, pub(crate)
,
pub(self)
, pub(super)
and pub(in path)
.
Wait, pub(self)
?
Yeah, same as pub(in self)
, same as not using pub
at all.
Uh-huh, continue.
Try putting Item
and the TryFrom
impl into its own module?
Do you mean, as a separate file?
Not necessarily! You wrote about this in 2019, remember?
Just.. ahh I'll show you:
mod item {
#[repr(transparent)]
struct Item(u8);
impl TryFrom<u8> for Item {
type Error = color_eyre::Report;
fn try_from(value: u8) -> Result<Self, Self::Error> {
match value {
b'a'..=b'z' | b'A'..=b'Z' => Ok(Item(value)),
_ => Err(color_eyre::eyre::eyre!(
"{} is not a valid item",
value as char
)),
}
}
}
}
fn main() -> color_eyre::Result<()> {
let _a = Item::try_from(b'a')?;
let _exclaim = Item::try_from(b'!')?;
Ok(())
}
Ah but that doesn't build, it can't find Item
in scope!
So use
it?
Very well:
// 👇
use item::Item;
fn main() -> color_eyre::Result<()> {
let _a = Item::try_from(b'a')?;
let _exclaim = Item::try_from(b'!')?;
Ok(())
}
...now it's telling me struct 'Item' is private
!
So make it... idk, pub(crate)
?
Okay then:
mod item {
#[repr(transparent)]
pub(crate) struct Item(u8);
// omitted: `impl TryFrom<u8> for Item`
}
Wait, doesn't that defeat the purpose of declaring Item
in its own module?
Can't we build invalid Item
values now?
Try it!
fn main() -> color_eyre::Result<()> {
let _a = Item::try_from(b'a')?;
let _exclaim = Item(b'!');
Ok(())
}
$ cargo check
Checking day3 v0.1.0 (/home/amos/bearcove/aoc2022/day3)
error[E0423]: cannot initialize a tuple struct which contains private fields
--> src/main.rs:24:20
|
24 | let _exclaim = Item(b'!');
| ^^^^
|
note: constructor is not visible here due to private fields
--> src/main.rs:3:28
|
3 | pub(crate) struct Item(u8);
| ^^ private field
For more information about this error, try `rustc --explain E0423`.
error: could not compile `day3` due to previous error
Ha, neat! We can't.
Ok what's next, mhh... now we want to be able to get an item's "priority", the numbers AoC made up so we can give our answer in the form of a number:
mod item {
// omitted: other declarations in this module
impl Item {
pub(crate) fn score(self) -> usize {
match self {
Item(b'a'..=b'z') => 1 + (self.0 - b'a') as usize,
Item(b'A'..=b'Z') => 27 + (self.0 - b'A') as usize,
_ => unreachable!(),
}
}
}
}
I mistakenly called it score
instead of priority
so now we're going with this.
Ah, mhh there's a couple traits we want to implement on Item
, now that I think
about it.
First off, we want to implement Debug
. We can just print the underlying letter:
impl std::fmt::Debug for Item {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.0 as char)
}
}
We also want Item
to behave like a Copy
value: like an u64
for example.
Which isn't the case right now: right now if you pass an Item
it moves it:
fn main() -> color_eyre::Result<()> {
let a = Item::try_from(b'a')?;
a.score();
a.score();
Ok(())
}
$ cargo check
Checking day3 v0.1.0 (/home/amos/bearcove/aoc2022/day3)
error[E0382]: use of moved value: `a`
--> src/main.rs:41:5
|
39 | let a = Item::try_from(b'a')?;
| - move occurs because `a` has type `Item`, which does not implement the `Copy` trait
40 | a.score();
| ------- `a` moved due to this method call
41 | a.score();
| ^ value used here after move
|
note: this function takes ownership of the receiver `self`, which moves `a`
--> src/main.rs:26:29
|
26 | pub(crate) fn score(self) -> usize {
| ^^^^
For more information about this error, try `rustc --explain E0382`.
error: could not compile `day3` due to previous error
Item
is just one byte, we're not planning on mutating it: we can treat it as a
plain old value, just like any other number, so, let's derive Copy
on it.
// in `mod item`
#[repr(transparent)]
#[derive(Copy)]
pub(crate) struct Item(u8);
$ cargo check
Checking day3 v0.1.0 (/home/amos/bearcove/aoc2022/day3)
error[E0277]: the trait bound `Item: Clone` is not satisfied
--> src/main.rs:3:14
|
3 | #[derive(Copy)]
| ^^^^ the trait `Clone` is not implemented for `Item`
|
note: required by a bound in `Copy`
--> /home/amos/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/marker.rs:382:17
|
382 | pub trait Copy: Clone {
| ^^^^^ required by this bound in `Copy`
= note: this error originates in the derive macro `Copy` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider annotating `Item` with `#[derive(Clone)]`
|
4 | #[derive(Clone)]
|
For more information about this error, try `rustc --explain E0277`.
error: could not compile `day3` due to previous error
...and Copy
requires Clone
, so let's derive that, too:
// in `mod item`
#[repr(transparent)]
#[derive(Clone, Copy)]
pub(crate) struct Item(u8);
Very good.
So now let's put the problem statement's input in src/input.txt
and start
reading it:
use item::Item;
fn main() -> color_eyre::Result<()> {
for line in include_str!("input.txt").lines() {
let items = line
.bytes()
.map(Item::try_from)
.collect::<Result<Vec<_>, _>>()?;
println!("- {items:?}");
}
Ok(())
}
$ cargo run --quiet
- [v, J, r, w, p, W, t, w, J, g, W, r, h, c, s, F, M, M, f, F, F, h, F, p]
- [j, q, H, R, N, q, R, j, q, z, j, G, D, L, G, L, r, s, F, M, f, F, Z, S, r, L, r, F, Z, s, S, L]
- [P, m, m, d, z, q, P, r, V, v, P, w, w, T, W, B, w, g]
- [w, M, q, v, L, M, Z, H, h, H, M, v, w, L, H, j, b, v, c, j, n, n, S, B, n, v, T, Q, F, n]
- [t, t, g, J, t, R, G, J, Q, c, t, T, Z, t, Z, T]
- [C, r, Z, s, J, s, P, P, Z, s, G, z, w, w, s, L, w, L, m, p, w, M, D, w]
Okay, now let's treat both compartments separately:
use item::Item;
fn main() -> color_eyre::Result<()> {
for line in include_str!("input.txt").lines() {
let (first, second) = line.split_at(line.len() / 2);
let first_items = first
.bytes()
.map(Item::try_from)
.collect::<Result<Vec<_>, _>>()?;
let second_items = second
.bytes()
.map(Item::try_from)
.collect::<Result<Vec<_>, _>>()?;
println!("- {first_items:?} | {second_items:?}");
}
Ok(())
}
$ cargo run --quiet
- [v, J, r, w, p, W, t, w, J, g, W, r] | [h, c, s, F, M, M, f, F, F, h, F, p]
- [j, q, H, R, N, q, R, j, q, z, j, G, D, L, G, L] | [r, s, F, M, f, F, Z, S, r, L, r, F, Z, s, S, L]
- [P, m, m, d, z, q, P, r, V] | [v, P, w, w, T, W, B, w, g]
- [w, M, q, v, L, M, Z, H, h, H, M, v, w, L, H] | [j, b, v, c, j, n, n, S, B, n, v, T, Q, F, n]
- [t, t, g, J, t, R, G, J] | [Q, c, t, T, Z, t, Z, T]
- [C, r, Z, s, J, s, P, P, Z, s, G, z] | [w, w, s, L, w, L, m, p, w, M, D, w]
Now... we don't really need to collect the second compartment's items: we just need to find which one is also included in the first compartment, and add its score to the total:
fn main() -> color_eyre::Result<()> {
let mut total_score = 0;
for line in include_str!("input.txt").lines() {
let (first, second) = line.split_at(line.len() / 2);
let first_items = first
.bytes()
.map(Item::try_from)
.collect::<Result<Vec<_>, _>>()?;
let dupe_score = second
.bytes()
.map(Item::try_from)
.find_map(|item| {
item.ok().and_then(|item| {
first_items
.iter()
// the iterator gives us `&Item`, but we want `Item`, and
// it's `Copy`, so we can call `copied()`
.copied()
// `find` gives us an `&Item`, but we want `Item`, so we
// destructure the reference here:
// 👇
.find(|&first_item| first_item == item)
})
})
.expect("there should be exactly one duplicate")
.score();
dbg!(dupe_score);
total_score += dupe_score;
}
dbg!(total_score);
Ok(())
}
The only problem with this code is that we can't compare Item
values for
equality (the first_item == item
bit):
$ cargo check
Checking day3 v0.1.0 (/home/amos/bearcove/aoc2022/day3)
error[E0369]: binary operation `==` cannot be applied to type `Item`
--> src/main.rs:59:56
|
59 | .find(|&first_item| first_item == item)
| ---------- ^^ ---- Item
| |
| Item
|
note: an implementation of `PartialEq<_>` might be missing for `Item`
--> src/main.rs:4:5
|
4 | pub(crate) struct Item(u8);
| ^^^^^^^^^^^^^^^^^^^^^^ must implement `PartialEq<_>`
help: consider annotating `Item` with `#[derive(PartialEq)]`
|
4 | #[derive(PartialEq)]
|
For more information about this error, try `rustc --explain E0369`.
error: could not compile `day3` due to previous error
Luckily the compiler tells us what to do!
// in `mod item`
#[repr(transparent)]
// 👇 👇
#[derive(Clone, Copy, PartialEq, Eq)]
pub(crate) struct Item(u8);
And that works! It matches the sample output given us in the problem statement:
$ cargo run --quiet
[src/main.rs:64] dupe_score = 16
[src/main.rs:64] dupe_score = 38
[src/main.rs:64] dupe_score = 42
[src/main.rs:64] dupe_score = 22
[src/main.rs:64] dupe_score = 20
[src/main.rs:64] dupe_score = 19
[src/main.rs:68] total_score = 157
But while we're here, let's mess around with it some more.
It probably doesn't make sense here, but if our dataset looked different, we
might want to collect the first compartment's items into a HashSet
rather than
a Vec
.
We need to think about it, but a HashSet
lookup is O(1)
, whereas checking
that an element is in a Vec
is O(N)
. The problem is that the fixed cost of
inserts and lookups into the HashSet
is most probably much higher than doing
operations in a tiny Vec
like we have here.
So, knowing full well that this we're probably a pessimization of our code,
let's try using a HashSet
instead:
// that one's not part of the prelude, so we have to `use` it ourselves:
use std::collections::HashSet;
// in fn main
// in the for loop
let first_items = first
.bytes()
.map(Item::try_from)
.collect::<Result<HashSet<_>, _>>()?;
When we do that, it complains that Item
does not implement the
Hash trait. And that
trait can be derived, too!
mod item {
#[repr(transparent)]
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct Item(u8);
// etc.
}
The program works exactly the same, so I won't repeat its output here.
Finally: can we do all that work as a single iterator which we can sum
,
without ever panicking? Let's find out!
$ cargo add itertools
(cut)
use item::Item;
use std::collections::HashSet;
fn main() -> color_eyre::Result<()> {
let sum = include_str!("input.txt")
.lines()
.map(|line| -> color_eyre::Result<_> {
let (first, second) = line.split_at(line.len() / 2);
let first_items = first
.bytes()
.map(Item::try_from)
.collect::<Result<HashSet<_>, _>>()?;
itertools::process_results(second.bytes().map(Item::try_from), |mut it| {
it.find(|&item| first_items.contains(&item))
.map(|item| dbg!(item.score()))
.ok_or_else(|| color_eyre::eyre::eyre!("compartments have no items in common"))
})?
})
.sum::<color_eyre::Result<usize>>()?;
dbg!(sum);
Ok(())
}
$ cargo run --quiet
[src/main.rs:52] item.score() = 16
[src/main.rs:52] item.score() = 38
[src/main.rs:52] item.score() = 42
[src/main.rs:52] item.score() = 22
[src/main.rs:52] item.score() = 20
[src/main.rs:52] item.score() = 19
[src/main.rs:57] sum = 157
Yes. Yes we can.
I forgot who clued me in on this, but you can sum
results!
Which we use here to avoid using process_results
a second time.
And with that, we are done with Part 1.
Part 2
In part 2, instead of splitting each lines in two compartments and finding the common item, we must split the whole input in groups of 3 lines, and find the common item in these three lines.
The sample input divides itself into two groups, like so:
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
The first group only has lowercase r
in common:
vJrwpWtwJgWrhcsFMMfFFhFp
^ ^
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
^ ^ ^
PmmdzqPrVvPwwTWBwg
^
And the second group only has uppercase Z
in common:
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
^
ttgJtRGJQctTZtZT
^
CrZsJsPPZsGzwwsLwLmpwMDw
^ ^
I'm feeling fairly lazy today (it is, after all, the week-end), and I know that
each line is fairly short, so I don't mind eagerly collecting all three lines of
a group into its own HashSet
— let's make an iterator that does that.
And then, because this is fallible we'll want itertools::process_results again, and we can simply find items that are in all three sets:
fn main() -> color_eyre::Result<()> {
let rucksacks = include_str!("input.txt").lines().map(|line| {
line.bytes()
.map(Item::try_from)
.collect::<Result<HashSet<_>, _>>()
});
let sum = itertools::process_results(rucksacks, |rs| {
rs.tuples()
.map(|(a, b, c)| {
a.iter()
.copied()
.find(|i| b.contains(i) && c.contains(i))
.map(|i| dbg!(i.score()))
.unwrap_or_default()
})
.sum::<usize>()
})?;
dbg!(sum);
Ok(())
}
This works:
$ cargo run --quiet
[src/main.rs:55] i.score() = 18
[src/main.rs:55] i.score() = 52
[src/main.rs:60] sum = 70
..but I'd like to showcase something else.
The im
crate
Let's forget about fallible iteration for a moment and try out the im crate, which provides immutable data structures like... HashSet!
$ cargo add im
(cut)
It lets us compute the intersection of two sets, which I think is interesting!
use im::HashSet;
use item::Item;
use itertools::Itertools;
fn main() -> color_eyre::Result<()> {
let sum: usize = include_str!("input.txt")
.lines()
.map(|line| {
line.bytes()
.map(|b| b.try_into().unwrap())
.collect::<HashSet<Item>>()
})
.chunks(3)
.into_iter()
.map(|chunks| {
chunks
.reduce(|a, b| a.intersection(b))
.expect("we always have 3 chunks")
.iter()
.next()
.expect("problem statement says there is always one item in common")
.score()
})
.sum();
dbg!(sum);
Ok(())
}
Instead of using tuples
, we used
Itertools::chunks.
That gaves us an iterator of iterators (of size 3). We reduce these inner
iterators into a single HashSet
, then find the first (and only, according to
the problem statement) item in there, and compute the score.
This is probably overkill, but it sure does work!
Reader suggestion: use a bool
array
Thanks to crazy01010
for suggesting this on
Reddit: because we have a small number of
possible keys here, we can use an array of bools instead of a HashSet
(I did mean to
cover that, but got lazy — well, now I have to!).
Here's what such a solution might look like:
use crate::item::Item;
use itertools::Itertools;
fn main() {
let sum: usize = include_str!("input.txt")
.lines()
.map(|line| {
line.bytes()
.map(|b| b.try_into().unwrap())
.fold([false; 53], |mut acc, x: Item| {
// this might panic! we could use a checked method instead
acc[x.score()] = true;
acc
})
})
.chunks(3)
.into_iter()
.map(|chunks| {
chunks
.reduce(|a, b| {
let mut res = [false; 53];
// `zip` is neat, we haven't gotten to use it yet!
for (acc, (a, b)) in res.iter_mut().zip(a.into_iter().zip(b.into_iter())) {
*acc = a && b;
}
res
})
.expect("we always have 3 chunks")
.iter()
.position(|&b| b)
.expect("problem statement says there is always one item in common")
})
.sum();
dbg!(sum);
}
Note that, to avoid off-by-one errors (by having to remember to subtract/add
one), I used a [bool; 53]
instead of a [bool; 52]
— I think we can afford an
extra bool :)
Reader suggestion: use a u8
array
Still by crazy01010
of using an array of bools, we can use an array of u8,
that way we can simply add values together and find the first one that sums to
3
:
use crate::item::Item;
use itertools::Itertools;
fn main() {
let sum: usize = include_str!("input.txt")
.lines()
.map(|line| {
line.bytes()
.map(|b| b.try_into().unwrap())
.fold([0u8; 53], |mut acc, x: Item| {
// this might panic!
acc[x.score()] = 1;
acc
})
})
.chunks(3)
.into_iter()
.map(|chunks| {
chunks
.reduce(|mut a, b| {
// another trick: we're re-using `a` as the output array
for (a, b) in a.iter_mut().zip(b.iter()) {
*a += *b;
}
a
})
.expect("we always have 3 chunks")
.iter()
.position(|&b| b == 3)
.expect("problem statement says there is always one item in common")
})
.sum();
dbg!(sum);
}
Too bad Sum
is not implemented for [T; N]
!
Thanks to my sponsors: Chris Walker, Lena Schönburg, Manuel Hutter, Vincent, callym, Dylan Anthony, Mikkel Rasmussen, Yann Schwartz, Timothée Gerber, Michael Mrozek, Garret Kelly, Nicolas Riebesel, playest, David Cornu, thbkrshw, Alejandro Angulo, Henrik Tudborg, Xirvik Servers, Tyler Schmidtke, Jon Gjengset and 250 more
My work is sponsored by people like you. Donate now so it can keep going:
Here's another article just for you:
Pin and suffering
I'd like to think that my understanding of "async Rust" has increased over the past year or so. I'm 100% onboard with the basic principle: I would like to handle thousands of concurrent tasks using a handful of threads. That sounds great!
And to become proficient with async Rust, I've accepted a lot of things. There are blue functions and red functions, and red (async) functions are contagious.