Advent of Code 2024

Today's implementation will be done in OCaml. OCaml is a strongly-typed function language with automatic currying and many similarities to Haskell, but many differences, as well, perhaps most notably that it uses eager evaluation. It's also an impure language with some support for imperative programming.

OCaml also has a cool module system that we won't be using at all today, and an object system that no one really uses.

Part 1

For today's first task, we begin with an array of stones, each engraved with a number, that change every time we blink. We need to calculate how many stones you will have after 25 blinks.

The stones change each blink according to the first matching rule:

• If the stone is a 0, it is replaced with a 1.
• If the stone has an even number of digits, it is replaced with two stones, where the left and right stones have the left and right digits of the number, respectively (ignoring leading 0's).
• Otherwise, the stone is replaced by one with the same value multiplied by 2024.

We will need a function read_int_list to read the input file, and a function apply_blinks that takes a stone and returns how many stones it will be after n blinks. Then we can get our result by sum the result of mapping apply_blinks over the initial list. We'll also use a hash table so that we can cache apply_blinks results as it recurses. Note that apply_blinks will take 3 arguments (the cache, the number of blinks, and the stone), but as OCaml (like Haskell) uses automatic currying, we can make a function that only accepts the third argument simply by only calling it with two arguments:

let () =
  let stones = int_list_of_string (read_first_line "2024/input/day-11.txt") in
  let cache : ((int * int), int) Hashtbl.t = Hashtbl.create 10 in
  stones
  |> List.map (apply_blinks cache 75)
  |> List.fold_left (+) 0
  |> Printf.printf "%d\n"

This uses the pipeline operator |>, which applies its righthand-side to its lefthand-side (like & in Haskell), ie, x |> f is the same as f x.

The read_int_list definition is straightforward, only introducing some file-related functions and exception-handling:

let read_int_list filename =
  let in_channel = open_in filename in
  try
    let first_line = input_line in_channel in
    close_in in_channel;
    first_line
    |> String.split_on_char ' '
    |> List.map int_of_string
  with e ->
    close_in in_channel;
    raise e

To prepare for implementing apply_blinks, we'll define two helper functions first, one for checking if an integer has an even number of digits, and another for getting the two halves of its digits:

let even_digits n =
  let num_str = string_of_int n in
  let num_length = String.length num_str in
  num_length mod 2 = 0

let split_number n =
  let string = string_of_int n in
  let middle = (String.length string) / 2 in
  let first_half = int_of_string (String.sub string 0 middle) in
  let second_half = int_of_string (String.sub string middle middle) in
  [first_half; second_half]

For implementing apply_blinks, we will follow a simple algorithm:

• Any stone will continue to be 1 stone after 0 blinks.
• If this call is cached, use the cache result.
• If the stone is 0, calculate the next value with a stone of 1.
• If the stone has even digits, split them and sum the result of applying num_blinks - 1 blinks to both halves.
• Otherwise, recurse with stone * 2024.

We will also use Hashtbl.find_opt which returns an option type depending on whether the value was found (eg, Some 23 or None). To consider both possibilities, we use pattern-matching with the match...with construct:

let rec apply_blinks (cache : (int * int, int) Hashtbl.t) (num_blinks : int) (stone : int) =
  if num_blinks = 0 then
    1
  else
    match Hashtbl.find_opt cache (stone, num_blinks) with
    | Some value -> value
    | None ->
       let (result : int) =
         if stone = 0 then
           apply_blinks cache (num_blinks - 1) 1
         else if even_digits stone then
           split_number stone
           |> List.map (apply_blinks cache (num_blinks - 1))
           |> List.fold_left (+) 0
         else
           apply_blinks cache (num_blinks - 1) (stone * 2024);
       in
          Hashtbl.add cache (stone, num_blinks) result;
          result

Our code now works and produces the correct result.

Part 2

For part 2, we only need to change 25 blinks to 75, which would be infeasible for a naive implementation. Due to our efficient strategy, our code continues to work. Here it is in full, with the parameter changed to 75:

let even_digits n =
  let num_str = string_of_int n in
  let num_length = String.length num_str in
  num_length mod 2 = 0

let split_number n =
  let string = string_of_int n in
  let middle = (String.length string) / 2 in
  let first_half = int_of_string (String.sub string 0 middle) in
  let second_half = int_of_string (String.sub string middle middle) in
  [first_half; second_half]

let rec apply_blinks (cache : (int * int, int) Hashtbl.t) (num_blinks : int) (stone : int) =
  if num_blinks = 0 then
    1
  else
    match Hashtbl.find_opt cache (stone, num_blinks) with
    | Some value -> value
    | None ->
       let (result : int) =
         if stone = 0 then
           apply_blinks cache (num_blinks - 1) 1
         else if even_digits stone then
           split_number stone
           |> List.map (apply_blinks cache (num_blinks - 1))
           |> List.fold_left (+) 0
         else
           apply_blinks cache (num_blinks - 1) (stone * 2024);
       in
          Hashtbl.add cache (stone, num_blinks) result;
          result

let read_int_list filename =
  let in_channel = open_in filename in
  try
    let first_line = input_line in_channel in
    close_in in_channel;
    first_line
    |> String.split_on_char ' '
    |> List.map int_of_string
  with e ->
    close_in in_channel;
    raise e

let () =
  let stones = read_int_list "2024/input/day-11.txt" in
  let table : ((int * int), int) Hashtbl.t = Hashtbl.create 10 in
  stones
  |> List.map (apply_blinks table 75)
  |> List.fold_left (+) 0
  |> Printf.printf "%d\n"