TL;DR

On with Advent of Code puzzle 19 from 2016: Josephus problem!

I know this is a spoiler in the very title of the post, but the 2016 edition of Advent of Code was… well… more than four years ago!

Although described as an instance of White Elephant parties, the author decided to give some spoiler too, because the title of the puzzle is… Day 19: An Elephant Named Joseph 😄

So… it seems that all that time spent on watching Numberphile videos was indeed well spent, because they covered this very topic quite well: The Josephus Problem - Numberphile. It’s a very interesting video!

The one interesting thing is that this problem has a closed-form solution that’s easy to code in $O(1)$. As a matter of fact, some bit fiddling suffices here, here’s my Perl implementation for the first part of the puzzle:

sub josephus ($n) {
   my $p2 = 0x1;
   $p2 = ($p2 << 1) | 0x1 while $p2 < $n;
   my $k = $n & ($p2 >> 1);
   return $k << 1 | 1;
}

The part that I’m not entirely happy with, to be honest, is the one where I look for the right mask to get rid of the biggest power of $2$ in the number, because it’s a loop and I should probably say that the algorithm is actually $O(k)$ where $k$ is the number of bits representing integers here. But… if we stick with 64 bit integers we’re still at $O(1)$, right?!?

I had fun with this puzzle because I remembered about the Josephus problem and I also remembered that there was some way to figure out the rule. So I had the pleasure to re-derive it.

I know, it’s easy to please me with these nerdy stuff 🤓