*This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions 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 `$cur`

sor, 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.