Advent of Code: Day Five

Spoilers for Advent of Code below

• Day four
• All Advent of Code posts
• Source

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.