Advent of Code 2021: Day 7Andrew Fontaine <email@example.com>
A giant whale has decided your submarine is its next meal, and it’s much faster than you are. There’s nowhere to run!
Thanks to the help of some crabs, we’ll get past that whale!
This seems like a great job for simply brute-forcing the whole thing. I am sure there is a way to utilize a binary search to find the answer, but I’m also sure I’m in no mood to figure it out. Part one is still pretty small:
let p1_sol crabs = List.fold_left (fun min_fuel pos -> let new_fuel = List.fold_left (fun x y -> max y pos - min y pos + x) 0 crabs in if new_fuel < min_fuel then new_fuel else min_fuel) Int.max_int crabs let p1 = let sol = p1_sol input in Int.to_string sol
Once again I
fold_left over all the crabs, calculating the fuel cost for the
rest of the crabs, and finding the smallest total.
⭐ one done!
Part two seems trickier at first. The idea of adding up all those numbers is
supposed to scare you. We both know there is a formula for calculating a sum of
n * (n + 1) / 2
That’s really it!
The answer is the exact same as part one, but with the summation formula filled in instead. I had to be a little more thorough and calculate the minimum for all the possible positions, but no difference otherwise:
let p2_sol positions crabs = List.fold_left (fun min_fuel pos -> let new_fuel = List.fold_left (fun x y -> let n = max y pos - min y pos in if n = 0 then x else (n * (n + 1) / 2) + x) 0 crabs in if new_fuel < min_fuel then new_fuel else min_fuel) Int.max_int positions let p2 = let crabs = input in let min, max = List.fold_left (fun (x, y) z -> let new_x = if z < x then z else x in let new_y = if z > y then z else y in (new_x, new_y)) (Int.max_int, 0) crabs in let positions = List.init (max - min) (fun x -> x + min) in let sol = p2_sol positions crabs in Int.to_string sol
I could have squeezed a bit more efficiency out of things if I had used a binary search, but I didn’t really need it here.
That’s it for today! I’m excited to see what tomorrow’s challenge will be!
Want to discuss this post?
Reach out via email to ~firstname.lastname@example.org, and be sure to follow the mailing list etiquette.Other posts