Advent of Code - Part 1

Two weeks ago, a friend challenged his entire friend group to participate in Advent of Code. Normally, I’d accept to put my Python prowess on display (I like to show off with that language). While mentioning the challenge to Jason, he pointed out the obvious fact that Hemlock has a complete bootstrap standard library in OCaml and that using it would be an even greater flex to my friends. Additionally, I’d gain some practical benefit. While I’ve implemented a bit and reviewed a lot of our bootstrap library, I haven’t had a reason to use most of it. It was pretty easy to convince myself that this would be useful and fun, so I accepted my friend’s challenge.

These are the goals I set for myself.

• Finally build a tolerable OCaml/Hemlock programming environment
  • Switch from Visual Studio Code back to tmux+Vim
  • Make sure my debugging tools (GDB, utop) are working
  • Enable OCaml LSP in Vim
  • Enable OCaml code completion in Vim
• Use data types I haven’t mastered
  • Lazy.t (We’re just using the OCaml version in our bootstrap library)
  • Stream.t
  • Set.t
  • Ordmap.t
• Use the control-flow mechanisms that will be useful or blazingly fast in native Hemlock
  • Lazy.force (Again, the underlying OCaml implementation)
  • Array.map
  • Array.reduce
• Solve every problem.
• Beautify and translate at least one solution into native Hemlock.

Programming Environment

While I already had a semi-effective OCaml environment set up in Visual Studio Code, I’d become increasingly unhappy with accumulating brittleness. Some combination of me, the editor, and plugins (OCaml Platform, remote-containers, Markdown All in One, rewrap, vscodevim) caused repeated data loss in my workspace. It pushed me to return to simple, reliable tmux and Vim and to try out a few fun remote development workflow ideas I wanted to explore. I had to stop myself after nearly a week of polishing to start making progress on Advent of Code problems. My awesome development environment will be the subject of a future blog post.

Lazy.t and Stream.t

As of writing this, I’ve solved just four of the available eighteen problems. With one small exception where I used a two-dimensional Array.t, Stream.t is the hammer I used in each solution. Here’s a typical example of almost every function I’ve written, transforming a bytes slice stream into a byte stream in solution #3.

val byte_stream_of_bytes_slice_stream: Byte.t Stream.t -> Bytes.Slice.t Stream.t

let byte_stream_of_bytes_slice_stream bytes_slice_stream =
    let rec f i bytes_slice bytes_slice_stream = begin
        match i = Bytes.Slice.length bytes_slice with
        | true -> begin
            match Stream.is_empty bytes_slice_stream with
            | true -> Stream.Nil
            | false -> begin
                let bytes_slice, bytes_slice_stream = Stream.pop bytes_slice_stream in
                f 0L bytes_slice bytes_slice_stream
              end
          end
        | false -> begin
            let byte = Bytes.Slice.get i bytes_slice in
            Stream.Cons (byte, lazy (f (i + 1L) bytes_slice bytes_slice_stream))
          end
    end in
    lazy (f 0L (Bytes.Slice.init [||]) bytes_slice_stream)

In each problem, I have a long chain of small Stream.t transformations that eventually results in the solution. Here are the transformations I made along the path to solving problem 3.

let () =
    "p03.input"
    |> String.C.Slice.of_string
    |> Bytes.Slice.of_string_slice
    |> File.of_path_hlt
    |> File.Stream.of_file
    |> byte_stream_of_bytes_slice_stream
    |> byte_stream_stream_of_byte_stream
    |> uns_stream_stream_of_byte_stream_stream
    |> fun uns_stream_stream ->
        uns_stream_stream
        |> bias_of_uns_stream_stream
        |> p03a_answer_of_bias
        |> fmt_answer "p03a";
        uns_stream_stream
        |> p03b_answer_of_uns_stream_stream
        |> fmt_answer "p03b";

I’m pretty happy with how easy it is to adapt Stream.t in manageable steps. When confronting a problem where it’s possible to discard past data, it feels right.

An Opportunity for Array.map

Day 15 is the only problem I solved where I thought a data structure other than Stream.t was warranted. The problem is nearly identical to Project Euler’s problem 83, which I solved ten years ago. I solved it again in almost exactly the same way.

In short, the task is to find the least-cost path from point A (the top-left corner) to point B (the bottom-right corner) within a two-dimensional array. Progressively adapting the data streams ('a Stream.t -> 'b Stream.t) throughout became impractical as my algorithm required backtracking to update a calculated cumulative cost array.

I find this problem interesting because I progressively built up a cumulative cost array with iteration by row and column, backtracking by one column and one row any time a cost is updated. I think this is actually easier to solve via an iterative map algorithm and I expect to revisit this problem to do just that.

1. Output the starting coordinate, (0, 0), to step 2.
2. Map - Evaluate all coordinates neighboring input coordinates (initially (0, 1), (1, 0)) to see if the cumulative cost of reaching them shrinks.
3. Gather coordinates where cumulative cost changed in step 2. Output these back to step 2. If there are no coordinates to output, the cumulative cost map is complete and the cost of reaching the bottom-right corner of the cumulative cost array is the answer.

Discrete cost (input data)
+---+---+---+---+---+---+
| 6 | 5 | 1 | 1 | 3 | 2 |
+---+---+---+---+---+---+
| 4 | 9 | 3 | 1 | 5 | 6 |
+---+---+---+---+---+---+
| 3 | 4 | 1 | 7 | 1 | 1 |
+---+---+---+---+---+---+
| 9 | 1 | 2 | 8 | 1 | 3 |
+---+---+---+---+---+---+
| 9 | 9 | 1 | 2 | 4 | 2 |
+---+---+---+---+---+---+
| 5 | 4 | 2 | 1 | 6 | 3 |
+---+---+---+---+---+---+

Cumulative cost (initial value)
+---+---+---+---+---+---+
| 0 | - | - | - | - | - |
+---+---+---+---+---+---+
| - | - | - | - | - | - |
+---+---+---+---+---+---+
| - | - | - | - | - | - |
+---+---+---+---+---+---+
| - | - | - | - | - | - |
+---+---+---+---+---+---+
| - | - | - | - | - | - |
+---+---+---+---+---+---+
| - | - | - | - | - | - |
+---+---+---+---+---+---+

Cumulative cost (final value)

+---+---+---+---+---+---+
| 0 | 5 | 6 | 7 | 10| 12|
+---+---+---+---+---+---+
| 4 | 13| 9 | 8 | 13| 18|
+---+---+---+---+---+---+
| 7 | 11| 10| 15| 14| 15|
+---+---+---+---+---+---+
| 16| 12| 12| 20| 15| 18|
+---+---+---+---+---+---+
| 25| 21| 13| 15| 19| 20|
+---+---+---+---+---+---+
| 24| 19| 15| 16| 22| 23|
+---+---+---+---+---+---+

We expect map to be extremely valuable in Hemlock since it’ll provide the best opportunities for parallelism via work stealing. Now that I’m sufficiently-practiced with Stream.t, I plan to hammer away at a few problems with Array.map.