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 š¤