Advent of Code 2020: Days 4-6

Days 4, 5 and 6 of AOC were pretty uneventful, but towards the end I learned some interesting new things.

Day 4’s problems were pretty much universally disliked by everyone I talked to. The common sentiment was “this feels like work”. The input format was kind of awkward, and the actual task was basically a series of input validations.

The code is quite long:

let rec split_batch_rec lines cur acc =
  match lines with
  | [] -> cur :: acc
  | "" :: tl -> split_batch_rec tl "" (cur :: acc)
  | hd :: tl -> split_batch_rec tl (cur ^ " " ^ hd) acc

let split_batch lines = split_batch_rec lines "" []

let split_passport passport =
  passport |> String.split ~on:' ' |> List.map ~f:String.strip
  |> List.filter ~f:(fun s -> not (String.is_empty s))
  |> List.map ~f:(fun s ->
         let[@warning "-8"] [ a; b ] = String.split s ~on:':' in
         (a, b))

let is_valid_passport_lazy passport =
  let required =
    Set.of_list
      (module String)
      [ "byr"; "iyr"; "eyr"; "hgt"; "hcl"; "ecl"; "pid" ]
  in
  let fields = passport |> split_passport |> List.map ~f:(fun (a, _) -> a) in
  let fields = Set.of_list (module String) fields in
  Set.is_subset required ~of_:fields

let is_between value min max =
  let int = int_of_string value in
  int >= min && int <= max

let is_between_years value min max =
  String.length value = 4 && is_between value min max

let regex_matches value pattern =
  let open Re in
  let re = Pcre.regexp pattern in
  execp re value

let validate_height value =
  let open Re in
  let re = Pcre.regexp "^(\\d+)(cm|in)$" in
  match exec_opt re value with
  | None -> false
  | Some m -> (
      let[@warning "-8"] [| _; n; unit |] = Group.all m in
      match[@warning "-8"] unit with
      | "cm" -> is_between n 150 193
      | "in" -> is_between n 59 76 )

let validate_eye_colour value =
  List.mem
    [ "amb"; "blu"; "brn"; "gry"; "grn"; "hzl"; "oth" ]
    value ~equal:String.equal

let validate_field (key, value) =
  match key with
  | "byr" -> is_between_years value 1920 2002
  | "iyr" -> is_between_years value 2010 2020
  | "eyr" -> is_between_years value 2020 2030
  | "hgt" -> validate_height value
  | "hcl" -> regex_matches value "^#[0-9a-f]{6}$"
  | "ecl" -> validate_eye_colour value
  | "pid" -> regex_matches value "^\\d{9}$"
  | _ -> true

let is_valid_passport_strict passport =
  if is_valid_passport_lazy passport then
    passport |> split_passport |> List.for_all ~f:validate_field
  else false

let part1 lines = lines |> split_batch |> List.count ~f:is_valid_passport_lazy

let part2 lines = lines |> split_batch |> List.count ~f:is_valid_passport_strict

I ran into a few problems. First, my split_batch_rec initially looked like this:

let rec split_batch_rec lines cur acc =
  match lines with
  | [] -> acc
  | "" :: tl -> split_batch_rec tl "" (cur :: acc)
  | hd :: tl -> split_batch_rec tl (cur ^ " " ^ hd) acc

Notice the mistake? When lines is an empty list, we return acc, but ignore cur. This effectively skips the last batch.

In part 2, I came to the conclusion that my reading comprehension skills are really not as good as I think they are. I submitted around 5 incorrect answers, and each time, upon re-reading the question, I found another part that I had totally ignored.

It also reminded me of a lovely quote:

If all you have is a hammer, everything looks like a nail.

In this case, the hammer was regex. Instead of validate_eye_colour, I was using the regular expresion ^amb|blu|brn|gry|grn|hzl|oth$. It’s not really that different from my final implementation in practice, but had I not already been using regex for everything else, that certainly wouldn’t have been my first choice.

All things considered, day 4 was a slog.

Day 5 was simple enough, but still a bit more interesting than the day before. The main idea was binary space partitioning. Thankfully, it didn’t require quite so much code:

let rec bin_partition ?(min = 0) ?max chars =
  let max = Option.value max ~default:(Int.pow 2 (String.length chars) - 1) in
  if String.is_empty chars then min
  else
    let hd = chars.[0] in
    let tl = String.slice chars 1 (String.length chars) in
    let delta =
      int_of_float (Float.round_up (float_of_int (max - min)) /. 2.0)
    in
    match[@warning "-8"] hd with
    | 'F' | 'L' -> bin_partition ~min ~max:(max - delta - 1) tl
    | 'B' | 'R' -> bin_partition ~min:(min + delta + 1) ~max tl

let seat_id pass =
  let row = bin_partition (String.slice pass 0 7) in
  let col = bin_partition (String.slice pass 7 10) in
  (row * 8) + col

let[@warning "-8"] rec find_hole_in_range = function
  | x :: y :: _ when x <> y - 1 -> x + 1
  | _ :: tl -> find_hole_in_range tl

let part1 lines =
  let id = lines |> List.map ~f:seat_id |> List.max_elt ~compare:Int.compare in
  Option.value_exn id

let part2 lines =
  lines |> List.map ~f:seat_id
  |> List.sort ~compare:Int.compare
  |> find_hole_in_range

These problems made me notice was how annoying it is to work with floating point numbers in OCaml. Having to convert between integers and floats is super tedious, and makes the code a lot harder to read. I’ve had nearly identical experiences writing Go, too. But at least it’s type-safe, I guess.

Something else that really stumped me in part 1 was this:

# Some 1 |> Option.value_exn
Line 1, characters 10-26:
Error: This expression has type
         ?here:Base__.Source_code_position0.t ->
         ?error:Base__.Error.t -> ?message:string -> 'a option -> 'a
       but an expression was expected of type int option -> 'b
       
# Option.value_exn (Some 1)
- : int = 1

How are these not the exact same thing? And what in the world does this error message mean? This StackOverflow post answers the question, although I’m not quite sure that I fully understand it.

I also learned how to properly use optional arguments. In day 4, I wrote a separate split_batch_rec so that the caller of split_batch wouldn’t have to know about the implementation details of acc and cur. But with optional arguments, that problem goes away.

Lastly, I realized after seeing some other solutions that this problem can be solved really well using bit shifting instead of iteratively recalculating the bounds. I wish I had thought of that myself!

Day 6 wasn’t too challenging either, but quite fun regardless. It featured the same awkward style of input as day 4, and thankfully I learned from my previous mistake. And best of all, it required even less code!

let rec split_groups ?(acc = []) ?(cur = []) lines =
  let string_set s = s |> String.to_list |> Set.of_list (module Char) in
  match lines with
  | [] -> cur :: acc
  | "" :: tl -> split_groups ~acc:(cur :: acc) ~cur:[] tl
  | hd :: tl -> split_groups ~acc ~cur:(string_set hd :: cur) tl

let solution lines ~f =
  lines |> split_groups
  |> List.map ~f:(fun sets -> sets |> List.reduce_exn ~f |> Set.length)
  |> List.reduce_exn ~f:( + )

let part1 lines = solution lines ~f:Set.union

let part2 lines = solution lines ~f:Set.inter

I’m quite happy with this code, and especially the fact that solution works for both part 1 and 2 via f.

Outside of the problems themselves, I tried to familiarize myself with some more tooling. I wanted a way to measure how fast my code was, and I figured there ought to be something better than manually using Time.now. I found the Core_bench library and its companion ppx_bench, which did the trick nicely. Core_bench was easy to set up, but ppx_bench was not. It claims to be integrated with Dune in the same way as ppx_inline_tests, but it requires a lot more manual work to get it set up and to actually run the benchmarks. But now I can see pretty tables:

┌─────────┬─────────────┬────────────┬─────────────┬─────────────┬────────────┐
│ Name    │    Time/Run │    mWd/Run │    mjWd/Run │    Prom/Run │ Percentage │
├─────────┼─────────────┼────────────┼─────────────┼─────────────┼────────────┤
│ Day06p1 │  2_915.21us │   817.71kw │  65_372.46w │  65_372.46w │     22.62% │
│ Day06p2 │  2_662.66us │   734.04kw │  66_979.23w │  66_979.23w │     20.66% │
│ Day05p1 │    356.61us │    45.38kw │      17.80w │      17.80w │      2.77% │
│ Day05p2 │    493.10us │    76.52kw │     434.97w │     434.97w │      3.83% │
│ Day04p1 │    790.01us │   212.87kw │   1_647.97w │   1_647.97w │      6.13% │
│ Day04p2 │  4_032.83us │ 1_390.11kw │   6_054.05w │   6_054.05w │     31.29% │
│ Day03p1 │    215.26us │    25.20kw │  10_990.38w │  10_342.38w │      1.67% │
│ Day03p2 │    240.06us │    25.24kw │  10_991.08w │  10_343.08w │      1.86% │
│ Day02p1 │ 12_888.46us │ 5_034.59kw │  23_262.84w │  23_262.84w │    100.00% │
│ Day02p2 │ 12_641.70us │ 5_017.59kw │  22_811.99w │  22_811.99w │     98.09% │
│ Day01p1 │     77.50us │    10.34kw │      43.16w │      43.16w │      0.60% │
│ Day01p2 │  9_282.53us │ 1_083.12kw │ 524_193.35w │ 520_606.35w │     72.02% │
└─────────┴─────────────┴────────────┴─────────────┴─────────────┴────────────┘

I’m not entirely sure what all the columns mean, but I’m sure I’ll be able to find that info somewhere.

OCaml’s module system is one of its most interesting features, and up until now, I wasn’t using it at all. Basically, modules are first-class, and can be parameterized by other modules. Further, those module parameters can have constraints that require them to fulfill a certain interface. Since every day of AOC follows basically the same format, it fits nicely into this framework.

Here’s what I came up with:

module type Day = sig
  module Out : sig
    type t

    val equal : t -> t -> bool
  end

  val day : int

  val part1 : string list -> Out.t

  val part2 : string list -> Out.t

  val sol1 : Out.t

  val sol2 : Out.t
end

module Make (D : Day) = struct
  let lines =
    let rec find_input_file dir =
      let open Filename in
      let git = concat dir ".git" in
      let inputs = concat dir "input" in
      if Sys.is_directory_exn git then concat inputs (sprintf "%d.txt" D.day)
      else find_input_file (dirname dir)
    in
    Unix.getcwd () |> find_input_file |> In_channel.read_lines

  let part1 = D.part1

  let part2 = D.part2

  let%test "input" =
    let ( = ) = D.Out.equal in
    D.part1 lines = D.sol1 && D.part2 lines = D.sol2

  let%bench_module ("Day"[@name_suffix sprintf "%02d" D.day]) =
    ( module struct
      let%bench "p1" = part1 lines

      let%bench "p2" = part2 lines
    end )
end

So the interface that a day must fulfill is:

• A module Out that defines an output type
• A day (e.g. 1 for day 1)
• Functions that compute solutions for part1 and part2
• The solutions for part1 and part2

Here’s how day 6 uses it:

module Impl = Day.Make (struct
  let rec split_groups ?(acc = []) ?(cur = []) lines =
    let string_set s = s |> String.to_list |> Set.of_list (module Char) in
    match lines with
    | [] -> cur :: acc
    | "" :: tl -> split_groups ~acc:(cur :: acc) ~cur:[] tl
    | hd :: tl -> split_groups ~acc ~cur:(string_set hd :: cur) tl

  let solution lines ~f =
    lines |> split_groups
    |> List.map ~f:(fun sets -> sets |> List.reduce_exn ~f |> Set.length)
    |> List.reduce_exn ~f:( + )

  module Out = Int

  let day = 6

  let part1 lines = solution lines ~f:Set.union

  let part2 lines = solution lines ~f:Set.inter

  let sol1 = 6748

  let sol2 = 3445

  let%test "examples" =
    let lines =
      "abc\n\na\nb\nc\n\nab\nac\n\na\na\na\na\n\nb" |> String.split ~on:'\n'
    in
    part1 lines = 11 && part2 lines = 6
end)

By fulfilling Day’s' interface, I get input loading, tests, and benchmarks for free!

I think there’s still room for improvement with this setup. For example, the module that holds each day’s code is DayN.Impl, and I don’t know how to drop the Impl. But it doesn’t really matter much for now.

You might notice that my solutions no longer have open Core as their first line. I’m still using the library, but I figured out how to import it automatically with the dune-workspace file:

(lang dune 2.7)
(env
 (_
  (flags (:standard -open Core))))

Not lifechanging, but convenient for sure!

---

Now that I’m starting to get comfortable with OCaml, I think most of my posts going forward will cover multiple days like this one. I’m looking forward to the difficulty ramping up!

As always, feel free to check out all my code here.