Advent of Code 2019 - Day 2 - Write a simple program interpreter

The full problem statement can be found on the Advent of Code 2019 page. I recommend reading the description on their page as it goes more in-depth on the expectations. However, you can find the relevant portions below.

NOTE: All the code in this post, including this write-up itself, can be found or generated from the GitHub repository.

Problem 2a

“That computer ran Intcode programs like the gravity assist program it was working on; surely there are enough spare parts up there to build a new Intcode computer!”

An Intcode program is a list of integers separated by commas (like 1,0,0,3,99). To run one, start by looking at the first integer (called position 0). Here, you will find an opcode - either 1, 2, or 99. The opcode indicates what to do; for example, 99 means that the program is finished and should immediately halt. Encountering an unknown opcode means something went wrong.

Opcode 1 adds together numbers read from two positions and stores the result in a third position. The three integers immediately after the opcode tell you these three positions - the first two indicate the positions from which you should read the input values, and the third indicates the position at which the output should be stored.

Opcode 2 works exactly like opcode 1, except it multiplies the two inputs instead of adding them.

Problem 2b

With terminology out of the way, we’re ready to proceed. To complete the gravity assist, you need to determine what pair of inputs produces the output 19690720.

Solution

The solution to the first problem was to write a basic interpreter. Then, solving the second problem was done by using a double-loop to iterate through all the input possibilities. I considered somehow trying to reverse engineer the solution for problem 2b, but wasn’t sure if that was feasible and brute-forcing the solution seemed rather easy to do (it had an upper limit of 10,000 executions).

Rather than going into the solution (which is a basic interpreter), I’d like to highlight a piece of code that was interesting to write.

I wrote a parse to convert an input string to my Model. The Model is just a single Vec<i64>. Converting from a string to the Model looks like this:

impl From<&str> for Model {
  /// Converts a &str to a Model using the following steps:
  /// - Remove all non-digits and non-commas from the input string
  /// - Remove empty inputs (i.e. no ',,'-style scenarios allowed)
  /// - Convert the remaining inputs to `i64` values
  /// - Collect as a `Vec<i64>` for `Model.int_code`
  fn from(s: &str) -> Self {
    Model {
      int_code: s
        .chars()
        .filter(|c| c.eq(&',') || c.is_ascii_digit())
        .collect::<String>()
        .split(",")
        .filter(|s| !s.is_empty())
        .map(|s| s.parse::<i64>().unwrap())
        .collect(),
    }
  }
}

I find it immensely satisfying when I can create a long chain that performs one step per line to move towards the final goal. This is only amplified when using IntelliJ to write Rust code, because it shows the type per line. That way, if there are any questions, about type mismatches, it’s relatively easy to resolve them. This particular chain reminded me of some of the longer chains that I’ve created when writing solutions in F#.

And can I just mention that using traits in Rust is really, really nice!

All testing was done using the sample inputs only. It is actually quite difficult to come up with a random set of numbers that represents a valid Intcode program, much less basically having to write a 2nd interpreter to validate the results from the first one!

Conclusion

As always, I really enjoyed what I learned from this problem. I’m glad the logic wasn’t really complicated at all, because it allowed me to focus on the mechanics of the language and translate the solution idea into code.

See you in the next one!