I've always enjoyed low level programming so this year I decided to scratch that itch by starting to do some hobby programming with microcontrollers. There's nothing more frustrating than trying to learn everything (new toolchains, new SDKs) all at once while trying to build something non-trivial, so the obvious answer was to take my existing, known-good 524 star repo and port that over to a microcontroller. It would also give me a chance to revisit some of my original solutions that were significantly sub-optimal.
I chose the Raspberry Pi Pico (RP2040) as the target microcontroller because it's geared towards learners, it has a thriving ecosystem and I really admire the work the Raspberry Pi Foundation do.
The repo is more or less in a fit state to be public after the first four years (2015-2018) have been squashed, the support libraries have been exercised and the workflow has had the major rough edges knocked off. There's still plenty more to do though, so I'm expecting it to be in a state of flux for the next 12 months or so.
Performance
The RP2040 is on average between ~100-200x slower than the laptop I'm using for development and I've set myself a soft target of 1s per solve on the microcontroller hardware (including IO transfer time), meaning that I need to target ~5ms or under on PC. What's really nice though is that by the time a solution has been squashed enough to fit in the memory restrictions, that's almost always a significantly faster solution than my original solution and often sub-ms without any further faffing.
The high level summary for puzzle solution times on the RP2040 so far:
| Year |
Min (ms) |
Max (ms) |
Avg (ms) |
Median (ms) |
| 2015 |
2.237 |
27,764.055 |
1,207.659 |
215.076 |
| 2016 |
0.755 |
450,195.662 |
17,832.642 |
134.623 |
| 2017 |
0.698 |
13,121.265 |
960.156 |
210.754 |
| 2018 |
4.52 |
9,074.706 |
687.048 |
318.475 |
There's a full breakdown of current timings here.
Note: I do my timings a little differently to a lot of the forum regulars who work on producing ultra-fast solutions. The timing starts on the host PC when I start transmitting the input over USB and stops when I get the final byte of the answer back. I time both parts separately and each part is an independent solve, I don't have any solutions that calculate both part 1 and part 2 answers at the same time.
There are some things that are absolute Kryptonite to the RP2040. MD5s are a particular weakness, hence the bad Max and Average times for 2015 and 2016, and anything that requires 64-bit maths is emulated in software.
IO can be an issue as well. 2016 day 7 has an input file ~170-180Kb in size, which takes ~1.5s just to transfer over USB-CDC. Many of the days are ~400-600x slower than PC purely because of the time it takes to send the input file.
Common changes
The most common changes I've made are to variable types and to data structures. 64-bit integers were always my default choice so that I didn't have to worry about figuring out which puzzles needed more than 32-bits and which didn't, but that's not practical with the 32-bit Pico. With an existing solution as a reference it's pretty quick to swap types and check that we still get the same result, and thankfully most of the days so far are perfectly solvable using 32-bit maths only. 2017 day 15 is probably the one that suffered the most from software emulated 64-bit integers; there is a way to implement the generators using only 32-bit arithmetic, which is what I use, but it's quite a few instructions and so it ends up being the slowest solution for all of 2017.
My default choice for data structures in my full-fat repo has always been std::set or std::map, even for data that would naturally go into an array. The main reason is programmer efficiency: you don't need to worry about getting a correct array size and insert returns a value to indicate if the element has been inserted or not, which is a very common test required in a lot of the algorithms. For the microcontroller, especially when trying to squeeze solutions into the memory limits, arrays/vectors are the default choice wherever possible, and I've written simple open-addressing (with linear probing) hash maps and sets templates. This is where a significant proportion of the speed-ups have come from compared to my original solutions.
Algorithm changes
Surprisingly, fewer than 20 have needed a complete overhaul on the algorithm used.
2015 day 13 is the first one which needed a change, swapping from a brute-force scoring of all possible permutations to a recursive DFS. Day 19 in the same year was the only other one which needed a completely different approach. That one was originally one which made my nemesis wall with a really horrible home-brew parser-adjacent algorithm, but after seeing in the megathread that it could be solved using a greedy algorithm it ended up significantly faster on the Pico than my original solution running on a fast PC by a few orders of magnitude.
2016 and 2017 also only needed a couple of days swapping over to a different algorithm. 2018 is the year so far that's required the most, with almost half of all days being revisited in terms of how they're solved.
Bit Packing
Of all the changes I was expecting to make, bit-packing values is the one I haven't needed anywhere near as often as I thought.
2016 day 18 didn't need bit packing to fit into memory, but I thought it would be fun to parallelise the logic into bitwise operations anyway. 2016 day 11, one from my wall of shame needed the search states packing in order to keep the queue size small. The others have largely been ones where we're dealing with large (for a Pico) 2D areas, like the infection states in 2017 day 22 and the cave terrain in 2018 day 22.
Windowing
Windowing, or working on only a small chunk of the full data range at any one time, has been a life-saver on a few occasions. 2018 day 17 has been the one I'm most pleased with, although the chunked seiving on 2015 day 20 was nice to work through, especially with the approximation function I iterated on to get a good lower bound starting point.
Maths
I tend to avoid closed-form solutions and have a personal preference for programmatic approaches, but there's really no beating the closed form solutions or using maths insights for speed and size. The Josephus problems are an immediate example of not having enough memory to process large rings of elves, or the Cosmological Decay approach to the Look-and-say sequence completely bypasses the need for large amounts of memory.
Recursion
By default when using the C/C++ toolchain each core on the Pico gets 2KiB of stack assigned. That's really not a huge amount by any stretch, so most recursive solutions are a no-go. Approximately ~9 solutions have needed swapping over to using an explicit stack, making it one of the most common changes I've had to make.
While it's true that all recursive algorithms can be implemented in terms of a stack based algorithm, the devil really is in the details and I never appreciated how many little decisions about state representation and return values would need making.
Take a normal recursive function:
int Func(int n)
{
// ...
int n1 = Func(n + 1);
int n2 = Func(n + 2);
return n1 + n2;
}
Stack frames and function calls give you 3 separate things:
- Local variables - these are what an explicit stack structure trivially gives you
- State - after the call to Func(n + 1) you need to encode somehow the fact that you've made that call and the next recursive call is the one to Func(n + 2)
- Return values - do you put the return value in the current stack top and let the parent take care of popping after reading, do you let a child pop its own stack and write the return into the parent stack frame, or something different. It was a real eye-opener to sit down and actually code up something like 2015 day 22 using an entirely stateful stack based approach.
Forum Help
I have a general rule that I won't look at anyone else's solution until I've got a solution of my own. Even if (and it commonly is) it's a rough and ready solution which take seconds or minutes to run and chews through half the memory in my machine. I'm pleased that for 523 of the 524 stars I've been able to get to a working answer with no hints, but there's absolutely no way I'd have been able to get the 200 on the microcontroller so far without the valuable suggestions, and the public repos of forum regulars. There have been over a dozen of these solutions that are either direct re-implementations of other people's solutions, like 2018 day 9 or 2018 day 14, or have used suggestions and explanations from information posted on the forum such as the equivalence pruning for 2016 day 11. u/musifter's review series has been a great focal point to discuss the problems with people who really know their stuff.
Thank you one and all!
Microcontrollers
The hardware you can buy now is utterly incredible for the price: I've been targetting the Raspberry Pi Pico as far as possible, but the Raspberry Pi Pico 2 W is a 150MHz 32-bit CPU with 520KiB RAM, Bluetooth and WiFi for under £10. As someone whose first computer was a Spectrum 48K, this is a ridiculous amount of computing power to have for very little money and in a tiny space. If I had kids who wanted to learn how to program, I would definitely think about sitting them down in front of Thonny and a microcontroller. It has exactly that same immediacy of feedback I remember from typing out Basic listings to see something cool happen on screen.
