Ruby/Crystal/Rust Advent of Code 2022 - Day 5
Kirk HainesTable of contents
Day 5's challenge was interesting less for the challenge itself, which can be implemented in a handful of lines, even in Rust, but rather for the mandatory precursor to all Advent of Code challenges -- the input data parsing. Today's input data is more complex to parse, and that parsing is where almost all of the work in the following solutions will be found.
The Repository
All of the code for this day's solutions, as well as the data input file, can be found at:
https://github.com/wyhaines/advent-of-code-2022/tree/main/day_5
Part 1
To see the full details of the challenge, visit the Advent of Code 2022 - Day 5 page. However, the tl;dr version of the challenge is as follows:
In this problem, there are several stacks of crates that need to be rearranged according to a series of steps specified in the puzzle input. The crates are moved one at a time, and the order in which they are moved will affect the final arrangement of the crates. The Elves have a drawing of the starting stacks of crates and the rearrangement procedure, but they forgot to ask the crane operator which crate will end up on top of each stack. They need to determine this information from the puzzle input so they can unload the crates and embark on their expedition as soon as possible.
Here is an example of the rearrangement procedure:
There are three stacks of crates, numbered 1, 2, and 3. Stack 1 contains two crates: crate Z is on the bottom, and crate N is on top. Stack 2 contains three crates, from bottom to top: crates M, C, and D. Finally, stack 3 contains a single crate, P.
The rearrangement procedure consists of four steps:
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
After the rearrangement procedure is completed, the top crate on stack 1 is C, the top crate on stack 2 is M, and the top crate on stack 3 is Z. The Elves need to determine the top crates on each stack and combine them to give the message "CMZ".
So, the task is to take a set of input that may look 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
And simulate the execution of all of those move instructions, where the movement of more than one crate is done a crate at a time, to determine which are the top crates on all of the stacks after everything has been moved.
The Approach
Read the input data, splitting it into two parts, a stack string and an instructions string.
For the stack string, determine the number of stacks, and create a data structure that encodes the contents of each stack. This is probably an array of arrays.
For the instructions string, parse it to create an array or instructions. The instructions could be encoded simply as a triplet of numbers, or as something more descriptive.
Follow the instructions, executing the move instructions.
Find the top crate of each stack, and compile them into a single string that is printed, showing the list of the top crates that the Elves want.
Ruby solution
# frozen_string_literal: true
class SupplyStacks
attr_accessor :stacks, :instructions
def initialize(filename)
@instructions = []
parse_stacks(filename)
end
def run
follow_instructions
puts 'The final layout of the stacks:'
pp stacks.reject(&:empty?)
puts "\nThe crates on top of the stacks are: #{stacks.reject(&:empty?).map(&:last).join}"
end
def parse_stacks(filename)
stack_spec, instructions_spec = File.read(filename).split("\n\n", 2).map do |lines|
lines.split("\n")
end
stack_count = stack_spec.last.split(/\s+/).size
@stacks = Array.new(stack_count + 1) { [] }
stack_spec.reverse[1..].each do |crate_line|
crates = crate_line.scan(/...\s?/)
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
end
end
instructions_spec.each do |line|
instructions << line.scan(/\d+/).map(&:to_i)
end
end
def follow_instructions
instructions.each do |instruction|
count, from, to = instruction
count.times { stacks[to].push stacks[from].pop }
end
end
end
SupplyStacks.new(ARGV[0] || 'input.txt').run
The Ruby solution will be the least interesting one for Day 5. Ruby is very good at text processing, and once the text processing is done, following the instructions is a trivial handful of lines. This solution creates accessors for :stacks and :instructions, which are instance variables and associated accessor methods for accessing them, for storing the stacks and the instructions within the SupplyStacks object instance. These will be used in all of the other methods in the solution, including both the data parsing and the finding of the solution.
def parse_stacks(filename)
stack_spec, instructions_spec = File.read(filename).split("\n\n", 2).map do |lines|
lines.split("\n")
end
stack_count = stack_spec.last.split(/\s+/).size
@stacks = Array.new(stack_count) { [] }
stack_spec.reverse[1..].each do |crate_line|
crates = crate_line.scan(/...\s?/)
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
end
end
The data file has two sections, the section that describes the starting contents of the stacks of crates, and the section that has all of the crate movement instructions. Separating the section is a blank line. i.e. two newlines. The first thing that the code does after reading the file contents as a string is to split on \n\n, and then feed that two-element array through a map call, splitting each chunk by \n. These two elements are assigned to stack_spec and instructions_spec as they represent the specifications for the stack and the instructions.
To get the number of stacks, there are two approaches. The last line of the stack_spec is a list of the numeric labels of each of the stacks:
1 2 3 4 5 6 7 8 9
One would be to just find the last set of digits in the line and parse that to an integer. This could be done in a couple of ways:
stack_count = stack_spec.last.match(/(\d+)\s*$/)[1].to_i
or
stack_count = stack_spec.last[-3..].to_i
The first uses a regular expression to find the last set of digits in the line, capturing that set of digits, and casting it to an integer.
Since we know that there are a limited number of stacks, and they are surrounded by ample whitespace, the second option, to just grab the last few characters, and interpret it as an integer, is a much simpler solution. This works because Ruby discards whitespace characters when casting a string to a number.
A third option would be to split the line on the whitespace, and count the length of the resulting array:
stack_count = stack_spec.last.split(/\s+/).size
1 2 3 4 5 6 7 8 9
In Ruby, the split will result in the following array:
["", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
That has a size of 10, and as it turns out, that is what I truly want. Take a look at the line that follows this one.
@stacks = Array.new(stack_count) { [] }
This creates an array with stack_count elements, where each element is set to the return value of the block. i.e. with the prior line establishing a stack_count of 10, it creates an array like this:
[[], [], [], [], [], [], [], [], [], []]
The crate movement instructions use a numbering system that starts with 1. Ruby arrays are indexed from 0. Later, when the instructions are being followed, it would be simple to just subtract one from each of the indexes, but it seems even simpler to not worry about that and to just create an extra array element at position 0 which will not be used.
The last part of parsing the stack specification is to read the actual contents of each of the stacks.
stack_spec[..-2].reverse_each do |crate_line|
crates = crate_line.scan(/...\s?/)
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
end
end
stack_spec[..-2] returns all of the lines in the stack specification, except for the last one, and then reverse_each iterates through each of those lines, from the last to the first.
For each iteration, scan is used to break the line into an array of 4 character chunks, except for the last element, which will have 3 characters. This array is then iterated through with the index, and the alphabetic content of each, which is always in position [1] of the chunk, is inserted into index + 1.
The hard work is about done. The last step is to create a list of crate movement instructions from the instructions_spec.
instructions_spec.each do |line|
instructions << line.scan(/\d+/).map(&:to_i)
end
This just uses scan to extract the digits from the movement instruction into an array, followed by map(&:to_i) to cast the strings into integers.
With all of the input data parsed, the next stop is to execute the movement instructions.
def follow_instructions
instructions.each do |instruction|
count, from, to = instruction
count.times { stacks[to].push stacks[from].pop }
end
end
This is a simple loop that iterates through each of the instructions. An instruction is composed of a three-element array containing the number of crates to move, the stack to move them from, and the stack to move them to. Those values are assigned to variables, and then an inner loop executes count times, popping a value off of the array representing the from stack, and pushing it onto the array representing the to stack.
And with that, the Ruby solution is nearly complete. The only major task that remains is parsing through the crates and compiling a list of the top crates in each stack.
puts "\nThe crates on top of the stacks are: #{stacks.reject(&:empty?).map(&:last).join}"
Reject any empty stacks (which will be that first, index 0 stack), then iterate through the remainder using map, querying the last element in each stack, and joining them all into a single string. Et voila! We have a Ruby solution!
Crystal solution
class SupplyStacks
property instructions = [] of Tuple(Int32, Int32, Int32)
property stacks = [] of Array(Char)
def initialize(filename)
parse_stacks(filename)
end
def run
follow_instructions
puts "The final layout of the stacks:"
pp stacks.reject(&.empty?)
puts "\nThe crates on top of the stacks are: #{stacks.reject(&.empty?).map(&.last).join}"
end
def parse_stacks(filename)
stack_spec, instructions_spec = File.read(filename).split("\n\n", 2).map do |lines|
lines.split("\n")
end
stack_spec.last.rstrip.split(/\s+/).size.times { stacks << [] of Char }
stack_spec[..-2].reverse_each do |crate_line|
crates = crate_line.scan(/...\s?/).map(&.[0])
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].letter?
end
end
instructions_spec.each do |line|
next if line.empty?
count, from, to = line.scan(/\d+/).map(&.[0].to_i)
instructions << {count, from, to}
end
end
def follow_instructions
instructions.each do |instruction|
count, from, to = instruction
count.times { stacks[to].push stacks[from].pop }
end
end
end
SupplyStacks.new(ARGV[0]? || "input.txt").run
This is the first day where the Crystal version has some truly interesting differences from the Ruby version. If you are skimming the Crystal version with a Ruby eye, it will mostly seem familiar, but some differences are worth discussing. To see what they are succinctly, here's a diff between the two versions.
@@ -1,21 +1,18 @@
-# frozen_string_literal: true
-
class SupplyStacks
- attr_accessor :stacks, :instructions
+ property instructions = [] of Tuple(Int32, Int32, Int32)
+ property stacks = [] of Array(Char)
def initialize(filename)
- @instructions = []
-
parse_stacks(filename)
end
def run
follow_instructions
- puts 'The final layout of the stacks:'
- pp stacks.reject(&:empty?)
+ puts "The final layout of the stacks:"
+ pp stacks.reject(&.empty?)
- puts "\nThe crates on top of the stacks are: #{stacks.reject(&:empty?).map(&:last).join}"
+ puts "\nThe crates on top of the stacks are: #{stacks.reject(&.empty?).map(&.last).join}"
end
def parse_stacks(filename)
@@ -23,18 +20,19 @@
lines.split("\n")
end
- stack_count = stack_spec.last.split(/\s+/).size
- @stacks = Array.new(stack_count) { [] }
-
+ stack_spec.last.rstrip.split(/\s+/).size.times { stacks << [] of Char }
+
stack_spec[..-2].reverse_each do |crate_line|
- crates = crate_line.scan(/...\s?/)
+ crates = crate_line.scan(/...\s?/).map(&.[0])
crates.each_with_index do |crate, idx|
- stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
+ stacks[idx + 1] << crate[1] if crate[1].letter?
end
end
instructions_spec.each do |line|
- instructions << line.scan(/\d+/).map(&:to_i)
+ next if line.empty?
+ count, from, to = line.scan(/\d+/).map(&.[0].to_i)
+ instructions << {count, from, to}
end
end
@@ -46,4 +44,4 @@
end
end
-SupplyStacks.new(ARGV[0] || 'input.txt').run
+SupplyStacks.new(ARGV[0]? || "input.txt").run
It has not been brought up in the previous writeups, but the first difference involves the magic comment that appears at the top of the Ruby files:
-# frozen_string_literal: true
-
This magic comment, which was introduced in Ruby 2.3, causes all string literals to be frozen. This is intended to be a performance-enhancing change, as frozen string literals, which is another way of saying immutable strings, allow the interpreter to treat those strings more like constants, allowing for a variety of optimizations both to method calls on the strings and to their impact on garbage collection.
In Crystal, unlike Ruby, all String instances are immutable.
Moving on, the next notable differences are found in the initial class definition and in the initialize method.
class SupplyStacks
- attr_accessor :stacks, :instructions
+ property instructions = [] of Tuple(Int32, Int32, Int32)
+ property stacks = [] of Array(Char)
def initialize(filename)
- @instructions = []
-
parse_stacks(filename)
end
In Ruby, instance variables can be created at any point within a class's code. However, in Crystal, instance variables have to be treated with a little more discipline, and the syntax for creating accessors is different.
Ruby has attr_reader, attr_writer, and attr_accessor methods, as well as an attr method, all defined on Module, which are all helpers to eliminate the boilerplate work of creating methods for accessing or changing the value of an instance variable. These methods take symbol inputs.
In Crystal, this capability works differently. Crystal doesn't do dynamic programming like Ruby does, as it is a static, compiled language. It uses something called macros. This lets Crystal's helper behave more like syntax. Like Ruby, Crystal has three main versions, getter, setter, and property. Unlike Ruby, they don't take symbols as arguments, and they define a single instance variable and helper method/method-set with each invocation.
Those property declarations do two things. They create instances variables, @instructions and @stacks, and it assigns a default value to each.
Crystal instance variables can be declared in the class body, within the initialize method definition, or within the method body. They must be initialized with a value, however.
class Foo
@a = "abc"
@b : Int32
def initialize(@c : String)
@d = [1, 2, 3]
end
end
This will return an error when compiled:
In foo.cr:3:3
3 | @b : Int32
^-
Error: instance variable '@b' of Foo was not initialized directly in all of the 'initialize' methods, rendering it nilable. Indirect initialization is not supported.
This error can be fixed by either declaring a value for @b: @b = 123, or by making @b nillable: @b : Int32 | Nil, or, more idiomatically, @b : Int32?.
The other significant set of differences between Crystal and Ruby comes in the code that parses the input text.
- stack_count = stack_spec.last.split(/\s+/).size
- @stacks = Array.new(stack_count) { [] }
-
+ stack_spec.last.rstrip.split(/\s+/).size.times { stacks << [] of Char }
+
stack_spec[..-2].reverse_each do |crate_line|
- crates = crate_line.scan(/...\s?/)
+ crates = crate_line.scan(/...\s?/).map(&.[0])
crates.each_with_index do |crate, idx|
- stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
+ stacks[idx + 1] << crate[1] if crate[1].letter?
end
end
instructions_spec.each do |line|
- instructions << line.scan(/\d+/).map(&:to_i)
+ next if line.empty?
+ count, from, to = line.scan(/\d+/).map(&.[0].to_i)
+ instructions << {count, from, to}
There is a difference in behavior between how split works in Ruby versus in Crystal. Consider this code:
a = " 1 2 3 4 5 6 7 8 9 "
pp a.split(/\s+/)
In Ruby, it returns:
["", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
In Crystal, though, it returns:
["", "1", "2", "3", "4", "5", "6", "7", "8", "9", ""]
While, given how the rest of the code is written, it doesn't hurt anything to have an extra stack, it feels better to have consistent behavior. This requires stripping the whitespace from the tail of the string before splitting it.
stack_spec.last.rstrip.split(/\s+/)
The second difference involves the array seeding code. Recall that in Ruby, this was done: @stacks = Array.new(stack_count) { [] }. This is because instance variables in Ruby can be declared anywhere. With our Crystal solution, however, the instance variable was initialized with an empty array at object creation. Thus, by this point in the code it already exists. It would be possible to overwrite it with a new instance variable:
stack_count = stack_spec.last.rstrip.split(/\s+/).size
@stacks = Array(Array(Char)).new(stack_count) { [] of Char }
This does indeed look a lot more like the Ruby code, but it is wasteful. It discards the original array to create a new array, and it ends up being a little longer, in addition. The better solution is to populate the original array with the internal stack arrays.
stack_spec.last.rstrip.split(/\s+/).size.times { stacks << [] of Char }
The final set of differences with the Crystal version are below:
stack_spec[..-2].reverse_each do |crate_line|
- crates = crate_line.scan(/...\s?/)
+ crates = crate_line.scan(/...\s?/).map(&.[0])
crates.each_with_index do |crate, idx|
- stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
+ stacks[idx + 1] << crate[1] if crate[1].letter?
end
end
instructions_spec.each do |line|
- instructions << line.scan(/\d+/).map(&:to_i)
+ next if line.empty?
+ count, from, to = line.scan(/\d+/).map(&.[0].to_i)
+ instructions << {count, from, to}
In Ruby, scan returns an array of the matches. So on a line like:
[R] [J] [S] [Z] [R] [S] [D] [L] [J]
Ruby returns:
["[R] ", "[J] ", "[S] ", "[Z] ", "[R] ", "[S] ", "[D] ", "[L] ", "[J]"]
Crystal, however, returns a more sophisticated response:
[Regex::MatchData("[R] "), Regex::MatchData("[J] "), Regex::MatchData("[S] "), Regex::MatchData("[Z] "), Regex::MatchData("[R] "), Regex::MatchData("[S] "), Regex::MatchData("[D] "), Regex::MatchData("[L] "), Regex::MatchData("[J]")]
Each of the matches is contained in a Regex::MatchData object. Thus, to access the string of the match, one must reference the capture group via an array-index-like operation, match[0].
Thus, collecting a list of all of the crates and empty spaces becomes:
crates = crate_line.scan(/...\s?/).map(&.[0])
Following this, in the portion of the code that checks to see if there is a crate or an empty space, the Ruby code uses a regular expression to see if there is a word character in that position.
The Crystal code, however, can just call Char#letter? on the character to determine if it is a letter or not.
Finally, in the code that is parsing the instructions, there is this difference:
- instructions << line.scan(/\d+/).map(&:to_i)
+ next if line.empty?
+ count, from, to = line.scan(/\d+/).map(&.[0].to_i)
+ instructions << {count, from, to}
The Crystal code specifically skips to the next line if the current one is empty, as Crystal will throw an error if the map(&.[0].to_i) method is called on an empty line. The scan line has the same change as was just mentioned, to deal with receiving an array of MatchData objects. The final line there, which adds the count, from, and to values to the instructions array, however, is doing something different from Ruby.
In Crystal, arrays are typically allocated on the Heap, which is a section of memory used for the dynamic allocation of variables. However, Crystal also has a data structure called a Tuple that is similar to an Array, but it is allocated on the Stack instead of the Heap. A Tuple can be thought of as an immutable Array, but it has some key differences. They are faster to allocate, faster to deallocate and live outside of garbage collection so their entire life cycle has less impact on application performance than Arrays. All of these characteristics make them ideal for a use case like this, where instructions is intended to hold an immutable, read-only set of data.
In the end, the Crystal code still hews closely to the Ruby code, but there are some differences today that really show how Crystal is a different, unique language from Ruby.
Rust solution
Rust, bless your soul, you are always the more challenging implementation.
use std::env;
struct Instruction {
count: usize,
from: usize,
to: usize,
}
struct SupplyStacks {
stacks: Vec<Vec<char>>,
instructions: Vec<Instruction>,
}
impl SupplyStacks {
fn new(filename: &str) -> SupplyStacks {
let (stacks, instructions) = Self::parse_stacks(filename).unwrap();
SupplyStacks {
stacks: stacks,
instructions: instructions,
}
}
fn run(&mut self) {
self.follow_instructions();
println!("{:#?}", self.stacks);
println!("{}", self.skim_top_crates());
}
fn parse_stacks(filename: &str) -> Option<(Vec<Vec<char>>, Vec<Instruction>)> {
let text = std::fs::read_to_string(filename).ok()?;
let (stack_spec_str, instructions_spec_str) = text.split_once("\n\n")?;
let (stack_spec_str, stack_labels) = stack_spec_str.rsplit_once("\n")?;
let stack_spec = stack_spec_str.lines();
let instructions_spec = instructions_spec_str.lines();
let stack_count = stack_labels.split_whitespace().count();
let mut stacks = vec![Vec::<char>::new(); stack_count + 1];
for line in stack_spec.rev() {
for (idx, payload) in line
.chars()
.collect::<Vec<_>>()
.chunks(4)
.enumerate()
{
let cr8 = payload[1];
if cr8.is_alphabetic() {
stacks[idx + 1].push(cr8);
}
}
}
// To use a Regular Expression here seems attractive, but it ends up being
// more work than it is worth. In addition to needing a Cargo.toml, and having
// to deal with crate dependencies in order to get access to the Regex crate,
// the code ends up being no cleaner, and no shorter, between the `use regex::Regex;`
// line at the beginning of the file to the syntax for declaring, using, and accessing
// the regular expression and its matches:
// let re = Regex::new(r"move (\d+) from (\w+) to (\w+)").unwrap();
//
// let mut instructions = Vec::<Instruction>::new();
// for line in instructions_spec {
// if let Some(captures) = re.captures(line) {
// let instruction = Instruction {
// count: captures[1].parse().ok()?,
// from: captures[2].parse().ok()?,
// to: captures[3].parse().ok()?,
// };
// instructions.push(instruction);
// }
// }
let mut instructions = Vec::<Instruction>::new();
for line in instructions_spec {
let core_information = line.strip_prefix("move ")?;
let (count, destination_information) = core_information.split_once(" from ")?;
let (from, to) = destination_information.split_once(" to ")?;
instructions.push(Instruction {
count: count.parse().ok()?,
from: from.parse().ok()?,
to: to.parse().ok()?,
});
}
Some((stacks, instructions))
}
fn follow_instructions(&mut self) {
for instruction in &self.instructions {
for _ in 0..instruction.count {
let item = self.stacks[instruction.from].pop().unwrap();
self.stacks[instruction.to].push(item);
}
}
}
fn skim_top_crates(&self) -> String {
self.stacks
.iter()
.filter(|stack| !stack.is_empty())
.map(|stack| *stack.last().unwrap())
.collect()
}
}
fn main() {
let args: Vec<String> = env::args().collect();
let mut filename = "input.txt";
if let Some(arg) = args.get(1) {
filename = arg;
}
SupplyStacks::new(filename).run();
}
The Rust version follows the same general outline as the two other languages, but as is often the case with Rust, it takes a little more work to get there.
Right off the top, you will notice that the Rust version uses two struct declarations for the data structures that it needs.
struct Instruction {
count: usize,
from: usize,
to: usize,
}
struct SupplyStacks {
stacks: Vec<Vec<char>>,
instructions: Vec<Instruction>,
}
These structures will be used to help organize the data storage in the code and make everything easier to work with and reason about.
The new() and the run() methods are clear and unsurprising in how they are structured, but just like with the Crystal and the Ruby solutions, the bulk of the work for this solution is found in the method that parses the puzzle input, parse_stacks().
fn parse_stacks(filename: &str) -> Option<(Vec<Vec<char>>, Vec<Instruction>)> {
let text = std::fs::read_to_string(filename).ok()?;
let (stack_spec_str, instructions_spec_str) = text.split_once("\n\n")?;
let (stack_spec_str, stack_labels) = stack_spec_str.rsplit_once("\n")?;
let stack_spec = stack_spec_str.lines();
let instructions_spec = instructions_spec_str.lines();
let stack_count = stack_labels.split_whitespace().count();
let mut stacks = vec![Vec::<char>::new(); stack_count + 1];
for line in stack_spec.rev() {
for (idx, payload) in line
.chars()
.collect::<Vec<_>>()
.chunks(4)
.enumerate()
{
let cr8 = payload[1];
if cr8.is_alphabetic() {
stacks[idx + 1].push(cr8);
}
}
}
let mut instructions = Vec::<Instruction>::new();
for line in instructions_spec {
let core_information = line.strip_prefix("move ")?;
let (count, destination_information) = core_information.split_once(" from ")?;
let (from, to) = destination_information.split_once(" to ")?;
instructions.push(Instruction {
count: count.parse().ok()?,
from: from.parse().ok()?,
to: to.parse().ok()?,
});
}
Some((stacks, instructions))
}
Rust doesn't have regular expression support in the core of the language; to use regular expressions, one must utilize a crate. The first thing that you probably notice, if you looked at either of the two previous versions before coming to this one, is that this solution is not utilizing regular expressions, while the previous two heavily utilized them. The reason for this is purely because, for this task, it was more trouble than it was worth. As will be illustrated below, using Rust regular expressions saves neither lines nor complexity for this puzzle.
The first part of the parsing, which splits the stack information from the instruction information, and which determines the number of stacks, works in effectively the same way as the other two languages' versions, and culminates with:
let stack_count = stack_labels.split_whitespace().count();
to capture the number of stacks, so that the correct number of Vec instances can be created to represent them:
let mut stacks = vec![Vec::<char>::new(); stack_count + 1];
The parsing of the contents of the stacks is a simple loop.
for line in stack_spec.rev() {
for (idx, payload) in line
.chars()
.collect::<Vec<_>>()
.chunks(4)
.enumerate()
{
let cr8 = payload[1];
if cr8.is_alphabetic() {
stacks[idx + 1].push(cr8);
}
}
}
It takes the lines of the stack spec, as read from the file, reverses them, and then iterates through each line.
Each line, in turn, is broken into an iterator over the individual characters with chars(), collected into a Vec, and then broken into chunks of 4 characters. The resulting iterator over the chunks then has enumerate() called on it, which returns an iterator that yields both the numerical index for each element and the element itself.
That iterator is then iterated. The element, which is called payload, has the character at position 1 assigned to a variable cr8 (crate is a keyword in Rust). That is then checked to see if it is an alphabetic character, signifying that it is a crate and is not blank. It is then inserted into the corresponding vec of crates.
After that is finished, the parsing work that remains is the parsing of the instructions.
let mut instructions = Vec::<Instruction>::new();
for line in instructions_spec {
let core_information = line.strip_prefix("move ")?;
let (count, destination_information) = core_information.split_once(" from ")?;
let (from, to) = destination_information.split_once(" to ")?;
instructions.push(Instruction {
count: count.parse().ok()?,
from: from.parse().ok()?,
to: to.parse().ok()?,
});
}
In Ruby, this was very concise:
instructions_spec.each do |line|
instructions << line.scan(/\d+/).map(&:to_i)
end
And it was also pretty concise in Crystal:
instructions_spec.each do |line|
next if line.empty?
count, from, to = line.scan(/\d+/).map(&.[0].to_i)
instructions << {count, from, to}
end
Rust, however, makes us work for it.
For each instruction line, there is a series of steps necessary to extract information from each line.
First, strip the boilerplate text off the front of the line.
let core_information = line.strip_prefix("move ")?;
Then extract the from value from what remains, and assign what is left to destination_information.
let (count, destination_information) = core_information.split_once(" from ")?;
Then split on the remaining text in the line, capturing the to and the from values.
let (from, to) = destination_information.split_once(" to ")?;
Finally, push an instance of the Instruction struct into the instructions vec.
instructions.push(Instruction {
count: count.parse().ok()?,
from: from.parse().ok()?,
to: to.parse().ok()?,
});
You may be wondering if this would, in fact, be cleaner or easier with regular expressions:
use regex::Regex
/// In the body of parse_stacks()
let re = Regex::new(r"move (\d+) from (\w+) to (\w+)").unwrap();
for line in instructions_spec {
if let Some(captures) = re.captures(line) {
let instruction = Instruction {
count: captures[1].parse().ok()?,
from: captures[2].parse().ok()?,
to: captures[3].parse().ok()?,
};
instructions.push(instruction);
}
}
In addition to the above, this also then requires a Cargo.toml, with a [dependencies] section. The code itself IS easier to read and to reason about, but only very modestly so, it isn't any less typing, and though it hardly matters for this AoC example, there is more overhead in execution. However, the main implementation for the regexp solution is included in the code repo, commented out, so if you want to play with it, you can.
The actual execution of the instructions is as straight forward with Rust as it was with Ruby/Crystal:
fn follow_instructions(&mut self) {
for instruction in &self.instructions {
for _ in 0..instruction.count {
let item = self.stacks[instruction.from].pop().unwrap();
self.stacks[instruction.to].push(item);
}
}
}
It simply iterates over the instructions, accessing the number of crates to move as instruction.count, and then looping that many times, popping the value off of the from stack and pushing the value onto the to stack.
The last bit of Rust code that might be of interest here is in the method that creates the string representing the top crates on the stacks.
fn skim_top_crates(&self) -> String {
self.stacks
.iter()
.filter(|stack| !stack.is_empty())
.map(|stack| *stack.last().unwrap())
.collect()
}
In all of the past examples, collect() has been used on iterators to return a vec. However, the reality is that collect() is agnostic about the type of collection that it returns, which means that it can return a String! Handy!
Part 2
Oh no! The simulation was written to the behavior of the wrong CraneMover, all because of some mud!
As you watch the crane operator expertly rearrange the crates, you notice the process isn't following your prediction. Some mud was covering the writing on the side of the crane, and you quickly wipe it away. The crane isn't a CrateMover 9000 - it's a CrateMover 9001. The CrateMover 9001 is notable for many new and exciting features: air conditioning, leather seats, an extra cup holder, and the ability to pick up and move multiple crates at once.
Given these crates and this instruction:
[D] [N] [C] [Z] [M] [P] 1 2 3
move 3 from 1 to 3The end result should be:
[D] [N] [C] [Z] [M] [P] 1 2 3The crates were all moved with their order intact from stack 1 to stack 3. The simulation should be updated with this information so the Elves know where to stand to be ready to unload the final supplies.
The only change here is that instead of moving the crates one at a time, they should all be moved in a single operation, now.
The Approach
- Nothing needs to change except for the
follow_instructionsmethods in each solution. It should move all of the elements from one stack to another while preserving their order, as they are all moved at once.
Ruby solution
# frozen_string_literal: true
class SupplyStacks
attr_accessor :stacks, :instructions
def initialize(filename)
@instructions = []
parse_stacks(filename)
end
def run
follow_instructions
puts 'The final layout of the stacks:'
pp stacks.reject(&:empty?)
puts "\nThe crates on top of the stacks are: #{stacks.reject(&:empty?).map(&:last).join}"
end
def parse_stacks(filename)
stack_spec, instructions_spec = File.read(filename).split("\n\n", 2).map do |lines|
lines.split("\n")
end
stack_count = stack_spec.last.split(/\s+/).size
@stacks = Array.new(stack_count) { [] }
stack_spec[..-2].reverse_each do |crate_line|
crates = crate_line.scan(/...\s?/)
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].match?(/\w/)
end
end
instructions_spec.each do |line|
instructions << line.scan(/\d+/).map(&:to_i)
end
end
def follow_instructions
instructions.each do |instruction|
count, from, to = instruction
stacks[to].concat stacks[from].slice!(-count..)
end
end
end
SupplyStacks.new(ARGV[0] || 'input.txt').run
The only change from the Part 1 solution is in follow_instructions:
- count.times { stacks[to].push stacks[from].pop }
+ stacks[to].concat stacks[from].slice!(-count..)
The array elements are removed from the from array via slice!, and are added to the to array via concat.
Crystal solution
class SupplyStacks
property instructions = [] of Tuple(Int32, Int32, Int32)
property stacks = [] of Array(Char)
def initialize(filename)
parse_stacks(filename)
end
def run
follow_instructions
puts "The final layout of the stacks:"
pp stacks.reject(&.empty?)
puts "\nThe crates on top of the stacks are: #{stacks.reject(&.empty?).map(&.last).join}"
end
def parse_stacks(filename)
stack_spec, instructions_spec = File.read(filename).split("\n\n", 2).map do |lines|
lines.split("\n")
end
stack_spec.last.rstrip.split(/\s+/).size.times { stacks << [] of Char }
stack_spec[..-2].reverse_each do |crate_line|
crates = crate_line.scan(/...\s?/).map(&.[0])
crates.each_with_index do |crate, idx|
stacks[idx + 1] << crate[1] if crate[1].letter?
end
end
instructions_spec.each do |line|
next if line.empty?
count, from, to = line.scan(/\d+/).map(&.[0].to_i)
instructions << {count, from, to}
end
end
def follow_instructions
instructions.each do |instruction|
count, from, to = instruction
stacks[to].concat stacks[from].delete_at(-count..)
end
end
end
SupplyStacks.new(ARGV[0]? || "input.txt").run
Like the Ruby solution, the change here is just in one line:
- count.times { stacks[to].push stacks[from].pop }
+ stacks[to].concat stacks[from].delete_at(-count..)
This is almost the same as the Ruby change. However, in Crystal, delete_at is used instead of slice!.
Rust solution
use std::env;
struct Instruction {
count: usize,
from: usize,
to: usize,
}
struct SupplyStacks {
stacks: Vec<Vec<char>>,
instructions: Vec<Instruction>,
}
impl SupplyStacks {
fn new(filename: &str) -> SupplyStacks {
let (stacks, instructions) = Self::parse_stacks(filename).unwrap();
SupplyStacks {
stacks: stacks,
instructions: instructions,
}
}
fn run(&mut self) {
self.follow_instructions();
println!("{:#?}", self.stacks);
println!("{}", self.skim_top_crates());
}
fn parse_stacks(filename: &str) -> Option<(Vec<Vec<char>>, Vec<Instruction>)> {
let text = std::fs::read_to_string(filename).ok()?;
let (stack_spec_str, instructions_spec_str) = text.split_once("\n\n")?;
let (stack_spec_str, stack_labels) = stack_spec_str.rsplit_once("\n")?;
let stack_spec = stack_spec_str.lines();
let instructions_spec = instructions_spec_str.lines();
let stack_count = stack_labels.split_whitespace().count();
let mut stacks = vec![Vec::<char>::new(); stack_count + 1];
for line in stack_spec.rev() {
for (idx, payload) in line.chars().collect::<Vec<_>>().chunks(4).enumerate() {
let cr8 = payload[1];
if cr8.is_alphabetic() {
stacks[idx + 1].push(cr8);
}
}
}
let mut instructions = Vec::<Instruction>::new();
for line in instructions_spec {
let core_information = line.strip_prefix("move ")?;
let (count, destination_information) = core_information.split_once(" from ")?;
let (from, to) = destination_information.split_once(" to ")?;
instructions.push(Instruction {
count: count.parse().ok()?,
from: from.parse().ok()?,
to: to.parse().ok()?,
});
}
Some((stacks, instructions))
}
fn follow_instructions(&mut self) {
for instruction in &self.instructions {
let from_stack_size = self.stacks[instruction.from].len();
let items = self.stacks[instruction.from]
.split_off(from_stack_size - instruction.count);
self.stacks[instruction.to].extend(items);
}
}
fn skim_top_crates(&self) -> String {
self.stacks
.iter()
.filter(|stack| !stack.is_empty())
.map(|stack| *stack.last().unwrap())
.collect()
}
}
fn main() {
let args: Vec<String> = env::args().collect();
let mut filename = "input.txt";
if let Some(arg) = args.get(1) {
filename = arg;
}
SupplyStacks::new(filename).run();
}
Like the previous two Part 2 solutions, Rust's Part 2 changes are confined to just the follow_instructions() method:
fn follow_instructions(&mut self) {
for instruction in &self.instructions {
- for _ in 0..instruction.count {
- let item = self.stacks[instruction.from].pop().unwrap();
- self.stacks[instruction.to].push(item);
- }
+ let from_stack_size = self.stacks[instruction.from].len();
+ let items = self.stacks[instruction.from]
+ .split_off(from_stack_size - instruction.count);
+ self.stacks[instruction.to].extend(items);
}
}
This determines how many elements are in the stack, and then, armed with that information, splits the stack into two pieces. items contains the instruction.count elements that were split from the original stack, while the original stack retains any remaining elements.
The items vec is then added to the to stack via extend.
One might be tempted to eliminate the temporary variable for the from_stack_size, and write the line that extracts items something like this:
let items = self.stacks[instruction.from].split_off(self.stacks[instruction.from].len() - instruction.count);
This will fail, however.
error[E0502]: cannot borrow `self.stacks` as immutable because it is also borrowed as mutable
--> day_5_2.rs:70:65
|
70 | let items = self.stacks[instruction.from].split_off(self.stacks[instruction.from].len() - instruction.count);
| ----------- --------- ^^^^^^^^^^^ immutable borrow occurs here
| | |
| | mutable borrow later used by call
| mutable borrow occurs here
error: aborting due to previous error
Inserting the result of len() into a temporary variable solves this problem very simply.
Conclusion
Day 5 was a simple task to solve, once the input data was read and parsed into usable, friendly data structures. That parsing, however, took a bit of work, particularly in Rust, to accomplish. Rust is remarkably expressive for a language intended for systems programming, but for tasks like text processing, it does take a lot more work to implement a given solution in Rust than in Ruby. Of course, a Rust solution, once it finally works, will execute faster than the Ruby solution.
Crystal sits in an interesting position for these sorts of tasks. The implementation for text processing will generally be similar to Ruby's, but in execution speed, Crystal implementations will be much faster, than Ruby's, as well. Maybe in a future AoC day, we will be able to more clearly see the speed differences that these languages bring to the table? Stay tuned....
Subscribe to my newsletter
Read articles from Kirk Haines directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by