merlyn stirs his dry martini on the latest linux geek cruise, unaware that the right. rev lars marius garshol has just arrived, late, and *someone* is going to have to double-up rooms.

rev. garshol is going to be preparing a sermon on the seven deadly (programming) sins, foremost of which is, naturally, > 4 operators in any script.

the cruise masters decree that to solve the problem, all cruise members are to be arranged in a circle, and every nth member is to be struck off until one remains, that one to get garshol.

ie: with 10 geeks, and a skip number of 1, the geeks will be relieved of lars in the following manner:

{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"},# start

{"3", "4", "5", "6", "7", "8", "9", "10", "1"},# 2 saved

{"5", "6", "7", "8", "9", "10", "1", "3"},# 4 saved

{"7", "8", "9", "10", "1", "3", "5"},# 6 saved

{"9", "10", "1", "3", "5", "7"},# 8 saved

{"1", "3", "5", "7", "9" },# 10 saved

{"5", "7", "9", "1"},# 3 saved

{"9", "1", "5" },# 7 saved

{"5", "9"},# 1 saved

{"5"}# 5 spends the night with garshol



of course things get more complex with n = any integer, and any number of geeks to be saved.

undeterred, our hero gathers the enlightened on the cruise, and instructs them all, using a simple script, on which places *not* to stand at.

here is what he might have coded:

for (($m,$n,$r)=@ARGV, $jl=[1..$n]; @$jl>$r; shift @$jl){
push(@$jl,shift @$jl) for (1 .. $m) 
}
print "avoid positions " , join(" ", @$jl) . "\n";
[download]

m, n and r are the skip number, the total number of geeks, and the number of (perl) enlightened to be saved from lars. so we get:

avoid positions 3222783

if we use m = 1, n = 9999999, r = 1

admittedly this is a large number of geeks and it takes time. admittedly, there is a low probability of having to share with the reverend. but there is also sod's law...

if a larger number of geeks appear on the cruise, and every other person is skipped, then for merlyn alone we can find out the position faster, in less memory, via:

sub joe {$n=$_[0];($n==1)? 1:(($n % 2)? 2*joe(($n - 1)/2)+1:2*joe($n/2
+)- 1)}
print "v2: use position " . joe($n) . "\n";
[download]

speedy and non-memory-exhaustive solutions ensue. the recursion is loads faster than the previous, but then it is not as generalizable. select your favourite, take it with you wherever you go, just in case ;-)

wufnik

-- in the world of the mules there are no rules --