Advent of Code '21 in OCaml, Days 4 and 5

Posted: 2022-11-19

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.

See the day one post for background! See the previous post for earlier puzzles.

As I get more experience with OCaml I have less basic exploring to do. I’ve decided to combine my notes for multiple days of puzzles into one post. This one covers days 4 and 5. The commits are available on GitHub.

Libraries

Day 4 was the first to use a common input format: multiple sections separated by blank lines. It also contains a common line format, where numbers are aligned for the reader rather than separated by a single character. That was my cue to start on a library for managing puzzle inputs!

I implemented section splitting as a fold followed by a reverse:

 1let to_sections lines =
 2  let result, current =
 3    List.fold lines ~init:([], []) ~f:(fun (result, current) l ->
 4        match l with
 5        | "" -> (List.rev current :: result, [])
 6        | contents -> (result, contents :: current))
 7  in
 8  let result =
 9    match current with
10    | [] -> result
11    | last_section -> List.rev last_section :: result
12  in
13  List.rev result

In Core, a related function uses List.rev_map to accomplish the same thing without reversing the groups during the fold. It seems at least plausible for that approach to allocate one fewer list node per group, but I didn’t investigate with a benchmark.

I implemented token splitting naively: I filtered empty elements from the result of String.split. It’s possible to avoid one list pass and all the empty string node allocations. I chose not to improve it as I wanted to get into the meat of the puzzles!

Day 4

Part A of the fourth day’s puzzle was to find the first board to win a simplified bingo (no diagonals). The input had draws on the first line comma-separated followed by a blank line, then 5-by-5 bingo boards each separated by blank lines.

In imperative languages, I’d represent a grid as either a dense array of arrays or a sparse map.¹ Bingo boards are dense, but I decided to try a purely functional approach using lists.

It would have been unpleasant to handle separate row and column indexing in a single list of lists. Fortunately, Core contains List.transpose, which I used to generate equivalent row-major and column-major representations of each board.

1(** Take a section and make it a board of entries. A board is represented in
2    both row-major and column-major form. *)
3let board_of_section section =
4  let rows =
5    List.map section ~f:(fun line ->
6        Input.to_tokens line |> List.map ~f:entry_of_tok)
7  in
8  (rows, List.transpose_exn rows)

From there, it was straightforward to iterate all the entries, track when a row or column has been totally drawn, and score the winning board!

Part B asked us track the last board to win, rather than the first. I just had to change the termination condition.

 1(* Returns First of a live board, and Second of a winning board's score *)
 2let mark_board (rows, cols) draw =
 3  let mark_rep rep =
 4    List.fold_map ~init:false rep ~f:(fun entry_all_ok entries ->
 5        let entries_ok, entries =
 6          List.fold_map ~init:true entries ~f:(fun all_ok { num; marked } ->
 7              let marked = marked || num = draw in
 8              (all_ok && marked, { num; marked }))
 9        in
10        (entry_all_ok || entries_ok, entries))
11  in
12  let won, rows = mark_rep rows in
13  if won then Second (draw * score_board rows)
14  else
15    let won, cols = mark_rep cols in
16    if won then Second (draw * score_board cols) else First (rows, cols)
17
18let partb ls =
19  let sections = Input.to_sections ls in
20  let draws =
21    List.hd_exn sections |> List.hd_exn |> String.split ~on:','
22    |> List.map ~f:Int.of_string
23  in
24  let init = List.tl_exn sections |> List.map ~f:board_of_section in
25  List.fold_until draws
26    ~finish:(fun _ -> failwith "no winner!")
27    ~init
28    ~f:(fun boards draw ->
29      match
30        List.partition_map boards ~f:(fun board -> mark_board board draw)
31      with
32      | [], [ winner ] -> Stop winner
33      | [], _ -> failwith "unexpectedly not one final winner!"
34      | remaining, _ -> Continue remaining)

Finally, for bingo specifically there shouldn’t be any duplicate draws. We could therefore represent boards as maps from integers to pairs of integer references, one each for the number of drawn entries in the column and row respectively. This might be a faster approach than iterating every element of every board on every draw, but it is also not purely functional!

Day 5

By day 5, my harness for running puzzle solutions was starting to show strain. I refactored it to add each new day’s solutions with one line of code. All the per-day information is now in a single list:

1let daymods =
2  Int.Map.of_alist_exn
3    [
4      (1, ((module Day1 : Day), (module Of_unit_day (Day1) : Printing_day)));
5      (2, ((module Day2), (module Of_int_day (Day2))));
6      (3, ((module Day3), (module Of_int_day (Day3))));
7      (4, ((module Day4), (module Of_int_day (Day4))));
8    ]

The harness takes care of the rest! It’s still pretty repetitive, and I’m cheating a little by preemptively parameterizing on output type.² There’s also probably a way to avoid repeating Day1, Day2, etc. multiple times on each line, but I’m happy enough with it for now.

Part A for day 5 gave us line segments in the format:

a,b -> c,d

where a,b and c,d were the endpoints and lines were horizontal, vertical, or diagonal at 45 degrees. Considering only the horizontal and vertical segments, we had to count the number of grid points with intersections.

A multicharacter separator was new in this puzzle, and they will come up again. The boilerplate to split strings on substrings in Core is longer than I’d like, so I extracted it to a function in my nascent Input module:

1let split_on_string s ~sep =
2  let p = String.Search_pattern.create sep in
3  String.Search_pattern.split_on p s

This was also the first puzzle where I had to use a map of sparse coordinates. OCaml makes this harder than I’d like. Extracting a tuple element is verbose for 3-tuples and up, and tuples can’t trivially be used as keys in a Core.Map.t. I decided to define an integer 2-tuple type called Xy.t for the mapping boilerplate.³

 1module Xy = struct
 2  module T = struct
 3    type t = int * int [@@deriving compare, sexp]
 4
 5    let x = fst 
 6    let y = snd
 7  end
 8
 9  include T
10  include Comparable.Make (T)
11end

Applying the functor Comparable.Make defines a type Map.t, and we include it to get Xy.Map.t to use as our sparse grid. The idiom is to define a module T, immediately include in its surrounding module (Xy in this case), and then use T as the argument to the functor. This is necessary because without T there wouldn’t be a name to pass to Comparable.Make.

The other boilerplate here is more magical. [@@deriving compare, sexp] are directives to ppx preprocessors, or code generators. ppx_compare provides the comparison functions needed to order elements in the map. ppx_sexp_conv provides conversions to and from S-expressions.⁴

I solved the puzzle naively from there: iterating the points in each line and incrementing a count, then iterating over the points and reporting how many had a count greater than 1. I had separate implementations to walk horizontal and vertical lines, starting from the left or top point and moving right or down, respectively.

Part B included the diagonal lines in the puzzle. Since the diagonal lines could be in two directions, I decided to generically implement moving from one point to another through 2-D space. I changed both solutions to use that mechanism, and the result feels neat:

 1let foldcoords startxy endxy ~init ~f =
 2  let incrx =
 3    match Int.compare (Xy.x startxy) (Xy.x endxy) with
 4    | 0 -> 0
 5    | i -> if i < 0 then 1 else -1
 6  in
 7  let incry =
 8    match Int.compare (Xy.y startxy) (Xy.y endxy) with
 9    | 0 -> 0
10    | i -> if i < 0 then 1 else -1
11  in
12  let rec loop acc currxy =
13    match Xy.x currxy = Xy.x endxy && Xy.y currxy = Xy.y endxy with
14    | true -> f acc currxy
15    | false ->
16        let acc = f acc currxy in
17        loop acc (Xy.x currxy + incrx, Xy.y currxy + incry)
18  in
19  loop init startxy
20
21let map_update = Map.update ~f:(function Some ls -> ls + 1 | None -> 1)
22
23let maplines ls unfixedf =
24  let overlaps =
25    List.fold ls ~init:Xy.Map.empty ~f:(fun acc line ->
26        let toxy s =
27          match String.split s ~on:',' with
28          | [ x; y ] -> (Int.of_string x, Int.of_string y)
29          | _ -> failwithf "unexpected coord %s" s ()
30        in
31        let startxy, endxy =
32          match Input.split_on_string line ~sep:" -> " with
33          | [ start; end_ ] -> (toxy start, toxy end_)
34          | _ -> failwithf "unexpected line %s" line ()
35        in
36        match (Xy.x startxy = Xy.x endxy, Xy.y startxy = Xy.y endxy) with
37        | false, false -> unfixedf acc startxy endxy
38        | _, _ -> foldcoords startxy endxy ~init:acc ~f:map_update)
39  in
40  Map.fold overlaps ~init:0 ~f:(fun ~key:_ ~data:os acc ->
41      match os > 1 with true -> acc + 1 | false -> acc)

Thoughts

These puzzles started to make more use of associative data structures and other “real world” tools. They also had more interesting inputs, so I started to work on a utility library to neaten up the solution boilerplate. I’m happy with my increasing comfort with OCaml idioms and better mental bookmarks: I’m starting to get a sense of the libraries that exist and how to use them.

--Chris