Day 3 (Advent of Code 2022)

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 half
• hcsFMMfFFhFp is the second half

Each letter denotes a given item type, there's ${2 \times 26}$ 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:

Rust code
#[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(())
}

Shell session
$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: Rust code 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: Rust code 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: Rust code // 👇 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: Rust code 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! Rust code fn main() -> color_eyre::Result<()> { let _a = Item::try_from(b'a')?; let _exclaim = Item(b'!'); Ok(()) }  Shell session $ 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:

Rust code
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:

Rust code
    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:

Rust code
fn main() -> color_eyre::Result<()> {
let a = Item::try_from(b'a')?;
a.score();
a.score();

Ok(())
}

Shell session
$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. Rust code  // in mod item #[repr(transparent)] #[derive(Copy)] pub(crate) struct Item(u8);  Shell session $ 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:

Rust code
    // 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:

Rust code
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(())
}

Shell session
$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: Rust code 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(()) }  Shell session $ 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:

Rust code
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):

Shell session
$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! Rust code  // 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: Shell session $ 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:

Rust code
// 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!

Rust code
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!

Shell session
$cargo add itertools (cut)  Rust code 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(()) }  Shell session $ 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:

Rust code
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:

Shell session
$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! Shell session $ cargo add im
(cut)


It lets us compute the intersection of two sets, which I think is interesting!

Rust code
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:

Rust code
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:

Rust code
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]!