A Functional view over Dart with Advent Of Code
Today we are going to take a look on AOC 2019 solutions using Dart. We will try to focus on it through a different side, trying to figure it out how to solve the problems with Dart functional side.
Dart is a clientoptimized language for fast apps on any platform.
Dart is an amazing language, which Iâm having so much fun coding with it. The syntax is pretty straight forward if you know Kotlin, Swift or JavaScript (itâs kinda of a mixup). We have all the desirable features of a modern language: OOP, async/await builtin support, functional collection APIs (map
, where
, reduce
, fold
, etc.), spread operator, static typing (but with a powerful type inference) and a lot more. Important to notice that this article is being written as of Dart 2.7
, so we already have the brand new Extensions
functionality, which we might explore in another post.
Advent of Code 2019 đ
We will get to learn about Dart going through my solutions for the AOC 2019. Advent of Code runs through the days 0125 of December (Advent time for christians), with two different problems each day. The second is normally built up on top of the first problem, and it is only made available for the âcontestantsâ after solving the first one. You can find out more about AOC on their official website.
Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.
I really encourage you to take on it next year, or solve the past ones as they continue available. I think it is a great opportunity to learn a new programming language, or if you are a really tryhard competitor, you can try to go for the leaderboar with your mastered language.
How will it work đ
We will go through the day, but not all of them, as some of them are not that interesting for our point of view, but we will at least explain how it was meant to be done, just in case you are here looking for the solutions. We will be relying on the code available at my Advent Of Dart repository.
Day One đ
We will from the beggining. Day one, The Tyranny of the Rocket Equation.
On part one, we have as our input a list of rocket module masses, and we need to compute the quantity of fuel needed to lift each rocket module using the formula fuelRequired = floor(mass / 3)  2
. We will assume that we have our problem input, the module masses, on an List<int>
.
List<T>
is a generic data structure available natively at Dart, for any typeT
. Throghout this article we will use the Dart syntaxDataStructure<T>
which means aDataStructure
which holds elements of typeT
. So, for instance,List<int>
is a list with elements of typeint
. Moving on.
This program can be solved with the following oneliner:
The fold
function has the following signature: T fold<T>(T initialValue, T Function(T previousValue, E element) combine)
. For those who know how reduce
works, it is similar, but we need to pass an obligatory initialValue
. It works combining the list on which it is iterating, accumulating the value for the next iteration. This is:
 It starts with the value
initialValue
and calls thecombine
function passinginitialValue
and the first value of theIterable
(the thing we are iterating).  The value returned by the first iteration is then passed for the next iteration, together with the second
Iterable
value.  And so onâŚ
Something really nice on Dart is the Iterable<T>
interface, which is something that we can iterate over. The great power on it comes from the fact that you doesnât need to store the entire data inside of it in memory, if you can compute it on the go. We will see more about it on the rest of the article. You can learn more about it on Dart official Iterable documentation.
Pretty nice, uh? That is the functional power. We just iterate over our list, passing the accumulated value ahead until we have applied the formula for all the elements. Also interesting to notice is the ~/
operator, that is the integer division operator in Dart.
Why didnât you use
reduce
?
Because in Dart Iterable.reduce<T>
only receives a combine
function as parameter, and assumes that the initial value is the first value of the array. But we donât want that, because we need to apply the formula to it. So, we use fold
to start with a sum neutral value: 0.
For part two, we need to build up on top of Part 1 problem. Every fuel we add to the rocket, is also counting as mass. So we need to compute the required fuel to be able to lift up the rocket with the already added fuel. We also need to take this fuel in consideration, and so on. The recursion ends when we would need less than 0 fuel, and we say that âit is handled by wishing really hardâ according to AOC. A recursive implementation can be seen below, also using fold
.
Day Two đĽď¸
Day 2 refers to the first problem using the IntCode interpreter. We wonât talk about IntCode programs on this article, as I coded them on a pretty objectoriented manner. Every odd day after day 4 is an IntCode program, so they wonât be listed. Maybe we can talk about the features used on it (Enum, Queue, Map, Extensions) on a future article.
Day Three â
Day 3, Crossed Wires, offers a pretty basic introduction to Iterable.map<T>
, and an overview on Iterable.reduce<T>
which is pretty similar to fold
as stated before.
For part one, given 2 lists of points, we need to find the closest point to the origin (using Manhattan Distance) which belongs to both the lists. We will assume that the list of points are represented by a Dart Set<Point<int>>
, which is an ordered data structure that holds unique elements on it. When refering to a Point<int>
, unique means same and same values.
Basically, we create a Set<Point<int>>
with the intersection between the points, and we âmapâ over them computing the distance to the origin. By âmapâ, on Dart, we are refering to the Iterable.map<T>(T Function(E element) f)
function. When called on an Iterable
it calls the function f
for each element
of the current Iterable, producing a new element for each of them.
After this, we only need to take the minimum value on this list of int
. On Dart, the min
function doesnât work with an Iterable
(like Python would), but only with two parameters a
and b
, returning the minimum of them. So we can use the Iterable.reduce<T>
function, which works similary to the fold
one, which was explained before, with the difference that its initialValue
is always the first element of the Iterable
.
Earlier, we created an anonymous function inside the fold
function parameters. Now, we have something better. reduce
will be waiting for a function which receives two integers and return an integer (so we can compute our minimum value). Instead of creating an anonymous function such as (acc, val) => min(acc, val)
, we can pass the raw min
function, as it already receives two parameters and return the minimum of them. So our oneliner (assuming we already have the points) is the following:
Day Four đŚ
Secure Container wasnât much of a functional algorithm. The algorithm I coded is a simple iterative function that goes through the string trying to find the valid strings naively.
Day Six đŞ
Remember Day Five is skipped as every odd number after it (and including it) refer to IntCode programs
On Day 6, Universal Orbit Map, for part one, given a DAG, we need to sum all the distances from every node to the root of it.
We will assume our DAG is represented by a Dart Map<String, List<String>> graph
which is basically an adjacency list, where every node is represented by a String
. When we acess graph[node]
(being node a String
) we access all the nodes which point to our node. This is, if we had a DAG such as , we would have:
graph['A']
:['B', 'D']
;graph['B']
:['C']
;graph['C']
:[]
, and,graph['D']
:[]
.
So, we only need to make a graph walking from the root to the leaves, summing every depth for every level. This can be made with a recursive function which receives the node
we are visiting now, and the current depth
. Every time we go through the list of neighbours, this is, the nodes which point to the current node we make a fold
through all the neighbours, summing their depth which is returned recursively. You can see the oneliner (assuming we have the graph on a global graph
variable) on the following image. To start computing it, we just need to call exploreGraph(root, 0);
.
For part two, we have a simple BFS, which can be seen on the repository.
Day Eight đ¤ł
On Day Eight, Space Image Format, part one, we are asked to multiply the number of 1
âs and 2
âs on an string (after we find the string). If you are curious to see how we did find this string (the one with most zeros in the middle of a lot of strings) you can look at the repository, as, now, we are more interested on counting the numbers and multiplying them.
This is actually pretty easy, assuming we already have the string. We can split
it to have a List<String>
where every string is actually a character of the original string with originalString.split('')
. After this, we can find the number of 1
âs and 2
âs in the same way using the commonly called filter
function which is called where
in Dart. Check it below:
On dart we also have the collectionfor
syntax, which is clearly non functional, but it is interesting to check it out, as it is pretty similar to Python list comprehension:
Part two has a kinda different focus than part one, and I didnât used anything worth of note (again, if you are here to find the answers, check the repository linked above). Letâs move on!
Day Ten âď¸
Day 10, Monitoring Station, wonât add anything new to the functional bucket.
For part one and two, we need a function which computes, for a given asteroid, all the angles to the other asteroids, and we get how many uniques values we have on it. On my test cases we didnât have to worry about double precision because the spatial map was really small, but it is worth notice that if this was asked in a Programming Contest, we would probably have problems with double precision related to really close angles.
Just to help you further, we can calculate the angle between two points and using the arctangent trigonometric function which is named atan2
in Dart. The formula would be as follow: atan2(A.y  B.y, A.x  B.x)
. We use the difference in the first parameter and on the second to get the values in the interval , which will make it easier on part 2.
Day Twelve âď¸
On day 12, The NBody Problem, we are introduced to the forEach
method. It is basically a replacemente for a for (var x in y) { doSomething(x); doOtherThing(x); }
. With a forEach
we would write y.forEach((x) { doSomething(x); doOtherThing(x); }
. It is actually nonidiomatic to use a forEach
in this case, but my functional curious heart like using it, sorry.
Part two also brings some interesting math theory to the board. On this day we are basically making a really rough gravitational simulation, and we are asked when will all the planets return to their start position for the first time. We canât simulate it, because, for my input, it occurs after steps, which would take LITERALLY ALMOST 4 YEARS on my computer (it takes 2,1s for 10 million iterations). To make it faster we only need to see how many iterations it take to repeat on the axis, axis and axis and compute their LCM. This way we only iterate something like 200k iterations until they repeat on each of the axis. Below we have the LCM
function implementation in Dart:
Day Fourteen đ
Day 14, Space Stoichiometry, wasnât actually pretty easy for me, so I kinda copied part one, sorry (acknowledgments on the code).
Part two is actually interesting, where we just need to use a binary search on the part one answer (kinda known to those who like competitive programming). As a tip, when you have binary search on the answers you may have problems with your final result being one less or one more the real result, so always compute the neighbours of your âbinary search answerâ to find the real answer.
Day Sixteen đť
Flawed Frequency Transmission doesnât have a lot of functional programming as well but there is a really nice curiosity about Dart (which Iâm not exact sure why it happens, comment it below if you know it for sure). On part one, we need to compute a value based iteratively. This is, we have a value on time and based on it we compute the value for the time . To do so, we will iterate over each digit of the number .
The full code can be seen on the repository, but we will focus on this little snippet:
If we run part one code with this code, it takes around 500ms
to give us the answer.
The interesting part comes now. I created a small helper Iterable<int> range(int initialValue, int endValue)
which works similar to Python range
function, so that I could substitute a for (var i = 0; i < n; i++)
with a for (var i in range(0, n))
. If I do so, we have this snippet:
Guess the execution time now? 1100ms
! It more than doubled! Why? I really donât know how the Dart VM is implemented, but I assume it has to be with loop unrolling and data independency. You can note that one iteration of my loop doesnât depend on the other iteration of it, as Iâm just accumulating the values in a variable, and the computed values doesnât need the values computed in the other iteration. So, the Dart VM can make use of parallelism or AVXlike instructions to compute more than one loop iteration at the same time. It also can easily predict what will be the next value, so it can easily add it to the chosen way of parallelism.
Why doesnât this happen with the range
based loop? Because the Dart VM canât do loop unrolling or know which will be the next until my range
function produces the value.
What if we try to do it the functional way, iterating over the data list? To do so we would need the indices as well, which we can get transforming the List<int>
into a Map<int, int>
and apply a fold
function on it, which can be seen here:
And it takes 2 SECONDS? Thatâs a huge performance loss. I thought the problem might be the conversion from List
to Map
but the list is only elements in size and even if I compute the map only once (before the loop) we donât see any time improvements. I really donât know what could be the reason, but maybe, just maybe, it is the same thing, and a lot of VM optimizations canât be applied when we are mapping over it this way.
On part 2, we needed to do the same thing but with 10 THOUSAND TIMES MORE DIGITS. This was a really huge problem, but people figured it out how to do it. Based on some matrix multiplication properties and the problem properties, people discovered we could use just partial sums. The interesting part on it, is how we generate the list with that much times more (we donât really need to generate more (again, because of some properties) but we will assume we need for the snippet below) digits. In python we would have something like list * 10000
, but we are not on this high level yet. We can make it like so on Dart:
The named constructor List.generate
receives the number of elements we want to generate on the List
and we pass a function that receives the index, and generate an element for that position. After this step we would have a List<List<int>>
but we need just a List<int>
so we can use the Iterable.expand<T>
function, to expand a List<List<E>>
in a List<T>
using a function which maps over the values, which, in our case, is just the indentity function ((_) => _
).
Day Eighteen đď¸
Holy buckets Manyworlds Interpretation, this was so damn hard. I really donât have anything to say about it. Next.
Day Twenty đŠ
Day 20, Donut Maze, is a trivial use of Dijkstraâs algorithm with some real problems to parse the input (where the portals are) and some small problems to build the graph. For part two we have some small complications because we need to know if the portals are âinsideâ or âoutsideâ, which is kinda hardcoded for me. Nothing functional worthy.
Day TwentyTwo đ
Day 22, Slam Suffle, is actually really fun to do, and we can use some of functional programming on part one. On this problem, we have a deck of cards (which is represented by a List<int>
), and we have three different shuffles we can apply on it.

Cut: We take the first cards and put them below the others. This can be executed with
skip(int k)
andtake(int k)
functions. Theskip
one returns anIterable<T>
WITHOUT the first values, while thetake
function returns anIterable<T>
WITH ONLY the first values. So, to cut cards we only need adeck = deck.skip(k).toList() + deck.take(k).toList();
. 
Deal: We reverse the cards. To do so, a simple
deck = deck.reversed.toList()
makes the job. Note thatIterable<T> reversed
returns anIterable
so we need to make it into a list. 
Deal with Increment: This one is not that easy to make with functional programming, so I made it an interative fashion. Assuming we are using an increment we need to place the first card on position , the next one on , the next on , and so on. Obviously, we would need to place cards on positions which doesnât belong to deck, so this formula is modded
deck.length
.
You can see the code for shuffling the deck on this snippet:
For part two, we are presented with a similar problem but with a HUGE amount of cards. We need to note that we can use modular arithmetic for everything, finding a way to represent modular division, which can be computed with modular multiplicative inverse. We also need to compute a huge polynomial exponential. I wonât explain the math behind this (I really donât know everything of it exactly, actually) but the code can be found on my repository. Something interesting is that we need to use the Dart builtin BigInt
type which has some pretty interesting methods (such as BigInt.modInverse
already builtin).
Day TwentyFour đ
Planet of Fiscord uses some pretty nice helper functions with Dart functionallike methods.

stringify: Given a
List<List<String>>
we want a continuous string, we can easily achieve so usingmap
to join all the inner lists into strings, and join all the newly generated ones as well. 
biodiversity_rating: Given a
String
, we want to compute the sum of the powers of the string positions which contain a character. This is a job forfold
(again)! 
count_bugs: Given a
List<String>
we want to know how many characters there are in all the strings altogether. This is a job forfold
(again, again)!
Additional Methods â
I just want to finish talking about some other functional methods we have in Dart Iterable
class which I didnât had the oportunity to use:

any: Runs a function
bool Function(T element)
, for every element of theIterable
. If the functions returnstrue
for any of the elements of it, it returnstrue
, else it returnsfalse
. Could be replaced by afold(false, (acc, value) => acc  condition(value)
. 
every: Runs a function
bool Function(T element)
, for every element of theIterable
. If the functions returnsfalse
for any of the elements of it, it returnsfalse
, else it returnstrue
. Could be replaced by afold(true, (acc, value) => acc && condition(value)
. 
followedBy: Receives another
Iterable<T>
and lazily concatenates them. By lazily, I mean that it wonât create a new list with bothIterable
s. This is especially useful if you will use something like atake
orskip
later. Imagine that you have anIterable
of size and one of size and you want a new one, with all of the first ones, and just from the second. If we had something like(firstIterable + secondIterable).take(2000)
we would actually build aList
with size , but withfirstIterable.followedBy(secondIterable).take(2000)
besides being really cleaner and semantic, we didnât even generated any of the numbers, occupying almost no memory in the operation. 
skipWhile and takeWhile: Similar to the already spoken
skip
andtake
, but instead of receiving anint
as parameter, they receive abool Function(T element)
which must returnfalse
when we should stop skipping or taking elements.
Conclusion đ
Wow, such a long article (those kinda reliable methods to measure the reading time said you took 18 minutes to read this, lulz). I really hope you liked it. I know it is kinda complex, and I didnât used functional programming in all of the questions, but I think you should start slowly, just like Iâm doing, trying to get every time more and more on this awesome world, praising the languages with firstorder functions. It is nice to see, though, that we may have some problems in nonbuildtobeusedasfunctional languages, because we can have problems like the ones I warned on Day 16.
Thank you so much for taking the time to read this with me. Keep an eye on the blog for more Dart, more functional programming, and more AOC. Cya!