• Yanman (unregistered) in reply to Josephus
Josephus:
Last

hero!

• Robert (Jamie) Munro (unregistered) in reply to Alex Mont

This simplifies to just

def J(n,k): return n!=1 and (J(n-1,k)+k)%n

• (cs) in reply to Code Dependent
Code Dependent:
Dave:
```foreach(soldier:soldiers){
soldier.kill();
}
God.getInstance().sortOut(soldiers);
```
Shouldn't God be static?
I can't decide whether God being static is bad coding or being inconsiderate towards other religions...

Also +1 internets for Dave. Made me laugh.

• SR (unregistered) in reply to d3matt
d3matt:
Code Dependent:
Dave:
```foreach(soldier:soldiers){
soldier.kill();
}
God.getInstance().sortOut(soldiers);
```
Shouldn't God be static?
yes... the God class is a singleton...

d3matt: I've got a billion or so Hindus on the phone who don't agree

• Andreas Kromann (unregistered) in reply to Wongo
Wongo:
The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

• (cs)

python one-liner, 1-based index using skips and not counts:

```f=lambda n,k:(f(n-1,k)+k)%n+1 if n-1 else 1
```
• (cs)

Hooray for "Scheme"

```(define josephus
(lambda (soldiers jump)
(if (eqv? soldiers 1)
0
(modulo (+ (josephus (- soldiers 1) jump) jump) soldiers)
)
)
)
```
• vang (unregistered)

```#!/usr/bin/perl

use strict;
use Getopt::Long;

our \$debug;
my \$number = 40;
my \$skip   = 3;

GetOptions(
"number=i" => \\$number,
"skip=i"   => \\$skip,
"debug"    => \\$debug
);

my \$index = josephus( \$number, \$skip );
print "Safe Spot: \$index\n";

sub josephus {
my \$number = shift;
my \$skip   = shift;

my @people = ();

my \$pos = -1;

for ( my \$i = 0 ; \$i < \$number ; \$i++ ) {
push @people, 1;
}

for ( my \$i = 0 ; \$i < \$number - 1 ; \$i++ ) {
\$pos = nextval( \$pos, \$skip, \@people );
dbg_print("killed \$pos\n");
\$people[\$pos] = 0;
}

\$pos = nextval( \$pos, 1, \@people );
return \$pos;
}

sub nextval {
my \$pos       = shift;
my \$skip      = shift;
my \$peopleref = shift;

my @people = @\$peopleref;

my \$i = 0;
while ( \$i != \$skip ) {
\$pos++;
\$pos %= scalar @people;
if ( \$people[\$pos] == 1 ) {
dbg_print("skipped \$pos\n");
\$i++;
}
}
return \$pos;
}

sub dbg_print {
my \$message = shift;
if (\$debug) {
print "DEBUG: " . \$message;
}
}
```
• Perl Monk (unregistered)

Perl Golf'd:

\$p[\$-1]=\$ for 1..\$ARGV[0];[email protected],\$k=(\$k+\$ARGV[1]-1)%@p,[email protected]>1;[email protected]

77 chars :-)

• rm5248 (unregistered)

Java! There are of course more elegant ways to do this, but that would be defeating the purpose.

public class JosephusCircle {

``````/**Perform a game of Josephus' Circle!  This is a game similar to Russain
* Roulette, in which the people playing have an unnerving desire to kill
* themselves.
*
* @param args Program arguments; the first is the number of soldiers, the
* second argument is the number of soldiers to skip
*/
public static void main(String[] args) {
if( args.length != 2 ){
System.err.println("Usage: JosephusCircle <soldiers> <soldiers to skip>");
System.exit(0);
}

int soldiers = Integer.parseInt(args[0]);
int soldiersToSkip = Integer.parseInt(args[1]);

boolean[] stillAlive = new boolean[soldiers];
for( int x = 0; x < stillAlive.length; x++){
//booleans are initialized to be false!
stillAlive[x] = true;
}

int numLeft = soldiers;
while(numLeft > 1){

for( int x = 0; x < stillAlive.length; x++){
//let's go find the next alive person!
if(stillAlive[x] == true){
}

stillAlive[x] = false;
numLeft--;
}
}
}

//loop thru to see who is still true!
for( int x = 0; x < stillAlive.length; x++){
if(stillAlive[x] == true ){
//must add one to the index because arrays are 0 based
System.out.println("Joesphus is at: " + (x+1) );
}
}
}
``````

}

• Observer (unregistered)
Thus our formula is (code in Python):
```def J(n,k):
if(n==1)
return 0
else
return (J(n-1,k)+k)%n
```

Congratulations to everyone that found the very elegant solution outlined on wikipedia...

http://en.wikipedia.org/wiki/Josephus_problem

When the optimal solution for a problem for a solution gets regurgitated in less than 30 minutes, it might be a sign that you need a more unique problem to solve.

How about next week we try to find a solution to the infamous TOWER OF HANOI problem or how to find the factorial of a number!

• Lifacciolo (unregistered)

Code in Python Instead of looking for a mathematical solution (Like Alex Mont did, I loved that solution) I opted for a more simple straightforward simulation of the process of picking.

(The solution given by this is the index of the array, thus the "real position" will be the return of the resolve function + 1)

```import itertools
def resolve(soldiers, skip):
circle_index = range(soldiers)
circle_choices = itertools.cycle(circle_index)
while len(circle_index) > 1:
print "Current circle: %s" % (circle_index,)
for i in range(skip):
to_remove = circle_choices.next()
index = circle_index.index(to_remove)
print "Will remove: %s" % (to_remove,)
circle_index = circle_index[index:] + circle_index[:index]
circle_index.remove(to_remove)
circle_choices = itertools.cycle(circle_index)
return circle_index[0]

print resolve(40,3)

```
• (cs) in reply to Andreas Kromann
Andreas Kromann:
Wongo:
The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

using (5,1) we should get 3, but with your shortcut you get

```    1 + (5-1)1 mod 5
==> 1 + 4 mod 5
==> 1 + 4
==> 5
==> fail
```
• (cs)

A missing point of the article: The reason for such a procedure is because in the Jewish religion it is not permitted to commit suicide.

There is a story in which an entire Jewish town was about to be captured, so it was decided that the head of the family will use a knife to slay each of his family members, then all the remaining men would kill each other, but never themselves. They would take responsibility for committing murder and suffer in the afterlife as a compassion gift to their families for not having to commit suicide nor having to suffer slavery. However there was no such circle, the men would instead kill each other with the last two killing each other simultaneously.

So yea, otherwise they would all just slit their own throats.

Ok back to the programming exercise.

• scp (unregistered)

This should work, even with bugs ;) (cpp)

```#include <stdio.h>
#include <stdlib.h>

struct human
{
human *prev, *next;
int number;
};

int main(int argc, char * argv[])
{
int i,j, n = atoi(argv[1]), k = atoi(argv[2]);
human * h = (human *) malloc(n * sizeof(human));
for (i=0;i<n;i++)
{
h[i].next = &h[(i+1)%n];
h[i].prev = (i-1<0) ? &h[n-1] : &h[i-1];
h[i].number = i+1;
}

human * _h = &h[n-1];

for (i=1;i<n;i++)
{
for (j=0;j<k;j++)
{
_h = _h->next;
printf("%d->", _h->number);
}
printf("X \n");
_h->prev->next = _h->next;
_h->next->prev = _h->prev;
_h=_h->prev;
}
printf("%d survives\n", _h->number);
return 0;
}
```
• Osno (unregistered)

Naïve C# implementation:

```        private static int JosephusCircle(uint participants)
{
int next = -1;
List<bool> standing = InitArray(participants);

{
next = FindNextToDie(next, standing);
KillNext(next, standing);
}
Console.WriteLine();
return next + 1;//list is 0 based, result is 1 based
}

private static void KillNext(int next, List<bool> standing)
{
Console.Write("{0} ", next + 1);
standing[next] = true;
}

private static int FindNextToDie(int next, List<bool> standing)
{
int count = 0;
while (count < 3)
{
next++;
if (next == standing.Count) next = 0;
if (!standing[next]) count++;
}
return next;
}

{
return standing.TrueForAll(p => p);
}

private static List<bool> InitArray(uint participants)
{
List<bool> standing = new List<bool>(Convert.ToInt32(participants));
for (int i = 0; i < participants; i++) standing.Add(false);
return standing;
}
```
• (cs) in reply to astonerbum
astonerbum:
A missing point of the article: The reason for such a procedure is because in the Jewish religion it is not permitted to commit suicide.

There is a story in which an entire Jewish town was about to be captured, so it was decided that the head of the family will use a knife to slay each of his family members, then all the remaining men would kill each other, but never themselves. They would take responsibility for committing murder and suffer in the afterlife as a compassion gift to their families for not having to commit suicide nor having to suffer slavery. However there was no such circle, the men would instead kill each other with the last two killing each other simultaneously.

So yea, otherwise they would all just slit their own throats.

Ok back to the programming exercise.

You're referring to the siege of masada.

• Osno (unregistered)

BTW, I love Josephus' books... and I think he actually only wrote those two (and Against the Greeks), and The Antiquities are almost identical to the Wars, IIRC.

Javascript solution:

// brute force method function josephus1(count, seed) { var men = new Array(count); var dead = 0; var index = 0; var passes = 0;

// 1. Loop through an array of men who's values are initially set to false to indicate they are not dead. for (var i = 0; i < count; i++) { men[i] = false; }

// 2. Keep counting men if they are not already dead and killing them if they are the nth man until the number of dead is one less than the total dead. while (dead < count - 1) { if (men[index] == false) { passes = passes >= seed ? 1 : passes + 1;

``````  if (passes % seed == 0)
{
men[index] = true;
}
}
index = index >= count - 1 ? 0 : index + 1;
``````

}

// 3. Return the last man standing by looping through the array of men and finding the one who is not dead for (var i = 0; i < count; i++) { // if the man has not been killed return his index plus one to indicate his position (to account for zero based arrays) if (!men[i]) return i + 1; } }

// an improved version which removes the array elements completely so we don't continually count dead men function josephus2(count, seed) { var men = new Array(count); var index = 0; var passes = 0;

// initialize the men to their position in the circle for (var i = 0; i < count; i++) { men[i] = i + 1; }

// keep killing the nth man by removing him from the array until there is only 1 man left while (men.length > 1) { passes = passes >= seed ? 1 : passes + 1; if (passes % seed == 0) { men.splice(index, 1); if (index >= men.length) index = 0; } else { index = index >= men.length - 1 ? 0 : index + 1; } }

// return the last man standing's position return men[0]; }

• Ian (unregistered) in reply to Code Dependent
Code Dependent:
Dave:

foreach(soldier:soldiers){

soldier.kill();

}

God.getInstance().sortOut(soldiers);

Shouldn't God be static?
If God were static how could He move in mysterious ways?
• Karol Urbanski (unregistered) in reply to Perl Monk
Perl Monk:
Perl Golf'd:

\$p[\$-1]=\$ for 1..\$ARGV[0];[email protected],\$k=(\$k+\$ARGV[1]-1)%@p,[email protected]>1;[email protected]

77 chars :-)

My own attempt at golfing this (subroutine):

`sub k{\$_[0]&&(k(\$_[0]-1,\$_[1])+pop)%pop}`
40 chars. I use \$_+indexes and two pops at the end because that ends up being 2 chars less than initialising \$a and \$b from @_ (which would have to be "my(\$a,\$b)[email protected]_;" <- 13 chars.) "[0][0][1]pp" (the additional chars needed to avoid initialising the vars) is just 11 chars.

The mandatory one-liner (true one-liner, no semicolons)

```\$ perl -E'sub k{\$_[0]&&(k(\$_[0]-1,\$_[1])+pop)%pop}say [email protected]' 12 3
9```
59 chars + args.

Indexed from 0. I'm certain it's possible to golf this further, though, I don't like this solution...and I'm loving those little challenges :).

• Anon (unregistered)

The obvious solution is tell everybody else that you just need to take a quick bathroom break and they should start without you.

• Andreas Kromann (unregistered) in reply to halber_mensch
halber_mensch:
Andreas Kromann:
Wongo:
The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

using (5,1) we should get 3, but with your shortcut you get

```    1 + (5-1)1 mod 5
==> 1 + 4 mod 5
==> 1 + 4
==> 5
==> fail
```

No it is 5 not 3 ... you fail ...

{1,2,3,4,5} => {2,3,4,5} => ... => {5}

• (cs)

Here's a straight forward solution in PHP. Not really a function but can be easily converted into one.

No recursivity, with 1000 soldiers or something like that PHP would probably crap out.

```<?
\$nr = 12;
\$step = 3;

\$soldiers = array();
for (\$i=1;\$i<=\$nr;\$i++) {
\$soldier = array();
\$soldier['next'] = \$i+1;
\$soldier['prev'] = \$i-1;
\$soldiers[\$i] = \$soldier;
}
\$soldiers[0]['next'] = 1;   // start from here but it's not in the chained list
\$soldiers[\$nr]['next'] = 1; // last element is linked to the first to form the circle
\$soldiers[1]['prev'] = \$nr; // and first element is linked to the last

\$count = \$nr;
\$soldiertodie = 0;
while (\$count!=1) {
for (\$i=1;\$i<=\$step;\$i++) {
\$soldiertodie = \$soldiers[\$soldiertodie]['next'];
}
echo 'Soldier '.\$soldiertodie.' is killed.<br/>';
\$soldiers[\$soldiers[\$soldiertodie]['prev']]['next'] = \$soldiers[\$soldiertodie]['next'];
\$soldiers[\$soldiers[\$soldiertodie]['next']]['prev'] = \$soldiers[\$soldiertodie]['prev'];
\$lastsoldier = \$soldiers[\$soldiertodie]['prev'];
\$count--;
}
echo 'The last soldier standing is '.\$lastsoldier.'';

?>

```
• Anon (unregistered) in reply to Wongo
Wongo:
Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

So there must be some kind of shortcut (e.g. to know whether a number is divisible by 5, you don't have to actually divide it, just check whether the final digit is 5 or 0).

The shortcut, according to Josephus himself, was luck (or the hand of God). Besides, if he hadn't been the last man (or rather one of the last two) men standing, he wouldn't have been able to write about it later.

• Yazeran (unregistered) in reply to null
null:
You stand as a first one to die and then invert the alive-dead state and you're the only one alive.

But you do realize that in order to do that you need 'The infinite improbability drive' which incidentally requires a good hot cup of tea.

But to get a good hot cup of tea is in my experience impossible, had it been coffee, then it could be done... -)

Yours Yazeran

Plan: To go to Mars one dya with a hammer

• Anon (unregistered) in reply to Andreas Kromann
Andreas Kromann:
halber_mensch:
Andreas Kromann:
Wongo:
The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

using (5,1) we should get 3, but with your shortcut you get

```    1 + (5-1)1 mod 5
==> 1 + 4 mod 5
==> 1 + 4
==> 5
==> fail
```

No it is 5 not 3 ... you fail ...

{1,2,3,4,5} => {2,3,4,5} => ... => {5}

I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0. What you have shown is skip 0, in which case you just kill 1 then 2 then 3, etc. If you skip one, you kill 2, then (skip 3) 4, then 1 (skip 5), then 5 (skip 3) leaving 3 alive. {1,2,3,4,5} => {1,3,4,5} => {1,3,5} => {3,5} => {3}

• (cs)

Since the recursive solution has been done quite a bit...I thought something more interesting was in order:

```survivalByAlcohol(int soldiersLeft, int deathNumber, Soldier you){
Soldier soldierInDanger = getNextLivingSoldier();
while (soldiersLeft > 1) {
if (soldierInDanger.equals(you)) {
offerEveryoneAlcoholicDrink();
if (yourNumber != deathNumber) {
System.Mouth.say(yourNumber);
}else{
try {
System.Mouth.say(deathNumber - 1);
} catch (SomeoneArguesException e) {
startAFight();
}
}
}else if (number == deathNumber) {
soldiersLeft--;
soldierInDanger.setAlive(false);
number = 0;
}
number++;
soldierInDanger = getNextLivingSoldier();
}
}
```
• Andreas Kromann (unregistered) in reply to Anon
Anon:
I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0. What you have shown is skip 0, in which case you just kill 1 then 2 then 3, etc. If you skip one, you kill 2, then (skip 3) 4, then 1 (skip 5), then 5 (skip 3) leaving 3 alive. {1,2,3,4,5} => {1,3,4,5} => {1,3,5} => {3,5} => {3}

Yes indeed. k = 1 means "first one I point at gets the fraking axe" :) So... 1 + (n-1)k mod n

• (cs)

Javascript -- Trial 1

```// a size number of indexes exist, we start killing indexes by taking the
// live index at the offset killed and skipping skip indexes before killing
// the next one pointed to.
// the Safe Number is the index that will not be killed.
// thus is the Josephus' Circle.
function JosephusCircle(size, skip) {
// some base conditions
// one size = safe
if (size === 1) {
return 1;
}
// less than zero size cannot exist
if (size <= 0) {
return -1;
}

// The value of each element in the array is the safe index.
var arr = [];
for (var i = 0; i < size; i++){
arr[i] = i;
}
// Start looking for safe indexes starting at 0.
var indx = 0;
while (arr.length > 1) {
// skip over skip indexes (-1) and wrap
// around the array length for the next index to remove
indx = ((indx + skip) - 1 ) % arr.length;
// kill the given index from the array, the index now
// points to the next element to start counting at
arr.splice(indx, 1);
}
// The safe number.
return arr[0];
}
```

Yay! <-- apparently this allows me to submit :)

Edit: The index returned is zero-based. Add 1 to it if you want a 1-based index.

• (cs) in reply to Ian
Ian:
If God were static how could He move in mysterious ways?
Well, I know that when my socks and shirts come out of the dryer they're full of static, and it makes them move in mysterious ways...
• (cs) in reply to Anon
Anon:
I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0.
Well, when the algorithm was posted, it was assume k meant "kill every kth person, not skip k persons between skips."

So, if you want the second letter to be the number of skips, modify the algorithm to: 1 + (n-1)(k-1) mod n

• Wongo (unregistered) in reply to Osno
Osno:
BTW, I love Josephus' books... and I think he actually only wrote those two (and Against the Greeks), and The Antiquities are almost identical to the Wars, IIRC.

He actually wrote "Teach yourself recursion in VB.Net in 10 days", did you know?

Anon:
The shortcut, according to Josephus himself, was luck (or the hand of God). Besides, if he hadn't been the last man (or rather one of the last two) men standing, he wouldn't have been able to write about it later.

So the "somehow managed to figure out" is a red herring???

Andreas Kromann:
As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

Er... nope, it doesn't work:

33 soldiers: (1 + (33-1) * 3) mod 33 = 31 instead of 7.

• Phil (unregistered) in reply to Wongo
Wongo:
Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

From where did you get that 860 iterations?

• IV (unregistered)

I am taking the Schroedinger approach - instead of using an axe, have everyone climb into a box with a bottle of poison. At that point, everyone is both alive and dead. Thus, the suicide is successful (each person is dead), but our hero has survived (he is alive).

• (cs)

A brute force, linked-list-traversal method for the HP 48:

(Replace != with the built-in not-equals symbol.)

```<< 0 { } 0 -> N S P L I
<< 1 N
FOR C C
NEXT N ROLL N
->LIST 'L' STO N 'I'
STO
WHILE 'L' I GET
I !=
REPEAT 1 S
START I 'P'
STO 'L' I GET 'I'
STO
NEXT 'L' P
'L' I GET PUT
END I
>>
>>
```
• Wongo (unregistered) in reply to Phil
Phil:
Wongo:
Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

From where did you get that 860 iterations?

static int counter;

int Josephus(int n, int k) counter++; ...

• Overcaffeinated (unregistered)

In Python:

def noKill(people, skip=3): people = range(1,people + 1) skipped = 0 current = -1 while len(people) > 1: skipped += 1 current += 1 if current == len(people): current = 0 pass

if skipped == skip: print 'killing %s' % (people.pop(current)) skipped = 0 current -= 1 return people.pop()

• sbrant (unregistered)

def josephus(soliders, skip): soliders = range(1, soliders + 1) iterations = range(1, len(soliders) * skip) counter = 1 killed = 0 for i in iterations: for n in soliders: if n != 0: if counter == skip: if killed == len(soliders) - 1: return n soliders[soliders.index(n)] = 0 killed += 1 counter = 1 else: counter += 1

print josephus(41, 3)

• Blarg (unregistered)

Say we skip skip soldiers, and have num soldiers in the circle. If skip and num are coprime, then the consecutive sums will be unique, and will eventually get back to num. Thus, -1*skip mod num is the safe spot.

If they are not coprime, then there are lots of safe spots. Find their gcd, and add 1.

• silvestrov (unregistered)

#!/usr/bin/perl

\$k = 3; @a=(1..40); @a = grep { ++\$x % \$k } @a while \$#a print @a, "\n";

• Overcaffeinated (unregistered)

Tabbing fail. Again, in Python:

```def noKill(people, skip=3):
people = range(1,people + 1)
skipped = 0
current = -1
while len(people) > 1:
skipped += 1
current += 1
if current == len(people):
current = 0
pass

if skipped == skip:
print 'killing %s' % (people.pop(current))
skipped = 0
current -= 1
return people.pop()
```
• time0ut (unregistered) in reply to Josephus

A terrible, but working solution (more or less) in Java. The test to see if a location is safe is accomplished by running the process until that location is killed. Positions are randomly selected for testing until the safe one is found. Positions can be tested more than once. Emphasis has been placed on writing naive and poorly performing code without going overboard on obscurity.

```import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
* A solution that might get Josephus killed.
* @author time0ut
*/
public class SafetyDance {
public static void main(String... args) {
new SafetyDance(Integer.parseInt(args[0]), Integer.parseInt(args[1])).play();
}
private int participants;
private int skip;

public SafetyDance(int participants, int skip) {
this.participants = participants;
this.skip = skip;
}

public void play() {
DanceMarathon danceMarathon = new DanceMarathon(participants, skip);
Random rand = new Random();
while (true) {
int position = rand.nextInt(participants);
if (danceMarathon.isSafe(position)) {
System.out.println("Position " + position + " is safe.");
break;
} else {
System.out.println("Position " + position + " is not safe.");
}
danceMarathon.reset();
}
}

class DanceMarathon {
List<Dancer> dancers;
private int  skip;

public DanceMarathon(int participants, int skip) {
this.dancers = new ArrayList<Dancer>();
for (int i = 0; i < participants; i++) {
}
this.skip = skip;
}

public boolean isSafe(int position) {
int currentPosition = 0;
while (!this.isOneStanding()) {
Dancer d = this.getNext(currentPosition);
if (d.getPosition() == position) {
return false;
}
d.setAlive(false);
currentPosition = d.getPosition();
}
return true;
}

public void reset() {
for (Dancer d : this.dancers) {
d.setAlive(true);
}
}

private boolean isOneStanding() {
int standing = 0;
for (Dancer d : this.dancers) {
if (d.isAlive()) {
standing++;
}
}
return standing == 1;
}

private Dancer getNext(int currentPosition) {
int count = 0;
Dancer d = null;
while (count < this.skip) {
if (currentPosition == this.dancers.size() - 1) {
currentPosition = 0;
} else {
currentPosition++;
}
d = this.dancers.get(currentPosition);
if (d.isAlive()) {
count++;
}
}
return d;
}
class Dancer {
private int     position;
private boolean alive;

public Dancer(int position) {
this.position = position;
this.alive = true;
}

public int getPosition() {
return this.position;
}

public boolean isAlive() {
return this.alive;
}

public void setAlive(boolean alive) {
this.alive = alive;
}
}
}
}```
• Anders Eurenius (unregistered) in reply to Andreas Kromann

Have you tested it?

Because I think I'm not getting the right answers from it. My own version before looking at the comments was:

def joe3(n, k): x = 0 for i in range(2, n+1): x = (x + k) % i return x

Which does seem to work. (0-indexed) I tried to eliminate more, but the lower modulos are apparently necessary.

• CF Guru (unregistered) in reply to Ben Forta

I am humbled that the great Ben Forta visits this site. In fact, I always feel like bowing when I see or hear his name! You the man Ben!!!

Ben Forta:
A not as ugly as the PHP script in CF ``` <cfparam name="url.soldiers" type="numeric" default="12"> <cfparam name="url.skip" type="numeric" default="3"> <cfset circle=""> <cfloop from=1 to=#url.soldiers# index=x> <cfset circle=listAppend(circle,x)> </cfloop> <cfset x=1> <cfloop condition="listLen(circle) gt 1"> <cfset x+=url.skip-1> <cfif x gt listLen(circle)> <cfset x=x mod listLen(circle)> </cfif> <cfoutput>Deleting man at position #listGetAt(circle,x)#</cfoutput> <cfset circle=listDeleteAt(circle, x)> </cfloop> <cfoutput>The last name standing was in position #circle#</cfoutput> ```
• Wongo (unregistered) in reply to Capt. Obvious
Capt. Obvious:
Anon:
I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0.
Well, when the algorithm was posted, it was assume k meant "kill every kth person, not skip k persons between skips."

So, if you want the second letter to be the number of skips, modify the algorithm to: 1 + (n-1)(k-1) mod n

33 soldiers, interval 2 (equivalent to killEveryKth 3) = 1+(33-1)(2-1) mod 33 = 0 instead of 7.

• Dave Bush (unregistered)

Numbering the top position as zero, in 'C': int Safe(int Soldiers, int Skip) { if (Soldiers == 1) return 0 ;

return (Safe(Soldiers - 1, Skip) + Skip) % Soldiers ; }

• Akoi Meexx (unregistered)

In php:

<?php function LifePosition(\$indexCount=41, \$skipCount=3) { /** * Josephus' Circle calculation function * Written to identify the array index that will be selected * last in a sequence with (x) indices and (y) skip count * @author: Akoi Meexx <[email protected]> * * @attrib: http://thedailywtf.com/Articles/Programming-Praxis-Josephus-Circle.aspx */ \$roulette = array_fill(1, \$indexCount, 'Alive'); \$increment = 1; while(count(\$roulette) > 1) { foreach(\$roulette as \$arrayIndex=>\$value) { if(\$increment == \$skipCount) { unset(\$roulette[\$value]); \$increment = 1; } \$increment++; } } print_r(\$roulette); } ?>
• (cs) in reply to Andreas Kromann
Andreas Kromann:
halber_mensch:
Andreas Kromann:
Wongo:
The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

As I posted earlier its just (n is number of soldiers and k the number of skips):

1 + (n-1)k mod n

using (5,1) we should get 3, but with your shortcut you get

```    1 + (5-1)1 mod 5
==> 1 + 4 mod 5
==> 1 + 4
==> 5
==> fail
```

No it is 5 not 3 ... you fail ...

{1,2,3,4,5} => {2,3,4,5} => ... => {5}

Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

{1,2,3,4,5} {1,3,5} {3}

• Wongo (unregistered) in reply to Blarg
Blarg:
Say we skip skip soldiers, and have num soldiers in the circle. If skip and num are coprime, then the consecutive sums will be unique, and will eventually get back to num. Thus, -1*skip mod num is the safe spot.

If they are not coprime, then there are lots of safe spots. Find their gcd, and add 1.

skip = 3, soldiers = 11 (coprimes). -1*3 mod 11 = -3 on the windows calculator, although I remember the modding of negative numbers being still under debate (please do not bait...). No -3 spot.

Not coprime, skip = 3, soldiers = 18, gcd = 3, gcd + 1 = 4 instead of 14. Doesn't work either.