Advent Of Code 2021 - Lessons Learned
TL;DR
In this post I sum up my recent time spent on Advent Of Code 2021 puzzles. Instead of month it took me 3 months to solve all of them. I share new scars I gained during this period and some findings that weren’t obvious for me before starting (or I knew about but didn’t respect so they kicked my ass). You can check out my solutions here - I am aware that they are far from perfect so don’t hesistate to point out anything that could be done better in PR. Enjoy!
What Is Advent of Code ?
It is a mix of advent calendar and programming puzzles - similar to those that you can find on interviews or sites like leetcode . Starting from first December, each day new puzzle is released. In order to get the star ⭐ one need to provide a correct answer for given input which is provided in file. After that the second part of the problem is unblocked which is some kind of variation which relates to the first part (most often it makes the problem harder). Advent Of Code ends on 25th December, so there is possibilty of collecting 50 stars - 2 per day.
There is a super cool talk given by Eric Wastl - an author of Advent of Code who explain what I wrote above in details and tell what happens ‘behind the scene’.
Advent of Code has few elements that especially encouraged me to take part in:
- It’s a cool challenge - people usually set some goals like solving all problems in new language to them or doing each problem in less than 2 hours
- Competition = Fun - I didn’t even thought about competing with people from all around the world , however we set a private Allegro leaderboard and it was fun to compete with people from the company I work to
- Puzzles are released at 6AM CET - so it was a great motivation to have a longer day - at least for first half of event
My Goals Before Starting
When Advent of Code started it was just the month after I started new job. My team is using Kotlin and Groovy with which I wasn’t that familiar, because I mostly used Java before so I decided to dive in and get acquainted with those two. Another thing I wanted to exercise was using immutability everywhere as I thought this is a silver bullet for all problems that happen in code.
Lessons Learned
Do not walk away from complexity, run!
This is the title of great presentation given by Venkat Subramaniam and simultaneously it is the first conclusion I have after doing 25 Advent of Code puzzles…
Accidental Complexity vs Inherited Complexity
Some problems are just hard to solve. Let’s think about D star search algorithm . It can be said that the code just inherits the complexity of the problem it solves. But c’mmon - let’s face it: most of the problems we (as programmers) deal with do not need that complex solutions. So the code should be simple as well. Accidential Complexity is the complexity that comes from our choices, not from the problem itself. It comes mainly from lack of discipline, wrong decisions about tooling and poor design.
Lack of discipline - Many times when implementing solutions I caught myself breaking some well known rules like Law of Demeter , Single Responsibility Principle or Single Level of Abstraction Principle and I was saying to myself that I’ll refactor it later on. Unfortunately many times I stuck reading my own code written not that long ago and trying to understand why it’s not working as expected and not being able to make my test green. Life is much easier when each test push you only a little to the final solution and you refactor the current solution after each green test!
Tooling - this part has probably more sense when thinking about projects when it comes to choosing wrong database, wrong programming paradigm or wrong type of communication between services. However, trying to solve all Advent of Code puzzles in AWK would be much harder than doing the same in Kotlin 😉
Poor Domain Design - there is usually many ways to think about the problem. Let’s take a look at day 23 of AoC 2021 . Our task is to move each amphipod to the ‘desired room’ with the lowest possible cost (each move costs differentely depending on amphipod type).
Initial State Desired State ############# ############# #...........# #...........# ###B#C#B#D### ###A#B#C#D### #A#D#C#A# #A#B#C#D# ######### #########Each letter represents different type of amphipod,
.is a free space and#is a wall. There is also many rules describing how amphipods can move. When I saw it I smiled and thought: “weren’t those puzzles supposed to be harder every day?!” And after many hours spent on this problem I was crying, because I didn’t thought about the consequences coming out from my design. I chose the first design that just came to my mind which fulfilled this idea:- Look what moves amphipod have
- Try out each of possible moves
- Keep new state whenever move fulfills all requirements
- Repeat for each new state, but starting from those that are closest to desired state
Time complexity kicked me so hard, that I decided to leave my first implementation in repo as a souvenir. The worst thing was that instead of thinking about problem differently I was trying to add more and more optimization tricks. So instead of focusing on the original problem I was solving the problems that came up with my poor design. You can compare this with the second implementation , which models the problem slight better.
Weeks of coding can save you hours of planning
Another quote I saw recently that can be used as heading for my next finding. This one is maybe obvious but it is so important that I want to emphasize it.
Make sure what do you want to solve This may sounds funny, however few times I caught myself on jumping straight into implementation after reading the problem description. Most of those attempts - as you coud expect - were awful failures. It is worth to ask as many questions as possible to not jump into coding with wrong assumptions.
Solve the problem manually using simple examples To see if we really understand the problem it is worth solving few simple examples (maybe with some harder variations) without using the code! This way we can find what are the hardest part to solve and we have more knowledge how our model should look like. Those simple cases can be the ported as our first test cases. In Advent of Code descrption of problem often shows some examples which is super cool.
- Think about complexity of solution! When thinking about solution it is worth to estimate how much it will cost you. It is worth to take into consideration three factors before jumping into coding: space, time and implementation complexities. Whenever I talked with people about day 6 I heard ‘oh yea, I got OOM at first try’ or ‘yup, it would take ages to complete with my first attempt’. And obviously I had the same. Spending a moment for thinking about complexity surely would save me this embarassing OOM moment :)
Mutability is like changing underwear
My goal was to create readable solutions and… immutable ones. I really don’t know why did I put such constraint on myself. Ok, maybe I know. If you are just learning how to code (as I am) and you see that there are many smart people saying things like this:
or write articles with titles like that: Mutability Leads to Suffering you can start thinking, that whenever you write a mutable code you will fry in hell. But you better notice, that most of those people have in mind shared mutability. There were many puzzles were I felt it would be much easier and faster to write mutable code, however I was reminding myself: ‘Peter, you must stay strong, mutating is for weak people only…’. One day something snapped inside me when I had to build graph based on list of coordinates. I closed my eyes and I wrote this:
companion object {
fun from(coords: List<Coords>): BurrowGraph {
val builder: MutableMap<Coords, MutableSet<Coords>> = HashMap()
coords.forEach { builder[it] = mutableSetOf() }
coords.forEach { coord -> coord.adjacent().forEach { builder[it]?.add(coord) } }
return BurrowGraph(builder)
}
}
When I opened eyes I realized, that there is nothing wrong that I mutate state in such limited scope!
Although I still prefer immutable code for many reasons, I am aware that sometimes mutability is just inevitable - and it can be done in elegant way (without side effects).
During writing this post I found the awesome advice about mutatability which totally dispelled my doubts 😄
Some thoughts about tests
“This software is hard to test” = “The design of this software sucks”
~Venkat Subramaniam
It is commonly known that the easiest way to have testable (well designed) software is to use Test Driven Design. This is an awesome exercise that force us to think about results we want to achieve first and then creating the solution. It can be connected with writing the methods from the end as well (starting from what we want to return). It may sounds little akward, however I feel like it helps in keeping focus on current implementation goal. So… theory is easy:
- Create a failing test
- Create simplest possible passing solution
- Refactor (remove redundancy)
repeat until you have desired result.
However, there was something that’s been eating me for longer time. How specific should be those tests?
For example in day 24 I wrote some tests like this:
def 'model number cannot have zeroes inside'() {
when:
new ModelNumber('12345678902345')
then:
def exception = thrown(IllegalArgumentException)
exception.message == "Model number can consists only of digits in 1..9 range"
}
I think that this is a good test. It tells about some ModelNumber constraints, so anyone who would like to use Model Number can just look at the specification and know what is going on. Additionally, it tests very small portion of functionality, so it is easy to implement it.
However, it seems for me that the hardest part is to find such tiny functionality to write next and sometimes from my fingers something like that came out:
def "should properly build polymer"() {
given:
def input = readLines(path)
PolymerRules rules = PolymerFactory.INSTANCE.readRulesFromStrings(input)
PolymerTemplate template = PolymerFactory.INSTANCE.readTemplateFromStrings(input, rules)
when:
def actual = template.mostCommonQuantityMinusLeastCommonQuantityAfterNSteps(numOfSteps)
then:
actual == expected
where:
path | numOfSteps || expected
'/advent-of-code/day14/input1' | 10 || 1588
'/advent-of-code/day14/input1' | 40 || 2188189693529
'/advent-of-code/day14/input2' | 40 || 3906445077999
}
and with a lot of debugger help I could make it green (only the first expected number was known, other ones were added later on).
Interesting technique that forces to make only tiny steps is test && commit || revert . This way I wrote solution for day 18 and you can see that it contains from really tiny steps like:
def 'should reduce snailfish number if it explodes on right'() {
expect:
snailfish([1, [1, 1]]).explode(3) == new Explosion(snailfish([2, 0]), null, 1)
}
def 'should reduce snailfish number if both carries have to be carried'() {
expect:
snailfish([[1, [1, 1]], 1]).explode(2) == new Explosion(snailfish([[2, 0], 2]), null, null)
}
def 'should add two snailfishes'() {
expect:
snailfish([1, 1]) + snailfish([1, 1]) == snailfish([[1, 1], [1, 1]])
}
I think that test && commit || revert is too extreme and it encourages to write tests that are too specific, however it was fun to try.
For me too specific tests are those that have to be changed whenever any change in implementation are introduced. They discourage refactors and pretty often assert things that shouldn’t be asserted like internals of intermediate structures. They focus too much on how but they should focus rather only on input and output.
Kotlin and Groovy Goodness
For last ~3 years Java was my main programming language. In this place I just want to express how delighted I am due to switching to Kotlin/Groovy stack. Below meme illustrates my story perfectly:
I like how concise those languages are. Of course, it is possible to write readable code in Java, however Kotlin have many things that encourage good practices like immutable collections by default or non-nullable types. Moreover it has a lot of ‘special gifts’ for developers like possibility of writing extensions (and a lot of super cool existing extensions!), data classes (Java 16 has them too! ), selaed classes, sequences, infix functions… When I was reading about all that stuff and then I could use it I felt like I am dreaming 😅
I like how expressive tests can be in Groovy:
def 'should add all version numbers in packet and subpackets'() {
given:
def aPacket = operatorPacket {
version 4
typeId 5
lengthTypeId 0
subPackets([
literalValuePacket {
version 16
literalValues([
literalValue { binary '1011' },
literalValue { binary '1011' },
literalValue {
isLast true
binary '0111'
}
])
}
])
}
expect:
aPacket.sumUpAllVersions() == 20
}
However, I feel like it has many drawbacks - it surprised me definetely more than once, for example:
- BigDecimal with value zero or empty list in tenary expression is treated as false
def 'big decimal 0 in tenary expression is treated as false'() {
when:
BigDecimal aBigDecimal = 0.0
then:
aBigDecimal ? 1 : 0 == 0
}
def 'empty list in tenary expression is treated as false'() {
when:
List emptyList = []
then:
emptyList ? 1 : 0 == 0
}
both tests are green.
- not obvious behaviours when using
@DelegatesTo
cuboidWithAction {
action ENABLE
cuboid cuboid {
x 10..12
y 10..12
z 10..12
}
}
will fail with exception:
groovy.lang.MissingMethodException: No signature of method: static
eu.proszkie.adventofcode.day22.CuboidBuilder.cuboid() is applicable for argument types:
(eu.proszkie.adventofcode.day22.Cuboid) values:
[Cuboid(x=[12, 10, 11], y=[12, 10, 11], z=[12, 10, 11], toSubtract=[])]
Possible solutions: cuboid(), cuboid(groovy.lang.Closure), build()
so there is need for adding ugly it. before cuboid:
cuboidWithAction {
action ENABLE
it.cuboid cuboid {
x 10..12
y 10..12
z 10..12
}
}
- NamedVariant ignores default parameters
def 'named variant ignores default values'() {
expect:
example(first: 1, second: 2) == 3
example(first: 5) == 10
}
@NamedVariant
private static Integer example(Integer first = 0, Integer second = 5) {
return first + second
}
results in
groovy.lang.GroovyRuntimeException: Ambiguous method overloading for method java.lang.Integer#plus.
Cannot resolve which method to invoke for [null] due to overlapping prototypes between:
[class java.lang.Character]
[class java.lang.String]
[class java.lang.Number]
And many more could be found. For next project for sure I will try some Kotlin framework like Spek or Kotest .
Sum up
Although it took me a lot of time to complete whole Advent of Code I am quite happy with the results and conclusions I gathered. I think that it is wonderful to have some space for experiments like that and allow yourself for testing new ideas and making errors that do not result in burning production and calls from clients. 😄
Advent of Code 2022 - I am waiting for you!