It all started with an innocent-looking question, from a colleague – “This year I’d like to propose an office leaderboard for the Advent of Code, what do you think?”. Well, why not? I made a lame attempt at AoC some years ago and possibly gave up on the first day for lack of time (and commitment).
But this looked like an interesting challenge and I agreed and promoted the idea. Since I miss working in Scala, I wrote AoC solutions in Scala 3 to dust off some rust (ops) and learn the new syntax. Solving a (double) puzzle a day for 25 days (Xmas day included), is not a light endeavor. It requires at least from 1 to 2 hours and is increasingly difficult to squeeze into a normal working day especially if you have a life.
I managed to work on most of the days and completed several parts 2, but more than solution accomplishment I’d like to share what I learned in the process.
“You learn to do what you do – if you listen to music, you’ll learn listening to music, not playing it”, this was a wise piece of advice from a colleague at the beginning of my career (yes, dinosaurs still roamed Earth). I found this very fitting in this case – solving AoC puzzles in language L, you become better and better at solving AoC puzzles, you may improve in L, but it is a marginal improvement since the puzzles tend to exercise just a few areas of a language and its libraries.
I’m not saying that AoC does not help you to be a better programmer, just that you can’t rely on AoC alone to learn a new language.
First, you can find my code, day by day, in this git repo, feel free to look there and ask me stuff about that.
Bad habits Encouraged
Regrettably, I found that some bad programming habits tend to be encouraged by the competition format. You have a very precise literal task, a single and correct input, and a very limited time.
All these encourage cutting corners. Input is fixed and correct so that you may skip error checking (I did). This is something that you should never ever do, even if you are writing code for yourself. It is better to consider the outside world full of evil people who craft wrong and subtly wrong inputs to cause trouble than skip some check on data input.
Another implicitly encouraged wrongdoing is copying and pasting parts of code from one day to another. This is usually faster than analyzing, generalizing, and abstracting into some kind of library or shared components. This is also promoted by the incremental revelation of the problems, you can’t see all the advent days, just the current and the previous. So, especially at the beginning, is difficult to factorize and easy to make wrong abstraction decisions. Since part 1 has been solved, you may solve part 2 just by copying part 1 solution and tweaking it, rather than generalizing part 1 to handle customization for both parts.
The last encouraged bad behavior I’d like to mention is the single-file app. Since this is mostly write-once code, there is no need to find a good file organization. Put everything in the same file and off you go.
Now these are undoubtedly bad behaviors, a minimally sane code review would stop them all from entering any decent code base. Nonetheless, there are special occasions, where taking these shortcuts could be proper (besides trying to complete the Advent of Code). E.g. when scouting a technology or a solution or when crafting a proof of concept, as long as this code is thrown away when going into the production realm.
Good Habits Encouraged
I have to say that I felt urged to do unit testing – to verify step by step my code before composing it into the final solution. Sometimes I felt contrasted between the need to test parts of my implementation and the OO instinct to hide those parts in the private section of the classes. I guess this scores another point for FP in the FP-OO match.
Unit tests proved very useful in perfecting the parts so that the final machine built on them worked as expected.
Functional thinking was also encouraged from the very definition of the problem – you have an argument to your code and you are demanded a result. That’s a function. You could even copy and paste the input in your code editor so that no I/O is even needed. I didn’t do that, but I tried to make all the implementations as functional as possible.
Another good habit encouraged was thinking hard about the structure and algorithm you need to solve the problem and choose wisely. The structure and algorithm must solve step 1 – the one you know about, but should be open and flexible enough to solve the (unknown) step 2. I learned this quite early when I tried to overoptimize the solution for step 1. I ended up with a code that was completely useless for step 2.
Emerging Patterns
Around half of Advent days, it became clear that there was some space for code reuse:
- Bidimensional map,
- Bidimensional position
- Facing
- Walker (position + facing)
My lack of knowledge of sbt didn’t allow me to factorize out these components properly, but sometimes I copied and pasted from day to day.
I tried to go a bit further trying to abstract the exploration pattern. Many problems in the AoC can be abstracted as:
- Start with a candidate set (that could contain just one item)
- if the solution is reached stop
- generate a new candidate set
- prune the candidate set according to the puzzle rules (e.g. you can’t walk out of the map)
- prune the candidate set according to some heuristic
- loop from 2
Now this schema is pretty general, can be made purely functional, and can be implemented with tail recursion (which is always a good feat), and helped me in solving (at least the first step of) quite a few puzzles. You can see it starting to shape out starting from Day 17. I didn’t manage to entirely clear the design out so as to be fully general, but the pattern helped me in designing the solution to several puzzles.
If you look at the list above, you may see that each step is described by a function –
- has the solution been reached? This can be made into a function that accepts the candidate set and the problem state and returns a boolean
- generate the new candidate set is a function that takes the current candidate set and the problem state and returns a new set of candidates,
- and so on.
Following this line and pushing the generic programming, you could implement the puzzle solver with a generic function that accepts the puzzle state and candidate set as parameter types and the step functions as arguments.
Scala to the Rescue
Scala proved to be a very good tool in tackling the challenge. The feature I liked most and that I didn’t know about it, is the string deinterpolator. I think that one of the first things you learn in Scala is the string interpolation:
val v = "something"
val text = s"the text is {v}"
What a few people may not know is that it works even in reverse:
val s"the text is {v}" = "the text is something"
// now v values is "something"
This can also be used in a pattern-matching function, helping you to implement quite convoluted parsing. This snippet is from day 20:
def lineToComponent( line: String ): Component =
line match {
case s"broadcaster -> $outputs" => Broadcaster( stringToOutputs( outputs ) )
case s"%$label -> $outputs" => FlipFlop( label, stringToOutputs( outputs ) )
case s"&$label -> $outputs" => Conjunction( label, stringToOutputs( outputs ) )
}
Another Scala 3 feature I found very useful is the enum. Back in Scala 2 days I had to write something like:
sealed trait Facing case object North extends Facing case object South extends Facing case object East extends Facing case object West extends Facing
The compiler was smart enough to understand this was a sum type. With the Scala 3 you may now write:
enum Facing: North South East West
Interestingly an enumeration may have methods. Modifying the toString method may not be the smartest idea in general, but could be a quick hack when you need some custom output:
enum Pipe:
case Vertical
case Horizontal
case NorthToEast
case NorthToWest
case SouthToEast
case SouthToWest
case Ground
case StartPosition
override def toString: String = this match {
case Vertical => "|"
case Horizontal => "-"
case NorthToEast => "L"
case NorthToWest => "J"
case SouthToEast => "F"
case SouthToWest => "7"
case Ground => "."
case StartPosition => "S"
}
Overall I found that the type system helped a lot and I think I never got a null pointer or any other exception. The most common wrong behavior was just a wrong result.
Also, the type system helped in complex expressions that in the end, thanks to the IDE, tend to be correct. On the other hand, I found myself several time writing exceedingly long lines.
Scala 3 significant indent gives me mixed feelings. I love it compactness, on the other end, it happened more than once (especially thanks to smart copy’n’paste, intellij courtesy), my code got aligned to the wrong indent resulting in puzzling compilation errors or even subtle bugs. Allowing both styles (curly braces and significant indentation) in the same file does not help. Even if I wanted to use significant indentation, out of habit, I used sometimes curly braces resulting in mixed styles, which is somewhat untidy when you get back to reading the code.
I also found the language a bit lacking in the bidimensional array area. Several puzzles were map-based, where the map was a grid of tiles on which solution “walkers” had to move and/or change the tile value. First, in Scala there is no such thing as a 2D array. You may implement it by using an array of arrays, but you have to allocate it before using it. Eventually, I discovered the Array.ofDim –
val grid: Array[Array[GridCellContent]] = Array.ofDim[GridCellContent](w, h)
grid.indices.foreach(
x => grid(x).indices.foreach(
y => grid(x)(y) = GridCellContent(Set.empty)
)
)
The second problem was that if you want to iterate over several changes to the map, as per functional programming, you should never modify an existing copy of the data, but just create a copy with the changes you need.
My ancestral programming instinct – formed by shaving bits off 48k – balks at this as it seems like an unacceptable waste. Even if possibly the new copy would share most of the data with the previous one, the other obstacle was the need for an optic, i.e. the functional way to copy data with changes down deep in the data structure. Though I know what optics are and the basic idea, I haven’t learned them yet (also because you need an external library to use them). And the pressure of solving the puzzle in a limited amount of time didn’t encourage me to study them.
Next Year
Am I going to participate in the next Advent of Code? Well possibly. I find it a good exercise, despite the bad habits encouraged, it poses intriguing challenges with an entertaining motivating story. The major obstacle is time (or lack of it).