Day 3 (Advent of Code 2022)

Dec 3, 2022 8 minute read rust · advent-of-code · modules · data-structures

This article is part of the Advent of Code 2022 series.

Part 1
Modules and visibility rules
Part 2
The im crate
Reader suggestion: use a bool array
Reader suggestion: use a u8 array

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);
}