Advent of code 2021: Day 7
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #7.
Part 1
The puzzle input this time around is a list of numbers. Each number represent a crab with a certain amount of fuel. The goal is to find the cheapest horizontal position (in total amounts of fuel) all the crabs can move to. The first solution is going to be a simple one, knowing that for part 2 I probably need to do something smarter. The first simple version:
fn cheapest_crab_move(crabs: Vec<isize>) -> isize {
let mut min_fuel = isize::MAX;
let mut lowest_move = -1;
let max = crabs.iter().max().unwrap();
for m in 0..*max {
let sum_fuel: isize = crabs
.iter()
.map(|n| (n - m).abs())
.fold(0, |acc, b| acc + b);
if sum_fuel < min_fuel {
min_fuel = sum_fuel;
lowest_move = m;
}
}
lowest_move
}
#[test]
fn test_cheapest_move() {
let moves = vec![16,1,2,0,4,2,7,1,2,14];
assert_eq!(cheapest_crab_move(moves), 2);
}
For part 1 the aforementioned code, returns 307. However, that seems to be the incorrect answer. I check all positions between 0 and 1931 (the highest number in the input). All the example values are correct (I get 41 fuel for position 1, 39 for position 3 and 71 for position 10). Perhaps there are two values that return 307? After some reading, the actual question dictates: “How much fuel does it take?”, which is a different question than “Which move consumes the least fuel?”. After tweaking the code slightly and getting rid of lowest_move, I get the correct answer.
Part 2
Apparently I didn’t do the actual crab engineering correctly, and I need to take into account that each horizontal step, increments the fuel consumption by 1. For part 2 I’ve extended the code at part 1 and do a little cheeky sum; making for a gnarly O(n3) algorithm:
fn cheapest_crab_move_with_tax(crabs: &Vec<isize>) -> isize {
let mut min_fuel = isize::MAX;
let max = crabs.iter().max().unwrap();
for m in 0..*max {
let sum_fuel: isize = crabs
.iter()
.map(|n| {
let steps = (n - m).abs();
(1..=steps).sum::<isize>()
})
.fold(0, |acc, b| acc + b);
if sum_fuel < min_fuel {
min_fuel = sum_fuel;
}
}
min_fuel
}
#[test]
fn test_cheapest_move_with_tax() {
let moves = vec![16,1,2,0,4,2,7,1,2,14];
assert_eq!(cheapest_crab_move_with_tax(moves), 168);
}
As slow as it may be, it does give the answer relatively quickly, meaning I’ve gained another two stars. ⭐️⭐️
PS: Why was this one so incredibly easy, compared to yesterday’s assault on the senses?
Improvements
To make part 2 quite a lot faster, you can calculate the ‘tax rates’ beforehand:
let mut min_fuel = isize::MAX;
let mut tax_rates = vec![0, 1];
let max = crabs.iter().max().unwrap();
for t in 2..=*max {
tax_rates.push((1..=t).sum::<isize>());
}
for m in 0..*max {
let sum_fuel: isize = crabs
.iter()
.map(|n| tax_rates[(n - m).abs() as usize])
.fold(0, |acc, b| acc + b);
if sum_fuel < min_fuel {
min_fuel = sum_fuel;
}
}
min_fuel
Another improvement is to make use of the min() method to make the code a bit more condensed:
let mut tax_rates = vec![0, 1];
let max = crabs.iter().max().unwrap();
for t in 2..=*max {
tax_rates.push((1..=t).sum::<isize>());
}
(0..*max)
.map(|m|
crabs
.iter()
.map(|n| tax_rates[(n - m).abs() as usize])
.fold(0, |acc, b| acc + b))
.min().unwrap()
The full solution is available on GitHub.
