• the pattern (unregistered)

assuming there are only two people (indices 0 and 1) and killing every third person the safe spot would be 1:

0 1 0 (kill)

people safespot 2 1

if you can't add the nth number to the safe spot without equaling or going over the total number of people you reset the safe spot to 0 or 1 depending on the outcome of the previous results difference as even or odd:

people = 2 safespot = 1 n = 3

for people = 3 1 + 3 >= 3 reset safe spot to 1 because (2-1)mod2 = 1 (odd)

so: people safespot 2 1 3 1

for people = 4 1 + 3 >= 4 (reset to 0) (3-1)mod2 = event

so: people safespot 2 1 3 1 4 0

for people = 5 0 + 3 = 3 (less than 5 so keep it)

people safespot 2 1 3 1 4 0 5 3

people = 6 3 + 3 >= 6 reset to 0 (5-3)mod2 = even

people safespot 2 1 3 1 4 0 5 3 6 0 7 3 8 6

6+3 >= 9... and so on

• (cs) in reply to JonsJava
JonsJava:
```function iWillSurvive(\$hey,\$hay){
```
I couldn't think of a better name for the function.

Kudos but screw you for putting that in my head now...

• IdontDoRecursion (unregistered)

#include <stdio.h> #include <stdlib.h> int getLastStanding(int num, int step) { int i,j; for(i=1,j=0;i<=num;i++) {j+=step; if(j>=i) j%=i; } return j+1; }

int main(int argc, char *argv[]) { int num=41, step=3; if(argc>1) num=atoi(argv); if(argc>2) step=atoi(argv); printf("You want to be solder %d of %d for a step of %d\n",getLastStanding(num,step),num,step); return(0); }

The trick is that it is a step function which repeats when the total exceds N on a modulo basis...

• (cs) in reply to Alex Mont
Alex Mont:
```def J(n,k):
if(n==1)
return 0
else
return (J(n-1,k)+k)%n
```

That's easy to make iterative.

```# Recursive
sub J {
my (\$n, \$k) = @_;
return 0 if \$n == 1;
return ( J(\$n-1, \$k) + \$k ) % \$n;
}

# Iterative
sub J {
my (\$n, \$k) = @_;
my \$j = 0;
\$j = (\$j + \$k) % \$_ for 2..\$n;
return \$j;
}
```
• Sue D. Nymme (unregistered)

I love a good perl golf challenge!

perl -E '\$k=pop;\$s=(\$s+\$k)%\$_ for 1..pop;say\$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

• Detunized Gravity (unregistered)

Since the sexy one-line mathematical solution has been exposed, I felt I had no other choice than going for the brain dead solution. But since my language of choice is Ruby, I'll also go for the iterator and a bit of "dynamycally modifying a core object class". Just for the fun of it.

```#!/usr/bin/ruby
class Array
def kill!(i)
count = 1
while self.size > 1
if count.modulo(i) == 0
yield self.shift
else
self << self.shift
end
count += 1
end
end
end
ARGV.map! { |x| x.to_i }
puts "Slaughtering #{ARGV} soldiers, chopping one head every #{ARGV}."
print "Chopping head off of "
soldiers = (1..ARGV).to_a
puts
puts "The last standing is #{soldiers}."```

Code which gives...

```dg@gaia:~/temp\$ ./soldier.rb 12 3
Slaughtering 12 soldiers, chopping one head every 3.
Chopping head off of 3 6 9 12 4 8 1 7 2 11 5
The last standing is 10.
dg@gaia:~/temp\$ ./soldier.rb 40 3
Slaughtering 40 soldiers, chopping one head every 3.
Chopping head off of 3 6 9 12 15 18 21 24 27 30 33 36 39 2 7 11 16 20 25 29 34 38 4 10 17 23 31 37 5 14 26 35 8 22 40 19 1 32 13
The last standing is 28.
dg@gaia:~/temp\$ ./soldier.rb 41 3
Slaughtering 41 soldiers, chopping one head every 3.
Chopping head off of 3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
The last standing is 31.
```
• Sue D. Nymme (unregistered) in reply to Sue D. Nymme
Sue D. Nymme:
I love a good perl golf challenge!

perl -E '\$k=pop;\$s=(\$s+\$k)%\$_ for 1..pop;say\$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

Of course... that's 1-based. If you allow 0-based counting, it's two characters shorter.

• tony roth (unregistered)

to many posts to look through so I'm sorry if somebody already posted this but if you read the wiki on this there are two versions and each one comes up with a different answer!

• (cs)
There is no “right” answer and no perfect solution, but some will certainly be better than others. The best of these will get a TDWTF sticker.
The comments are most certainly worth a read, if nothing else but to see things like the circuit diagram solution [...]

Being the author of the linked solution, do I qualify for a TDWTF sticker? That'd be awesome!

• (cs)

Here's the fast way, in Java, based on the Wikipedia article Josephus problem:

```   public static int circleSurvivorRecursive(int men, int countTo)
{
return (men == 1) ?
0 :
(circleSurvivorRecursive(men - 1, countTo) + countTo) % men;
}

```

Unfortunately, this is deficient, since it provides no means to identify the best place for the surviving accomplice. So I decided to go to the even more general function that determines the kill order. The requested survivor is, of course, the last man in the array (and his accomplice next to last):

```   public static int[] circleKillOrder(int men, int countTo)
{
int kills[] = new int[men];

int pos = men;
for (int i=0; i < men; i++) {
int steps = countTo;
while (steps > 0) {
pos = (pos + 1 >= men) ? 0 : pos + 1;
}
kills[i] = pos;
}

return kills;
}

```

This next function then uses the above to determine the survival positions for any number of conspriators:

```   public static int[] circleConspiringSurvivors(int men,
int countTo, int conspirators) {
int kills[] = circleKillOrder(men,countTo);
int where[] = new int[conspirators];
for (int i = 0; i < conspirators; i++) {
where[i] = kills[--men];
}
return where;
}

```

Finally, this next is the most useful function of all. It describes where to put the bright boy who had this stupid idea so he's the first to get the axe. Everyone else survives.

```   public static int whereToPutBrightBoy(int men, int countTo) {
//return circleKillOrder(men,countTo);
return (countTo + men - 1) % men;
}
```
• (cs)

Here's my python one-liner again :)

```def joph(n):
return int(bin(n)[2:][1:] + bin(n)[2:], 2)
```

Hopefully the next 'praxis' won't be available in Concrete Mathematics ;)

Next challenge is trying it without it being solved with string manipulation.

• (cs) 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".

Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.

• Karol Urbanski (unregistered) in reply to Sue D. Nymme
Sue D. Nymme:
Sue D. Nymme:
I love a good perl golf challenge!

perl -E '\$k=pop;\$s=(\$s+\$k)%\$_ for 1..pop;say\$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

Of course... that's 1-based. If you allow 0-based counting, it's two characters shorter.

Awesome :).

• DF (unregistered)

I wrote a weirdo erlang solution which I think works. I am a functional programming noob and I started looking at erlang yesterday.

```-module(josephus).
-export([josephus/2]).

josephus(Soldiers, Interval)->
josephus(soldier_list(Soldiers),[], Interval, 0).

josephus([Current | Rest], Survivors, Interval, Count) when Count /= Interval->
josephus(Rest, [Current | Survivors], Interval, Count + 1);

josephus([_ | Rest], Survivors, Interval, _)->
josephus(Rest, Survivors, Interval, 0);

josephus([], Survivors, Interval, Count)->
if
length(Survivors) > 1 ->
josephus(Survivors, [], Interval, Count);
true ->
[LastMan | _] = Survivors,
LastMan

end.

soldier_list(Soldiers)->
soldier_list(Soldiers, []).

soldier_list(Soldiers, List) when Soldiers > 0 ->
soldier_list(Soldiers - 1, [Soldiers | List]);

soldier_list(0, List)->
[0 | List].
```
• Matti Helin (unregistered)

Matlab, using inbuilt circular shift function:

```function alive = josephus(n, k)
alive =(1:n)';
shift = 1-k;
for h = 1:(n-1)
alive = circshift(alive, shift);
alive(1) = [];
end
```
• thc4k (unregistered)

When you remove the recursion from j(1,k) = 1 j(n,k) = (j(n-1,k)+k) mod n

its ( (k mod 2) + k ) mod 3 ) + k ) mod 4 ) ... ) + k mod n )

can that be further simplified ?

• Nukeme1 (unregistered)

This version uses a form and posts the result back to the form.
Edit1 contains mans Edit2 contains mansToSkip Edit3 gets the result (base 1 result, base 0 calculations) Using an array and a I'm dead indicator (to lazy to use a boolean array)

```procedure TForm1.Button1Click(Sender: TObject);
var
i,
j,
noMen,
noMenToSkip: integer;
circleRepresentation: array of integer;
begin
noMen := strToInt(edit1.text);
noMenToSkip := strToInt(edit2.text);
Edit3.text := '';
SetLength(circleRepresentation,noMen);
i := 0;
while noMen <> 1 do
begin
j := noMenToSkip;
while j <> 0 do //steps to the next to die
begin
if circleRepresentation[i] = 0 then
begin
j := j-1;
end;
if j <> 0 then
i := (i+1) mod length(circleRepresentation);
end;
circleRepresentation[i] := 1; //kill the current man that is alive
noMen := noMen - 1;
end;
while circleRepresentation[i] = 1 do
i := (i+1) mod length(circleRepresentation);//go to the last man alive
Edit3.Text := intToStr(i + 1);
end;
```
• (cs)

AppleScript :

```on run
set num_soldiers to 0

repeat until num_soldiers is greater than 0
display dialog "Number of soldiers" default answer 12
set text_entered to text returned of the result
try
set num_soldiers to text_entered as integer
end try
end repeat

repeat until num_to_skip is greater than 0
display dialog "Soldiers to skip" default answer 3
set text_entered to text returned of the result
try
end try
end repeat

display dialog "Result: " & Josephus(num_soldiers, num_to_skip) & " (from 0 to " & (num_soldiers - 1) & ")" buttons {"WTF?!"} default button 1
end run

on Josephus(num, skip)
if num is 1 then return 0
return (Josephus(num - 1, skip) + skip) mod num
end Josephus```
• Melvis (unregistered) in reply to Ron Moses
Ron Moses:
How's about a T-SQL function? I could probably tighten this up considerably but it works.
```CREATE FUNCTION dbo.JosephusFunction
(
@NumberOfSoldiers int,
@SoldiersToSkip int
)
RETURNS int
AS
BEGIN
```DECLARE @i int, @TempSkip int;
DECLARE @Soldiers table (SoldierNumber int, Dead bit);

SET @i = 1;
WHILE @i <= @NumberOfSoldiers
BEGIN
INSERT INTO @Soldiers VALUES (@i, 0);
SET @i = @i + 1;
END

SET @i = 1;
WHILE (SELECT COUNT(*) FROM @Soldiers WHERE Dead = 0) > 1
BEGIN
SET @TempSkip = @SoldiersToSkip + 1;
WHILE @TempSkip > 0
BEGIN
SET @i = @i % @NumberOfSoldiers + 1;

WHILE (SELECT Dead FROM @Soldiers WHERE SoldierNumber = @i) = 1
BEGIN
SET @i = @i % @NumberOfSoldiers + 1;
END

SET @TempSkip = @TempSkip - 1;
END

UPDATE @Soldiers
WHERE SoldierNumber = @i;

END

RETURN (SELECT SoldierNumber - 1 FROM @Soldiers WHERE Dead = 0);
```
END
```

This doesn't seem to work if the answer is equal to the number of soldiers...

• scott (unregistered) in reply to rm5248

Same brute force, just using BitSet instead:

```import java.util.BitSet;

public final class JosephusCircle
{
public static void main(String[] args)
{
JosephusCircle c = new JosephusCircle();
c.bruteForce(12, 3);
}

private int bruteForce(int size, int numSkip)
{
BitSet s = new BitSet(size);

int axeCounter = 1;
while (s.cardinality() < size - 1)
{
for (int i = s.nextClearBit(0); i < size; i = s.nextClearBit(i + 1))
{
if (0 == axeCounter % numSkip)
{
s.set(i);
}
++axeCounter;
}
}
int live = s.nextClearBit(0) + 1;
System.out.println("When axing every " + numSkip + ", you want " + live + " of " + size);
return live;
}
}
```
• H2 (unregistered)

My Perl-solution. No recusion, just one loop. But I have to confess it's not totally straight forward ;)

```#/usr/bin/perl
use strict;
use warnings;

if ((@ARGV != 2) || (\$ARGV!~m/[1-9]/) || (\$ARGV!~m/[1-9]/)) {
print "Missing or wrong arguments! Need two integers\n";
exit(0);
}

my (\$soldiers,\$count_val)=@ARGV;
my @survivors;
my \$initiate=1;
my \$died_this_round=0;

for (my \$i=0;(@survivors>1 || \$initiate==1);((\$i<\$soldiers && \$initiate==1)?(\$i++):(\$i+=\$count_val))) {
if (\$i<\$soldiers && \$initiate==1) {
\$survivors[\$i]=\$i+1;
}
elsif (\$i==\$soldiers && \$initiate==1) {
\$initiate=0;
\$i=0;
}
else {
if (\$i>(@survivors+\$died_this_round)) {
\$i-=(@survivors+\$died_this_round);
\$died_this_round=0;
}

my \$delete;
if (\$i-\$died_this_round-1>\$#survivors) {
\$delete=\$i-\$died_this_round-@survivors-1;
}
else{
\$delete=\$i-\$died_this_round-1;
}

splice(@survivors,\$delete,1);
\$died_this_round++;
}
}
print "Lucky one: \$survivors\n";

# perl Josephus.pl 12 3
Lucky one: 10
```
• Shiftyness (unregistered)

public class DeathLinkage { static int _Soldiers; static int _Skip; int dead = 0; int index = 0; Person[] jews;

``````    public DeathLinkage(int numSoldiers, int numSkip)
{
_Soldiers = numSoldiers;
_Skip = numSkip;
jews = new Person[_Soldiers];
for (int i = 0; i < _Soldiers; i++)
{
jews[i] = new Person();
}
}
int counter = 1;
public int killEachOther()
{

{
for (int i = 0; i < _Soldiers; i++)
{
if (jews[i].alive)
{
if (counter == _Skip)
{
jews[i].alive = false;
counter = 1;
}
else counter++;
}
}
killEachOther();

}
for (int i = 0; i < _Soldiers; i++)
{
if (jews[i].alive) index = i;
}
return index;
}
public string circleOfDeath()
{

if (_Soldiers <= 0 || _Skip <= 0)
{
return "Neither of the inputs may be 0 or a negative number.  Jews don't believe in counter-clockwise.";

}
else
{
if (_Soldiers == 1) return "1";
else
{
return dl.killEachOther().ToString();
}
}
}

}
public class Person
{

public Person()
{
alive = true;
}
public bool alive { get; set; }
}
class Program
{

static void Main(string[] args)
{
System.Console.WriteLine(dl.circleOfDeath());
}
``````

}

• (cs)

A perhaps not very clean but working solution in F#

```#light "off"	// Because I like tabs
let Josephus num skip =
begin
let mutable soldiers = [| 1 .. num |] in
let offset = ref 0 in
while Array.length soldiers > 1 do
printfn "Solders left standing: %A" soldiers;
// Killing
soldiers <- Array.mapi (fun i s -> if ((i + 1 + !offset) % skip) > 0 then s else 0) soldiers;
offset := ((Array.length soldiers % skip) + !offset) % skip;
printfn "Solders after killing: %A" soldiers;
// Cleaning
soldiers <- Array.filter (fun s -> s <> 0) soldiers;
done;
if Array.isEmpty soldiers then failwith "Damn...";
Array.get soldiers 0;
end in
```

(Just discovered F# while reading through the comments to the previous programming problem.)

• jb somebody (unregistered)

This is probably a WTF solution in itself. I've purposely not checked other comments so as not to spoil it. Here's my solution in C#:

//assuming index 0 is top of circle public static int saveMe(int numOfSoldiers, int skip) {

``````        Boolean[] soldiers = new Boolean[numOfSoldiers];
int ctr = 0;
int removedCtr = 0;

//Set all soldiers to a living state
for (int i = 0; i < numOfSoldiers; i++)
soldiers[i] = true;

while (removedCtr != numOfSoldiers - 1)
{

for (int i = 0; i < skip; i++)
{
//If a soldier is dead skip him
while(soldiers[ctr] == false)
{
ctr += 1;
if (ctr > numOfSoldiers - 1) ctr = 0;
}

if (i == (skip - 1)  )
{
soldiers[ctr] = false;
removedCtr += 1;
Console.WriteLine("Soldier at {0} was removed.", ctr);
}

ctr += 1;
if (ctr > numOfSoldiers - 1) ctr = 0;

}
}

ctr = 0;
while (soldiers[ctr] == false)
{
ctr += 1;
}

return ctr;
}
}
``````
• (cs)

Since 2 people have beaten me to it already....

unit Josephus;

interface uses Generics.Collections, SysUtils;

type BoolP = ^Boolean;

function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer;

implementation

function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer; var AliveList: TList<BoolP>; I: Integer; SkipI: Integer; Alive: BoolP; AliveCount: Integer; Found: Boolean; begin SkipI := 1; Found := False; AliveList := TList<BoolP>.Create(); for I := 1 to Soldiers do begin new(Alive); Alive^ := True; AliveList.Add(Alive); end; AliveList.TrimExcess; I:= 0; AliveCount := AliveList.Count; while AliveCount > 1 do begin if I = AliveList.Count then I := 0; Alive := AliveList[I]; if Alive^ then begin if SkipI = Skip then begin Alive^ := False; dec(AliveCount); SkipI := 1; end else inc(SkipI); end; inc(I) end; I:= 0; while (I < AliveList.Count) and (not Found) do begin Alive := AliveList[I]; if Alive^ then Found := True else inc(I); end; if Found then Result := I + 1 else I := -1;

for I := 0 to AliveList.Count - 1 do begin Alive := AliveList; Dispose(Alive); AliveList.Delete(0); end; FreeAndNil(AliveList); end;

end.

• odio (unregistered) in reply to Ian
Ian:
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?

To me, listening to static is indeed mysterious!

• byornski (unregistered)

The index starting at 0. Seems i've been beaten to the short iterative answer but who cares :P

``````    public static int Lives(int nSize, int nSkip)
{
int n = 0;
for (int i = 2; i <= nSize; i++)
n = (n + nSkip) % i;
return n;
}
``````

A brute force Python version...

menCount = 40 men = ["duck"] * menCount goose = 0

while men.count("goose") < menCount - 1: chopper = ["duck", "duck", "goose"] while chopper != [] and men.count("goose") < (menCount - 1): if men[goose] != "goose": men[goose] = chopper.pop(0) goose = (goose + 1) % menCount print men

print "Survivor: %s" %(men.index("duck") + 1)

I hate formatting issues... here's a brute-forced Python one:

```menCount = 40
men = ["duck"] * menCount
goose = 0

while men.count("goose") < menCount - 1:
chopper = ["duck", "duck", "goose"]
while chopper != [] and men.count("goose") < (menCount - 1):
if men[goose] != "goose":
men[goose] = chopper.pop(0)
goose = (goose + 1) % menCount
print men

print "Survivor:  %s" %(men.index("duck") + 1)
```
• Lerb (unregistered) in reply to nonny nonny

Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:

GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

• Redredredredredred (unregistered)

Too much recursion in here for my taste.

Okay... first some ruby code (boring)

```def jc(men, skip)
c=Array.new()
men.times do |n| c << n end
i=0
d=skip
while c.length > 1
i = 0 if i==c.length
```d = d - 1
puts "killed nr. #{c[i]}" if d==0
c.delete c[i] if d==0
i=i+1 if d!=0
d=skip if d==0
```
end
c
end
puts jc(12,3)
```

And here C with double linked list awesomeness:

```#include <stdio.h>
#include <stdlib.h>
typedef struct circle_t
{
unsigned int nr;
struct circle_t* next;
struct circle_t* prev;
} circle;

void add(unsigned int nr, struct circle_t* prev)
{
struct circle_t* a;
a=(struct circle_t*)malloc(sizeof(struct circle_t));
a->nr=nr;
a->prev=prev;
prev->next=a;
}

void del(struct circle_t* ptr)
{
ptr->prev->next=ptr->next;
ptr->next->prev=ptr->prev;
free(ptr);
}

unsigned int jc(unsigned int men, unsigned int skip)
{
struct circle_t* p;
struct circle_t* start;
start=malloc(sizeof(struct circle_t));
p=start;

start->next=start;
start->prev=start;
start->nr=0;

int i=1;
int d=skip;

while (i<men)
{
p=p->next;
i++;
}

p->next=start;
start->prev=p;

p=start;
while (p != p->prev)
{
d--;
if (d==0) {
printf("killed nr. %-4u\n",p->nr,p);
p=p->next;
del(p->prev);
d=skip;
}
else
{
p=p->next;
}
}

printf("\n\n");

return p->nr;
}

int main(int argc, char** argv)
{
if (argc < 3) {
printf("usage: %s men skip\n",argv);
return 1;
}
printf("safe spot: %u\n",jc(atoi(argv),atoi(argv)));

return 0;
}```
Wongo:
db2:
It looks like this works:

n = number of soldiers k = skip ahead interval (3 in this example) i = "safe spot" index (1-based)

```i = 1;
for (int c = 2; c <= n; c++) {
i = (i + k) % c;
if (i == 0) {
i = c;
}
}
return i;
```

Brilliant! It works perfectly! Congrats, db2, you made my day!

Now, if we could just remove the loop and turn it into a formula, we might find out how Josephus did it "very quickly"...

The only way I can see for him to succeed in this is for him to have known about the arrangements before-hand so he could prepare. Let's assume that this method of surrender was discussed and agreed-upon before the battle. There would be no way to know how many soldiers were left, so he would have made up the same table we made earlier at the bottom of Page 1 of the comments. He could have memorized this, but could also have used the algorithm that many people here found (but I did not :( ) I am using the one quoted. The important line is "i = (i + k) % c;" This gives us a table that looks kind of like this: (1 + 3) % 2 (2 + 3) % 3 { 3 soldiers, stand at position 2} (2 + 3) % 4 (1 + 3) % 5 (4 + 3) % 6 { 6 soldiers, stand at position 1 } ... ...

Refer to the comment at the bottom of page 1 of comments for a bigger table. You can see that it resets to 1, 0( which becomes 2), or 2 every now and then. The series on the right climbs by 3 until it "catches up" to the series on the left. So you can jump from one reset straight to the next. (2 + 3) % 15 for 15 is one reset, the next is 6 steps up: (2 + 3 + (3 * 6)) % (15 + 6), or 23 % 21 for 21. This means that if there are 21 soldiers, he should stand as the second. The next jump takes you straight to (2 + 3 + (3 * 9)) % (22 + 9). This resets to 32 % 31 for 31 soldiers. You can now jump straight to (1 + 3 + (3 * 9)) % (32 + 9) which is 31 % 41 for 41 soldiers.

So as long as he remembered the resetting values i.e. 1 .. 7 1 .. 10 2 .. 15 2 .. 22 1 .. 32 2 .. 48, etc. he would be able to calculate the appropriate position in seconds. So for 41, he would know to use the entry corresponding to 32 since it is less than the next reset at 48. 41 - 32 = 9; and the position he needed to stand on would be (1 + 3) {corresponding to 32 in that table} added to 3 * 9. This would be 31.

• Herby (unregistered) in reply to RayMarron
RayMarron:
I just wanted to say that the animations accompanying these are brilliant. :)
I have to say that I agree. Now for the next problem, code up the animations.
• reuven (unregistered)

Here's my solution in Matlab (only language I really know that well.): function safe_index = josephus(num_soldiers,num_skip)

survivor_mat=[];

for i=1:num_soldiers survivor_mat(i)=i;; end

count = 0; while length(survivor_mat) > 1 count = count + num_skip; while count > length(survivor_mat) count= count-length(survivor_mat); survivor_mat(survivor_mat == 0) = []; end if length(survivor_mat) > 1 survivor_mat(count)=0; end end safe_index = survivor_mat;

• (cs)

C#, using regex and strings - for fun.

```        private static int GetJosephusSafeSpot(int nSoliderCount, int nSkipValue)
{
var sbRegexSkips = new StringBuilder("L");
nSkipValue--;
for (int i = 0; i < nSkipValue; i++)
sbRegexSkips.Append("D*L");

Regex regKill = new Regex(sbRegexSkips.ToString(), RegexOptions.Compiled);

string strCircleOfDeath = new string('L', nSoliderCount);

int nIndex = 0;
while (strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).Count(c => c == 'L') > 1)
{
Match match = regKill.Match(strCircleOfDeath, nIndex);
strCircleOfDeath = regKill.Replace(strCircleOfDeath, m => { return m.Value.Remove(m.Value.Length - 1) + "D"; }, 1, nIndex);
nIndex = match.Index+match.Value.Length;
while (strCircleOfDeath.Substring(nIndex).Count(c => c == 'L') <= nSkipValue)
strCircleOfDeath += strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount);
}

return strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).LastIndexOf('L');
}
```
• Paul Marfleet (unregistered)

Solution in F#:

```let josephus numberOfMen skip =
let men = [1..numberOfMen]
let rec doTurn men position =
match men with
| hd :: [] -> hd
| _ ->
let newPosition = (position + skip) % men.Length
doTurn (List.mapi (fun i man -> if i = newPosition then 0 else man) men
|> List.filter(fun man -> man > 0)) (newPosition - 1)
doTurn men -1
```
• Wongo (unregistered) in reply to Maurits
Maurits:
Wongo:
Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.

OK, so here's another solution to the problem, this time in BabyTalk :

Josephus - Eenie Meenie Miiii...(skip himself)...iiiny Moe.

• Kevin M (unregistered)

Here's a brute force solution in Java that I don't think anyone else has posted. It follows the problem description by treating a Vector as a circular buffer. Each vector element is the initial index of each soldier.

```int josephus(Vector<Integer> v) {
if (v.size() == 1)
return v.elementAt(0).intValue();

v.remove(0);
return josephus(v);
}
```
• (cs) in reply to Lerb
Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:

GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

GodFactory.getGods(GodFactory.AGNOSTIC) = throw Unknown Exception

• JHolland (unregistered)

This is such a simple algorithm I am not sure how to make my solution THAT much more complicated. I did manage to use two subroutines, not counting josephus(), as well as recursion. And I broke LOTS of Perl Best Practices. Maybe tomorrow I'll try to figure this one out using only Regexes.

```sub josephus {
my (\$circle, \$skip) = @_;
return 1 + calc_j(0, \$skip, 0 .. \$circle-1);
}

sub calc_j {
sub array_except {
my \$except = pop @_;
my @array = @_;
splice @array, \$except, 1;
return @array;
}
(\$idx, \$skip, @array) = @_;
return @array == 1 ?
\$array :
calc_j(\$new_idx=(\$idx+\$skip-1) % @array, \$skip, array_except(@array, \$new_idx));
}

print "josephus(12, 3) = ", josephus(12, 3), "\n";```
• God (unregistered) in reply to Lerb
Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:

GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

Zeus is Greek not Roman... that would be Jupiter

• Jedi (unregistered)

*v,n;main(s,f){for(n=1;atoi(1[v=f])-s;n=(n+atoi(2[v=f]))%++s);printf("%d\n",n);}

• Still Not Tim (unregistered)

So 39 soldiers were done for, but Titus escaped.

All these comments, and not one pointing out the irony of using Python to show... erm... the Romans didn't do for Titus.

• Oscar Olim (unregistered)

I'd say the safe spot is in the middle, as only the people in the circle get killed :P

• Dr. Batch (unregistered)

Looking at the table of reset values idea that is discussed in earlier comments, I see that finding those helpful values is quite easy.

Pseudocode:

X is a placeholder for the last reset value, starts at 1 Y is a placeholder for what you have to reset to at X, starts at 0 function is called with variables S(oldiors) and C(ount)

-startloop distanceToNextX = ( (X-Y)/(C-1) rounded up )

if S is less than nextX return Y + (S-X)*c else X = nextX Y = (Y + (distance to next X * C)) mod x -endloop

Batch file:

@echo off rem - argument 1 is number of soldiers, argument 2 is the number to count to each time

call :josephus %1 %2

echo the servivor is at index %j%

exit /b

:josephus set s=%1 set c=%2 set x=1 set y=0

:loopbegin echo begin loop set /a z="(((2*(x-y))/(c-1))+1)/2" set /a xn="x+z" if %s% lss %xn% ( set /a j="y+((s-x)c)" ) else ( set x=%xn% set /a y="(y+(zc))%%x" goto :loopbegin )

exit /b

This algoritem is more efficient than any of the other looping or recursion alborithems I have seen implemented thus far. Even as a (ineficient) batch file it finds the servivor in a group of 32727 (#6132) in the blink of an eye while looping only two dozen times.

Trying that will overflow the stack on any of the recursive programs. Go ahead and try it with any of the other looping ones. I'll wait.

• Gary Hall (unregistered) in reply to Dave
Dave:
```foreach(soldier:soldiers){
soldier.kill();
}
God.getInstance().sortOut(soldiers);
```

Monotheist, ey?

```DeityRepo.FindBySpecialisation(DeitySpecialisations.War).SortOut(soldiers);
```
• Dr. Batch (unregistered) in reply to Dr. Batch

find and replace "servivor" with "survivor". How embarrassing.

• Michael van der Gulik (unregistered)

I tried to go for good readability.

In Smalltalk, comments are delimited using double-quotes. Variables are declared between verticle bars. The caret returns a value from the method. Otherwise it's pretty much like Python, but with a built-in debugger.

Interestingly, if you want to give the survivors names, you can replace:

circle := OrderedCollection withAll: (1 to: n).

with:

circle := OrderedCollection withAll: #('Phillipus' 'Caesor' 'Nero' 'Josephus' 'Cactus').

and then this method will return the name of the survivor.

```survivorInCircleOfSize: n
| circle victim |
circle := OrderedCollection withAll: (1 to: n).
victim := 0.
[circle size > 1] whileTrue: [
victim := victim + 3.
victim := victim rem: (circle size). " rem means 'mod' "
(victim = 0) ifTrue: [ victim := circle size ].
" Murder! "
circle removeAt: victim.
victim := victim - 1. " Make sure that we take the removal into account. "
].
^ circle anyOne. " There should only be one dude left. "
```
• (cs)

Really modeling the situation using Scheme message passsing OOP.

```(define (make-person num)
(let ((alive true)
(next 'nobody))
(lambda (op)
(cond ((eq? op 'alive?) alive)
((eq? op 'position) num)
((eq? op 'next) next)
((eq? op 'stand-next-to) (lambda (person)
(set! next person)))
((eq? op 'kill) (if (not alive)
(set! alive false)))
(else (error "Unknown operation -- PERSON" num))))))

(define (make-circle n)
(let ((first-person (make-person n)))
(let iter ((n (- n 1))
(current-person first-person))
(if (zero? n)
(begin
((first-person 'stand-next-to) current-person)
current-person)
(iter (- n 1) (let ((new-person (make-person n)))
((new-person 'stand-next-to) current-person)
new-person))))))

(define (josephus n m)
(define (skip-m-and-kill circleptr)
(let iter ((i m)
(cur-person circleptr))
(cond ((cur-person 'dead?) (iter i (cur-person 'next)))
((zero? i) (cur-person 'kill) cur-person)
(else (iter (- i 1) (cur-person 'next))))))
(let ((circle (make-circle n)))
(let iter ((number-alive n)
(curpos circle))
(if (zero? number-alive)
(curpos 'position)
(iter (- number-alive 1) (skip-m-and-kill curpos))))))
```
• Comp Sci Student (unregistered) in reply to God
Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:

GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

I tried to call GodFactory.getGods(GodFactory.AGNOSTIC), but the call keeps blocking.

Help?