Advent of Code 2020: Day 1

It’s December! That means that Advent of Code 2020 began today! In case you don’t know, Advent of Code is a series of daily programming puzzles published every December. You can compete to be among the fastest finishers, brush up on your algorithmic chops, learn a new language, or just have fun with something you already know. Last year, I made it about halfway through with Elixir. This year, I’m expanding my toolbox by picking up OCaml, another functional programming language, but a statically typed one this time. I’ve wanted to learn it for a long time, but I’ve never really found the time to commit. For as long as I can keep up with the puzzles, I’ll be posting about my experiences with the puzzles and OCaml every few days.

Day 1’s puzzles tend to be pretty simple, so I’m using this evening to familiarize myself a bit with OCaml’s tooling and development environment. I’ve previously used Tuareg and Merlin for Emacs integration, but I thought I’d try out the LSP server this time around. This experiment didn’t last long. The LSP server seemed to require more than the minimum amount of Emacs configuration, so I figured I’d avoid wasting time and just use what I knew worked. Next, I set up a Dune project according to this post, although I only did the minimal work required to get started.

In the past, my attempts at learning OCaml have been plagued by a lack of accessible documentation on its ibraries and build system. I’m hoping that the small amount of Dune configuration I’ve already done will last me for a long time, so I can focus on the actual code. I’m using Jane Street’s Core standard library, which seems to have better documentation than most other libraries I’ve seen, but even then, it can be fairly cryptic with not much more than type signatures. In general, I find OCaml’s learning resources to be quite academic, which reflects its typical usage I guess.

Day 1’s problems are the “two-sum” and “three-sum” problems, where you need to find two or three numbers in a list that add up to a specified value, and in this case, multiply them together to get your final answer. I haven’t practiced algorithms for a long time, so I’ve forgotten a lot of the strategies for writing efficient code, but that’s alright. I spent a while writing a brute-force two-sum solution, where most of the time was spent figuring out the very basics of OCaml, and where various standard library functions were for reading files, converting strings, and understanding the compiler errors. Pretty much immediately after I solved it, I remembered the more efficient method, so I scrapped what I had and implemented it again.

Here’s what I ended up with:

open Core

let rec two_sum_product xs target set =
  match xs with
  | [] -> raise (Invalid_argument "No solution")
  | hd :: tl ->
      let comp = target - hd in
      if Set.exists set ~f:(( = ) comp) then hd * comp
      else two_sum_product tl target set

let part1 xs target =
  let set = Set.of_list (module Int) xs in
  two_sum_product xs target set

I feel like it’s pretty readable. It made for a nice introduction to OCaml’s recursion, partial function application, and pattern matching.

Part 2 didn’t feel much harder than part 1 once I had the data structure in mind, and the process of actually writing the code went a lot smoother now that I had a better idea of what the compiler was telling me. There are some parts that seem a bit smelly, but it works! Similar to my few brief adventures with Rust, once my code compiled, it basically did exactly what I wanted it to.

open Core

let three_sum_table xs =
  let tbl = Hashtbl.create (module Int) in
  let idxs = List.mapi xs ~f:(fun i x -> (i, x)) in
  let _ =
    idxs
    |> List.cartesian_product idxs
    |> List.filter ~f:(fun ((i, _), (j, _)) -> not (i = j))
    |> List.map ~f:(fun ((i, a), (j, b)) ->
           Hashtbl.add tbl ~key:(a + b) ~data:(i, j))
  in
  tbl

let rec three_sum_idxs xs target tbl =
  match xs with
  | [] -> raise (Invalid_argument "No solution")
  | (i, x) :: tl -> (
      let comp = target - x in
      match Hashtbl.find tbl comp with
      | Some (j, k) ->
          if i = j || i = k then three_sum_idxs tl target tbl else (i, j, k)
      | None -> three_sum_idxs tl target tbl )

let three_sum_product xs i j k =
  let arr = Array.of_list xs in
  arr.(i) * arr.(j) * arr.(k)

let part2 xs target =
  let tbl = three_sum_table xs in
  let with_idx = List.mapi xs ~f:(fun i x -> (i, x)) in
  let i, j, k = three_sum_idxs with_idx target tbl in
  three_sum_product xs i j k

OCaml certainly has some quirks, but I had fun struggling through these first problems and I think it’ll only get more enjoyable as I get more comfortable and productive. See my code for each day here!

Edit (12/02): Reformatted the code with ocamlformat. Also, I realize now that my part 2 solution isn’t the most efficient algorithm, but I don’t really care. Learning the language is more important to me than writing optimal code, especially so early on. I’m more annoyed with my janky Hashtbl population than the fact that I shouldn’t have used one at all!