Advent of code

I remember the time late 2015, when I was ahead of schedule on my project, and I was looking for ways to pass the time. We were spending around 7-9 hours in the office back in the day, no matter what, so being bored at work was an unpleasant experience.

Anyway, I stumbled upon Advent of Code: what would soon to become a recurring event of 25 coding challenges in December. I did a bunch of those and either lost interest, or needed to get back to my actual work. But now, a couple years later, again not having anything to code on a daily basis, I went back and continued from where I left off.

TypeScript

I remember doing the first couple of challenges in python as a learning experience. I think that is the most python I’ve done in my life, as far as I remember. Now, since I’m mostly transitioning to TypeScript (the last thing I’ve written in PHP was 6 months ago), I thought that would be a good choice for me.

Unfortunately it didn’t pan out. I didn’t feel comfortable with wiring all the things around the challenges — like mostly building the module loader, and all the existing boilerplates / launchers / template generators didn’t actually fit my needs. It just wasn’t fun coding using them, and the constraint’s felt unnecessary. So after a couple of tries, I switched back to PHP.

PHP

The chair was good, thank you. Fortunately, I am not concerned about recruiting to this project, and PHP is a lot of fun for me, so here we go. After stitching together a basic loader, I went on to implement the first challenges.

And immediately I miss TypeScript. It’s mostly the short lambdas (aka fat arrows) that make the difference. Since I was using a lot of colletion transformations, they pop up a lot, and typing the PHP’s static fn (…) => … really makes a difference in comparison to pure (…) => …. Prettier is a close second. It just works, and it allows me to write the code in an absolute sloppy manner, and it will fix anything, while PHP CS Fixer on the other hand, won’t even bother to insert a semicolon for me.

Other than that, I’m having a fast pace moving forward. Whenever I’m experiencing any inconveniences, I improve the loader/boilerplate/launcher parts, and that in turn improves the DX. I extract common parts to a shared lib to reuse between solutions. And I am exploring a lot.

Example tools used

The loader uses the simplest form of DIC container. It scans the source directory for implementations of certain interfaces, and exposes those to certain factories. This way all I have to do is drop an entrypoint-like class anywhere, and use a marker interface on it to indicate that it should be used as a challenge solution. Similarly with input parsers — since they are always provided in a text form, the very first step of every solve is to parse it into a nice DTO.

A lot of the solutions rely on finding the answer by brute-force. This means thousands or millions of operations. And just so I know what is going on, I created the Progress indicator class, that iteratively displays partial results in the console, while the script is running. It also allows me to estimate the time/iterations required to find the solution, so I get a nice progress bar.

There is a lot of combinatorics in the challenges, for example:

• In what ways can we rearrange the set?
• How can we pick n elements out of a set of m, when the order either matters or not

I learned about all of this in high school, but that was decades ago, so I can’t say I remember a lot, so I am having quite a hard time to name the concepts, so that I could build a dedicated library for it.

I also use a lot of high level concepts, like OOP, a collection library, value objects, etc, which makes the code readable on the one hand, but painfully slow at times. Replacing a filter() or a map() method with a foreach() makes a difference here.

Example challenges

2015, day 19, Medicine for Rudolph

While most answers can be brute forced, and the hard part is to optimize the algo or find shortcuts, there are challenges which can be solved metodically.

One such example was molecule folding challenge, where some solution could be brute forced very easily. Proving that this was the best one took me 100s of millions of iterations, and the process did not finish event then.

Switching to a smarter approach was a lot of fun. And while I either googled or discovered a bunch of breakthroughs, that did not yield an elegant solution for me. I remember spending literally days on that one, and I learned a bunch about chemistry, parsers, and other stuff.

2015, day 22: Wizard simulator

This one simulates an RPG-style combat. I recall a great article about representing this kind of rules in the type system (and failing), so I immediately recognized that this time, rules on who can use what weapon, and how the combat proceeds in different scenarios are business rules, and as such are required to be represented as first class in the code.

It is quite a different approach to what I was used to: where entities holding state are also responsible for the validity of this state and it’s mutations. Here, those responsibilities are separated, and there is a separate layer on top that ensures the business rules are followed. In my example you can see how enforcing the inventory rules of a warrior was moved from that players class factory method to a separate builder.

But for the second part, where another class of characters is implemented, I also wanted to try a different approach: to use an evolutionary algorithm to solve the challenge. After implementing the magical combat rules, and making sure they work, instead of brute-forcing the solution or trying to be smart about it… I created a legion of random wizards, let them fight a clone of the final boss, and mutated the ones that did best in each iteration. And I repeated the process until my processor got hot.

I thought it would be much easier, and much more spectacular. I was aiming to visualize the process, in which different species take over the population, because they have better results. I ended up just showing the best 5-10 ones of each iteration. And the difficult part was: how to best classify who got better result.

My first thought was, that whomever won the combat was better to any loser, and then whomever dealt the most damage, and then who used the least resources. This yielded results quickly, but interestingly, not the best results. The algorithm quickly arrived at local maximums and had a hard time mutating out of them. Apparently, some strategies that are good for early stage combat, arent as efficient in the later stages, and when my highly trained wizards evolved for a couple of generations, it was basically impossible for them to backtrack and change strategies that would yield the best result in the long run.

Which brings me to my second point: I struggled a lot with the mutation strategies. Even slightly changing the ways species mutated resulted in very different outcomes. In the end, a couple of small tweaks were responsible for big improvements:

• Not favouring winners. When you think about it, an inefficient winner isn’t closer to a final solution, than a player who lost by a couple of hit points. The latter is possibly one mutation away from winning, and doing so in a much more economic way. So that part was removed from rankings
• A more diverse algo was favoured over simple ones. This immediately replaced 3-5 move strategies with 8-9 move ones, and made different mutations appear more frequently in the final solution.
• Keeping the most efficient winner and not mutating it. I can’t quite pin-point it, but I knew that that one species was on the right track, but often I saw more efficient losers take over the population. So I don’t want to take all the winers over losers, but I want to preserve at least some of them.

This somehow allowed me to arrive at my final solution. Curiously enough, the most efficient species didn’t survive over generations, which I expected. Instead, I had to keep track of the best solution in each generation, insted of relying on the most recent one.

Coding style choices

I use a lot of OOP here. While inefficient at times, it makes the code so much readable. I see people implementing their solutions in a procedural style, on one file, top to bottom. I on the other hand separate responsibilities, test individual components automatically, and build architectures that allow me to expand the code easily.

For example, in the Warrior/Wizard simulator: the second challenge relied on the previous one, and it was quite easy for me to reuse the code for both solutions. And there are two parts to each challenge — usually a tweak to the code to account for new requirements is easy and elegant.

In addition, I riddle my code with assertions. This allows me to make sure that not only the types are correct, but also the values make sense in a semantic way. E.g. if I have method Character::gainHealth(value), I make sure value is a positive integer. No sense in damaging a player by healing them with negative health. Or using magical, healing fireballs with negative damage, for that matter.

Another thing I used is combining assertions with exceptions. I wouldn’t use that on a larger codebase this way, but there is a certain elegance to just enumerating border conditions in code, without any control statements. Building custom assertion classes would probably achieve similar results in a more mature codebase.

Named parameters and factory methods also improve code readability a lot. Use them whenever you can.

In closing

In the end, Advent of Code, despite being largely about algorithms and structures, is a lot of fun (and warning: it consumes a lot of time). Would recommend!