PWC 048 › Survivor (Josepheus problem)

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is described as follows:

There are 50 people standing in a circle in position 1 to 50. The person standing at position 1 has a sword. He kills the next person i.e. standing at position 2 and pass on the sword to the immediate next i.e. person standing at position 3. Now the person at position 3 does the same and it goes on until only one survives.

Write a script to find out the survivor.

This is a well known theoretical exercise in computer science, by the name of the Josepheus problem, based on the story of Flavius Josephus, a Jewish historian in the first century.

Algorithm

To me, the most natural way to solve this problem is with a circular linked list. As a very quick review, a linked list is a list of items where each item also contains a pointer, reference, index, whatever to the next item in the list. A single element is usually drawn like this:

A circular linked list is just a special case where the last item (the tail) points back to the first item (the head). A circular linked list with 4 items (values 1, 2, 3, and 4), can be drawn like this:

Note that this linked list no longer has a head or a tail. Now, say we had a cursor pointed at element 1, and we wanted to delete element 2. We simply set the next reference on element 1 to whatever element 2’s next was (in this case, 3):

Hopefully now it’s becoming obvious why I chose a circular linked list. The delete operation of a circular linked list looks exactly like the procedure given by the problem. Element 1 “kills” element 2 and passes the sword to the element to the right. This operation is constant time, and the only other operation we need for this problem (accessing the next element) is also constant time.

Since the operations we need are constant time, and we always delete one element per iteration, and there are N elements, it follows this algorithm will iterate N – 1 times, resulting in asymptotic performance of O(N).

Perl

Most of the things we might use a linked list for in lower-level languages like C are already very well served by Perl’s built in lists, arrays, and hashes. This is one of those times where I really do want a linked list, though, so I’ll make my own.

Since I only need delete and next, my values are integers and those values never change, I’m going to use an array as my underlying representation. The array index will be the person number, and the array value will be the “next” person number. The 0th array element is unused, so I can use 1-based indexing. So, a circular linked list with 4 elements (people) looks like this:

my @ll = (undef, 2, 3, 4, 1);

In other words, $ll[1] is person 1. Right now $ll[1] = 2, so person 1’s next is person 2. If person 1 kills the next person (2), we do a delete operation by simply changing $ll[1] = $ll[ll[2]].

That’s the main idea. We maintain a $cursor, starting with person 1, and keep performing a delete followed by a next operation until $ll[$cur] == $cur, meaning, there is only one person left.

sub survivor {
    my $N = shift;
    my @ll = (undef, 2..$N, 1); # Circular linked list
    my $cur = 1;
    $ll[$cur] = $ll[$ll[$cur]], $cur = $ll[$cur] until $ll[$cur] == $cur;

    $cur;
}

Raku

In Raku, the code is extremely similar, though the .rotate method is a bit more natural:

sub MAIN( Int $N = 50 ) {
    my Int @ll = 0, |[1..$N].rotate;
    my Int $cur = 1;

    @ll[$cur] = @ll[ @ll[$cur] ] and $cur = @ll[$cur] until @ll[$cur] == $cur;

    say $cur;
}

Analytic solution

There is a constant-time analytic solution to this problem as well. Although I did my own derivation, I am centuries late on being able to claim any sort of original idea. “Publish early and publish often,” right?

Here, I am going to simply present the formula, but if you are interested in the math, I’d suggest having a go yourself first, and then reading the Wikipedia page, as it has a reasonably robust discussion.

For a problem size of N people, you first find \(p = 2^{n} \ni p \le N\). (In other words, find the largest power of two less than or equal to N). Then, the solution, S is given by:

p can be found using logarithms, so the entire solution can be represented by the following expression:

Coding this up is easy enough. I only bothered with a Perl version, as the Raku version would be practically identical:

sub analytic2 {
    my $N = shift;
    2 * ($N - 2**int( log($N) / log(2) )) + 1;
}

Predictably, it vastly out-performs the looping version:

            Rate   linked analytic
linked     707/s       --     -97%
analytic 20442/s    2790%       --

There’s no denying the math is elegant and it’s hard to argue with O(1) time and space efficiency, but from an irrationally recreational point of view, I like the linked list version better.