Advent of Code '21 in OCaml, Day 1

Posted: 2022-09-04

I recently started at Jane Street, a technology-centric trading firm which uses OCaml. I’ve spent my whole career writing imperative languages, so I am exploring OCaml development using the Advent of Code, a puzzle game which I’ve played in Go multiple times.

Follow along as I explore thinking imperatively:

 1func B(l []string) {
 2	d := lib.SliceAtoi(l)
 3	count := 0
 4	win := [3]int{d[0] + d[1] + d[2], d[1] + d[2], d[2]}
 5	for i := 3; i < len(l); i++ {
 6		win[(i-1)%3] += d[i]
 7		win[(i-2)%3] += d[i]
 8		// Completed win i-2, and win i is done. Compare
 9		if win[(i-2)%3] > win[i%3] {
10			count++
11		}
12		// Reset win[i]
13		win[i%3] = d[i]
14	}
15	fmt.Println(count)
16}

and functionally:

 1let rec fold2 ~init ~f = function
 2  | a :: b :: tl -> fold2 ~init:(f init a b) ~f (b :: tl)
 3  | _ -> init
 4
 5let rec fold3 ~init ~f = function
 6  | a :: b :: c :: tl -> fold3 ~init:(f init a b c) ~f (b :: c :: tl)
 7  | _ -> init
 8
 9let count_triple_increases l =
10  let add acc a b c = (a + b + c) :: acc in
11  let count_dec acc a b = if a > b then acc + 1 else acc in
12  fold3 ~init:[] ~f:add l |> fold2 ~init:0 ~f:count_dec
13
14let day1b ls =
15  List.map ls ~f:Int.of_string
16  |> count_triple_increases |> Int.to_string |> print_endline

The Advent of Code

The Advent of Code is a 25-day Advent calendar of programming and math puzzles, with a very loose Santa Claus theme. Each day has a 2-part puzzle,¹ both parts have the same input, and the solution to the second part generally builds off the solution to the first.

I’ll be working back through the 2021 edition. The theme was to find Santa’s sleigh keys at the bottom of the ocean.²

There is an optional speed programming aspect. The fastest 100 solutions for each part win points. I don’t generally think of myself as a fast programmer, but I am competitive, so in Go I played “against” some coworkers and aimed to get a solution quickly. This time, my goal is to understand OCaml better, so I want to fully understand the “OCaml way” to solve puzzles like these, and be able to explain them to myself (and you!).³

First, I set up an environment to build OCaml binaries.

Setup

Go has a built-in dependency management system. The system has changed over time, but in 2021 I used a go.mod file and VSCode integration.

OCaml has a less automatic package and dependency manager called opam.⁴ It has “switches” to handle versioned dependencies. I don’t think I’ll need that to play around with puzzles, so I am planning to use the default switch throughout.⁵

OCaml docs also recommend building with Dune. I am very familiar with Bazel, and Dune’s target definition language and build strategy is morally similar,⁶ so this felt comfortable.

S-expressions (“sexps”) are everywhere in OCaml, including in Dune. I personally find Bazel’s Skylark language for target definitions to be both easier to read and more flexible, since it supports e.g. imperative loops and conditionals. Those don’t matter for building some puzzle-solving programs, though. In Dune’s favor, it globs files into libraries automatically and is less verbose, so the minimal Dune files are much shorter than the equivalent minimal Bazel files. After the initial setup, my build works more like a Go package than a Bazel package.

Day 1

Part A of the first day’s puzzle involves processing a list serially, counting how often an element is greater than its predecessor. This should be natural in a functional language!

To get a feel for OCaml development, I wrote a test for the sample input. Setting up expect_test⁷ required reading the Dune documentation carefully, but in the end I have useful copypasta, and the OCaml default library structure means I shouldn’t have to play with it again.⁸

Folds are the standard functional way of accumulating a value across the elements of a data structure. List.fold accumulates one element at a time, though, and the puzzle asks us to compare two elements! There are a variety of ways to accomplish this,⁹ but I decided to approach it naively, exactly as described:

 1let count_increases l =
 2  let rec sum acc = function
 3    | f :: s :: tl ->
 4        if s > f then sum (acc + 1) (s :: tl) else sum acc (s :: tl)
 5    | _ -> acc
 6  in
 7  sum 0 l
 8
 9let day1a ls =
10  List.map ls ~f:Int.of_string
11  |> count_increases |> Int.to_string |> print_endline

This puzzle uses the first common input format in Advent of Code: a text file with a sequence of independent elements, one on each line. Async.Reader.file_lines¹⁰ gathers the lines of a file into a string list, and after some minor futzing I had my first puzzle solved!

Part B of the puzzle is to count the number of times the trailing sum of three elements increases. In Go, I did exactly as the puzzle suggested, and kept three running sums of three elements each. In OCaml, it felt more natural to build a new list with the desired property.

 1let sum3 l =
 2  let rec sum acc = function
 3    | f :: s :: t :: tl -> sum ((f + s + t) :: acc) (s :: t :: tl)
 4    | _ -> acc
 5  in
 6  sum [] l |> List.rev
 7
 8let day1b ls =
 9  List.map ls ~f:Int.of_string
10  |> sum3 |> count_increases |> Int.to_string |> print_endline

I’m trying to develop good OCaml habits, and these functions felt too specific and not particularly idiomatic. I was effectively folding with two (or three) elements at a time passed to an accumulator function, which is very similar to List.fold! I wound up rewriting these as fold2 and fold3¹¹ respectively, passing in simpler accumulator functions. While there, I removed the unnecessary List.rev in day1b.

 1let rec fold2 ~init ~f = function
 2  | a :: b :: tl -> fold2 ~init:(f init a b) ~f (b :: tl)
 3  | _ -> init
 4
 5let count_increases l =
 6  let f acc a b = if b > a then acc + 1 else acc in
 7  fold2 ~init:0 ~f l
 8
 9let day1a ls =
10  List.map ls ~f:Int.of_string
11  |> count_increases |> Int.to_string |> print_endline
12
13let rec fold3 ~init ~f = function
14  | a :: b :: c :: tl -> fold3 ~init:(f init a b c) ~f (b :: c :: tl)
15  | _ -> init
16
17let count_triple_increases l =
18  (* build sums in reverse order... *)
19  let add acc a b c = (a + b + c) :: acc in
20  (* ...then count decreases instead of increases *)
21  let count_dec acc a b = if a > b then acc + 1 else acc in
22  fold3 ~init:[] ~f:add l |> fold2 ~init:0 ~f:count_dec
23
24let day1b ls =
25  List.map ls ~f:Int.of_string
26  |> count_triple_increases |> Int.to_string |> print_endline

My final commit of day 1 code is here.

Thoughts

I’m happy with the result, which is more general than my Go approach. The |> operator for function chaining was quite natural.

Searching for OCaml tools and libraries is much harder than searching for Go ones, probably due to its smaller community. The best resources I found were https://ocaml.org/packages and https://dev.realworldocaml.org.

My performance sensibilities were built by years of writing efficiency-oriented C++. Iterating over a series of separate singly-linked lists feels bad. An alternatively implementation based on Array might make me feel better. I haven’t benchmarked it, though, and for one-off iteration of a text file, the list approach is sufficient.

--Chris