One of my major achievements of 2020 – apart from solving the Rubik’s cube blindfold, which I’m still very smug about – was completing the Advent of Code challenge.

It’s pitched just about right for me: enough to get my teeth into, enough to make me feel clever when I code up the answer, but (usually) not so tough that I tear my hair out.

With one exception: part two of day 23.

For reasons that make limited sense, you are on a raft playing games with a crab. The game in question involves a million numbered cups set out in a circle and a set of rules:

  • Pick up the three cups clockwise of cup you’re currently looking at
  • Find the cup numbered one less than the current cup (keep reducing by 1 if it’s a cup you’ve picked up, and wrap around to the biggest numbered cup if you need to)
  • Put the three cups clockwise of the cup you just found
  • Change the current cup to the one immediately clockwise of the current cup.

You need to do this ten million times and find the two cups clockwise of cup 1.

If you want to have a go at it, please do! There are spoilers below the line.

The obvious way

The “obvious” way is to create an array and shuffle things around according to the rules. That’s how I did the first part. In principle, it’ll work for the second as well.

“In principle”. That’s not good.

The trouble is, at least in my language of choice (Python), it takes ages. Every time you do an iteration, the computer has to move huge numbers of cups (or numbers) from one memory location to another. While each of those moves only takes a small fraction of a second, doing lots of them adds up – especially if you’re doing ten million moves. If each move takes 0.005s, ten million moves takes about 14 hours.

So we either need a lot of thumb-twiddling (and hoping that it works properly first time), or we need a different approach.

A better approach

My epiphany came pretty much as soon as I realised what the hold-up was. What if there was a way of doing the moves without updating the whole array each time?

Now, back in the day, I looked for jobs in coding, and interview preparation involved looking at all manner of data structures – how to arrange the things the computer does in an efficient way. One of these is the linked list.

Rather than holding the whole set of cups in order in memory, a linked list consists of storing only what’s clockwise from each cup – a link to the next element of the list.

In a linked list context, each move consists of updating just three values:

  • the current cup’s next element becomes the third cup’s next element
  • the third picked-up cup’s next element becomes the target cup’s next element
  • the target cup’s next element becomes the first picked-up cup.

And that’s it! Three operations per move instead of (on average) half a million - with the result that my code gave the correct answer in a few seconds.