Advent of Code Day 22–Selecting Spells

As expected, the difficulty level of the Advent of Code challenges is ramping up, and due to some silly mistakes on my part, today’s challenge took longer than I’d like. It meant I didn’t have time to either improve my C# solution or create an F# one. But I’ve still got someone else’s F# solution to talk about in the video, and we see that both my approach and this F# one have their own unique strengths and weaknesses.

My rather ugly C# solution can be found at this gist. It turns out that a random spell selecting strategy will help you converge on the right answer without too much effort. Interestingly, the guy who came 4th on the leaderboard took exactly the same approach with random spell selection in C# (apart from implemented much less verbosely than I did it!), so maybe this solution isn’t as crazy as it might appear

The F# strategy I discuss in the video can be found here. Whilst it worked great for the author’s test input, for mine it ran way too slow as it evaluated all possible battles. However, I think it is a really elegant piece of code, and the original author kindly provided an improved version, that solves my input much quicker by abandoning battles that don’t improve upon the best score found so far.

As I said in the video, what was really needed was a systematic way of storing partial game states, whilst heading onwards to a complete battle (a “depth first search”?), and then going back and completing the partial battles only if they would produce a better solution. That would be best of both worlds, and it turns out that someone did exactly that in C#, and their solution can be found here.

There were a few takeaways from today’s challenge. First was the easier you make your code to debug, the quicker you’ll track down silly mistakes. Second was that brute force solutions, while being much more concise and elegant and sometimes fail to provide the answer in reasonable time. Thirdly, sometimes solutions that are not strictly “correct” (e.g. a random spell chooser) can nevertheless get the job done. And finally, don’t be too proud to look at the way other people solved the same problem. You will learn a lot from examining other people’s solutions.