Back to blog

Advent of Code: Day Five

Spoilers for Advent of Code below

Today was the first day that I can definitely say that I struggled to get the task done.

Part one

The brief sounded fairly simple. Given a list of "stacks" of boxes (represented by a character), and a set of instructions (in the format move n from x to y), work out what the final configuration would look like.

The 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

I was planning out my data structures, and this is where I made my first and silliest mistake: I used String for my stacks. "They're just lists of chars", I thought, this should be easy.

Unfortunately, my logic was off and I kept forgetting to reverse my strings, leading to a lot of banging my head against the wall when I came up with this:

#[derive(Debug, PartialEq, Eq)]
struct Operation {
    quantity: usize,
    source: usize,
    target: usize
} 

#[derive(Debug, PartialEq, Eq)]
pub struct Crane {
    pub stacks: Vec<String>,
    operations: VecDeque<Operation>,
}

impl Crane {
    fn operate(&mut self) {
        let operation = self.operations.pop_front().unwrap();
        let split: String = self.stacks[operation.source - 1].take(operation.quantity).unwrap();
        self.stacks[operation.target - 1].insert_str(0, &split);
    }
}

The take function was my first foray into using Trait to extend a core type:

trait Take<T> {
    fn take(&mut self, n: usize) -> Option<T>;
}

impl Take<String> for String {
    fn take(&mut self, n: usize) -> Option<String> {
        if n <= self.len() {
            let split = String::from(&self[..n]);
            self.replace_range(..n, "");
            return Some(split);
        }
        None
    }
}

But this didn't work, because my take function took the top off the string, and then replaced it in the original order, so instead of going from:

      P
N     Z
C  D  B

to:

N     
C     P
P     Z
Z  D  B

I was doing:

N     
C     
Z     
P  D  B

A subtle difference, but very important for the final result. In the end, I updated operate to reverse the strings before prepending them to the stack:

fn operate(&mut self) {
    let operation = self.operations.pop_front().unwrap();
    let split: String = self.stacks[operation.source - 1]
        .take(operation.quantity)
        .unwrap()
        .chars()
        .rev()
        .collect();
    self.stacks[operation.target - 1].insert_str(0, &split);
}

Part two

Interestingly... Part two's problem was the same, but I was to retain the original insertion order of the stack. Well, well, well, look how the tables have turned. My earlier cockup has become my superpower.

All I had to do was revert my little change from earlier, returning operate back to it's original state, and that was it!

Day 5 was a toughie for me, but mostly because I tried to be clever but really wasn't. Next time, I'll use an actual Stack - even if I need to write the operations for it myself.