Day 5 (Advent of Code 2022)

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

Part 1

The day 5 challenge actually looks fun!

Our input looks like this:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

Which is a visual representation of stacks, and so, for once, we have some serious parsing to do, and that means I finally have a good reason to bust out the nom crate.

Shell session
$ cargo add nom@7
    Updating crates.io index
      Adding nom v7 to dependencies.
             Features as of v7.0.0:
             + alloc
             + std
             - docsrs

We're going to need a bunch of use statements, here they are in bulk:

Rust code
use nom::{
    branch::alt,
    bytes::complete::{tag, take},
    combinator::{all_consuming, map, opt},
    sequence::{delimited, preceded},
    Finish, IResult,
};

(This matters because nom has both bytes::streaming and bytes::complete. We have all the input here, so we don't need to write a streaming parser).

First we'll want to parse the crates: a crate is [c] where c is a char (it could be a u8 but let's waste a little memory to make our lives slightly comfier).

Rust code
#[derive(Debug)]
struct Crate(char);

fn parse_crate(i: &str) -> IResult<&str, Crate> {
    let first_char = |s: &str| Crate(s.chars().next().unwrap());
    let f = delimited(tag("["), take(1_usize), tag("]"));
    map(f, first_char)(i)
}

Equally important is a hole, that's just three spaces.

Rust code
fn parse_hole(i: &str) -> IResult<&str, ()> {
    // `drop` takes a value and returns nothing, which is
    // perfect for our case
    map(tag("   "), drop)(i)
}

We must be able to parse both crates and holes, so let's have a function that does either, and returns an Option<Crate>:

Rust code
fn parse_crate_or_hole(i: &str) -> IResult<&str, Option<Crate>> {
    alt((map(parse_crate, Some), map(parse_hole, |_| None)))(i)
}

And then, one that parses a full line:

Rust code
fn parse_crate_line(i: &str) -> IResult<&str, Vec<Option<Crate>>> {
    let (mut i, c) = parse_crate_or_hole(i)?;
    let mut v = vec![c];

    loop {
        let (next_i, maybe_c) = opt(preceded(tag(" "), parse_crate_or_hole))(i)?;
        match maybe_c {
            Some(c) => v.push(c),
            None => break,
        }
        i = next_i;
    }

    Ok((i, v))
}

Finally, we can use it like so:

Rust code
fn main() {
    let mut crate_lines = vec![];

    for line in include_str!("sample-input.txt").lines() {
        if let Ok((_rest, crate_line)) = all_consuming(parse_crate_line)(line).finish() {
            crate_lines.push(crate_line);
        }
    }

    for line in &crate_lines {
        println!("{line:?}");
    }
}

This gives us, for the sample input:

Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.40s
     Running `target/debug/day5`
[None, Some(Crate('D')), None]
[Some(Crate('N')), Some(Crate('C')), None]
[Some(Crate('Z')), Some(Crate('M')), Some(Crate('P'))]

Which is a pretty good start! However, the problem has us consider those crates in "piles", which are columns, and we have lines/rows. So, we need a "transpose" implementation.

Here's a Rust tip: the language has been around for a while, you don't need to code everything yourself! I did a quick web search for "transpose vec of vecs in rust" and stumbled upon this StackOverflow answer, which we can use as-is:

Rust code
fn transpose<T>(v: Vec<Vec<T>>) -> Vec<Vec<T>> {
    assert!(!v.is_empty());
    let len = v[0].len();
    let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
    (0..len)
        .map(|_| {
            iters
                .iter_mut()
                .map(|n| n.next().unwrap())
                .collect::<Vec<T>>()
        })
        .collect()
}

Our main function then becomes:

Rust code
fn main() {
    let mut crate_lines = vec![];

    for line in include_str!("sample-input.txt").lines() {
        if let Ok((_rest, crate_line)) = all_consuming(parse_crate_line)(line).finish() {
            crate_lines.push(crate_line);
        }
    }

    let crate_columns = transpose(crate_lines);
    for col in &crate_columns {
        println!("{col:?}");
    }
}
Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.47s
     Running `target/debug/day5`
[None, Some(Crate('N')), Some(Crate('Z'))]
[Some(Crate('D')), Some(Crate('C')), Some(Crate('M'))]
[None, None, Some(Crate('P'))]

Now they're arranged by columns, but we still have the holes! We can get rid of those by having transpose accept a Vec<Vec<Option<T>>> and switching from map to filter_map, which already expects an Option<T> and will simply ignore the None items.

Rust code
//                           👇
fn transpose<T>(v: Vec<Vec<Option<T>>>) -> Vec<Vec<T>> {
    assert!(!v.is_empty());
    let len = v[0].len();
    let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
    (0..len)
        .map(|_| {
            iters
                .iter_mut()
                // 👇
                .filter_map(|n| n.next().unwrap())
                .collect::<Vec<T>>()
        })
        .collect()
}
Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running `target/debug/day5`
[Crate('N'), Crate('Z')]
[Crate('D'), Crate('C'), Crate('M')]
[Crate('P')]

That's better. But there's still an issue: we have those in "top to bottom order". Because we're going to need to pop crates off of some piles and plop them over the top of some other piles (that's what the next few lines are instructing us to do), it would be more convenient to have them in the reverse order:

Rust code
// renamed to 👇 better indicate functionality
fn transpose_rev<T>(v: Vec<Vec<Option<T>>>) -> Vec<Vec<T>> {
    assert!(!v.is_empty());
    let len = v[0].len();
    let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
    (0..len)
        .map(|_| {
            iters
                .iter_mut()
                // 👇
                .rev()
                .filter_map(|n| n.next().unwrap())
                .collect::<Vec<T>>()
        })
        .collect()
}
Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.46s
     Running `target/debug/day5`
[Crate('Z'), Crate('N')]
[Crate('M'), Crate('C'), Crate('D')]
[Crate('P')]

Let's clean up the Debug output a bit:

Rust code
struct Crate(char);

impl fmt::Debug for Crate {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}
Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.48s
     Running `target/debug/day5`
[Z, N]
[M, C, D]
[P]

And compare with our input:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

Shape rotators of the world, unite! I think this looks okay.

Next up, we should parse instructions. We have decimal numbers:

Rust code
fn parse_number(i: &str) -> IResult<&str, usize> {
    map_res(take_while1(|c: char| c.is_ascii_digit()), |s: &str| {
        s.parse::<usize>()
    })(i)
}

Our piles are 0-indexed, not 1-indexed, so:

Rust code
// convert from 1-indexed to 0-indexed
fn parse_pile_number(i: &str) -> IResult<&str, usize> {
    map(parse_number, |i| i - 1)(i)
}

And then full instructions:

Rust code
#[derive(Debug)]
struct Instruction {
    quantity: usize,
    src: usize,
    dst: usize,
}

fn parse_instruction(i: &str) -> IResult<&str, Instruction> {
    map(
        tuple((
            preceded(tag("move "), parse_number),
            preceded(tag(" from "), parse_pile_number),
            preceded(tag(" to "), parse_pile_number),
        )),
        |(quantity, src, dst)| Instruction { quantity, src, dst },
    )(i)
}

Our main function becomes:

Rust code
fn main() {
    let mut lines = include_str!("sample-input.txt").lines();

    let crate_lines: Vec<_> = (&mut lines)
        .map_while(|line| {
            all_consuming(parse_crate_line)(line)
                .finish()
                .ok()
                .map(|(_, line)| line)
        })
        .collect();
    let crate_columns = transpose_rev(crate_lines);
    for col in &crate_columns {
        println!("{col:?}");
    }

    // we've consumed the "numbers line" but not the separating line
    assert!(lines.next().unwrap().is_empty());

    let instructions: Vec<_> = lines
        .map(|line| all_consuming(parse_instruction)(line).finish().unwrap().1)
        .collect();
    for ins in &instructions {
        println!("{ins:?}");
    }
}

Note that our error handling here is minimal. You can make it better if you want!

Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.42s
     Running `target/debug/day5`
[Z, N]
[M, C, D]
[P]
Instruction { quantity: 1, src: 1, dst: 0 }
Instruction { quantity: 3, src: 0, dst: 2 }
Instruction { quantity: 2, src: 1, dst: 0 }
Instruction { quantity: 1, src: 0, dst: 1 }

It's time to apply instructions, one by one! For convenience, we'll make Crate Copy:

Rust code
#[derive(Clone, Copy)]
struct Crate(char);

And we'll make a Piles type, with a Debug impl:

Rust code
struct Piles(Vec<Vec<Crate>>);

impl fmt::Debug for Piles {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for (i, pile) in self.0.iter().enumerate() {
            writeln!(f, "Pile {}: {:?}", i, pile)?;
        }
        Ok(())
    }
}

So we can easily dump it:

Rust code
    let piles = Piles(transpose_rev(crate_lines));
    println!("{piles:?}");
Shell session
$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/day5`
Pile 0: [Z, N]
Pile 1: [M, C, D]
Pile 2: [P]

Instruction { quantity: 1, src: 1, dst: 0 }
Instruction { quantity: 3, src: 0, dst: 2 }
Instruction { quantity: 2, src: 1, dst: 0 }
Instruction { quantity: 1, src: 0, dst: 1 }

And now we can have an apply method on Piles:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        for _ in 0..ins.quantity {
            let el = self.0[ins.src].pop().unwrap();
            self.0[ins.dst].push(el);
        }
    }
}

And our main function can apply instructions as we parse them:

Rust code
fn main() {
    let mut lines = include_str!("sample-input.txt").lines();

    let crate_lines: Vec<_> = (&mut lines)
        .map_while(|line| {
            all_consuming(parse_crate_line)(line)
                .finish()
                .ok()
                .map(|(_, line)| line)
        })
        .collect();

    let mut piles = Piles(transpose_rev(crate_lines));
    println!("{piles:?}");

    // we've consumed the "numbers line" but not the separating line
    assert!(lines.next().unwrap().is_empty());

    for ins in lines.map(|line| all_consuming(parse_instruction)(line).finish().unwrap().1) {
        println!("{ins:?}");
        piles.apply(ins);
        println!("{piles:?}");
    }
}
Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.50s
     Running `target/debug/day5`
Pile 0: [Z, N]
Pile 1: [M, C, D]
Pile 2: [P]

Instruction { quantity: 1, src: 1, dst: 0 }
Pile 0: [Z, N, D]
Pile 1: [M, C]
Pile 2: [P]

Instruction { quantity: 3, src: 0, dst: 2 }
Pile 0: []
Pile 1: [M, C]
Pile 2: [P, D, N, Z]

Instruction { quantity: 2, src: 1, dst: 0 }
Pile 0: [C, M]
Pile 1: []
Pile 2: [P, D, N, Z]

Instruction { quantity: 1, src: 0, dst: 1 }
Pile 0: [C]
Pile 1: [M]
Pile 2: [P, D, N, Z]

Finally, the answer has to be what's on top of each pile: for us, that's the last item of the Vec (since we are in "bottom to top" order):

Rust code
    println!(
        "answer = {}",
        piles.0.iter().map(|pile| pile.last().unwrap()).join("")
    );

Joining iterators is not functionality that's in the Rust standard library: we could collect to a Vec first if we wanted to stick with libstd, but I don't mind reaching for itertools again, so:

Shell session
$ cargo add itertools
(cut)
Rust code
use itertools::Itertools;

Now .join works on iterators, and all that's left is to implement Display for Crate, which we can just forward to its Debug impl:

Rust code
impl fmt::Display for Crate {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(self, f)
    }
}
Shell session
$ cargo run
   Compiling either v1.8.0
   Compiling itertools v0.10.5
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 1.72s
     Running `target/debug/day5`
Pile 0: [Z, N]
Pile 1: [M, C, D]
Pile 2: [P]

Instruction { quantity: 1, src: 1, dst: 0 }
Pile 0: [Z, N, D]
Pile 1: [M, C]
Pile 2: [P]

Instruction { quantity: 3, src: 0, dst: 2 }
Pile 0: []
Pile 1: [M, C]
Pile 2: [P, D, N, Z]

Instruction { quantity: 2, src: 1, dst: 0 }
Pile 0: [C, M]
Pile 1: []
Pile 2: [P, D, N, Z]

Instruction { quantity: 1, src: 0, dst: 1 }
Pile 0: [C]
Pile 1: [M]
Pile 2: [P, D, N, Z]

answer = CMZ

That does give the right answer for the sample input... and for my real input! Neat!

Part 2

In part 2, we discover that in fact, when applying an instruction, we shouldn't lift crates off of the source pile and into the destination pile one by one, but all together!

This is a simple change:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        // N.B: `crate` is a keyword
        for krate in (0..ins.quantity)
            .map(|_| self.0[ins.src].pop().unwrap())
            .rev()
        {
            self.0[ins.dst].push(krate);
        }
    }
}

Or.. it would be, if it compiled:

Shell session
$ cargo check --quiet
error[E0501]: cannot borrow `self.0` as mutable because previous closure requires unique access
  --> src/main.rs:60:13
   |
56 |           for krate in (0..ins.quantity)
   |  ______________________-
57 | |             .map(|_| self.0[ins.src].pop().unwrap())
   | |                  --- ------ first borrow occurs due to use of `self.0` in closure
   | |                  |
   | |                  closure construction occurs here
58 | |             .rev()
   | |__________________- first borrow later used here
59 |           {
60 |               self.0[ins.dst].push(krate);
   |               ^^^^^^ second borrow occurs here

For more information about this error, try `rustc --explain E0501`.
error: could not compile `day5` due to previous error

The problem here is that we cannot have two mutable references to the same Vec. This is actually fine, since they're (supposedly!) references to different items of the Vec, but it's just something the borrow checker doesn't understand.

There's a bunch of ways to solve this, which is why it's interesting to discuss.

Borrow checker limitations and workarounds

It's worth noting that the borrow checker is already quite smart. I won't get into everything here, but, I just want to note that, for example, this compiles:

Rust code
#[derive(Default)]
struct S {
    a: u32,
    b: u32,
}

let mut s = S::default();
let a = &mut s.a;
let b = &mut s.b;
*a = 1;
*b = 2;
*a = 3;
*b = 4;

Here, we're borrowing mutably two different fields from the same struct. That's no problem at all!

Things are different with a Vec, or even an array:

Rust code
let mut arr = [12_usize, 34];
let a = &mut arr[0];
let b = &mut arr[1];
*a = 1;
*b = 2;
*a = 3;
*b = 4;
Rust code
$ cargo check --quiet
error[E0499]: cannot borrow `arr[_]` as mutable more than once at a time
  --> src/main.rs:65:17
   |
64 |         let a = &mut arr[0];
   |                 ----------- first mutable borrow occurs here
65 |         let b = &mut arr[1];
   |                 ^^^^^^^^^^^ second mutable borrow occurs here
66 |         *a = 1;
   |         ------ first borrow later used here
   |
   = help: consider using `.split_at_mut(position)` or similar method to obtain two mutable non-overlapping sub-slices

For more information about this error, try `rustc --explain E0499`.
error: could not compile `day5` due to previous error

The compiler does give a suggestion though: that's our first workaround. It is obviously correct to hold two mutable references to different positions of an array/slice/vec, so we are able to achieve that with only safe code.

It's just that the API is a bit awkward for what we're trying to do:

Rust code
// this is `[12, 34]`
let mut arr = [12_usize, 34];

let (xx, yy) = arr.split_at_mut(1);
// `xx` is now `[12]` and `yy` is `[34]`

let a = &mut xx[0];
let b = &mut yy[0];
*a = 1;
*b = 2;
*a = 3;
*b = 4;

"Why this is even an issue" might be especially puzzling if you're coming at Rust with a C/C++ mindset.

You'd expect to just be able to mutate whatever, and be careful as to what you're doing so you don't accidentally create data races etc.

And that's something "unsafe Rust" lets you do.

It doesn't change the normal rules, so this still doesn't compile:

Rust code
unsafe {
    let mut arr = [12_usize, 34];
    let a = &mut arr[0];
    let b = &mut arr[1];
    *a = 1;
    *b = 2;
    *a = 3;
    *b = 4;
}
Shell session
$ cargo check --quiet
error[E0499]: cannot borrow `arr[_]` as mutable more than once at a time
  --> src/main.rs:66:21
   |
65 |             let a = &mut arr[0];
   |                     ----------- first mutable borrow occurs here
66 |             let b = &mut arr[1];
   |                     ^^^^^^^^^^^ second mutable borrow occurs here
67 |             *a = 1;
   |             ------ first borrow later used here
   |
   = help: consider using `.split_at_mut(position)` or similar method to obtain two mutable non-overlapping sub-slices

warning: unnecessary `unsafe` block
  --> src/main.rs:63:9
   |
63 |         unsafe {
   |         ^^^^^^ unnecessary `unsafe` block
   |
   = note: `#[warn(unused_unsafe)]` on by default

For more information about this error, try `rustc --explain E0499`.
error: could not compile `day5` due to previous error; 1 warning emitted

Which is to say: the borrow checker still runs on unsafe code. The compiler even helpfully points out that, since we're not doing unsafe things inside that block (merely illegal things), it's unnecessary and should be removed.

This is important, because the unsafe keyword denote parts of the code that warrant careful inspection, since it's where we can accidentaly invoke nasal demons UB (undefined behavior).

Here's something unsafe: raw pointers!

Rust code
unsafe {
    let mut arr = [12_usize, 34];
    let arr_ptr = arr.as_mut_ptr();

    let a_index = 0;
    let b_index = 1;

    let a = &mut *arr_ptr.add(a_index);
    let b = &mut *arr_ptr.add(b_index);
    *a = 1;
    *b = 2;
    *a = 3;
    *b = 4;
}

This code is fine. Probably. But this one isn't:

Rust code
unsafe {
    let mut arr = [12_usize, 34];
    let arr_ptr = arr.as_mut_ptr();

    let a_index = 0;
    let b_index = 0;

    let a = &mut *arr_ptr.add(a_index);
    let b = &mut *arr_ptr.add(b_index);
    *a = 1;
    *b = 2;
    *a = 3;
    *b = 4;
}

Can you tell why?

We're creating two mutable references to the same memory location. And that's not just "potentially trouble down the line, if we have accesses to the two references from different threads", it's insta-UB and everything goes: the compiler may delete your program or shave your head if it so wishes. Nothing is guaranteed anymore.

Which is why, if we're going to do it this way, we'll want to build a safe abstraction on top of it:

Rust code
pub trait BorrowTwoMut<T> {
    fn borrow_two_mut(&mut self, a: usize, b: usize) -> (&mut T, &mut T);
}

impl<T> BorrowTwoMut<T> for [T] {
    fn borrow_two_mut(&mut self, a: usize, b: usize) -> (&mut T, &mut T) {
        assert!(a != b);
        unsafe {
            let ptr = self.as_mut_ptr();
            let a_ptr = ptr.add(a);
            let b_ptr = ptr.add(b);
            (&mut *a_ptr, &mut *b_ptr)
        }
    }
}

And now, we can do this:

Rust code
let mut arr = [12_usize, 34];
let (a, b) = arr.borrow_two_mut(0, 1);

*a = 1;
*b = 2;
*a = 3;
*b = 4;

It'll fail at runtime if you pass the same two indices. It's perfect!

Uh... no it's not?

Consider this:

Rust code
let mut arr = [12_usize, 34];
//                              👇
let (a, b) = arr.borrow_two_mut(8, 9);

*a = 1;
*b = 2;
*a = 3;
*b = 4;

Uh oh, that's right! I forgot about bound checks. Those are done when indexing on slices (you can use unchecked versions if that's really your bottleneck but chances are, it's really not).

Here's a more correct version:

Rust code
impl<T> BorrowTwoMut<T> for [T] {
    fn borrow_two_mut(&mut self, a: usize, b: usize) -> (&mut T, &mut T) {
        assert!(a != b);
        assert!(a < self.len());
        assert!(b < self.len());
        unsafe {
            let ptr = self.as_mut_ptr();
            let a_ptr = ptr.add(a);
            let b_ptr = ptr.add(b);
            (&mut *a_ptr, &mut *b_ptr)
        }
    }
}

I say "more correct" because there might still be bugs. I don't know! I don't write a lot of unsafe code — I don't have to.

In fact, I'd be much more comfortable with this implementation:

Rust code
impl<T> BorrowTwoMut<T> for [T] {
    fn borrow_two_mut(&mut self, a: usize, b: usize) -> (&mut T, &mut T) {
        assert!(a != b);
        if a < b {
            let (l, r) = self.split_at_mut(b);
            (&mut l[a], &mut r[0])
        } else {
            let (l, r) = self.split_at_mut(a);
            (&mut r[0], &mut l[b])
        }
    }
}

And some tests, of course:

Rust code
#[cfg(test)]
mod tests {
    use crate::BorrowTwoMut;

    #[test]
    fn borrow_two_mut_works() {
        let mut arr = [0, 1, 2, 3, 4, 5];
        {
            let (a, b) = arr.borrow_two_mut(1, 4);
            assert_eq!(*a, 1);
            assert_eq!(*b, 4);
        }
        {
            let (a, b) = arr.borrow_two_mut(5, 2);
            assert_eq!(*a, 5);
            assert_eq!(*b, 2);
        }
    }

    #[test]
    #[should_panic]
    fn borrow_two_mut_panics_on_same_index() {
        let mut arr = [0, 1, 2, 3, 4, 5];
        let (_, _) = arr.borrow_two_mut(1, 1);
    }
}

Anyway, that's not the only way for us to get out of this pickle.

We can use a RefCell to do borrow-checking at runtime instead:

Rust code
use std::cell::RefCell;

struct Piles(Vec<RefCell<Vec<Crate>>>);

We have to change some code:

Rust code
    // in main

    let mut piles = Piles(
        transpose_rev(crate_lines)
            .into_iter()
            .map(RefCell::new)
            .collect(),
    );
    println!("{piles:?}");

    // then, later
    println!(
        "answer = {}",
        piles
            .0
            .iter()
            .map(|pile| *pile.borrow().last().unwrap())
            .join("")
    );

And:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        // N.B: `crate` is a keyword
        for krate in (0..ins.quantity)
            .map(|_| self.0[ins.src].borrow_mut().pop().unwrap())
            .rev()
        {
            self.0[ins.dst].borrow_mut().push(krate);
        }
    }
}

But it does work!

Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.52s
     Running `target/debug/day5`
Pile 0: RefCell { value: [Z, N] }
Pile 1: RefCell { value: [M, C, D] }
Pile 2: RefCell { value: [P] }

Instruction { quantity: 1, src: 1, dst: 0 }
Pile 0: RefCell { value: [Z, N, D] }
Pile 1: RefCell { value: [M, C] }
Pile 2: RefCell { value: [P] }

Instruction { quantity: 3, src: 0, dst: 2 }
Pile 0: RefCell { value: [] }
Pile 1: RefCell { value: [M, C] }
Pile 2: RefCell { value: [P, D, N, Z] }

Instruction { quantity: 2, src: 1, dst: 0 }
Pile 0: RefCell { value: [C, M] }
Pile 1: RefCell { value: [] }
Pile 2: RefCell { value: [P, D, N, Z] }

Instruction { quantity: 1, src: 0, dst: 1 }
Pile 0: RefCell { value: [C] }
Pile 1: RefCell { value: [M] }
Pile 2: RefCell { value: [P, D, N, Z] }

answer = CMZ

...wait, no it doesn't. Well I mean it builds, but it doesn't do the right thing!

In fact, .rev() doesn't seem to do anything here...

Well I supposed if you iterate (0, 1, 2) or (2, 1, 0), and then lazily map that to some_vec.pop()... it makes no difference.

No yeah I can see the reasoning, I just... mhh. It feels wrong. But I get it.

So, huh, I suppose... we can move on to my next solution, which is simply:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        // N.B: `crate` is a keyword
        for krate in (0..ins.quantity)
            .map(|_| self.0[ins.src].pop().unwrap())
            .collect::<Vec<_>>()
            .into_iter()
            .rev()
        {
            self.0[ins.dst].push(krate);
        }
    }
}

That way, we're forcing evaluation of the first map early, and then iterating those results in reverse order.

That code (which is what I wanted to do in the first place) does give the correct result:

Shell session
$ cargo run
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished dev [unoptimized + debuginfo] target(s) in 0.57s
     Running `target/debug/day5`
Pile 0: [Z, N]
Pile 1: [M, C, D]
Pile 2: [P]

Instruction { quantity: 1, src: 1, dst: 0 }
Pile 0: [Z, N, D]
Pile 1: [M, C]
Pile 2: [P]

Instruction { quantity: 3, src: 0, dst: 2 }
Pile 0: []
Pile 1: [M, C]
Pile 2: [P, Z, N, D]

Instruction { quantity: 2, src: 1, dst: 0 }
Pile 0: [M, C]
Pile 1: []
Pile 2: [P, Z, N, D]

Instruction { quantity: 1, src: 0, dst: 1 }
Pile 0: [M]
Pile 1: [C]
Pile 2: [P, Z, N, D]

answer = MCD

Heap allocation hate club

And I can hear you from here: "But Amos, that's unnecessary heap allocation! can't we get rid of it?"

And of course we can. I skimmed through my input and found that we never need to move more than 64 items, so, if you insist, we can allocate that on the stack instead:

Shell session
$ cargo add smallvec
    Updating crates.io index
      Adding smallvec v1.10.0 to dependencies.
             (cut)
Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        // N.B: `crate` is a keyword
        for krate in (0..ins.quantity)
            .map(|_| self.0[ins.src].pop().unwrap())
            .collect::<SmallVec<[_; 64]>>()
            .into_iter()
            .rev()
        {
            self.0[ins.dst].push(krate);
        }
    }
}

Now let's track how many allocations we saved with tracking-allocator.

Shell session
$ cargo add tracking-allocator@0.4 --no-default-features
    Updating crates.io index
      Adding tracking-allocator v0.4 to dependencies.
             Features as of v0.4.0:
             - tracing
             - tracing-compat
             - tracing-subscriber

Then, above main:

Rust code
use std::alloc::System;
use tracking_allocator::{
    AllocationGroupId, AllocationGroupToken, AllocationRegistry, AllocationTracker, Allocator,
};

#[global_allocator]
static GLOBAL: tracking_allocator::Allocator<std::alloc::System> =
    tracking_allocator::Allocator::system();

#[global_allocator]
static GLOBAL: Allocator<System> = Allocator::system();

struct StdoutTracker;

impl AllocationTracker for StdoutTracker {
    fn allocated(
        &self,
        addr: usize,
        object_size: usize,
        wrapped_size: usize,
        group_id: AllocationGroupId,
    ) {
        println!(
            "allocation -> addr=0x{:0x} object_size={} wrapped_size={} group_id={:?}",
            addr, object_size, wrapped_size, group_id
        );
    }

    fn deallocated(
        &self,
        addr: usize,
        object_size: usize,
        wrapped_size: usize,
        source_group_id: AllocationGroupId,
        current_group_id: AllocationGroupId,
    ) {
        println!(
            "deallocation -> addr=0x{:0x} object_size={} wrapped_size={} source_group_id={:?} current_group_id={:?}",
            addr, object_size, wrapped_size, source_group_id, current_group_id
        );
    }
}

And then, in main:

Rust code
    AllocationRegistry::set_global_tracker(StdoutTracker)
        .expect("no other global tracker should be set yet");

    AllocationRegistry::enable_tracking();

    for ins in lines.map(|line| all_consuming(parse_instruction)(line).finish().unwrap().1) {
        println!("{ins:?}");
        piles.apply(ins);
        println!("{piles:?}");
    }

    AllocationRegistry::disable_tracking();

This generates output like:

Shell session
$ cargo run --release
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/day5`
Pile 0: [Q, S, W, C, Z, V, F, T]
Pile 1: [Q, R, B]
Pile 2: [B, Z, T, Q, P, M, S]
Pile 3: [D, V, F, R, Q, H]
Pile 4: [J, G, L, D, B, S, T, P]
Pile 5: [W, R, T, Z]
Pile 6: [H, Q, M, N, S, F, R, J]
Pile 7: [R, N, F, H, W]
Pile 8: [J, Z, T, Q, P, R, B]

Instruction { quantity: 3, src: 7, dst: 1 }
allocation -> addr=0x55d54070f2b8 object_size=12 wrapped_size=24 group_id=AllocationGroupId(1)
allocation -> addr=0x55d54070f308 object_size=32 wrapped_size=40 group_id=AllocationGroupId(1)
deallocation -> addr=0x55d54070f2b8 object_size=12 wrapped_size=24 source_group_id=AllocationGroupId(1) current_group_id=AllocationGroupId(1)
Pile 0: [Q, S, W, C, Z, V, F, T]
Pile 1: [Q, R, B, F, H, W]
Pile 2: [B, Z, T, Q, P, M, S]
Pile 3: [D, V, F, R, Q, H]
Pile 4: [J, G, L, D, B, S, T, P]
Pile 5: [W, R, T, Z]
Pile 6: [H, Q, M, N, S, F, R, J]
Pile 7: [R, N]
Pile 8: [J, Z, T, Q, P, R, B]

Instruction { quantity: 3, src: 0, dst: 4 }
allocation -> addr=0x55d54070f2b8 object_size=12 wrapped_size=24 group_id=AllocationGroupId(1)
allocation -> addr=0x55d54070ef08 object_size=64 wrapped_size=72 group_id=AllocationGroupId(1)
deallocation -> addr=0x55d54070f2b8 object_size=12 wrapped_size=24 source_group_id=AllocationGroupId(1) current_group_id=AllocationGroupId(1)
Pile 0: [Q, S, W, C, Z]
Pile 1: [Q, R, B, F, H, W]
Pile 2: [B, Z, T, Q, P, M, S]
Pile 3: [D, V, F, R, Q, H]
Pile 4: [J, G, L, D, B, S, T, P, V, F, T]
Pile 5: [W, R, T, Z]
Pile 6: [H, Q, M, N, S, F, R, J]
Pile 7: [R, N]
Pile 8: [J, Z, T, Q, P, R, B]

And we can count allocations:

Shell session
$ cargo run --release | grep -E '^allocation' | wc -l
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/day5`
532

That was with Vec, let's do SmallVec:

Shell session
$ cargo run --release | grep -E '^allocation' | wc -l
   Compiling day5 v0.1.0 (/home/amos/bearcove/aoc2022/day5)
    Finished release [optimized] target(s) in 0.62s
     Running `target/release/day5`
29

Wait, 29? Not zero? Let's find out where the allocation happened:

Rust code
impl AllocationTracker for StdoutTracker {
    fn allocated(
        &self,
        addr: usize,
        object_size: usize,
        wrapped_size: usize,
        group_id: AllocationGroupId,
    ) {
        println!(
            "allocation -> addr=0x{:0x} object_size={} wrapped_size={} group_id={:?}",
            addr, object_size, wrapped_size, group_id
        );
        // 👇
        panic!();
    }

    // etc.
}
Shell session
$ RUST_BACKTRACE=1 cargo run --release
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/day5`
Pile 0: [Q, S, W, C, Z, V, F, T]
Pile 1: [Q, R, B]
Pile 2: [B, Z, T, Q, P, M, S]
Pile 3: [D, V, F, R, Q, H]
Pile 4: [J, G, L, D, B, S, T, P]
Pile 5: [W, R, T, Z]
Pile 6: [H, Q, M, N, S, F, R, J]
Pile 7: [R, N, F, H, W]
Pile 8: [J, Z, T, Q, P, R, B]

Instruction { quantity: 3, src: 7, dst: 1 }
allocation -> addr=0x562feb2eb2b8 object_size=32 wrapped_size=40 group_id=AllocationGroupId(1)
thread 'main' panicked at 'explicit panic', src/main.rs:31:9
stack backtrace:
   0: rust_begin_unwind
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/std/src/panicking.rs:584:5
   1: core::panicking::panic_fmt
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/panicking.rs:142:14
   2: core::panicking::panic
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/panicking.rs:48:5
   3: <day5::StdoutTracker as tracking_allocator::AllocationTracker>::allocated
   4: <tracking_allocator::allocator::Allocator<A> as core::alloc::global::GlobalAlloc>::alloc
   5: __rg_realloc
   6: alloc::raw_vec::finish_grow
   7: alloc::raw_vec::RawVec<T,A>::reserve_for_push
   8: day5::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

We get an even better stack trace if we turn up debug information for our release build:

TOML markup
[package]
name = "day5"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
itertools = "0.10.5"
nom = "7"
smallvec = "1.10.0"
tracking-allocator = { version = "0.4", default-features = false }

# 👇 new!
[profile.release]
debug = 1
Shell session
$ RUST_BACKTRACE=1 cargo run --release
    Finished release [optimized + debuginfo] target(s) in 0.16s
     Running `target/release/day5`
Pile 0: [Q, S, W, C, Z, V, F, T]
Pile 1: [Q, R, B]
Pile 2: [B, Z, T, Q, P, M, S]
Pile 3: [D, V, F, R, Q, H]
Pile 4: [J, G, L, D, B, S, T, P]
Pile 5: [W, R, T, Z]
Pile 6: [H, Q, M, N, S, F, R, J]
Pile 7: [R, N, F, H, W]
Pile 8: [J, Z, T, Q, P, R, B]

Instruction { quantity: 3, src: 7, dst: 1 }
allocation -> addr=0x5619efa782b8 object_size=32 wrapped_size=40 group_id=AllocationGroupId(1)
thread 'main' panicked at 'explicit panic', src/main.rs:31:9
stack backtrace:
   0: rust_begin_unwind
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/std/src/panicking.rs:584:5
   1: core::panicking::panic_fmt
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/panicking.rs:142:14
   2: core::panicking::panic
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/panicking.rs:48:5
   3: <day5::StdoutTracker as tracking_allocator::AllocationTracker>::allocated
             at ./src/main.rs:31:9
   4: <tracking_allocator::allocator::Allocator<A> as core::alloc::global::GlobalAlloc>::alloc::{{closure}}
             at /home/amos/.cargo/registry/src/github.com-1ecc6299db9ec823/tracking-allocator-0.4.0/src/allocator.rs:85:21
   5: tracking_allocator::token::try_with_suspended_allocation_group::{{closure}}
             at /home/amos/.cargo/registry/src/github.com-1ecc6299db9ec823/tracking-allocator-0.4.0/src/token.rs:268:17
   6: std::thread::local::LocalKey<T>::try_with
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/std/src/thread/local.rs:445:16
   7: tracking_allocator::token::try_with_suspended_allocation_group
             at /home/amos/.cargo/registry/src/github.com-1ecc6299db9ec823/tracking-allocator-0.4.0/src/token.rs:261:13
   8: <tracking_allocator::allocator::Allocator<A> as core::alloc::global::GlobalAlloc>::alloc
             at /home/amos/.cargo/registry/src/github.com-1ecc6299db9ec823/tracking-allocator-0.4.0/src/allocator.rs:74:13
   9: core::alloc::global::GlobalAlloc::realloc
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/alloc/global.rs:264:32
  10: __rg_realloc
             at ./src/main.rs:15:16
  11: alloc::alloc::realloc
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/alloc.rs:132:14
  12: alloc::alloc::Global::grow_impl
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/alloc.rs:209:31
  13: <alloc::alloc::Global as core::alloc::Allocator>::grow
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/alloc.rs:262:18
  14: alloc::raw_vec::finish_grow
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/raw_vec.rs:466:13
  15: alloc::raw_vec::RawVec<T,A>::grow_amortized
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/raw_vec.rs:400:19
  16: alloc::raw_vec::RawVec<T,A>::reserve_for_push
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/raw_vec.rs:298:24
  17: alloc::vec::Vec<T,A>::push
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/alloc/src/vec/mod.rs:1768:13
  18: day5::Piles::apply
             at ./src/main.rs:107:13
  19: day5::main
             at ./src/main.rs:74:9
  20: core::ops::function::FnOnce::call_once
             at /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/ops/function.rs:248:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

And.. yeah, it happens when we actually push to another pile:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        // N.B: `crate` is a keyword
        for krate in (0..ins.quantity)
            .map(|_| self.0[ins.src].pop().unwrap())
            .collect::<SmallVec<[_; 256]>>()
            // .collect::<Vec<_>>()
            .into_iter()
            .rev()
        {
            //              👇 here!
            self.0[ins.dst].push(krate);
        }
    }
}

Very well — we can simply reserve capacity for our piles, trading memory usage for speed:

Rust code
fn transpose_rev<T>(v: Vec<Vec<Option<T>>>) -> Vec<Vec<T>> {
    assert!(!v.is_empty());
    let len = v[0].len();
    let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
    (0..len)
        .map(|_| {
            //               👇
            let v = Vec::with_capacity(256); // just to be on the safe side
            iters
                .iter_mut()
                .rev()
                .filter_map(|n| n.next().unwrap())
                //    👇
                .collect_into(&mut v);
            v
        })
        .collect()
}

Woops, that one is nightly-only (as of Rust 1.65), but we can use extend instead:

Rust code
fn transpose_rev<T>(v: Vec<Vec<Option<T>>>) -> Vec<Vec<T>> {
    assert!(!v.is_empty());
    let len = v[0].len();
    let mut iters: Vec<_> = v.into_iter().map(|n| n.into_iter()).collect();
    (0..len)
        .map(|_| {
            let mut v = Vec::with_capacity(256); // just to be on the safe side
            v.extend(iters.iter_mut().rev().filter_map(|n| n.next().unwrap()));
            v
        })
        .collect()
}

And voila! No more heap allocations!

Shell session
$ cargo run --release | grep -E '^allocation' | wc -l
    Finished release [optimized + debuginfo] target(s) in 0.00s
     Running `target/release/day5`
0

Happy now?

Cool bear's hot tip

Vec::with_capacity still allocates on the heap, but it does so before we start tracking allocations. We got rid of re-allocations that used to happen while moving the crates around, not the initial allocations.

Removing all heap allocations is a fool's errand anyway. Don't do it! Except as a challenge... maybe.

Reader suggestion: use nom's digit1 parser

Instead of this:

Rust code
fn parse_number(i: &str) -> IResult<&str, usize> {
    map_res(take_while1(|c: char| c.is_ascii_digit()), |s: &str| {
        s.parse::<usize>()
    })(i)
}

We can use nom's built-in digit1 parser.

Rust code
fn parse_number(i: &str) -> IResult<&str, usize> {
    map_res(digit1, |s: &str| s.parse::<usize>())(i)
}

Which is simpler and shorter!

Thanks to salameme on GitHub!

Reader suggestion: use nom's number parser

Simpler still (but it doesn't support usize), we can use nom's number parsers:

Rust code
fn parse_number(i: &str) -> IResult<&str, usize> {
    map(nom::character::complete::u32, |n| n as _)(i)
}

Thanks to afdbcreid on Reddit for this suggestion.

Reader suggestion: use nom's separated_list1 combinator

In parse_crate_line, instead of our complicated loop:

Rust code
fn parse_crate_line(i: &str) -> IResult<&str, Vec<Option<Crate>>> {
    let (mut i, c) = parse_crate_or_hole(i)?;
    let mut v = vec![c];

    loop {
        let (next_i, maybe_c) = opt(preceded(tag(" "), parse_crate_or_hole))(i)?;
        match maybe_c {
            Some(c) => v.push(c),
            None => break,
        }
        i = next_i;
    }

    Ok((i, v))
}

We can use nom's separated_list1 combinator:

Rust code
fn parse_crate_line(i: &str) -> IResult<&str, Vec<Option<Crate>>> {
    separated_list1(tag(" "), parse_crate_or_hole)(i)
}

Thanks to afdbcreid on Reddit for this suggestion.

Reader suggestion: Iterator::by_ref

When we're parsing crate lines, and we don't want to move out of the iterator, since we still have more stuff to parse after, instead of doing (&mut lines)

Rust code
    //                          👇
    let crate_lines: Vec<_> = (&mut lines)
        .map_while(|line| {
            all_consuming(parse_crate_line)(line)
                .finish()
                .ok()
                .map(|(_, line)| line)
        })
        .collect();

We can use lines.by_ref():

Rust code
    let crate_lines: Vec<_> = lines
        // 👇
        .by_ref()
        .map_while(|line| {
            all_consuming(parse_crate_line)(line)
                .finish()
                .ok()
                .map(|(_, line)| line)
        })
        .collect();

Thanks to afdbcreid on Reddit for this suggestion.

Reader suggestion: use nightly rust's get_many_mut

We need to switch to Rust nightly for this, let's create a rust-toolchain.toml file that pins a recent nightly:

TOML markup
[toolchain]
channel = "nightly-2022-12-06"

And then we can use get_many_mut instead of our BorrowTwoMut trait:

Rust code
// at the top of the file
#![feature(get_many_mut)]

impl Piles {
    fn apply(&mut self, ins: Instruction) {
        let [src, dst] = self
            .0
            .get_many_mut([ins.src, ins.dst])
            .expect("out of bounds / overlapping src/dst stacks");

        (0..ins.quantity)
            .map(|_| src.pop().unwrap())
            .collect::<SmallVec<[_; 64]>>()
            .into_iter()
            .rev()
            .for_each(|c| dst.push(c));
    }
}

Thanks to afdbcreid on Reddit for this suggestion, which was slightly better than that but it overlapped with another suggestion that was posted earlier, so I separated out just the get_many_mut part.

Reader suggestion: use drain and extend

Instead of popping each item from the end of the source stack, we can use drain with a range to drain only the part we need to move. Then, we can use extend on the destination stack to add everything from that iterator:

Rust code
impl Piles {
    fn apply(&mut self, ins: Instruction) {
        let [src, dst] = self
            .0
            .get_many_mut([ins.src, ins.dst])
            .expect("out of bounds / overlapping src/dst stacks");

        dst.extend(src.drain((src.len() - ins.quantity)..))
    }
}

This also works for part 1 if you call rev on the iterator returned by drain.

Thanks to usr_bin_nya and afdbcreid on Reddit, and probably others, for pointing this out.

Reader suggestion: collect into a String

Several folks, including psychonoff on Reddit suggested that, although, yes, Iterator::join wasn't in the standard library, in this case we could simply collect our Iterator<Item = char> into a String:

This code:

Rust code
    println!(
        "answer = {}",
        piles.0.iter().map(|pile| *pile.last().unwrap()).join("")
    );

Becomes:

Rust code
    println!(
        "answer = {}",
        piles
            .0
            .iter()
            // this accesses the inner char 👇 (we could also use `.to_string()`)
            .map(|pile| pile.last().unwrap().0)
            .collect::<String>()
    );

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

Read the next part

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Latest video View all

video cover image
C++ vs Rust: which is faster?

I ported some Advent of Code solutions from C/C++ to Rust, and used the opportunity to compare performance. When I couldn't explain why they performed differently, I had no choice but to disassemble both and look at what the codegen was like!

Watch now