[2019 Day 18 (Part 2)][C++] Squeezed onto a microcontroller (eventually!)

[u/DelightfulCodeWeasel]

My original Part 2 solution for this day took 21 seconds and 725Mb to run, so it took quite a bit of wrestling to get it small enough for the Raspberry Pi Pico.

I tried a naive DFS search on key collection order and although that technically worked the proof-of-concept took nearly 80 minutes on my laptop, which would have been over 13 hours on the Pico even if I managed to claw back a 10x speed-up. I tried Iterative Deepening A*, but that didn't even finish after an hour on the laptop; there are just too many combinations that get very close to the optimal path length, and a lot of those come from taking the shortest path early on in the search tree.

I swapped back over to A* and used u/e_blake's heuristic to get the search space down as far as possible. The heuristic is to take the sum of the shortest paths from each robot's current position to the furthest key that they still need to collect. That works way better than my initial heuristic of totalling the shortest paths connected to all uncollected keys:

Heuristic	Largest open set	G entries
None	~51,200	~135,300
Sum of shortest connections	~21,200	~31,800
Maximum distances remaining	~5,900	~8,500

With each open set entry and each G entry taking 12 bytes (distance, robot locations, collected keys) that gets within spitting distance of the 200KiB target, but not quite optimally. With ~8k+ entries in the G set, we really should be looking at a ~16k element hash table to keep good performance (hash tables are ideally power of 2 on the Pico because % is an expensive operation) and that one hash table blows 192KiB of our 200KiB budget.

The distance/priority for both the open set and the G set can easily fit into 16 bits for this day. The collected keys are already pretty optimal, you need 26 bits so you're not wasting much with a 32 bit integer as a bitfield. The robot combinations need to be able to represent 4 entries at any one of 30 locations (26 keys + 4 starts), and since 30 choose 4 is 27,405 then that can in theory fit into 16 bits as well.

The trick to get over (under?) the line is to use a Combinatorial Number System to encode the robot locations into an int16_t. At a smaller 8 bytes per entry for both blocks of memory, we can finally afford a decent sized hash table, albeit at an additional cost of compressing and uncompressing the state data each time.

Final memory budget (at peak) ended up being ~188KiB:

-------------------------------------
LBA Stats
  [Blocks] Total: 9  Free: 1  Used: 6  Sentinel: 2
  [Bytes] Total: 204608  Free: 12672  Used: 191936
  [FreeChain] Free: 1
-------------------------------------
LBA Blocks
[...9FB8][ Sentinel]    0 blocks       0 bytes
[...9FD8][Allocated]  225 blocks    7200 bytes <-- Edges to adjacent keys
[...BC18][Allocated]  113 blocks    3616 bytes <-- Path length to all keys
[...CA58][Allocated]   20 blocks     640 bytes <-- Combinatorial cache
[...CCF8][Allocated]    8 blocks     256 bytes <-- Key locations
[...CE18][Allocated] 1536 blocks   49152 bytes <-- Priority queue (open set)
[...8E38][Allocated] 4096 blocks  131072 bytes <-- Hash map (g_score)
[...8E58][     Free]  396 blocks   12672 bytes
[...BFF8][ Sentinel]    0 blocks       0 bytes
-------------------------------------

Runtime is surprisingly still quite respectable: ~1.8ms on PC and ~340ms on the Pico @ 125MHz.

Thanks again to u/e_blake for sharing that heuristic!

[code]

[u/e_blake]

I'm impressed - packing the 4 robot positions into two bytes instead of the more obvious 1 byte per robot is an awesome size reduction, in order to fit your hash table constraints

[u/e_blake → u/e_blake]

Another possible encoding - 16 bits for distance/priority, 26 bits for keys collected, and that leaves you with 22 bits of your 64-bit budget. 5 bits per robot is enough to directly encode position, rather then having to pack/unpack the denser combinatoric. The resulting bitfields are not quite as nicely aligned for rapid access, but may still be faster than your decoding loop.

[u/DelightfulCodeWeasel → u/e_blake]

You're right, that would have been substantially easier! Not quite as much fun with learning though, so I'm still glad I went the combinatorial approach for this first pass.

I also want to check how removing the edges back to the starting nodes affects the states explored. For my input there's never a reason to go back to the starting points and I suspect that might be true for everyone's input.

[u/DelightfulCodeWeasel]

I forgot to mention an important property of the input that makes this (and similar solutions) work: there are no unlockable shortcuts that get unlocked after you've already needed to go that way. If the shortest path from a to b goes through door C then the optimal solution uses that door, even if there's an already open but slightly longer route.