DEV Community

Cover image for Advent of Code 2019 Solution Megathread - Day 18: Many-Worlds Interpretation
Jon Bristow
Jon Bristow

Posted on

Advent of Code 2019 Solution Megathread - Day 18: Many-Worlds Interpretation

Welp, it's time for the A Stars to get to work.

Day 18 - The Problem

Our run-in with the space police earlier was a dread foreshadowing!

Passing Triton, we've been pulled into some sort of base or prison and need to escape. Lets pick up the keys (which are helpfully all color coded).

Part 1 is to find the most efficient way to get all the keys and report their order.

Part 2 has to wait, since Tuesday is my nerd night out.

Ongoing Meta List of Leaderboards

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Discussion (2)

neilgall profile image
Neil Gall

While I'm sure there's a fast solution to day 16 part 2, I find fiddly numeric algorithms quite frustrating and my laptop at home is still running a brute-force solution 36 hours on. Day 17 part 1 was straightforward (mainly because it doesn't matter which way you follow a loop in the path so an effective strategy is to go straight ahead at every intersection) but part 2 seems to involve a depth-first search for the possible routes with another depth-first search to find a data compression candidate. Day 18 part 1 is another complex search.

I want to solve these problems and I want to do them well, not just find any old solution that gets me the stars. Hopefully that's evident in some of my earlier solutions which have tests and what I believe to be well-structured code, rather than a dense set of nested for loops iterating over a tuple-of-maps-of-lists-of data structure. The first two weeks of AoC 2019 were fun and mostly small enough to do in an hour or two, then optimise or improve if you have more time. The problems since day 16 are too hard to solve well in a single day. If you have other commitments (a job, kids, Christmas parties!) it's impossible. This, a bit of burn-out and Ben Lovy's post the other day have made me reconsider racing through AoC.

I hope to finish AoC 2019 but I feel I've already let the quality slip and that gives me no joy. I'll post solutions as I get them, even if that means I'm still thinking about how to help the elves when I'm sitting in the garden in the summer sun.

jbristow profile image
Jon Bristow Author • Edited

No need to apologize for doing what’s right for your health (mentally, spiritually, physically)! There are NO PRIZES or deadlines, so I encourage everyone to solve these at your leisure.

I’ll be watching these threads and the category tag, so I’m looking forward to see more people’s solutions.

My only hint: any solution that requires more than a minute or two to run is probably not the intended solution.

Also also: yesterday’s problem was most likely meant to be solved by hand for the middle portion. There was only 20-30 instruction pairs in my set...