Advent of Code 2021: Day 1

Ah, it has begun! The story this year is pretty good:

You’re minding your own business on a ship at sea when the overboard alarm goes off! You rush to see if you can help. Apparently, one of the Elves tripped and accidentally sent the sleigh keys flying into the ocean!

Of course, our first instinct is to climb into the handy to have submarine and get to work! The puzzle input is a list of numbers, each measuring the depth of the water. First, I need to calculate the (rough) rate of change by counting the number of times the depth increases.

This is a pretty simple job for some quick recursion!

let rec p1_sol input count   match input with
  | []
  | [ _ ] -> count
  | h1 :: h2 :: t ->
      if h1 < h2 then p1_sol (h2 :: t) (count + 1) else p1_sol (h2 :: t) count

Here, input is the list of numbers and count is how often it has increased. I match on the full list to see if there are at least 2 elements, so I can compare them. If the second is higher, I increment the count by one. I pass the rest of the list, including the second element, back to my function to compare it to the next element and so on until the list is processed, and all in one pass!

I find it interesting that recursive functions in ocaml must explicitly be marked as recursive with the rec tag. This goes for mutually recursive functions, too! They use rec and and to indicate that one may call the other and vice versa. I am not sure why this is, but I assume it is to indicate to the compiler that, while p1_sol doesn’t exist yet, it is currently being defined and don’t worry too much.

⭐ one done!

Problem 2

It turns out that the first result is too noisy, and that by taking the sum of 3 elements as a sliding window would help a lot more. This helps to understand trends better in situations where individual data points vary wildly. This requires a slight modification to the original solution, but not by much.

let rec p2_sol input count   match input with
  | []
  | [ _ ]
  | [ _; _ ]
  | [ _; _; _ ] -> count
  | h1 :: h2 :: h3 :: h4 :: t ->
      if h1 + h2 + h3 < h2 + h3 + h4 then
        p2_sol (h2 :: h3 :: h4 :: t) (count + 1)
      else p2_sol (h2 :: h3 :: h4 :: t) count

Instead of grabbing the first 2 elements, the first 4 are required. The rest is the same. I sum the windows, compare them, and increment if necessary. Only the first element is discarded, so the windows slide smoothly over the list.

While this might seem easy, I know the challenge is coming quickly. I think if I was reviewing this code, I would have dropped the match statement and checked the list’s length instead, to drop the similar matches. Although, I bet there is a version of this typed such that the list is guaranteed to have 2 and 4 elements, similar to the non-empty list shown in Alexis King’s wonderful Parse, don’t validate. A challenge for another time, though.

Want to discuss this post?

Reach out via email to ~afontaine/blog-discuss@lists.sr.ht, and be sure to follow the mailing list etiquette.