DISQUS

It helps to get the algorithm right.

sub josephus
{
my %alive = map { $_, 1 } (0..TOTAL-1);
my $current = -1;

while (scalar keys %alive 1)
{
for (1..INTERVAL)
{
do
{
$current = ($current + 1) % TOTAL;
} until exists $alive{$current};
}

delete $alive{$current};
print "$current just died.\n"
if DEBUG;
}

my ($survivor) = (keys %alive);

print "last to die: $survivor\n"
if DEBUG;

return $survivor;
}

Not surprisingly, solving the problem in idiomatic but clean Perl winds up being *extremely* fast:

#!/usr/bin/perl

use strict;
use warnings;
use diagnostics;

use Benchmark qw(:all);

use constant TOTAL = 40;
use constant INTERVAL = 3;
use constant DEBUG = 0;

sub josephus
{
my %alive = map { $_, 1 } (0..TOTAL-1);
my $current = -1;

while (scalar keys %alive 1)
{
$current += INTERVAL;
$current %= TOTAL;

while (!exists $alive{$current})
{
$current++;
$current %= TOTAL;
}

delete $alive{$current};
print "$current just died.\n"
if DEBUG;
}

my ($survivor) = (keys %alive);

print "last to die: $survivor\n"
if DEBUG;

return $survivor;
}

my $bm = timeit (10000, \josephus);
print timestr ($bm);

On my 7-year-old Linux box, I get 6172 iterations per second with this code.