Day 5, we tasked with solving a printing problem. This is our first challenge of the year with mixed input. The first set
of input is a list of rules. We have two numbers, x, and y seperated by a pipe |. These numbers represent the order of
pages in the document we have to print. Essentially pages on the left must always be before pages on the right. The second part
of our input is a set of pages or updates. Some are in order per the rules set out above. Others are not and cannot be printed. Part 1
is simple. We must find the updates that are in the correct order. Once we find those pages, we must take the middle page of each
update, and sum them together. This is arguably the first puzzle where we are truly processing data. Previous puzzles was more
analysis of the input. Let's start with a test.
#[test]
fn test_solve_part_one() {
let input = String::from(
r#"47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47"#,
);
let print_queue = PrintQueue {
output_signal: Box::new(DefaultOutputSignal),
};
let result = print_queue.solve_part_one(input);
assert_eq!(result, Ok("143".to_string()));
}
To solve this, data relationships are going to be important. So before I even start processing the input, I want to specify a data structure to sort our input. Thinking about our problem, we have to evaluate a set of numbers. To do so we need to understand their relationship to each other, but also be able to readily access those relationships on the fly. As such let's define a structure where we can keep the relationship on hand, while making it easy to access.
mod part_one {
#[derive(Clone)]
pub struct PageRules {
pub before: Vec<usize>,
pub after: Vec<usize>,
}
impl PrintQueue {
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut page_rules = HashMap::<usize, PageRules>::new();
let mut updates: Vec<Vec<usize>> = vec![vec![]];
...
}
}
}
Here we have a struct. This struct is going to represent rules. We store this struct in a HashMap with the key to the HashMap being the page number that the rules relate to. We also have a vector of vectors. This is going to store the updates. Each update consists or a list a numbers, and we have many sets, hence the vector of vectors. Let's move on to parsing the input.
mod part_one {
#[derive(Clone)]
pub struct PageRules {
pub before: Vec<usize>,
pub after: Vec<usize>,
}
impl PrintQueue {
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut page_rules = HashMap::<usize, PageRules>::new();
let mut updates: Vec<Vec<usize>> = vec![vec![]];
input_as_lines.iter().for_each(|line| {
if line.trim().is_empty() {
// Do nothing
} else if line.contains('|') {
let mut parts = line.split('|');
let before = parts.next().unwrap().trim().parse::<usize>().unwrap();
let after = parts.next().unwrap().trim().parse::<usize>().unwrap();
{
let x = page_rules.entry(before).or_insert(PageRules {
before: vec![],
after: vec![],
});
x.after.push(after);
}
{
let y = page_rules.entry(after).or_insert(PageRules {
before: vec![],
after: vec![],
});
y.before.push(before)
}
} else {
let mut update = vec![];
line.split(',').for_each(|x| {
update.push(x.trim().parse::<usize>().unwrap());
});
updates.push(update);
}
});
...
}
}
}
This parsing is relatively straight forward. The interesting part is the use of entry of the hashmap. This allows us to get a reference, or insert a new value if it does not exist. From there, we sort the input into before and after for two records in the hashmap. The rest is just parsing the updates. Now that we have our data, we can start processing it.
mod part_one {
#[derive(Clone)]
pub struct PageRules {
pub before: Vec<usize>,
pub after: Vec<usize>,
}
impl PrintQueue {
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
let input_as_lines = split_multiline_string(input);
let mut page_rules = HashMap::<usize, PageRules>::new();
let mut updates: Vec<Vec<usize>> = vec![vec![]];
...
let valid_updates: Vec<Vec<usize>> = updates
.iter()
.filter(|update| {
let is_valid = Self::is_valid(page_rules.clone(), &update);
is_valid
})
.map(|u| u.clone())
.collect::<Vec<Vec<usize>>>();
...
}
pub(crate) fn is_valid(
mut page_rules: HashMap<usize, PageRules>,
update: &&&Vec<usize>,
) -> bool {
if update.is_empty() {
return false;
}
for i in 0..update.len() {
let rules = page_rules.get(&update[i]).unwrap();
let before_vec = &update[0..i];
let after_vec = &update[i + 1..update.len()];
if rules.before.iter().any(|&x| after_vec.contains(&x)) {
return false;
}
if rules.after.iter().any(|&x| before_vec.contains(&x)) {
return false;
}
}
true
}
}
}
Here we are applying our validation. This validation iterates over each element in an update. With that element, we retrieve the rules from the hashmap for that element. We then split the update into two parts, before and after the current element. Finally, we can verify per the rules that nothing form before is in the after list, and nothing from after is in the before list.
With that we find the center element of each update, sum them together, and return the result.
pub fn part_one_process(&self, input: String) -> Result<String, ()> {
...
let sum: usize = valid_updates
.iter()
.map(|update| {
let center_index = update.len() / 2;
update.get(center_index).unwrap()
})
.sum();
Ok(sum.to_string())
}
Part 2 is interesting. We are tasked with taking the invalid updates, and making them valid. We then in turn need to apply the same sum of certain elements in the update. This would be a challenging problem to solve, if we needed to build a sorting algorithm from scratch. However, Rust like many other languages already support sorting ordered collections. We just need to tell Rust how to sort our data. With that we need to build a comparator. This comparator will translate the relationship between two elements, and tell the sorting function how to order them. Let's start with a test.
#[test]
fn test_solve_part_two() {
let input = String::from(
r#"47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13
75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47"#,
);
let print_queue = PrintQueue {
output_signal: Box::new(DefaultOutputSignal),
};
let result = print_queue.solve_part_two(input);
assert_eq!(result, Ok("123".to_string()));
}
Now let's update our method to allow us to handle the invalid updates.
mod part_two {
impl PrintQueue {
pub fn part_two_process(&self, input: String) -> Result<String, ()> {
...
let invalid_updates: Vec<Vec<usize>> = updates
.iter()
.filter(|update| {
let is_valid = Self::is_valid(page_rules.clone(), &update);
!is_valid
})
.map(|u| u.clone())
.collect::<Vec<Vec<usize>>>();
let new_updates = order_invalid(invalid_updates, page_rules.clone());
let sum: usize = new_updates
.iter()
.map(|update| {
let center_index = update.len() / 2;
update.get(center_index).unwrap()
})
.sum();
Ok(sum.to_string())
}
...
}
All we have done is reversed the filter function to retrieve invalid, and passed our invalid updates with the page rules to a separate function. This function will sort the invalid updates, and return them. Let's write that function.
fn order_invalid(
unordered_updates: Vec<Vec<usize>>,
map: HashMap<usize, PageRules>,
) -> Vec<Vec<usize>> {
unordered_updates
.iter()
.map(|update| {
let mut new_update = update.clone();
new_update.sort_by(|a, b| {
if map.get(a).unwrap().before.contains(b) {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Greater
}
});
new_update
})
.collect()
}
This is where I found part 2 really enjoyable. We take our updates, and we use a standard rust function sort_by. This function
will sort our collection based on any arbitrary rule we define. In this case, we are defining the relationship between two elements
as whether the element b exists in the a elements before list. If it does, then we return less, otherwise greater. Whether we
order it ascending or descending does not matter in this case as we care only of the center element.
With that we have solved day 5. This was a fun problem to solve. It's a good example of why we don't have to reinvent the wheel. Rust, along with many other languages, have a lot of built in functionality that can help us solve problems quickly and efficiently. In this case we saved time by focusing only on what defines the order of our data, and let Rust do the heavy lifting.