Advent of Code '22 in OCaml, Week 1

Posted: 2022-12-03

The 2022 Advent of Code has started! I’m continuing to learn OCaml in practice. I’m also tackling the puzzles when they’re released at midnight when possible.

When I worked through some of the 2021 puzzles last month I wanted to understand OCaml idioms and performance characteristics. This time, I want to see how quickly I can get solutions out!

Week 2 ahead.

Day 1

The elves want to redistribute the snacks away from the calorie-rich to the calorie-poor. When the calorie-richest have no more to give, the calorie-second- and third-richest will have to do.

To go fast, I took the first approach that leapt to mind. My library code to group sections separated by newlines also helped a lot.

For part a we were only looking for the elf carrying the most calories. I mapped the lines to ints, summed the ints, and used List.max_elt to extract the max.

1let parta ls =
2  Input.to_sections ls
3  |> List.map ~f:(fun bag ->
4         List.map bag ~f:Int.of_string |> List.sum (module Int) ~f:Fn.id)
5  |> List.max_elt ~compare:Int.compare
6  |> Option.value_exn

There were a lot of things to neaten up there (see the snippet below), but I was able to squeak into the top 1000, which felt great!

For part b we needed to sum the calories held by the top 3 elves, at which point sorting the list made more sense. I fumbled with 2 clear mistakes in my first pass here:

  1. I wrote out an explicit match on lists with at least 3 elements instead of using List.take l 3.
  2. I reimplemented Fn.flip to get a decreasing-order sort.

I was happy enough with my speed on day 1, though, and with the cleaned up code.

  • Part a: 00:02:44, rank 918
  • Part b: 00:04:48, rank 1189
  • Commit
1let calorie_counts_decreasing bags =
2  List.map bags ~f:(List.sum (module Int) ~f:Int.of_string)
3  |> List.sort ~compare:(Fn.flip Int.compare)
4
5let parta ls = Input.to_sections ls |> calorie_counts_decreasing |> List.hd_exn
6
7let partb ls =
8  let sorted = Input.to_sections ls |> calorie_counts_decreasing in
9  List.take sorted 3 |> List.sum (module Int) ~f:Fn.id

Day 2

The elves use games of chance to mediate access to resources. Naturally, we cheat.

I didn’t find this puzzle as fun. Each line represented a Rock Paper Scissors game, which translated to a score between 1 and 9. The task was to sum the scores, and the only difference between the two parts was the scoring function. There are only 9 possible Rock Paper Scissors outcomes, so most natural way to approach this was to enumerate them all.

I learned something about going fast, though. My first approach split the lines into 2-tuples of strings before matching, which meant handling malformed lines. Then I matched against the tuples to get the score, which meant handling unexpected strings.

 1let score1 = function
 2  | "A", "X" -> 4
 3  (* ... etc ... *)
 4  | _ -> failwith "bad pair"
 5
 6let parta =
 7  List.sum
 8    (module Int)
 9    ~f:(fun line ->
10      match String.split line ~on:' ' with
11      | [ a; b ] -> score1 (a, b)
12      | _ -> failwith "bad line")

I later refactored this to move all handling into one place, matching against the output of String.split directly. This would have been the fastest thing to type for the puzzle. In real code where I might be nervous about new tokens, I would probably split the lines into tuples of polymorphic variants so the compiler could warn me of a non-exhaustive match.

I got a late start on this one, probably at around ~00:15.

  • Part a: 00:19:51, rank 8153
  • Part b: 00:23:20, rank 5863
  • Commit
 1let score1 line =
 2  match String.split line ~on:' ' with
 3  | [ "A"; "X" ] -> 4
 4  (* ... etc ... *)
 5  | _ -> failwith "bad line"
 6
 7let parta = List.sum (module Int) ~f:score1
 8
 9let score2 line =
10  match String.split line ~on:' ' with
11  | [ "A"; "X" ] -> 3
12  (* ... etc ... *)
13  | _ -> failwith "bad line"
14
15let partb = List.sum (module Int) ~f:score2

Day 3

The elves packed some non-snack items too, but not very well. We had to discover items packed into more than one side of the bag for part a, and figure out an item unique to each elf trio for part b.

I was pretty disappointed in my performance for this one. It was clear for part a that we’d need a set of the elements on one side in order to find the only matching element on the other side. I initially chose to iterate the items on the other side as a List.t:

 1let charpriority c =
 2  if Char.is_uppercase c then Char.to_int c - Char.to_int 'A' + 27
 3  else Char.to_int c - Char.to_int 'a' + 1
 4
 5let charset s = String.to_list s |> Char.Set.of_list
 6
 7let parta =
 8  List.fold ~init:0 ~f:(fun acc sack ->
 9      let sidelen = String.length sack / 2 in
10      let inleft = String.prefix sack sidelen |> charset in
11      let elem =
12        String.suffix sack sidelen |> String.to_list
13        |> List.find ~f:(Set.mem inleft)
14        |> Option.value_exn
15      in
16      acc + charpriority elem)

For part b, we had to find the single character common in each trio of consecutive lines. I forgot that each bag could contain more than one of each item, even though that was the premise of part a! So my first approach was to increment an int Char.Map.t for each character, then iterate over the map to find the key whose value was 3. This doesn’t work, and in an effort to move quickly I constructed 3 maps whose values were 1, then merged them, then found the key whose value was 3.

This does work, but was not at all fast to write. Only after I took a step back did I realize that set intersection provides the solution to both parts with much less typing!

Since I was no longer going for speed, I took the opporunity to write a library function for folds which consider multiple consecutive elements. This was useful in past years also.

1let rec foldn ~n ~init ~f l =
2  let curr, tl = List.split_n l n in
3  match tl with
4  | [] -> f init curr
5  | tl ->
6      let init = f init curr in
7      foldn ~n ~init ~f tl

With that tool available, I rewrote the code.

  • Part a: 00:13:07, rank 4294
  • Part b: 00:28:28, rank 6224
  • Commit
 1let charpriority c =
 2  if Char.is_uppercase c then Char.to_int c - Char.to_int 'A' + 27
 3  else Char.to_int c - Char.to_int 'a' + 1
 4
 5let charset s = String.to_list s |> Char.Set.of_list
 6
 7let parta =
 8  List.sum
 9    (module Int)
10    ~f:(fun sack ->
11      let sidelen = String.length sack / 2 in
12      let inleft = String.prefix sack sidelen |> charset in
13      let inright = String.suffix sack sidelen |> charset in
14      let elem = Set.inter inleft inright |> Set.min_elt_exn in
15      charpriority elem)
16
17let partb =
18  Types.foldn ~n:3 ~init:0 ~f:(fun acc sacks ->
19      let badge =
20        List.map sacks ~f:charset |> List.reduce ~f:Set.inter
21        |> Option.value_exn |> Set.min_elt_exn
22      in
23      acc + charpriority badge)

--Chris

Home | Feedback | RSS