[2015-2018 All Days][C++] 200 Tiny Stars (and counting...)

[u/DelightfulCodeWeasel]

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:

1. Local variables - these are what an explicit stack structure trivially gives you
2. 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)
3. 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.

[u/herocoding]

An amazing write-up! Really great approaches!! Thank you very much for sharing!!

[u/DelightfulCodeWeasel → u/herocoding]

Thank you, you're welcome!

[u/terje_wiig_mathisen]

We have been reviewing all the solutions, one year every month, we are currently on Day17 of 2022. Among the regulars we have people who tries to solve on very resource-constrained platforms, you would find kindred spirits there!

[u/ednl → u/terje_wiig_mathisen]

OP has been there all along and also references this in the post!

[u/terje_wiig_mathisen → u/ednl]

Oops! I did not notice that u/DelightfulCodeWeasel was the author. Mea Culpa. :-(

Anyway, anyone interested in interesting solutions should join us, right?

[u/ednl → u/terje_wiig_mathisen]

Definitely.

[u/DelightfulCodeWeasel]

Looking ahead to 2019, these are the ones that are going to need some serious TLC:

Day	PC Time (ms)	Memory
3	60	16 MiB
10	70	27 MiB
12	500	41 MiB
16	114	52 MiB
18	20,500	725 MiB!!!
20	520	103 MiB
23	26	5.5 MiB
25	1,580	2.3 MiB

[u/e_blake → u/DelightfulCodeWeasel]

Day 18 is going to be a bear to pull into less memory. But one thing I learned while playing with my solution - an A* solution is possible for both parts to prune the search space. If I do bare Dijkstra, my input needed 23.2k insertions and 15.8k pops to the work queue for part 1, and 33.2k insertions and 29.2k pops for part 2. But I played with a couple of heuristic ideas, and got the best performance for part 1 when using an O(1) heuristic (for my input, improving to 23.0k insertions and 14.5k pops), while for part 2 I got better performance using an O(n) heuristic (13.8k insertions and 6.7k pops). For part 1, I pre-computed the minimum distance from any one node to another, then the heuristic started out with the sum of all those minimums, and subtracted a given node's minimum from the heuristic when that node was visited. For part 2, I dynamically computed the largest minimum distance remaining from each robot's current position to any of its remaining nodes (that computation benefits from a cache, since 3 of the 4 robots keep the same heuristic from the previous move).

[u/DelightfulCodeWeasel → u/e_blake]

You're not kidding!

I'm currently toying around with the idea of DFS and pruning the heck out of the search space. I also need to do a bit of an analysis on which keys are locked behind which doors to see if that can either force a particular ordering on part of the search space, or if Eric has been super-nice with the unlocking ordering and it's actually guaranteed that the best time for each individual robot, ignoring doors, will be achievable with some ordering. That's probably not a realistic hope for a day 18 problem though.

[u/e_blake → u/DelightfulCodeWeasel]

Are you precomputing the distances between each key, to prune the actual search down to a much smaller network of non-uniform weights and where you can use a 32-bit mask to track which nodes still need visiting, or are you still trying to explore on the original grid but where every move is distance 1?

[u/DelightfulCodeWeasel → u/e_blake]

Precomputing the distances between each item of interest: a door counts as a potential waypoint. The choice on door representation was just to make the precompute step simpler. My current solution uses strings as well rather than a bitmask, so there's plenty of fat to be culled in the search queue representation. This is definitely one of my "paid for the RAM, use the RAM!" solutions.

Part 2 is currently visiting ~1.7M nodes and has a maximum pending queue of ~2.7M nodes, which I'm expecting should drop dramatically when I eliminate the doors as nodes and take a look at adding in some heuristics.

The only fly in the ointment in terms of eliminating the doors (and why I didn't do it the first time) is that I've got some transitions that are unlocked with "this door or this door" and some that are unlocked with "this door and this door".

Other potential thoughts: generate the quickest 10 routes for each robot, ignoring door unlock ordering, and then check each of the 10,000 combinations to find ones that are compatible.

[u/DelightfulCodeWeasel → u/e_blake]

Well the good news is that DFS on key collection ordering does successfully solve part 2 within the memory constraints. The bad news is that it took ~77 minutes on PC.

The code is currently pretty awful and uses sub-optimal data structures, so I'm sure I could get that down to ~8 minutes without too much effort, but that would still net me a runtime of ~13 hours on Pico.

I haven't figured out a proper way to exploit symmetry yet (it's still exploring both robot 1 to w followed by robot 2 to k and robot 2 to k followed by robot 1 to w) which would dramatically reduce the search space further.

I'll shift focus over to A* for now and see if I can keep the search queue and visited state set small enough. The fallback is of course making this one require PSRAM to gain another 8Mb of working space.

[u/DelightfulCodeWeasel → u/e_blake]

It's going to be very tight and not at all fast, but it should juuuuuust fit in the 200kb target.

Using your heuristic of the maximum distance for each robot from current location to the remaining keys I'm seeing a maximum priority queue size of ~5,800 (~9,100 pushes and ~3,200 pops), and a total of ~8,500 g_score entries.

At 12 bytes per entry for each, that's ~70kb for the queue, ~102kb for the g_scores, and I've got ~21kb of other data for the various type of edge transition.

The primary issue with speed is going to be storing and looking up in g_store. Ideally that would be a 16,384 entry hash table, but that blows my entire budget in one go.

[u/DelightfulCodeWeasel → u/e_blake]

This is the topology of my maze: [graphviz online]. Not quite as nice as I'd hoped, but at least there's a nice long tail on #2 that forces a large part of the ordering.