Dec 1, 2018
Advent of Code is a series of daily programming puzzles created by Eric Wastl and published daily in the month of December. I wrote one post on last year’s challenges, but this year would like to write about them more frequently, while the solutions are top-of-mind. Do not read this if you would like to solve these challenges without any assistance!
For 2018, I plan to do all of the challenges in ReasonML. I write a lot of JavaScript at my current job, and I thought it’d be interesting to see how it compares to my experience with Flow and TypeScript. I hope to produce some Clojure solutions as well, as a point of comparison (and because doing it Clojure was a lot of fun last year).
The first problem required reading inputs representing “frequency changes” that look like "-1" and "+43".
The goal is to determine the result of starting from a frequency of 0 and applying those operations.
For example, applying the two changes above would produce 42.
Here is my Reason solution.
I decided early that I wanted to have a type to represent a “frequency change” and wrote a function that could take a string of one such change, and return a frequencyChange (something that I didn’t realize prior to today was that ReasonML types must start with a lower-case letter).
A frequencyChange is a two-ple of an operation and an amount. operation is an alias of char, and amount is an alias of Int32.t (as I understand it: Int32 is a module, and t is the member of the module which returns the module’s type).
My initial solution used int instead of Int32.t, but I switched to Int32 while implementing the solution to the second problem, as I’ll detail below.
The solution turns the raw input into a list of change strings, turns the change strings into frequencyChange two-ples, and then folds over the frequencyChanges to product the final frequency.
It might be clearer to just see the highest-level code:
inputLines()
|> List.map(lineToFrequencyChange)
|> List.fold_left(applyFrequencyChange, Int32.zero);
The second problem was a bit trickier: figure out the first frequency result to be computed twice, applying the list of changes as many times as is required to find such a repeat.
Clojure has a handy cycle function that would take the list of changes and return an infinite, lazy sequence of those changes, repeating ad infinitum – exactly the kind of sequence we’d like to iterate over to solve this problem.
Unfortunately, I did not see anything like that in the Reason standard library.
After some false starts, I ended up on the API docs for Streams and figured out how to make a Stream that would behave like cycle, yielding the first item in a list after it yielded the last item in the list.
let circularStream = (l: list('a)): Stream.t('a) => {
let length = List.length(l);
Stream.from(i => Some(List.nth(l, i mod length)));
};
To keep track of which frequencies had been computed, I wanted to use a set.
I found the Set documentation a little confusing at first, but the example helped make things click: there’s not a general-purpose set constructor or type.
Instead, there’s a Set.Make “functor” which takes a type and returns a module that contains functions for operating on sets of that type.
The way I’m thinking about it is: rather than having a Set library, there’s a Set library-maker, for any type that knows how to compare two of its values.
This led me to rewrite all of the int-based frequency expressions to use Int32; as far as I can tell, there’s no way to use Set.Make with int.
With my cycling stream and a set module, I was able to write a while loop that takes items from the stream, computes the next frequency, and adds it to a set of known frequencies.
If the next frequency is already known, it’s our solution.
Overall, I’m pretty sure there’s a lot that’s not quite idiomatic about these solutions, but I am happy to have found the correct results!
The two specific questions I have are:
refs?