Advent of Code '21 in OCaml, Days 6 and 7

Posted: 2022-11-28

To explore OCaml development in practice, I’ve been working my way through 2021’s Advent of Code. This edition covers days six and seven. Day 6 was a densely-indexed puzzle I solved with imperative code, and day 7 was a sparsely-indexed puzzle I solved with a mix of functional data structures and imperative loops.

See the day one post for background! See the previous post for earlier puzzles. The commits are available on GitHub.

Day 6

This puzzle was all about exponential growth. The puzzle set out some rules for how lanternfish reproduce each day and asked us to count how many would exist after some number of days. Each lanternfish had a counter which ticked down each day, unless it was at zero, in which case it reset to 6 and a spawned new lanternfish with a counter of 8.¹

Part A asked us to count the fish after 80 days, and part B asked us for the count after 256 days.

Allocating an object for each fish would quickly become too expensive because of the exponential growth. In this case, we knew that each fish only had one interesting feature, its counter, and that there were only 9 possible counts (0 through 8). It was a clear use case for a 9-element array of integers.

 1let run_array ls ct =
 2  let inits =
 3    List.hd_exn ls |> String.split ~on:',' |> List.map ~f:Int.of_string
 4  in
 5  let fish = Array.create ~len:9 0 in
 6  List.iter inits ~f:(fun i -> fish.(i) <- fish.(i) + 1);
 7  for _ = 1 to ct do
 8    let zeroes = fish.(0) in
 9    for i = 0 to 7 do
10      fish.(i) <- fish.(i + 1)
11    done;
12    fish.(6) <- (fish.(6) + zeroes);
13    fish.(8) <- zeroes
14  done;
15  Array.fold fish ~init:0 ~f:(fun acc ct -> acc + ct)

I also wanted to investigate a purely functional approach. In this case it didn’t do as poorly as I expected, taking ~2x as long for 256 iterations. However the functional approach’s garbage collection overhead also scaled with the number of iterations since each loop involved several list node allocations.

 1let run_list ls ct =
 2  let inits =
 3    List.hd_exn ls |> String.split ~on:',' |> List.map ~f:Int.of_string
 4  in
 5  let fish_map =
 6    Int.Map.of_increasing_iterator_unchecked ~len:9 ~f:(fun i -> (i, 0))
 7  in
 8  let fish_map =
 9    List.fold inits ~init:fish_map
10      ~f:(Map.update ~f:(Option.value_map ~default:1 ~f:succ))
11  in
12  let fish = Map.to_alist fish_map |> List.unzip |> snd in
13  let rec loop fish = function
14    | 0 -> fish
15    | ct ->
16        let zeroes = List.hd_exn fish in
17        let nonzero_fish =
18          List.tl_exn fish
19          |> List.rev_mapi ~f:(fun i f ->
20                match i with 6 -> f + zeroes | _ -> f)
21          in
22          let fish = zeroes :: nonzero_fish |> List.rev in
23          loop fish (ct - 1)
24  in
25  loop fish ct |> List.sum (module Int) ~f:Fn.id

Day 7

Day 7’s puzzles had us minimizing cost. For part A, we were given a line of crabs at different positions and asked to find the position they could all walk to with the fewest total number of crab steps.

When I first solved this in 2021, I noticed that the solution was the simple average of all positions. Part B used a more complex quadratic step cost function, though.² I chose to consider all feasible positions, the ones between the extreme end crabs, and apply the cost function to each crab, yielding an O(n^2) approach.

 1let minimize line cost_f =
 2  let poses =
 3    String.split ~on:',' line
 4    |> List.fold ~init:Int.Map.empty ~f:(fun m s ->
 5           let i = Int.of_string s in
 6           Map.update m i ~f:(fun ct ->
 7               Option.value_map ct ~default:1 ~f:(fun ct -> ct + 1)))
 8  in
 9  let cost = ref Int.max_value in
10  for p = Map.min_elt_exn poses |> fst to Map.max_elt_exn poses |> fst do
11    let newcost =
12      Map.fold poses ~init:0 ~f:(fun ~key:q ~data:ct acc ->
13          acc + (cost_f p q * ct))
14    in
15    if newcost < !cost then cost := newcost else ()
16  done;
17  !cost
18
19let parta ls = minimize (List.hd_exn ls) (fun a b -> Int.abs (a - b))
20
21let partb ls =
22  minimize (List.hd_exn ls) (fun a b ->
23      let d = Int.abs (a - b) in
24      d * (d + 1) / 2)

Even though I used a map since the crabs may be sparse, my solution was mostly imperative. I used a for loop to iterate the possible positions and a reference to track the least total cost. I could have done this functionally, using List.init and List.min_elt.

Thoughts

As soon as I started thinking in the imerative mode, which suited day 6 perfectly, I had a hard time considering a purely functional solution for day 7. I’ll see if future puzzles push me further towards imperative solutions or if any are particularly well suited to functional solutions.

--Chris