Advent of Code 2021: Day 7

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

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 numbers though: 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 ~afontaine/blog-discuss@lists.sr.ht, and be sure to follow the mailing list etiquette.