Today's challenge is a good opportunity to use the parser crate peg to parse the text input. The task is to move crates between stacks using a giant cargo crane.
Let's have a look at 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
The input is more complex than the previous days, as it encodes information about the supply stack and a set of moves how to rearrange the crates. The first block is the supply stack consisting of three stacks
[D]
[N] [C]
[Z] [M] [P]
1 2 3
The first stack (or column) contains the element Z at the bottom & N on top. The second stack consists of crates M, C, D (bottom to top) & the last stack consists of the single element P. Each stack is assigned a label, 1, 2 & 3 that are referenced in the moves to re-arrange stacks.
The second half of the input is a list of moves that are applied. For example the line move 1 from 2 to 1 means to move one crate from stack labelled 2 to the target stack 1. Applied to the given input example the stack after one move would result in:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
After the second line with move 3 from 1 to 3 the stack would look
[Z]
[N]
[C] [D]
[M] [P]
1 2 3
The crane is able to move one crate at a time, thereby reversing the order of crates when moved from source stack to the target stack.
Part 1
Let's use peg to parse the content of all lines that make up the supply stack. peg is a flexible parser generator based on Parsing expression grammar formalism. There exist other parser generators or combinators that would do a similar job.
One of the other well known crates is nom, which is shown in more detail in fasterthanlime's excellent summary of day 5.
The basic idea of the parser is to detect an empty slot, a filled crate or a label. Empty slots & labels will be ignored later, but they are parsed as they are part of the stack. It's also more convenient to split the input at the newline (\n\n) to separate stack from moves.
First we add the peg crate as a dependency to the Cargo.toml. We also add the anyhow crate there as well to manage errors this time.
# Cargo.toml
[dependencies]
anyhow = "1.0"
peg = "0.8.1"
The parser grammar then looks like this:
peg::parser! {
grammar stack_parser() for str {
rule number_slot() -> char
= " " n:['0'..='9'] " " { n }
rule empty_slot() -> char
= " " { '.' }
rule filled_slot() -> char
= "[" c:['A'..='Z'] "]" { c }
rule slot() -> char
= filled_slot() / empty_slot() / number_slot()
pub rule line() -> Vec<char>
= s:(slot() ** " " ) { s }
}
}
#[cfg(test)]
mod tests {
use crate::*;
#[test]
fn check_stack_parser() -> anyhow::Result<()> {
assert_eq!(vec!['.', 'D', '.'], stack_parser::line(" [D] ")?);
assert_eq!(vec!['1', '2', '3'], stack_parser::line(" 1 2 3 ")?);
Ok(())
}
}
The parser implements a grammar for str, other input types are possible. The grammar is made of rules, its syntax uses pattern matching and a few constructs to combine them, e.g. the / character is an ordered choice which returns the first rule that matches from left to right.
The expected results are defined by return types. Our main rule is line which reads a single line from the input to generate a Vec<char>.
Type char is sufficient for our purposes. The interesting part here is the three different cases result in different chars. An empty slot will return ., a label will return the number and a filled slot the crate identifier. One possible issue with using the peg::parser! macro
is sometimes error messages are not easy to discern or understand. A test to check the parser accepts our input is given as well.
We use the parse function to read the input text, split the input into two blocks at the blank line. For now the first block is parsed.
peg::parser! {
grammar stack_parser() for str {
// as above
}
}
fn parse(input: &str) -> anyhow::Result<()> {
let (stack, _moves) = input
.split_once("\n\n")
.ok_or_else(|| anyhow!("Failed to split input"))?;
let stacks = stack
.lines()
.filter_map(|line| stack_parser::line(line).ok())
.collect::<Vec<_>>();
println!("STACKS: {:?}", stacks);
todo!()
}
fn main() -> anyhow::Result<()> {
parse(include_str!("input.txt"))?;
}
As before the input file is copied into a local file input.txt next to the main.rs file and loaded via the include_str! macro.
The second block with the move arrangements can also be parsed its own peg parser. The parser will use pattern matching to determine the
components of a line, e.g. move 3 from 1 to 3. It makes sense to group these components into their own struct to give it a name. We
name it very appropriately Move.
#[derive(Debug, PartialEq, Eq)]
pub struct Move {
pub num_crates: u32,
pub from: usize,
pub to: usize,
}
impl Move {
pub fn new(num_crates: u32, from: usize, to: usize) -> Self {
Self {
num_crates,
from,
to,
}
}
}
peg::parser! {
grammar move_parser() for str {
rule number() -> u32
= n:$(['1'..='9']+) { n.parse::<u32>().unwrap() }
rule digit() -> usize
= n:['1'..='9'] { n.to_string().parse::<usize>().unwrap() }
/// Parses the line "move 1 from 2 to 1"
pub rule line() -> Move
= "move " num:number() " from " f:digit() " to " t:digit() { Move::new(num, f, t) }
}
}
#[cfg(test)]
mod tests {
#[test]
fn check_move_parser() -> anyhow::Result<()> {
assert_eq!(
Ok(Move::new(1, 2, 1)),
move_parser::line("move 1 from 2 to 1")
);
assert_eq!(
Ok(Move::new(10, 1, 3)),
move_parser::line("move 10 from 1 to 3")
);
Ok(())
}
}
The number of crates to move can be in double digits, while all stack labels are given between 1 and 9. There is another test to check
the move_parser accepts the possible inputs.
There is one thing left we have to figure out first. The crate stacks are read line by line, meaning the input is read as rows, but the stacks are encoded as columns. Therefore it's required to transform the list of rows appropriately into a list of columns by transposing them. A transpose operation flips a matrix over it's diagonal. This is a well known operation in Matrix calculations. After a short search this Matrix Transposition example looks very promising. It's adjusted for our use case slightly, e.g. we will ignore any non-alphabetical entries.
Similar to the Move struct we group all of it into its own SupplyStack struct that manages the transpose.
#[derive(Debug)]
pub struct SupplyStack {
pub stacks: Vec<Vec<char>>,
}
impl SupplyStack {
pub fn new(rows: &[Vec<char>]) -> Self {
let mut stacks = vec![Vec::with_capacity(rows.len()); rows[0].len()];
for row in rows {
for (index, c) in row.iter().enumerate() {
if c.is_alphabetic() {
stacks[index].push(*c);
}
}
}
Self { stacks }
}
}
This initializes the 2-dimensional vectors first, then fills it with crates by ignoring all non-alphabetical ones.
With both parsers in place and the SupplyStack transposing the crates correctly we can update the parse function now.
fn parse(input: &str) -> anyhow::Result<(SupplyStack, Vec<Move>)> {
let (stack, moves) = input
.split_once("\n\n")
.ok_or_else(|| anyhow!("Failed to split input"))?;
let stacks = stack
.lines()
.filter_map(|line| stack_parser::line(line).ok())
.collect::<Vec<_>>();
let stack = SupplyStack::new(&stacks);
let moves = moves
.lines()
.filter_map(|line| move_parser::line(line).ok())
.collect::<Vec<_>>();
Ok((stack, moves))
}
The function returns a anyhow::Result<(SupplyStack, Vec<Move>), on success the tuple contains the SupplyStack with all stacks and a list of Move.
Now the parser logic is in place and we are ready to tackle the task itself. The task is to re-arrange the given supply stack by applying a list of re-arrangement moves on it, then to read the top crates of all stacks. The final result is a transformed stack where crates are distributed differently. In the given input example above after applying all moves on the given supply stack the top crates are C in stack 1, M in stack 2 and Z in stack 3, resulting in the message CMZ.
As seen on previous days, a part1 function will produce the result:
impl SupplyStack {
pub fn apply_move(&mut self, mv: &Move) -> anyhow::Result<()> {
todo!("")
}
pub fn top(&self) -> String {
todo!("")
}
}
fn part1(stack: &mut SupplyStack, moves: &[Move]) -> anyhow::Result<String> {
for m in moves {
stack.apply(m)?;
}
Ok(stack.top())
}
#[cfg(test)]
mod tests {
use crate::*;
// This time the formating needs to keep all whitespaces in place.
const INPUT: &str = r#" [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
"#;
#[test]
fn check_part1() -> anyhow::Result<()> {
let (mut stack, moves) = parse(INPUT)?;
assert_eq!("CMZ", part1(&mut stack, &moves)?);
Ok(())
}
}
The SupplyStack has two new methods apply_move to apply a list of moves & top to produce the final String. A test checks our sample input.
A move consists of three properties, the number of crates to move, the source stack and the target stack. The crane itself can only transfer one crate at a time, therefore the process needs to be repeated num_crates times. A move removes the top element from one stack & inserts it on top of the other stack. There are different types or collections to choose from.
For example a VecDeque a double ended queue works similar to Vec and has methods to push & pop elements from front or back.
In our case we stick with Vec as it's not really a performance issue, even though removing or inserting elements will re-allocate the Vec internally.
impl SupplyStack {
pub fn apply_move(&mut self, mv: &Move) -> anyhow::Result<()> {
for _ in 0..mv.num_crates {
let c = self.stacks[mv.from - 1].remove(0);
self.stacks[mv.to - 1].insert(0, c);
}
Ok(())
}
/// Returns the top crates from the stacks, ignores any empty stacks
pub fn top(&self) -> String {
self.stacks
.iter()
.filter_map(|stack| stack.first())
.collect::<String>()
}
}
Method apply_move could fail, for example when the given stack labels used in the moves would have have been different.
A slightly more robust approach would have been to use a HashMap for example to map labels to stacks. There is still a chance that something could fail, when a re-arrangement tries to move a crate from an empty stack then a call of remove would panic. The return type anyhow::Result<()> is not really useful here. Let's add some logic to guard the remove call to avoid any possible panics.
impl SupplyStack {
pub fn apply_move(&mut self, mv: &Move) -> anyhow::Result<()> {
for _ in 0..mv.num_crates {
if self.stacks[mv.from - 1].is_empty() {
return Err(anyhow!("Cannot take crate from empty stack"));
}
let c = self.stacks[mv.from - 1].remove(0);
self.stacks[mv.to - 1].insert(0, c);
}
Ok(())
}
}
The top function is fairly simply. It iterates over all stacks ignoring empty ones and convert the letters into a String. The input text
does not result in a supply stack with any empty stacks, therefore the resulting string will contain 9 letters.
We should now have all the logic in place, the updated main function then looks as follows:
fn main() -> anyhow::Result<()> {
let (mut stack, moves) = parse(include_str!("input.txt"))?;
println!("Part 1: {}", part1(&mut stack, &moves)?);
Ok(())
}
The tests should pass & executing cargo run should provide the first solution.
Part 2
The second updates the working of the cargo crane, as it appears it's able to move a substack of crates at once, not one by one. Which means a move now can transfer multiple crates at once from source to target stack without changing the order in which they appear.
Given the earlier example supply stack:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
Applying the re-arrangement using move 3 from 1 to 3 the stack would look then as:
[D]
[N]
[C] [Z]
[M] [P]
1 2 3
Note the order of crates D, N, Z is the same. To make this work we add a new method SupplyStack named multi_move
& add another test to check new expected outcome.
impl SupplyStack {
pub fn multi_move(&mut self, mv: &Move) -> anyhow::Result<()> {
todo!()
}
}
fn part2(stack: &mut SupplyStack, moves: &[Move]) -> anyhow::Result<String> {
for m in moves {
stack.multi_move(m)?;
}
Ok(stack.top())
}
fn main() -> anyhow::Result<()> {
let (mut stack, moves) = parse(include_str!("input.txt"))?;
println!("Part 1: {}", part1(&mut stack, &moves)?);
println!("Part 2: {}", part2(&mut stack, &moves)?);
Ok(())
}
#[cfg(test)]
mod tests {
// as before
#[test]
fn check_part2() -> anyhow::Result<()> {
let (mut stack, moves) = parse(INPUT)?;
assert_eq!("MCD", part2(&mut stack, &moves)?);
Ok(())
}
}
Otherwise the same rules apply, the stacks are re-arranged by the list of moves. The idea here is to take crates from source to target stack without changing their order. One way to handle the removal of crates is to call remove a number of times, alternatively there is the drain method that takes a Range parameter to remove number of elements and returns them as a new Vec. For now we take a similar approach as in the first part by using remove & insert. The difference is the index elements are removed from.
impl SupplyStack {
pub fn multi_move(&mut self, mv: &Move) -> anyhow::Result<()> {
for index in (0..mv.num_crates as usize).rev() {
if self.stacks[mv.from - 1].len() < index {
return Err(anyhow!("Stack is smaller than the given index to remove from."));
}
let c = self.stacks[mv.from - 1].remove(index);
self.stacks[mv.to - 1].insert(0, c);
}
Ok(())
}
}
The expected outcome for the given sample input now is MCD. The test passes, but running the program via cargo run panics now. The panic message is:
thread 'main' panicked at 'removal index (is 6) should be < len (is 1)', src/main.rs:46:46
The observant reader may have spotted the problem already. When the function part2 is called with the stack variable what it receives is not the original state after parsing the input text, but rather the modified state after running part1. The variable stack has been modified inside part1 due to the &mut annotation. Applying moves has modified the given variable.
Therefore it's necessary to pass in the original state. One solution to solve this is to derive Clone on the SupplyStack struct and call clone on the stack variable before passing it to the part1 function.
#[derive(Debug, Clone)] // <- Clone added
pub struct SupplyStack {
pub stacks: Vec<Vec<char>>,
}
The Clone derive works fine here, because its member stacks also can be cloned. The function parameters for part1 & part2 can be adjusted as well to take ownership of the passed SupplyStack. Then the compiler will complain when we try to pass in the same variable twice. The main function then looks like:
fn part1(mut stack: SupplyStack, moves: &[Move]) -> anyhow::Result<String> { .. }
fn part2(mut stack: SupplyStack, moves: &[Move]) -> anyhow::Result<String> { .. }
fn main() -> anyhow::Result<()> {
let (stack, moves) = parse(include_str!("input.txt"))?;
println!("Part 1: {}", part1(stack.clone(), &moves)?);
println!("Part 2: {}", part2(stack, &moves)?);
}
#[cfg(test)]
// [..]
#[test]
fn check_part1() -> anyhow::Result<()> {
let (stack, moves) = parse(INPUT)?;
assert_eq!("CMZ", part1(stack, &moves)?);
Ok(())
}
#[test]
fn check_part2() -> anyhow::Result<()> {
let (stack, moves) = parse(INPUT)?;
assert_eq!("MCD", part2(stack, &moves)?);
Ok(())
}
}
Once the test has been adjusted as well to pass in the stack variable, all tests pass.
Running the program now should return the second solution.