As I mentioned, a colleague recommended the 2019 series of puzzles because of the CPU emulation aspect. I'll go into that in a later entry.
A puzzle from 2019 that I particularly enjoyed was 2019.18. A very interesting challenge.
Essentially, you are given a maze as input. The interesting aspect of this puzzle though is that there are upper- and lower-case characters strewn throughout the maze. The uppercase characters represent doors, while lowercase ones represent keys that will open the corresponding door.
Your job is to find the shortest path through the maze that unlocks all the doors. I was very intrigued with this one.
Here is a visualisation of how I solved the problem, and I'll explain my approach below.
So, this is not necessarily a textbook CS approach to it, but it is how I decided to solve it (no doubt biased by my maze solving adventures as a child.)
I approached the problem in two phases essentially.
- Find the distances between all the doors, keys and the start point (start - 2:23).
- Find the shortest path that opens every door given what was discovered in phase one.
Phase 2 is not really engaging to visualise, so the remainder of the video (2:23 - end) is just the execution of the path that the code found.
While visualising using the console as in this video was a useful aid, I wish I'd switched to using MonoGame earlier for more performant and visually interesting illustrations. More on that in a later post I expect.
Phase 1
As you may be able to discern in the video, I start a "bot" at each significant point on the map (keys, doors and start point.)
Each of these bots will then try and explore the entire map. They do this by splitting into copies of themselves whenever there is a choice of more than one way to go. Each copy retains the history of the bot that spawned them. While in the visualisation this may not look too efficient, it actually completes in ~200ms.
The hardest problem I faced in this exploration phase was the centre of the map. The maze exploring bots were designed to split at junctions, which is fine. However, the center of the map was an open 3×3 square. This caused a massive problem with any bots entering that area just splitting infinitely. I eventually solved this by ensuring each bot not only stores the important cells they had encountered, but their entire history of travel. This way, I could prevent a bot from spawning a copy to visit a cell that it had already been to.
At the end of this phase, I now have a list of the routes between all significant points on the map.
Phase 2
To be continued... (mainly because it's late and there was actually quite a lot of code in my solution for this one which I need remind myself of how it works.)
I kind of have a policy that code should mostly not need comments if it is well thought out, well structured, good variable names etc... but sometimes, I wish I'd left myself some comments.
