Advent of Code using functional programming in TypeScript day 1
The advent of Code is an annual event where developers from all around the world solve Christmas-themed programming challenges. It has been running since 2015 and, what’s important, it doesn’t enforce usage of any particular language or paradigm! I believe it’s a perfect opportunity to try new things and learn exciting concepts such as functional programming in TypeScript.
TypeScript and functional programming
But first things first, some rules: I won’t write about the academic and theoretical approach to functional programming. We’ll focus on pragmatism and we’ll try to solve these challenges using as much FP as it makes sense but no more. Interested? Oh, and we’ll use TypeScript for that.
TypeScript might seem like an unusual choice for functional programming but that’s exactly what makes it amusing. Maximising the gains of FP and minimising the risks of going too esoteric is both thought-provoking and fun!
Note: I’m omitting the implementation of all the functions in the examples below on purpose. They’re all pretty standard and can be imported from libraries such as
ramda or even
lodash/fp with only minor modifications. I highly recommend this follow-up read.
Advent of Code day 1
I’ll skip the atmospheric background the authors of Advent of Code introduce us to and I’ll just get straight to the point. You, on the other hand, are more than welcome to read the whole description of the task here: https://adventofcode.com/2021/day/1
We get a bunch of numbers and we need to determine how many of them are larger than the previous one. For example:
199 (N/A - no previous measurement) 200 (increased) 208 (increased) 210 (increased) 200 (decreased) 207 (increased) 240 (increased) 269 (increased) 260 (decreased) 263 (increased)
In the above example, the answer is 7.
Let’s assume we get the input as an array of numbers named
data. It might be tempting to create some kind of variable to keep count and a
for-loop… but forget all that! We’re going to take another approach here. More functional, if you will. To determine if the value is larger than the previous one, we could pair the value with its predecessor. So we pair 199 with 200, 200 with 208, 208 with 210 and so on:
199 -> 200 200 -> 208 208 -> 210 210 -> 200 200 -> 207 207 -> 240 240 -> 269 269 -> 260 260 -> 263
In functional programming, we call this operation
I’m not sure if you’ve noticed it yet but if you squint your eyes a bit it’s almost is we were zipping an array with the same array minus its first element. Let that sink in. What it means is that we could drop the first element from the array and zip it with the original array. Or speaking in TypeScript:
zip(data, drop(data, 1));
Solution in TypeScript
You might be confused about where this is all going but please, bear with me for just a few more minutes. We get an array of pairs and now we need to remove the ones where the second element is not larger than the first. Or, we could subtract them and only keep negative values. In functional programming, there’s a function named
zipWith which might come useful here instead of just
zip. Instead of creating a pair of values, it applies a function to it (
subtract in our case):
zipWith(data, drop(data, 1), subtract);
Now, all we have to do is keep only negative values and get the length of the resulting array:
length( filter( zipWith(data, drop(data, 1), subtract), (x) => x < 0 ), );
Advent of Code day 1 part 2
Part 2 of the first Advent of Code task is just a wee bit more difficult. Instead of comparing one value to another, we’re now asked to compare sums of a three-elements sliding window. Applying the same thinking as previously yields:
199+200+208 -> 200+208+210 (increased) 200+208+210 -> 208+210+200 (same) 208+210+200 -> 210+200+207 (decreased) 210+200+207 -> 200+207+240 (increased) 200+207+240 -> 207+240+269 (increased) 207+240+269 -> 240+269+260 (increased) 240+269+260 -> 269+260+263 (increased)
And the correct solution is 5.
Don’t panic yet, there’s no need to reimplement everything!
We can vastly simplify part 2 if we notice that some of the numbers always repeat on both the left-hand side and right-hand side. In the first row, 200 and 208 are on both sides, in the second row 208 and 210, in third 210 and 200 and so on… It seems we could only compare left-most and right-most numbers and still get correct results:
199 -> 210 (increased) 200 -> 200 (same) 208 -> 207 (decreased) 210 -> 240 (increased) 200 -> 269 (increased) 207 -> 260 (increased) 240 -> 263 (increased)
As it turns out, thanks to our functional implementation, part 2 problem is the same as part 1 and the only variable is the number of elements we have to drop before zipping! We set it to
3 instead of
1 and our final solution becomes:
length( filter( zipWith(data, drop(data, 3), subtract), (x) => x < 0 ), );
Advent of Code in functional TypeScript: day 1
This is it for day one! We’ve successfully managed to solve the first challenge in Advent of Code 2021 in a functional manner using TypeScript. Note that we’ve avoided quite a few pitfalls that we most likely would’ve stumbled upon had we used imperative programming paradigms.
For example, we never really worried about edge cases such as the first or the last element in the array not being paired with anything – we simply ignored it and everything still worked out just fine.
Moreover, we didn’t have to redo all the analysis and implementation for part 2 of the problem thanks to the design we’d chosen – instead we only adjusted a single parameter even though part 2 initially looked vastly different from part 1.
Thank you and I hope you enjoyed it!