LD
Change your colour scheme

Advent of Code: Day Five

Published:

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.

Tags:

About the author

My face

I'm Lewis Dale, a software engineer and web developer based in the UK. I write about writing software, silly projects, and cycling. A lot of cycling. Too much, maybe.

Responses