Introduction
As part of my ongoing effort to learn Rust, I thought it would be interesting to not just revisit problems I've solved in Clojure (see Day 1 in Rust), but also try to solve problems I haven't figured out.
I think the Intcode computer will live on in Clojure as I have no great desire to revisit it in Rust, but Day 6 is standalone (for now), so I dived right in.
Day 6.1
Types sure are a thing, huh...?
Rust takes some getting used to once you get into more complicated challenges. The type system is relatively intuitive, but puzzling your way through return values is another matter altogether. I struggled with Options returned from HashMaps for a while, making this more complicated than it needed to be, but I guess that's the point of doing something in a language you're learning.
Starting point, a completely unnecessary (as it turned out) custom type. Really, it's a vector masquerading as something more complicated:
pub struct Day6Inputs<'a> {
day6_input: Vec<&'a str>,
}
I'm still not comfortable with lifetimes in Rust, but the way I use this type means that the compiler recommended it's lifetime ('a) be explicitly defined. So I did as I was told - a lesson for any Rust newbie! Compiler knows best.
Next I allocate the input to the type:
let day6 = Day6Inputs {day6_input: vec!["Z9G)Q7N","D1W)7G9", ***MORE THINGS***, "QRW)9MD","LVF)MGV","RFM)NDH"]};
Then we get into the first meaningful action. I iterate over the day 6 input, mapping a split to each item, spliting the string at ) and storing the resulting pair of strings (or &str) in a vector. Those vectors are then added to another vector.
let capture: Vec<Vec<&str>> = day6.day6_input.iter().map(|x: &&str| x.split(")").collect::<Vec<_>>()).collect::<Vec<Vec<_>>>();
//&&str is because I am passing a reference to a &str into the closure:
// |x: &&str| x.split(")")
//Inside the closure, collect the split string into a vector (e.g. "Z9G)Q7N" -> ["Z9G", "Q7N"]) using .collect::<Vec<_>>
//Finally collect the resulting vectors of points into another vector, which must be explicitly shown as being a vector of vectors: .collect::<Vec<Vec<_>>>()
Next I want to make a HashMap that shows each point with its immediate children:
{"COM": ["A", "B"], "A": ["C"] etc.}
So I start with the declaration, then I iterate over my vector of vectors. For each sub-vector, the first &str will be the parent, while the second &str will be the child.
let mut connections: HashMap<&str, Vec<&str>> = HashMap::new();
for combination in capture {
if connections.contains_key(combination[0]) {
/*This next "let" gets me the value if there is an
entry with a key that matches the first `&str`.*/
let value_vec = connections.entry(&combination[0]).or_insert(vec!["Nothing"]);
/*Then it checks if that value (a vector) already contains any
of the connections. This prevents duplicate entries.*/
if value_vec.iter().any(|v| v == &combination[1]) {
println!{"Already in vector"};
} else {
value_vec.push(&combination[1]);
}
} else {
connections.insert(&combination[0], vec![&combination[1]]);
}
/*This section checks if the child point is present as a key and, if not,
adds it as a key and an empty vector as the value.
This is necessary as the points with no children would not otherwise
be recorded in the HashMap.*/
if !connections.contains_key(combination[1]) {
connections.insert(&combination[1], Vec::new());
}
}
Now, with my HashMap populated, I need to determine the orbits for each point. This is done by counting the children of each child point from whichever starting point is chosen. COM - A - B - C has 6 orbits: 3 for COM, 2 for A, 1 for B, and 0 for C.
I do this with a recursive function:
fn chase_the_longest_path<'b>(connections: &'b HashMap<&str, Vec<&str>>, key_to_use: &'b str) -> usize {
/*Get the value vector out of the HashMap for the key_to_use*/
let starting_point: Vec<&str> = connections.get(key_to_use).unwrap().to_vec();
/*Declare and assign a counter that begins with the number of orbits for
key_to_use*/
let mut persistent_counter: usize = starting_point.len();
/*Then, for each point in the value vector associated with key_to_use,
recursively find all child orbits and increment the persistent_counter
with the return value from those recursive functions*/
for value in starting_point {
let temp_counter = chase_the_longest_path(connections, value);
persistent_counter = persistent_counter + temp_counter;
}
/*Return the counter, either to the earlier instance of this function,
or to the call in the main function*/
persistent_counter
}
This recursive function only operates on the chain for one key value, so we need another loop that iterates over the HashMap keys to run the function for each key. We also need a counter to sum the return values for each key, producing our total orbits:
let mut counter: usize = 0;
for (key, _val) in connections.iter() {
counter += chase_the_longest_path(&connections, key);
}
println!("Total orbits: {}", counter);
And the right answer is returned. This file includes my Day 1 code, yet still takes only 1.027 seconds to run. Clojure is fun to write, but you can't beat that speed.
Update
RECORD SCRATCH
OK. Breathe.
What I did above absolutely does NOT work for part 2. While soothing my brain with well-written rust, I happened upon the following article:
No more tears no more knots arena allocated trees in rust
It turns out that Ben, the author, used the approach in his article to perform his version of Day 6. His GitHub is attached to his dev.to, for anyone curious.
So, huge caveat to my update, I leaned on Ben's code. If it looks like I reused code, I probably did. I decided to try and write it myself and then, if I hit issues, I used Ben's code to see the right way of doing it.
I will still write from my own perspective as it helps me to write, but I do not want to pretend or in any way suggest that this is 100% my own work.
TL;DR - this is a mix of my work and borrowed best practice from Ben Lovy
Day 6.1 - Redux
First, create a new type to hold the data for each heavenly body and its associated relationships. Parent is the body it orbits; descendants are the bodies that directly orbit it.
#[derive(Debug, Clone)]
pub struct Node {
/* Each planet/asteroid/other heavenly body is a Node
consisting of its own position in the tree of nodes (index),
it's literal name (string_value), its immediate parent (which can
be None or exactly 1, hence the Option), and its descendants
(which can be >1, hence the vector).*/
index: usize,
string_value: String,
parent: Option<usize>,
descendants: Vec<usize>,
}
Then, in order to compare the name to other Nodes, PartialEq is needed on this type:
impl PartialEq for Node {
/*Without implementing PartialEq, could not compare
names between different nodes*/
fn eq(&self, comparator: &Self) -> bool {
self.string_value == comparator.string_value
}
}
And I then implemented a new function on the type to make creating Nodes easier:
impl Node {
fn new(index: usize, name: &str) -> Self {
/*Implemented on Node type, so Self is a Node.
Creates a new Node and returns it for assignment*/
Self {
index,
string_value: String::from(name),
parent: None,
descendants: vec![],
}
}
}
Next, Ben recommends a type that holds the vector of Nodes (or whatever you have named yours). Since it's a tree, I named it ChristmasTree:
#[derive(Debug, Clone, Default)]
pub struct ChristmasTree {
/*Thematically-named type for storing the Nodes.
bodies means "heavenly bodies".*/
bodies: Vec<Node>,
}
Then come the functions. I've commented them up pretty extensively, so they should be clear.
Part 1:
impl ChristmasTree {
fn update_node_relationships(&mut self) {
/*Use the input_file_handler file_open function to open the day6 inputs,
unwrap the Result to gain access to the string of the file.
Split the string at newlines to get the separate "PRNT)CHLD" strings
and then for each string, trim it and pass it to use_the_split_string*/
let file_input = file_open();
let input_string = file_input.unwrap();
input_string.split("\n").for_each(|o| self.use_the_split_string(o.trim()));
}
fn use_the_split_string(&mut self, parent_and_child: &str) {
/*Split each string passed to the function (e.g. "PRNT)CHLD")
into a vector of ["PRNT", "CHLD"].
For the parent and child, use put_nodes_in_trees to return the
index for the parent and child Nodes.*/
let splits = parent_and_child.split(")").collect::<Vec<&str>>();
let parent_index = self.put_nodes_in_tree(splits[0]);
let child_index = self.put_nodes_in_tree(splits[1]);
/*With the parent and child Node locations now known:
1) For the child Node, retrieve the parent. As a Node can have only
one parent, any Some(_) result means we are trying to add a second
parent and something has gone wrong.
a) If the result is None, write the parent index to the child Node
as Some(parent_index)
2) For the parent Node, any number of children are valid, so push the
child Node index to the descendant vector*/
match self.bodies[child_index].parent {
Some(_) => panic!("Trying to write to existing parent field"),
None => self.bodies[child_index].parent = Some(parent_index),
}
self.bodies[parent_index].descendants.push(child_index);
}
fn put_nodes_in_tree(&mut self, name: &str) -> usize {
/*Check if any Nodes in the tree have the name of the
current object. If true, return the Node location.
If false, create a new Node and push it to the tree with
and index == length of the tree vector before it's added.
Return the new Node index.*/
for node in &self.bodies {
if node.string_value == name {
return node.index;
}
}
let index_to_set = self.bodies.len();
self.bodies.push(Node::new(index_to_set, name));
index_to_set
}
fn count_chain_to_root(&self, node_index: usize) -> usize {
//I count back along the parent line for any given node, until I hit root
match self.bodies[node_index].parent {
Some(n) => 1 + self.count_chain_to_root(n),
None => 0,
}
}
fn sum_all_chains_to_root(&self) -> usize {
/*I iterate over the tree vector, reducing the chain from node to root
for every node in the vector. I return the sum*/
self.bodies.iter().fold(0, |acc, n| {
let node_chain_length = self.count_chain_to_root(n.index);
acc + node_chain_length
})
}
}
pub fn six_two() {
let mut tree = ChristmasTree::default();
tree.update_node_relationships();
let orbits = tree.sum_all_chains_to_root();
println!("{}", orbits);
}
I'll cover the file handler later. It is a separate file that provides a utility file opener, returning the string version of the entire input.
Day 6.2
Part 2 builds on the ChristmasTree type, adding some additional functions that work out the logic.
I implemented my approach by picking one path as the fast path and one as the slow. I work backward along the fast path in full for every step along the slow path. If the two paths are ever on the same Node, then that is the common Node.
I use the common Node in place of the root Node used in part 1, and calculate the chain of orbits. Basically, I count from "YOU" to the common Node, then from "SAN" to the common Node. Add the two path lengths and subtract 2. My code counts "YOU" and "SAN" as Nodes, but the challenge tells us not to count them, so subtract 1 for each.
impl ChristmasTree {
***SNIP***
fn find_index_for_known_string(&self, value: &str) -> Option<usize> {
/*For a given string, return an Option containing the index, or None if not found*/
for node in &self.bodies {
if node.string_value == value.to_string() {
return Some(node.index)
}
}
None
}
fn chain_between_two_points(&self, point_one: &str, point_two: &str) -> usize {
/*I do gather the indices for two points and collect the final distance between them.
I also subtract 2 from the answer returned so that the orbit of each point is not counted,
per AOC directions*/
let point_one_index = match self.find_index_for_known_string(point_one) {
Some(x) => x,
None => panic!("Didn't find {} in the tree!", point_one),
};
let point_two_index = match self.find_index_for_known_string(point_two) {
Some(x) => x,
None => panic!("Didn't find {} in the tree!", point_two),
};
let count = self.move_slow_node(point_one_index, point_two_index, point_one_index, point_two_index) - 2;
count
}
fn move_slow_node(&self, slow_node: usize, fast_node: usize, no_touch_slow: usize, no_touch_fast: usize) -> usize {
/*I move the slow node up its parent chain every time the fast node completes a full recur to root
If the fast node returns Some, it has found a point where both chains meet. The sum of both chains is then
initiated and the result returned*/
match self.move_fast_node(slow_node, fast_node) {
Some(n) => self.sum_all_chains_to_node(n, no_touch_slow, no_touch_fast),
None => self.move_slow_node(self.bodies[slow_node].parent.unwrap(), fast_node, no_touch_slow, no_touch_fast),
}
}
fn move_fast_node(&self, slow_node: usize, fast_node: usize) -> Option<usize> {
/*If the slow and fast node match, return an Option containing the matching index.
Recur through the fast node, propogating an Option back up the recur for return.*/
if self.bodies[slow_node].index == self.bodies[fast_node].index {
return Some(slow_node); //The Node to return is irrelevant; they match if you're here
} else {
if self.bodies[fast_node].parent.is_some() {
let par = self.bodies[fast_node].parent.unwrap();
match self.move_fast_node(slow_node, par) {
Some(x) => return Some(x),
None => return None,
}
} else {
None
}
}
}
fn sum_all_chains_to_node(&self, node_target: usize, node_index_one: usize, node_index_two: usize) -> usize {
/*I iterate over the tree vector, reducing the chain from node to target node
for every node in the custom vector. I return the sum*/
let san_to_you: Vec<usize> = vec![node_index_one, node_index_two];
println!("{:?} {:?} {:?}", self.bodies[node_index_one], self.bodies[node_index_two], san_to_you);
san_to_you.iter().fold(0, |acc, &n| {
let node_chain_length = self.count_chain_to_node(n, node_target);
acc + node_chain_length
})
}
fn count_chain_to_node(&self, node_index: usize, node_target: usize) -> usize {
//I count back along the parent line for any given node, until I hit the target node
if node_index == node_target {
return 0
};
match self.bodies[node_index].parent {
Some(n) => 1 + self.count_chain_to_node(n, node_target),
None => 0,
}
}
}
pub fn six_two() {
let mut tree = ChristmasTree::default();
tree.update_node_relationships();
***SNIP***
let chain_from_me_to_santa = tree.chain_between_two_points(&"YOU", &"SAN");
println!("{}", chain_from_me_to_santa);
}
Testing
Here I did my own thing. I hadn't followed some of Ben's patterns for creating the types, so my tests have to do more legwork than his. An area for learning.
I wrote my own simple tree for one test just so I could try out a different data set and I was glad I did. It exposed some pretty awful summing errors that the shorter tree didn't.
For anyone used to Clojure testing, rust testing feels very familiar. Take Ben's lead on this one: pretty assertions make a HUGE difference in readability when the test fails.
#[cfg(test)]
mod test {
use super::*;
use pretty_assertions::assert_eq;//{assert_eq, assert_ne};
#[test]
fn test_example_from_aoc() {
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let orbits = test_tree.sum_orbits();
assert_eq!(orbits, 42);
}
#[test]
fn test_count_descendants() {
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let direct_children = test_tree.bodies.iter().fold(0, |acc, node| acc + test_tree._count_descendants(node.index));
assert_eq!(direct_children, 11);
}
#[test]
fn test_two_points() {
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L\nK)YOU\nI)SAN");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let chain_between = test_tree.chain_between_two_points(&"YOU", &"SAN");
println!("{}", chain_between);
assert_eq!(chain_between, 4);
}
#[test]
fn test_two_points_new_you() {
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nK)YOU\nB)C\nC)D\nD)E\nE)F\nB)G\nG)H\nD)I\nE)J\nJ)K\nK)L\nI)SAN");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let chain_between = test_tree.chain_between_two_points(&"YOU", &"SAN");
println!("{}", chain_between);
assert_eq!(chain_between, 4);
}
#[test]
fn test_two_points_rewritten_input() {
println!("===\ntest_two_points_rewritten_input()\n===");
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nB)G\nG)H\nB)C\nC)D\nD)E\nE)F\nE)J\nJ)K\nK)L\nD)I\nI)SAN\nK)YOU");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let chain_between = test_tree.chain_between_two_points(&"YOU", &"SAN");
println!("{}", chain_between);
assert_eq!(chain_between, 4);
}
#[test]
fn test_two_points_self_built_data() {
let mut test_tree = ChristmasTree::default();
let test_input = String::from("COM)B\nB)C\nC)D\nD)E\nE)SAN\nB)F\nF)G\nF)H\nH)I\nI)J\nI)K\nK)YOU\nJ)L");
test_input.split("\n").for_each(|o| test_tree.use_the_split_string(o.trim()));
let chain_between = test_tree.chain_between_two_points(&"YOU", &"SAN");
println!("{}", chain_between);
assert_eq!(chain_between, 7);
}
}
Oldest comments (0)