# ETOOBUSY 🚀 minimal blogging for the impatient

# AoC 2016/19 - Josephus problem

**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 🤓

*Comments? Octodon, , GitHub, Reddit, or drop me a line!*