Posted in:

So, for the first time, I’m having to admit failure on an Advent of Code puzzle. I knew today’s challenge would be a hard one when I saw that the leaderboard wasn’t full when I woke up a few hours after the puzzle went live. I had to leave the house early, so I wasn’t able to tackle the problem right away, but I did at least have time to read it and think about how I might solve it.

The challenge appears simple. Basically we have a bunch of items that we need to move up to the top floor, using an elevator that can only take two items at a time, and there are some complicated rules about what can and can’t be left on the same floor at the same time. It’s essentially the classic “fox, rabbit and cabbage” problem taken to the next level.

As usual, I wanted to solve this in F# with functional code if possible. So here was my plan:

Given a starting state (what floor is everything on), create a function to enumerate all valid next states. For each of those next states, recursively try all of their valid next states. Keep going until we reach a solution.

That in itself shouldn’t be too hard, but there’s a big problem and that’s performance. We’d essentially get stuck in infinite loops of undoing changes we’d already made, and waste lots of time making pointless moves that got us further from the solution not nearer.

So I attempted some optimisations. First, if we reached a state we’d seen before, we wouldn’t re-attempt it. Comparing lists/maps in F# is nice and easy so this wasn’t too hard. Second, we’d try to make the moves most likely to help first, before trying others. And third, we’d keep track of the shortest solution we’d found so far, and abort any that were longer.

The code I wrote was ugly but did at least work for the test case we were given. However, when presented with the real input, my code was horribly slow. So slow that it’s been running for over an hour even after a few attempts to speed it up. Who knows if it will ever produce an answer?

I do have a few ideas for how to optimize my solution further, but probably that would require a fairly major rewrite which I don’t really have time for.

It is at least reassuring to know that I wasn’t the only one who struggled today. It seems that many who solved it did so by reasoning about their input data, rather than directly coding an algorithm that could find the shortest solution.

One obvious takeaway is that I need to read up more on breadth-first search algorithms and A* search algorithms. My solution is basically failing because it doesn’t explore the possibilities in an efficient order.

So even though I’m probably going to have to admit defeat on today’s challenge, I have at least learnt some valuable lessons. Most notable is that not every programming problem can be solved with brute force, and sometimes you have to think very creatively in order to optimize an algorithm. It would also have helped me a lot if I knew my classic search algorithms a lot better than I do.

If you want to laugh at my code, or tell me how I should have done better take a look here. I’d still like to solve this challenge, but not sure when I’ll get round to doing so, and I guess there is a chance that this series may have to come to a premature end if the problems get any harder!

I did eventually permit myself to look at the shared solutions on Reddit to see what I could learn from other people’s answers, but so far the main thing I learned is that they are a lot cleverer than me! The best answer there is in Ruby which I’m am not too familiar with, so will require time for me to understand and learn from. There certainly didn’t seem to be any easy short-cuts for today’s challenge.