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

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

#[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.

Cool bear

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.

Cool bear

Oh, wait, I know this. Rust has visibility rules, like pub, pub(crate), pub(self), pub(super) and pub(in path).

Wait, pub(self)?

Cool bear

Yeah, same as pub(in self), same as not using pub at all.

Uh-huh, continue.

Cool bear

Try putting Item and the TryFrom impl into its own module?

Do you mean, as a separate file?

Cool bear

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!

Cool bear

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!

Cool bear

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?

Cool bear

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!(),
            }
        }
    }
}
Amos

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

Comment on /r/fasterthanlime

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:

GitHub Continue with GitHub Patreon Continue with Patreon

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.