Mar 02 2020

Advent of Code 2019, The Intcode Problems

Every Year Advent of Code releases a holiday themed series of programming puzzles, unlocked in small bundles from December 1st through 25th. While I've been aware of the challenge in the past, this was my first year digging in to the puzzles in earnest.

For Advent of Code 2019 I focused on solving the series of related puzzles featuring the fictional "Intcode Computer" used to operate Santa's interplanetary sleigh. The Intcode interpreter is introduced on day 2 of the calendar, and then used for increasingly more complex tasks on all odd numbered days from day 5 through 25.

Since the core of these puzzles involves building and using an interpreter for an esoteric programming language, it seemed natural to use OCaml, a language with a solid history in PL and compilers. As a twist, I've been meaning to try out ReasonML for a while, so I chose to give Reason's syntax and tooling a shot.

My Intcode interpreter and puzzle solutions are available on github.

What I learned

Thoughts on OCaml, ReasonML, and AoC19, in no particular order:

  • OCaml's module system is powerful and lends itself well to modeling a problem domain. I saw this proved out over and over, but one example that stood out to me was on day 9 which adds the requirement "The computer should have support for large numbers." Up until that point I had performed all operations on

    int
    s, but to meet this new requirement I had to refactor everything to
    int64
    . I was able to encapsulate the extra complexity and refactor cleanly by creating the
    Intcode.Memory.Value
    and
    Intcode.Memory.Address
    modules.

  • The first time I used OCaml I had a lot of trouble understanding how to use Polymorphic Variants. Now that I'm revisiting the language with the added context of structurally typed languages such as Typescript, Polymorphic Variants seem much more natural. In the

    Intcode.Instruction
    module I use this language feature to define the
    Value
    ,
    AbsoluteAddress
    , and
    RelativeAddress
    variants, which represent the three ways an Intcode integer can be interpreted. By using appropriate combinations of these types we can accurately encode interpreter rules into the types. It's a light splash of more flexible structural typing into a nominally typed language.

  • In an early version of my Intcode interpreter I used

    Result
    types to track every Intcode operation that could fail, threading through the computation state and returning a final value or error. While this technique works well for many real-world use cases, I decided that in the constrained world of solving puzzles with well-defined inputs it was too much overhead. Errors would only ever trigger if there was a bug in my code, so failing fast with an exception proved more valuable than rigorously accounting for every case with
    Result
    s.

  • ReasonML's standard library leaves a lot to be desired. I ended up going with Belt, which is also far from perfect. It's still unclear to me why I can't use a well established OCaml utils library such as core, but I didn't really research the issue.

  • I also noticed a mismatch between data-first libraries that use the fast-pipe operator

    ->
    , and data-last libraries that use the
    |>
    pipe operator. This wasn't much more than an inconvenience, but it seems like an unnecessary pain point for new users. I ended up using
    ->
    , which comes with some kind of macro for designating the curried value with an underscore, e.g.
    str->Js.String.split(",", _)
    .

  • In OCaml

    is used for "type-driven code generation." I don't have a lot of experience with this tooling, but it's particularly useful for things like
    [@@deriving show]
    which generates functions to pretty-print complex data structures. BuckleScript has a little bit of this functionality built in with features like
    [@bs.deriving accessors]
    , but it's pretty limited. The
    bs-deriving
    library claims to have ported
    ppx_deriving
    to BuckleScript, but it uses pre-compiled binaries that I couldn't get working on my system. It would be nice if more
    deriving
    features were folded into BuckleScript, or even introduced at the Reason level.

  • The puzzles in this series can be split between Intcode implementation problems and application problems. I liked this, since it meant that I had to think about both the internal organization of the interpreter, and the external "Intcode Computer" API. You can see this play out for problems such as day 7, where 5 separate "computers" perform calculations in series.

  • Advent of code is very time consuming! Each day is a 2-part puzzle, so doing the full calendar means solving 50 moderately-involved programming puzzles.

Progress and Roadblocks

Day 13 is complete, day 15 is unfinished. I lost steam on this project shortly after New Year's, both because I ran out of free time and because day 15 throws in a new twist which I've found to be frustrating more because of language limitations than because of inherent complexity.

From a code complexity perspective day 15 could be solved by either over-engineering the repair droid as an autonomous unit that explores its surroundings, or by simply allowing a user to input directional commands to navigate to the goal. Unfortunately implementing the simple solution in the terminal with Reason and the underlying node runtime is proving difficult. Node's callback style doesn't mesh well with Reason, and I haven't found a way to get the program to block execution while waiting for user input. It's a mess!

If I were to revisit this project I might try to build a simple ReasonReact app to run the Intcode program and process user input in the browser. This solution would potentially unlock many of the subsequent puzzles for me, since user input plays a large part in the later Intcode puzzles.

Elias Mulhall

Share: