fun j(n,k,i) = (if i=1 then k-1 else k+j(n-1,k,i-1)) mod n;
fun J(n,k) = j(n,k,n);

Anon2009-07-29 09:18

Josephus' Circle, AKA Eeny, meeny, miny, moe. The solution is to argue about how many words are in the rhyme and whether the person selected at the end is "it" or "not it".

DaveK2009-07-29 09:18

$ cat jos.c

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

/* f(n,k)=(f(n-1,k)+k) mod n
f(1,k)=0 */

static int f (int n, int k)
{
if (n == 1)
return 0;
return (f (n-1, k) + k) % n;
}

int main (int argc, const char **argv)
{
int n, k;
if (argc != 3)
{
fprintf (stderr, "Usage: %s <N> <K>\n", argv[0]);
return -1;
}

n = atoi (argv[1]);
k = atoi (argv[2]);

fprintf (stdout, "With %d soldiers and killing every %d'th, the safe spot is p
osition %d\n",
n, k, f (n, k) + 1);
return 0;
}

$ gcc -g -O2 -W -Wall -Wextra jos.c -o jos

$ ./jos.exe 12 3
With 12 soldiers and killing every 3'th, the safe spot is position 10

$ ./jos.exe 40 3
With 40 soldiers and killing every 3'th, the safe spot is position 28

$

HypocriteWorld2009-07-29 09:20

Ha, now we have a way to stop people from posting "Frist!!1".
Anyways, random solution here

josepheus total skip =
head $ head $ dropWhile notDone $ iterate go (cycle [1..total])
where go xs = let y:ys = drop (skip - 1) xs in filter (/=y) ys
notDone (x1:x2:_) = x1 /= x2

ps: TRWTF is the forum software erroring out because I forgot the /code tag.

DaveK2009-07-29 09:22

DaveK:

$ ./jos.exe 40 3
With 40 soldiers and killing every 3'th, the safe spot is position 28

$

Hah, I just rewrote history and doomed Josephus with an off-by-one error. There weren't 40 soldiers, there were 40 soldiers /with Josephus/.

DaveK:

$ ./jos.exe 41 3
With 41 soldiers and killing every 3'th, the safe spot is position 31

Engival2009-07-29 09:26

This is pretty brain dead, but coffee hasn't done it's job yet:

I think this is more about being the guy who decides where the "top of the circle" is than anything else.

Code Dependent2009-07-29 09:34

I doubt I could find the safe spot very quickly, but I've always been good at finding the G spot.

steenbergh2009-07-29 09:40

Code Dependent:

I doubt I could find the safe spot very quickly, but I've always been good at finding the G spot.

Fat lotta good that'll do you in a cave full of suicidal men...

JonsJava2009-07-29 09:42

An ugly script to handle this (via PHP)

<?php
function iWillSurvive($hey,$hay){
$spots = range(1,$hey);
$count = 1;
while (count($spots) > 1){
foreach ($spots as $key=>$val){
if (count($spots) > 1){
if ($count == $hay){
echo "unsetting $val\n";
unset($spots[$key]);
$count = 1;
}
else{
echo "$val is safe...for now.\n";
$count++;
}
}
}
}
foreach ($spots as $val){
$return = $val;
}
return $return;
}
print "and the winner is....: ".iWillSurvive(100,3);
?>

I couldn't think of a better name for the function.

Alex Mont2009-07-29 09:47

Consider the function J(n,k) which is the position of the surviving soldier relative to the current starting point of the count, where n is the number of remaining soldiers and k is the interval (3 in the example). (Note that counting 3 at a time actually means you're only skipping 2 at a time.) Note that "position" is counting only currently alive soldiers.

If n=1 then clearly we are done, and J(1,k) = 0 for any k. Now consider the case of n>1. We have something like this:

* * * * * * * * * *
^

Where the caret marks where the count starts. Now at the next step (assuming again k=3)

* * * * * X * * * *
^

So now suppose that J(n-1,k) = x. That means that the surviving soldier is X positions after the caret in the second diagram. But the caret in the second diagram is 3 positions after the caret in the first diagram, so the surviving soldier is X+3 positions after the caret in the first diagram. Of course you have to take the mod of that by n to account for wrap around.

Note that because of the way the recursion is set up, at no point do you have to keep track of which positions of soldiers are dead already. And it is an O(n) algorithm.

If I'm remembering right, Josephus was actually one of the last two standing, upon which he said to the other guy, as they were surrounded by corpses, "Maybe surrender isn't so shameful after all?" Not sure if the algorithm for figuring out how to be one of the last two is significantly easier.

<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)#<br/></cfoutput>
<cfset circle=listDeleteAt(circle, x)>
</cfloop>
<cfoutput>The last name standing was in position #circle#<br/></cfoutput>
</code>

<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)#<br/></cfoutput>
<cfset circle=listDeleteAt(circle, x)>
</cfloop>
<cfoutput>The last name standing was in position #circle#<br/></cfoutput>

<!--- validate cos some smartarse will supply zero or negative arguments --->
<cfif total LTE 0 OR interval LTE 0>
<cfthrow message="Stupid, stupid, stupid" detail="Both total and interval must be positive - imagine -1 soldiers or whatever!">
</cfif>

<!--- create and populate the array --->
<cfset aSoldiers = ArrayNew(1)>
<cfloop index="i" from="1" to="#total#">
<cfset aSoldiers[i] = i>
</cfloop>

<!--- now for the killing --->
<cfset target = interval>
<cfloop condition="#ArrayLen(aSoldiers)# GT 1">
<cfif target GT ArrayLen(aSoldiers)>
<cfset target = target - ArrayLen(aSoldiers)>
</cfif>
<cfset ArrayDeleteAt(aSoldiers, target)>
</cfloop>

<!--- and the lucky survivor is... --->
<cfreturn aSoldiers[1]>
</cffunction>

Purpurowy Tentakyl2009-07-29 09:59

a simple python solution:

def josephus( numSoldiers, skip ):
soldiers = range( 1, numSoldiers + 1 )
i = skip - 1
while len( soldiers ) > 1 :
while True :
print soldiers
if i >= len( soldiers ) :
i = i % len( soldiers )
soldiers = filter( lambda x : x != 0, soldiers )
break
soldiers[i] = 0
i += skip
print "Lucky number is ", soldiers[0]

if __name__ == "__main__" :
from sys import argv
josephus( int( argv[1] ), int( argv[2] ) )

Public Function Murderize(ByVal SoldiersInCircle As Integer, ByVal KillEveryXth As Integer) As Integer
Return IIf(SoldiersInCircle = 1, 0, (Murderize(SoldiersInCircle - 1, KillEveryXth) + KillEveryXth) Mod SoldiersInCircle)
End Function

pjt332009-07-29 10:03

jfruh:

If I'm remembering right, Josephus was actually one of the last two standing, upon which he said to the other guy, as they were surrounded by corpses, "Maybe surrender isn't so shameful after all?" Not sure if the algorithm for figuring out how to be one of the last two is significantly easier.

Virtually identical. In my solution, replace

fun J(n,k) = j(n,k,n);

with

fun J2(n,k) = j(n,k,n-1);

Code Independent2009-07-29 10:03

steenbergh:

Code Dependent:

I doubt I could find the safe spot very quickly, but I've always been good at finding the G spot.

Fat lotta good that'll do you in a cave full of suicidal men...

In that case, I'll find the P Spot.

null2009-07-29 10:05

You stand as a first one to die and then invert the alive-dead state and you're the only one alive.

Robert Kosten2009-07-29 10:05

PHP:

function j($n, $k) {
if ( $n == 1 ) {
return 0;
} else {
return ((j($n-1,$k)+$k)%$n);
}
}

C#:
private int Josephus(int soldiers, int everyOther)
{
List<int> alive = new List<int>();
for (int i = 1; i <= soldiers; i++)
alive.Add(i);

int ndx = 0;
while (alive.Count > 1)
alive.RemoveAt(ndx = (ndx + everyOther - 1) % alive.Count);

return alive[0];
}

SR2009-07-29 10:09

Pipped at the post by the one and only Ben Forta. I'm half livid, half honoured :)

Andreas Kromann2009-07-29 10:15

Assuming that the start position is index 1.
He is safe as he is the only one in the game:
f(1,k) = 1
In general you solve the n'th case by reducing the problem by 1 and solving, adding k afterwards:
f(n,k) = f(n-1,k)+ k mod n+1
= f(n-2,k) + 2k mod n
= f(1,k) + (n-1)k mod n
= 1 + (n-1)k mod n
So all you need to do is:

public static int f(int n, int k)
{
return 1 + (((n-1) * k) % n);
}

Tom Parker2009-07-29 10:15

Crude Python method (which calculates lists of soldiers along the way):

def josephus(count):
soldiers = list(range(1,count+1))
index = 0
while len(soldiers)>1:
index = (index+2)%len(soldiers)
del soldiers[index]
return soldiers[0]

Kman2009-07-29 10:17

c++ templates

template <unsigned int s, unsigned int k> struct safe {
static const unsigned int result = (safe<s - 1, k>::result + k) % s;
};

template <unsigned int k> struct safe<1, k> {
static const unsigned int result = 0;
};

unsigned int index = safe<12, 3>::result;

it came out looking exactly like the python implementation

Ahox2009-07-29 10:17

What happened to the locker problem comment? I can't find it anymore, and I had such a nice solution

package require Tcl 8.5
proc josephus {number step} {
for {set i 0} {$i<$number} {incr i} {lappend l $i}
for {set i 0} {[llength $l] > 1} {incr i} {set l [if {$i%$step} {
list {*}[lrange $l 1 end] [lindex $l 0]
} else {
lrange $l 1 end
}]}
return $l
}
# Zero-based indexing...
puts [josephus 40 3]

Sure I could have used a modulus, but I like the notion of representing the circle of soldiers literally.

Random Net Poster2009-07-29 10:29

I prefer to avoid recursion if possible (and in C++ for no good reason):

#include <iostream>
#include <cstdlib>

using namespace std;
/* f(n,k)=(f(n-1,k)+k) mod n
f(1,k)=0
=>
a[n]=a[n-1]%n -> (...(((k%2 +k)%3 +k%4) +k%5... +k)%n
*/

int main (int argc, const char **argv)
{
int n, k;
if (argc != 3)
{
cerr << "Usage: "<< argv[0] << "<N> <K>\n";
return -1;
}

n = atoi (argv[1]);
k = atoi (argv[2]);

int r = 0;
for(int a=2; a<=n; a++)
r= (r+k)%a;

cout<< "With " <<n<<" soldiers and killing every "<< k <<"'th, the safe spot is position "<<r+1<<endl;
return 0;
}

DesGrieux2009-07-29 10:29

In Java, using Lists:

public static int getLastManStanding(int count, int step) {
List<Integer> aliveMen = new ArrayList<Integer>(count);
for (int i = 1; i <= count; i++) {
aliveMen.add(i);
}

Dim checker As String
Dim soldiers As Integer
Dim skips As Integer

Private Sub SetupSoldiers()
soldiers = Range("A1").Value
skips = Range("B1").Value

checker = "C" & CStr(soldiers + 1)

For i = 1 To soldiers
Range("C" & CStr(i)).Value = 1
Next

Range(checker) = "=SUM(C1:C" & CStr(soldiers) & ")"
Range(Replace(checker, "C", "B")) = "Counting survivors:"
End Sub

Private Sub CommenceKilling()
Dim i As Integer: i = 0
Do While Range(checker).Value > 1
For j = 1 To soldiers
Dim cur As String: cur = "C" & CStr(j)
If Range(cur).Value = "1" Then
i = i + 1
End If

If i = skips Then
Range(cur).Value = 0
i = 0
If Range(checker).Value = 1 Then
Exit For
End If
End If
Next
Loop

For i = 1 To soldiers
If Range("C" & CStr(i)).Value = 1 Then
Range("D" & CStr(i)).Value = "Survivor!"
End If
Next
End Sub

Private Sub AskNumbers()
Columns("A").ClearContents
Columns("B").ClearContents
Columns("C").ClearContents
Columns("D").ClearContents
Range("A1").Value = InputBox("No. of Soldiers")
Range("B1").Value = InputBox("Skips per kill")
End Sub

Private Sub CommandButton1_Click()
AskNumbers
SetupSoldiers
CommenceKilling
End Sub

But then we wouldn't be able to mock God in a unit test!

Be not misled, God is not mocked; for whatsoever a man codeth, this shall he also support.

aehiilrs2009-07-29 10:36

Anon:

Josephus' Circle, AKA Eeny, meeny, miny, moe. The solution is to argue about how many words are in the rhyme and whether the person selected at the end is "it" or "not it".

And also, if your grandparents are there, what the word ending in "ger" is. Talk about embarrassing.

def josephus(s,n)c=(0...s).to_a
i=0
while c.size>1
c[i,1]=nil
i=i+n
i=i%c.size
end
return c[0];
end

Wongo2009-07-29 10:39

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).

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

Soldiers: 2, Last Spot: 2
Soldiers: 3, Last Spot: 2
Soldiers: 4, Last Spot: 1
Soldiers: 5, Last Spot: 4
Soldiers: 6, Last Spot: 1
Soldiers: 7, Last Spot: 4
Soldiers: 8, Last Spot: 7
Soldiers: 9, Last Spot: 1
Soldiers: 10, Last Spot: 4
Soldiers: 11, Last Spot: 7
Soldiers: 12, Last Spot: 10
Soldiers: 13, Last Spot: 13
Soldiers: 14, Last Spot: 2
Soldiers: 15, Last Spot: 5
Soldiers: 16, Last Spot: 8
Soldiers: 17, Last Spot: 11
Soldiers: 18, Last Spot: 14
Soldiers: 19, Last Spot: 17
Soldiers: 20, Last Spot: 20
Soldiers: 21, Last Spot: 2
Soldiers: 22, Last Spot: 5
Soldiers: 23, Last Spot: 8
Soldiers: 24, Last Spot: 11
Soldiers: 25, Last Spot: 14
Soldiers: 26, Last Spot: 17
Soldiers: 27, Last Spot: 20
Soldiers: 28, Last Spot: 23
Soldiers: 29, Last Spot: 26
Soldiers: 30, Last Spot: 29
Soldiers: 31, Last Spot: 1
Soldiers: 32, Last Spot: 4
Soldiers: 33, Last Spot: 7
Soldiers: 34, Last Spot: 10
Soldiers: 35, Last Spot: 13
Soldiers: 36, Last Spot: 16
Soldiers: 37, Last Spot: 19
Soldiers: 38, Last Spot: 22
Soldiers: 39, Last Spot: 25
Soldiers: 40, Last Spot: 28
Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

sub dbg_print {
my $message = shift;
if ($debug) {
print "DEBUG: " . $message;
}
}

Perl Monk2009-07-29 10:51

Perl Golf'd:

$p[$_-1]=$_ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

77 chars :-)

rm52482009-07-29 10:52

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;
int soldiersSkipped = 0;
while(numLeft > 1){

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

//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) );
}
}
}

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!

Lifacciolo2009-07-29 10:52

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)

halber_mensch2009-07-29 10:53

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

astonerbum2009-07-29 10:54

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.

scp2009-07-29 10:54

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;
}

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

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

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;
}

halber_mensch2009-07-29 11:00

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.

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.

Chad2009-07-29 11:03

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;
dead++;
}
}
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];
}

Ian2009-07-29 11:04

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 Urbanski2009-07-29 11:06

Perl Monk:

Perl Golf'd:

$p[$_-1]=$_ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

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)=@_;" <- 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)

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 :).

Anon2009-07-29 11:07

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

Andreas Kromann2009-07-29 11:09

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}

mariushm2009-07-29 11:11

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.'<br/>';

?>

Anon2009-07-29 11:11

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.

Yazeran2009-07-29 11:12

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

Anon2009-07-29 11:15

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}

Knux22009-07-29 11:18

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 Kromann2009-07-29 11:22

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

astonerbum2009-07-29 11:23

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.

Code Dependent2009-07-29 11:25

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

Capt. Obvious2009-07-29 11:26

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

Wongo2009-07-29 11:30

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.

Phil2009-07-29 11:31

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?

IV2009-07-29 11:33

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).

db22009-07-29 11:35

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
>>
>>

Wongo2009-07-29 11:37

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++;
...

Overcaffeinated2009-07-29 11:37

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()

sbrant2009-07-29 11:37

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)

Blarg2009-07-29 11:39

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.

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()

time0ut2009-07-29 11:42

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.

/**
* 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.dancers.add(new Dancer(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;

<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)#<br/></cfoutput>
<cfset circle=listDeleteAt(circle, x)>
</cfloop>
<cfoutput>The last name standing was in position #circle#<br/></cfoutput>
</code>

Wongo2009-07-29 11:43

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 Bush2009-07-29 11:44

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

<?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 <akoimeexx@gmail.com>
*
* @attrib: http://thedailywtf.com/Articles/Programming-Praxis-Josephus-Circle.aspx
*/

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}

Wongo2009-07-29 11:54

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.

Brad2009-07-29 11:57

Delphi

program Josephus;

{$APPTYPE CONSOLE}

uses
SysUtils;

{ SafeIndex : Returns zero-based index of safe location in Josephus' Circle.
- soldierCount : number of soldiers in initial circle
- killEvery : interval at which to kill off soldiers
}
function SafeIndex(
soldierCount : Integer;
killEvery : Integer
) : Integer;
var
count : Integer;
safe : Integer;
begin
count := 1;
safe := 0;

while (count < soldierCount) do begin
Inc( count );
safe := (safe + killEvery) mod count;
end;

Result := safe;
end; // SafeIndex

procedure WriteUsage;
begin
WriteLn('Usage: Josephus <soldierCount> <killEvery>');
end;

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

Soldiers: 2, Last Spot: 2
Soldiers: 3, Last Spot: 2
Soldiers: 4, Last Spot: 1
Soldiers: 5, Last Spot: 4
...snip...
Soldiers: 37, Last Spot: 19
Soldiers: 38, Last Spot: 22
Soldiers: 39, Last Spot: 25
Soldiers: 40, Last Spot: 28
Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

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;

justsomedude2009-07-29 11:58

Of course that is Excel + VBA, not pure VBA.

VBA's bad reputation drives me nuts...it's a good language for what it's intended uses are...so I can't help but be the ass who points out:

1)There's no need to manipulate values on a worksheet, you can use variables and it will run much faster. Each time code touches a worksheet object you pay a large price in speed. Better to do everything in memory and only kick the final result. You can also use Debug.Print to write to the immediate window. Do While Range(checker).Value > 1 will perform much better if replaced by a check against an internal variable, particularly for large loops.

2) You should use Columns("A:D").ClearContents instead of four separate calls; faster to both write and run. No need to clear columns if you keep data in memory. (arrays?)

3) It's a bad habbit to use code like: Range(somthing).Method, doing this will break if you accidentally activate a different worksheet while the code is running. When you reference "Range", you are implictly saying Application.ActiveWorksheet.Range, which users can break easily. It's much better to explictly declare which worksheet you want to operate on, using something like sheet1.Range(something) or Worksheets("ExternalSheetName").Range(something) (and bonus points if you use with blocks to reduce the number references to higher level objects)

4) No need to type cast strings when using & for string concatination. strMyString = "Some Text " & i runs faster than strMyString ="Some text" & Cstr(i)

5) using code to write worksheet functions is a bit much, there are times where that is useful, but you have the values in code so why not just add them in code too?

6) Dim cur As String: cur = "C" & CStr(j), not sure if this is considered bad form or not, but I'd wager dimming a var inside a loop slows things significantly. You're replacing the value of this variable each time, no need to redim it.

Wongo2009-07-29 11:58

halber_mensch:

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}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

justsomedude2009-07-29 12:00

justsomedude:

Of course that is Excel + VBA, not pure VBA..

{snip}

Quote fail...that was in reference to the vba post on page 1...

Karol Urbanski2009-07-29 12:01

Capt. Obvious:

1 + (n-1)(k-1) mod n

Neither this nor 1+(n-1)k mod n works. Consider case 17 soldiers, the person to count 2 dies. So, n=17, k=2. The correct answer for those is index 2 (3 if indexed from 1).

for 1 + (n-1)k mod n: 1 + (17-1)2 mod 17 = 1 + 32 mod 17 = 16, which is incorrect.
for 1 + (n-1)(k-1) mod n: 1 + (17-1)(2-1) mod 17 = 1 + 16 mod 17 = 17, which is also incorrect.

I assumed you mean % as taking precedence over addition, in C fashion. However, even if you actually meant (1 + (n-1)k) mod n or (1 + (n-1)(k-1)) mod n for 17,2 the results are 16 and 0, respectively. Also incorrect.

DesGrieux2009-07-29 12:07

Wongo:

halber_mensch:

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}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}.
We begin counting now at 5, which is skipped, so remove 1: {3,5}.
We begin count now at 3, which is skipped, so remove 5: {3}

Chad2009-07-29 12:09

By looking at that sequence I was able to come up with the following javascript solution:

function josephus3(count, seed)
{
var index = seed % 2 == 0 ? 1 : 2;

for (var i = 3; i <= count; i++)
{
index += seed;
while (index > i)
index -= i;
}

return index;
}

First we determine the starting index based on whether the seed is even or odd.

Next we follow the pattern of the solution above, which is, every time you go up from two you add the seed to the index and if the new index is greater than i (the number of men) you subtract i.

I expected this to work with a seed of 3, but I was surprised when I found out it works with any seed. It was easy for me to write an algorithm to represent the pattern, whereas I don't think I could figure out the other more elegant approaches.

Ron Moses2009-07-29 12:10

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

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
SET Dead = 1
WHERE SoldierNumber = @i;

END

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

END

Wongo2009-07-29 12:11

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"...

Most of this function is just the definition for the ax() function.

Ed2009-07-29 12:15

JavaScript 1.8:

function j(n, k) n <= 1 ? 0 : (j(n - 1, k) + k) % n;

Non-recursive form:

function j(n, k) { let p = 0, i = 1; while (i < n) p += k, p %= ++i; return p }

As mentioned at Wikipedia, a closed form exists for k = 2: j(n, 2) = 2 * (n - 2 ^ log2(n))
There is no closed form for k = 3; a good place to start is OEIS A054995.

Akoi Meexx2009-07-29 12:17

Woops, that should be
unset($roulette[$arrayIndex]);
not unset($roulette[$value]);

Why must comments keep erroring out?

Wongo2009-07-29 12:19

DesGrieux:

Wongo:

halber_mensch:

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}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}.
We begin counting now at 5, which is skipped, so remove 1: {3,5}.
We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

Truly, there is nothing sexier than recursion. It's especially elegant for problems like this one.

Unfortunately, it's a bitch to maintain, and a memory hog for larger functions.

Sexier: Cate Blanchett.
Bitch to maintain: Well, possibly Ms Blanchett also, for all I know. Then again, why on earth would a correct recursive procedure be any more of a bitch to maintain than a correct iterative homologue?
Memory hog: Tail recursion, my man. Tail recursion.

Other than that, all these solutions appear to assume a boolean state for each soldier of dead/alive. Whatever happened to death_not_found?

Andreas Kromann2009-07-29 12:23

Wongo:

DesGrieux:

Wongo:

halber_mensch:

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}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}.
We begin counting now at 5, which is skipped, so remove 1: {3,5}.
We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc.
Sorry for wasting yout time :)

MHolt2009-07-29 12:27

Naive, very much to the letter solution in Scheme:

(define josephus
(lambda (n skip)
(let ([S (build-list n #t)]
[a n])
(letrec ([inner
(lambda (i c)
(if (> a 1)
(if (car (list-ref S i))
(if (< c skip)
(begin
(inner (modulo (1+ i) n) (1+ c)))
(begin
(set-car! (list-ref S i) #f)
(set! a (- a 1))
(inner (modulo (1+ i) n) 0)))
(inner (modulo (1+ i) n) c))
(get-alive 0)))]
[get-alive
(lambda (i)
(if (eq? (car (list-ref S i)) #f)
(get-alive (1+ i))
(begin (display "With ")
(display n)
(display " soldiers and killing every ")
(display (1+ skip))
(display "th, the safe spot is: ")
(1+ i))))])
(inner 0 0)))))

(define build-list
(lambda (n val)
(if (zero? n)
'()
(cons (cons val '()) (build-list (- n 1) val)))))

And a test session:

Petite Chez Scheme Version 7.4
Copyright (c) 1985-2007 Cadence Research Systems

> (load "josephus.scm")
> (josephus 12 2)
With 12 soldiers and killing every 3th, the safe spot is: 10
> (josephus 41 2)
With 41 soldiers and killing every 3th, the safe spot is: 31
>

samanddeanus2009-07-29 12:30

(define (josephus n q)
(let solve ((i 1) (jn 0))
(if (< n i)
(+ 1 jn)
(solve (+ i 1) (remainder (+ jn q 1) i)))))

Edit: Use one-based index

Addendum (2009-07-29 14:13): (q is "number to skip", so kill every q+1 th) -- I originally had it the other way but then edited it.

Mr. Bob2009-07-29 12:31

The solution is:

"Hey everyone, I'll watch the door while you guys sort this out."

Wongo2009-07-29 12:31

Andreas Kromann:

My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc.
Sorry for wasting yout time :)

Nah, I knew you were on to something... Couldn't have found it myself anyway (or maybe with lots more time).

db22009-07-29 12:33

Wongo:

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"...

Granted, I haven't tested it for other values of k, or for weird edge cases, but I was able to precisely reproduce your list of safe spots by putting a Console.WriteLine() at the bottom of the loop body.

Ev2009-07-29 12:35

Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

s0be2009-07-29 12:47

Perl Monk:

Perl Golf'd:

$p[$_-1]=$_ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

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}

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

{1,2,3,4,5} => {1,3,4,5} => {1,3,5}.
We begin counting now at 5, which is skipped, so remove 1: {3,5}.
We begin count now at 3, which is skipped, so remove 5: {3}

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

Anon2009-07-29 12:52

Ev:

Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

samanddeanus2009-07-29 12:56

(define (josephus n m)
(let loop ((d 1))
(if (> d (* m n))
(- (+ (* n m) n 1) d)
(loop (ceiling (* d (/ (+ m 1) m)))))))

Iterative and runs in logarithmic time

Addendum (2009-07-29 14:08): NOTE: m is number to skip as listed in article -- so every m+1 is killed.

Korkut2009-07-29 12:59

Why Prolog gets no love... K is step size, I is 0 based index, N is number of unluckies.

josephus(0,1,_).
josephus(I,N,K) :- M is N-1, josephus(J,M,K), I is (J+K) mod N, !.

Cut is not absolutely necessary.

Srki2009-07-29 13:01

horizon:

assuming that the starting position is 0:

int f(int numberOfSoldiert, int numberOfSkips)
{
return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers;
}

Great, I believed there is a very simple solution... Because of "VERY FAST" phrase. This solution has constant time, all others are n dependent.

Ramūns2009-07-29 13:05

Here's another javascript version

function josephus(n,k){
if ( n <= 1 ) {
return 1;
}
var data = [];
for ( var i = 0; i < n; i++ ) {
data[i] = i+1;
}
var l = n;
for ( var i = (k-1)%l; l > 1; i = (i+k-1)%(--l) ) {
data.splice(i,1);
}
return data[0];
}

Phil2009-07-29 13:07

Good old C. Still no 860 iterations. First method 398 steps; recursive method does n-1 recursions; iterative solution loops n-1 times.

public string DoJosephus(int soldiersCount, int soldiersToSkip)
{
List<string> soldiers = new List<string>(soldiersCount);
for (int j = 0; j < soldiersCount; j++) soldiers.Add((j+1).ToString());
int i = soldiersToSkip - 1;
do
{
i = GetStep(i, soldiers.Count);
soldiers.RemoveAt(i);
if (i + soldiersToSkip > soldiers.Count) i = i - soldiers.Count;
i = i + soldiersToSkip - 1;

} while (soldiers.Count>1);
return soldiers[0];
}

private int GetStep(int i, int count)
{
if (i < count) return i;
else i = i - count;
return GetStep(i, count);
}

Dr. Batch2009-07-29 13:18

A batch file solution:

@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 survivor is at index %survivor%
exit /b

:josephus
set soldiers=%1
set /a soldiersnext="soldiers-1"
set count=%2
if %soldiers% neq 1 call :josephus %soldiersnext% %count%
set soldiers=%1
set /a survivor="(count+survivor)%%soldiers"
exit /b

Function Josephus(Number,Skip : integer) : integer;
var
cur : Jptr;
lcv : integer;
begin
cur := MakeCircle(Number);
repeat
for lcv := 1 to Skip do cur := cur^.next;
cur := kill(cur);
until cur^.next = cur;
Josephus := cur^.Number;
cur := kill(cur);
end;

begin
Write('Number of Soldiers: ');
Readln(n);
Write('Number to Skip: ');
Readln(s);
Writeln('Safe Spot: ',Josephus(n,s));
end.

John Evans, btradish@earthlink.net2009-07-29 13:36

#include <stdio.h>
int f(n,k){return n<=1?0:(f(n-1,k)+k)%n;}
main() {
int g; for (g = 0; g < 48; ++g)
printf("josephus %d skip %d = %d\n", (int)(g/3)+1, (g%3)+2, f((int)(g/3)+1,(g%3)+2));
}

Thank you, CLR.

Jadawin2009-07-29 13:38

What have I learned today?

If I'm going to have a Judeo circle of mass [suicide|assisted suicide], be the one who announces the skip number AFTER the circle is formed.

marco2009-07-29 13:38

yes the last

push into an array all the loosers
with a for loop that counts 3
and inside the for put an if for checking the actual array
if is in the array dont push it and continue checking the array of the standing soldiers

for this u need 2 arrays one for loop and put it into a function and done

my inglish is bad i know

:)

halber_mensch2009-07-29 13:52

Anon:

No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

k is the skip, count is k+1. You count to three and thus skip over two guys. 1 2 3 4 5 6 7 8 9 etc. If your count is one, your k is 0 in which case J(5,0) yields 5. But our count is 2 and the k is 1 to skip every other guy.

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

mtu2009-07-29 13:54

God, that took me so much longer than it should have - and I'm not even proud of the code :-(

(define (create-circle n)
(let ((initial-pair (list n)))
(let iter ((i (- n 1)) (accum initial-pair))
(if (zero? i)
(begin (set-cdr! initial-pair accum) accum)
(iter (- i 1) (cons i accum))))))

(define (josephus n m)
(let iter ((circle (create-circle n)))
(if (eq? (car circle)
(cadr circle))
(car circle)
(let ((skipped-m (list-tail circle m)))
(set-car! skipped-m (cadr skipped-m))
(set-cdr! skipped-m (cddr skipped-m))
(iter skipped-m)))))

Note: m is the "number to skip" as in the spec, so you kill every m+1 th

Addendum (2009-07-29 17:09): This is intended to model the actual chopping process, not to be efficient.

neo2009-07-29 14:14

Just started learning Haskell so ...
but this seems to work

-- josephus try

joHelper xs = if null (drop 2 xs)
then drop 1 xs
else joHelper ((drop 3 xs) ++ (take 2 xs))

josephus i = head (joHelper [1..i])

the pattern2009-07-29 14:17

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

DeLos2009-07-29 14:22

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

IdontDoRecursion2009-07-29 14:28

#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[1]);
if(argc>2) step=atoi(argv[2]);
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...

# 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. Nymme2009-07-29 14:37

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 Gravity2009-07-29 14:37

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[0]} soldiers, chopping one head every #{ARGV[1]}."
print "Chopping head off of "
soldiers = (1..ARGV[0]).to_a
soldiers.kill!(3) { |dead_soldier| print dead_soldier, " " }
puts
puts "The last standing is #{soldiers[0]}."

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. Nymme2009-07-29 14:40

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 roth2009-07-29 14:56

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!

ikegami2009-07-29 14:56

Alex Papadimoulis:

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.

Alex Papadimoulis:

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!

ikegami@adaelis.com

Coyne2009-07-29 14:57

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)
{
boolean dead[] = new boolean[men];
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;
if (!dead[pos]) steps--;
}
dead[pos] = true;
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)[0];
return (countTo + men - 1) % men;
}

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

thc4k2009-07-29 15:31

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 ?

Nukeme12009-07-29 15:37

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;

VinDuv2009-07-29 15:37

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

set num_to_skip to 0

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
set num_to_skip to text_entered as integer
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

Melvis2009-07-29 15:40

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

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
SET Dead = 1
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...

scott2009-07-29 15:46

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;
}
}

H22009-07-29 15:52

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[0]!~m/[1-9]/) || ($ARGV[1]!~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;

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()
{

while (dead < (_Soldiers -1))
{
for (int i = 0; i < _Soldiers; i++)
{
if (jews[i].alive)
{
if (counter == _Skip)
{
jews[i].alive = false;
counter = 1;
dead++;
}
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.";

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 somebody2009-07-29 16:00

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);
}

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[0];
Dispose(Alive);
AliveList.Delete(0);
end;
FreeAndNil(AliveList);
end;

end.

odio2009-07-29 16:09

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!

byornski2009-07-29 16:16

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;
}

MadCow422009-07-29 16:17

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)

MadCow422009-07-29 16:19

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)

Lerb2009-07-29 16:21

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

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[0]);
return 1;
}
printf("safe spot: %u\n",jc(atoi(argv[1]),atoi(argv[2])));

return 0;
}

electrichead2009-07-29 16:23

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.

Herby2009-07-29 16:37

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.

reuven2009-07-29 16:39

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;

PatrickBeebe2009-07-29 16:40

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);
}

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

Wongo2009-07-29 16:58

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 :

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();

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[0] :
calc_j($new_idx=($idx+$skip-1) % @array, $skip, array_except(@array, $new_idx));
}

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

Oscar Olim2009-07-29 17:46

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

Dr. Batch2009-07-29 17:53

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+(z*c))%%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.

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

Michael van der Gulik2009-07-29 18:00

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. "

samanddeanus2009-07-29 18:02

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 'dead?) (not 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)
(error "Cannot kill PERSON" num "-- already dead")
(set! alive false)))
(else (error "Unknown operation -- PERSON" num))))))

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

Help?

Frisbeetarian isn't working, either... it keeps getting stuck somewhere.

corvi2009-07-29 18:13

HAI 1.2

BTW used some syntax liberties for areas underdefined around arrays

HOW DUZ I JosephusCircle YR soldiers AN YR skip

I HAS A soldier
soldier r 1

I HAS A dead
dead r 0

I HAS A deadsoldiers
deadsoldiers r DIFF OF soldiers AN 1

I HAS A circle
IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers
soldier IN MAH circle r WIN
IM OUTTA YR LOOP

I HAS A skipnum
skipnum r 1

soldier r 1
IM IN YR KILLLOOP UPPIN YR soldier WILE DIFFRINT dead AN BIGGR OF dead AN deadsoldiers
BOTH SAEM soldier IN MAH circle AN WIN, O RLY?
YA RLY
BOTH SAEM skipnum AN skip, O RLY?
YA RLY
soldier IN MAH circle r FAIL
dead r SUM OF 1 AN dead
skipnum r 1
NO WAI, skipnum r SUM OF skipnum AN 1
OIC

OIC

BOTH SAEM soldier AN soldiers, O RLY?
YA RLY, soldier r 0
OIC

IM OUTTA YR KILLLOOP

BOTH SAEM dead AN deadsoldiers, O RLY?
YA RLY

IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers
BOTH SAEM soldier IN MAH circle AN WIN, O RLY?
YA RLY, safespot r soldier
OIC
IM OUTTA YR LOOP
NO WAI, safespot r 0
OIC

FOUND YR safespot
IF U SAY SO

KTHXBYE

samanddeanus2009-07-29 18:15

@Dr. Batch:

I have posted code in Scheme which yielded
(josephus 32767 2) [of 32767 people, skip 2 and then kill the next person] in 27 iterations and (josephus (largest-fixnum) 2) in 98 iterations. [largest-fixnum is 144115188075855871]

Even
(josephus (expt (largest-fixnum) 100) 2)
returns immediately.

The ceiling function in Scheme works on rational numbers as well as floats, so it returns exact answers.

I also made some Scheme code that "models" the situation using circular lists or message-passing, which probably runs slow as !@#$$

Kevin M2009-07-29 18:20

An iterative version of my previous solution, also handles arbitrary count value k (kill every k'th element):

int josephus(Vector<Integer> v, int k) {
while (v.size() > 1) {
for (int i = 0; i < k - 1; i++) {
v.add(v.remove(0));
}
v.remove(0);
}

return v.elementAt(0).intValue();
}

Dr. Batch2009-07-29 18:28

Bob:

@Dr. Batch:

I have posted code in Scheme which yielded
(josephus 32767 2) [of 32767 people, skip 2 and then kill the next person] in 27 iterations and (josephus (largest-fixnum) 2) in 98 iterations. [largest-fixnum is 144115188075855871]

Even
(josephus (expt (largest-fixnum) 100) 2)
returns immediately.

The ceiling function in Scheme works on rational numbers as well as floats, so it returns exact answers.

I also made some Scheme code that "models" the situation using circular lists or message-passing, which probably runs slow as !@#$$

My arrogance and I stand corrected.

dvrslype2009-07-29 18:31

public class JosephusCircle {

public static int lastManStanding(int soldiers, int skip) {
if (soldiers == 1)
return 0;

1 REM **********************
2 REM * *
3 REM * Josephus' CIRCLE *
4 REM * *
5 REM * TheDailyWTF.com *
6 REM * *
7 REM * by mol1111 *
8 REM * *
9 REM * Greets go to *
10 REM * Alex,the organizer *
11 REM * Yorick *
12 REM * Lamac, for his ROM *
13 REM * *
14 REM **********************
15 REM .
45 REM Bigger number makes
46 REM it slower. Set to zero
47 REM to wait for keypress
48 REM after each step.
50 LET wait=20
60 PAPER 0
70 INK 7
80 BORDER 0
90 CLS
100 INPUT "How many soldiers?",n
110 INPUT "How many to skip", skip
112 IF n>0 AND skip>=0 THEN GO TO 119
114 PRINT "There should be at least one soldier and the skip should be 0 or more."
116 GO TO 100
119 REM .
120 REM Draw soldiers
121 REM .
125 CLS
130 LET angle=2*PI/n
132 LET scale=60
140 FOR i=1 TO n
150 GO SUB 1000
160 CIRCLE x, y, 10
165 GO SUB 1100
170 NEXT i
180 REM .
190 REM Play.
200 REM .
204 REM Modulo function.
205 DEF FN m(a,b)=a-(INT (a/b)*b)
208 INK 2
210 DIM s(n)
220 LET i=1
230 LET lasts=n
240 IF lasts=0 THEN GO TO 500
250 LET stilltoskip=skip+1
260 IF stilltoskip=0 THEN GO TO 320
270 LET i=1+FN m(i,n)
280 IF s(i) THEN GO TO 270
300 LET stilltoskip=stilltoskip-1
310 GO TO 260
320 LET s(i)=1
322 LET lasts=lasts-1
324 IF lasts=0 THEN INK 4
330 GO SUB 1000
335 PAUSE wait
340 CIRCLE x,y,10
345 GO SUB 1100
350 GO TO 240
500 REM The End.
980 INK 7: REM reset to white
990 STOP
1000 REM .
1001 REM Compute middle of the CIRCLE .
1002 REM .
1010 LET x=128+scale*COS (angle*i)
1020 LET y=96+scale*SIN (angle*i)
1030 RETURN
1100 REM .
1101 REM Prints soldier's number
1102 REM It's not exact because
1103 REM print works just with
1104 REM rows and columns, not
1105 REM pixels.
1106 REM .
1110 LET column=x*(33/256)-1
1120 LET row=22-y*(25/192)
1130 PRINT AT row,column;i
1140 RETURN

Addendum (2009-07-29 19:36): If you want to start counting including the first soldier (as in article's picture) change the line 220 to LET i=0 .

ponky2009-07-29 19:55

piet

First input is the number of soldiers.
Second input is the number to skip.
Output is the (zero based) index of the survivor.

Bradley Dean2009-07-29 20:00

C# / generics:

static int Josephus(int numSoldiers, int soldiersToSkip)
{

// create soldiers
List<int> Soldiers = new List<int>();
for (int i = 0; i < numSoldiers; i++)
{
Soldiers.Add(i);
}

// kill soldiers
int iSoldier = 0;
while (Soldiers.Count() > 1)
{

// skip ahead by the requested number of soldiers
iSoldier = iSoldier + soldiersToSkip;

// if we've gone over, then wrap back around to the top
while (iSoldier > Soldiers.Count())
{
iSoldier -= Soldiers.Count();
}

// kill the choosen soldier
Soldiers.RemoveAt(iSoldier - 1);
}

// return answer
return Soldiers[0] - 1;

}

Utunga2009-07-29 20:14

IV:

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).

No, no, no. For Scrödinger's approach to work you need quantum. Doesn't work without one, everyone knows that.

Goglu2009-07-29 21:00

If it were, many wars would have been avoided...

bwross2009-07-29 21:31

In dc:

[ Lks. Lns. ] SR
[ lRx 0 q ] SX
[
Sk Sn
1 ln =X
ln 1- lk lJx lk+ ln%
lRx
] SJ

Veltyen2009-07-29 21:34

Shellscript. With graphical output. :)

USAGE = <scriptname> <number in circle>
Error handling non-existant.

#!/bin/sh

NUM=$1;

echo "Starting Number = " $NUM

for (( i = $NUM ; i != 0; i-- ))
do
ARRAY="a $ARRAY"
done

echo $ARRAY

#Killing time

INCREMENTOR=0
ALLDEAD=NUP

while [ $ALLDEAD != YUP ]
do

ARRAY2=""

for ELEMENT in $ARRAY
do
if [ $ELEMENT = a ]
then
INCREMENTOR=`expr $INCREMENTOR + 1`
#echo "Incrementor is $INCREMENTOR"
fi
if [ $INCREMENTOR -eq 3 ]
then
INCREMENTOR=0
ARRAY2="$ARRAY2 d "
else
ARRAY2="$ARRAY2 $ELEMENT"
fi

#echo $ARRAY2
done

ARRAY=$ARRAY2
echo $ARRAY

STILLALIVE=0
for ELEMENT in $ARRAY
do
if [ $ELEMENT = a ]
then
STILLALIVE=`expr $STILLALIVE + 1`
fi

done

if [ $STILLALIVE -eq 1 ]
then
ALLDEAD=YUP
fi

echo "still alive = $STILLALIVE"

done

LUCKYNUM=1
for ELEMENT in $ARRAY
do
if [ $ELEMENT = d ]
then
LUCKYNUM=`expr $LUCKYNUM + 1`
else
echo "Survivor is number $LUCKYNUM"
fi

done

Strange Quark2009-07-29 21:54

int josephus(int size, int skip)
{
if(size <= 1)
return 1; // You have no reason to worry if its just you

// Allocate array of size @size
bool *point = new bool[size];

int axed = 0; // People axed
int seq = 0; // Current skip sequence
int pos = 0; // Current position in circle

// Loop while there is more than 1 person alive
while(axed < size - 1)
{
// if its reached the sequence and that person is still alive...
if(seq == (skip - 1) && point[pos])
{
// Axe the person
point[pos] = false;
axed++;
seq = 0;
}
else
if(point[pos])
seq++; // Else increase the sequence

pos++; // Move to next position

if(pos == size)
pos = 0; // Reset to beginning if reached the end

}

// return the single living position
for(int i = 0; i < size; i++)
if(point[i])
return i;

return -1;
}

John Stracke2009-07-29 22:00

j delta n = step [1..n] 1
where step [x] _ = x
step (x:xs) i = if i == delta
then step xs 1
else step (xs++[x]) (i+1)

Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

Paddles2009-07-29 22:26

Here it is, in awk. A more awk-ish implementation would replace the troops string with an associative array, deleting (how appropriate!) elements until there was only one left - but that would come at the cost of making the snuff movie a bit harder.

int($1)>0 {
troopsize =$1;
troops = "";
for (i=1;i<=troopsize;i++) troops = troops "^";
lastmember = 0;
for (i=1;i<troopsize;i++) {
for (j=1;j<=interval;j++) {
nextmember=index(substr(troops,lastmember+1),"^");
if (nextmember==0) nextmember=index(troops,"^")
else nextmember += lastmember;
lastmember = nextmember;
}
troops = substr(troops,1,lastmember-1) "v" substr(troops,lastmember+1);
if (VERBOSE>0) {
printf("%s\r",troops); # Prints a pretty progressive display of alive and dead members marked by ^ and v.
for (k=1;k<=300000;k++) {foo=sin(k);} # In lieu of a sleep command.
}
}
if (VERBOSE >0) print "";
print index(troops,"^");
}

I feel like pointing out that O(n) is a horrible running time in this case. It's pseudo-linear (linear in the numeric value of the input but exponential in the size of the input). We can do much better than exponential in N's representation.

Here is an algorithm which runs in O(lg(N)*S) time, assuming arithmetic operations are constant time.

function f(int n, int s) as int:
if n < 1 or s < 1 then error
if s == 1 then return n - 1 #special case
if n == 1 then return 0 #end condition

#recurse on sub-group obtained after a cycle completed
var t = f(n - ceiling(n / s), s)

#map sub-result to current group
t += -n mod s #assumes mod result is in [0, s)
t += floor(t / (s-1))
return t mod n

It achieves the massive speed up by performing an entire trip (and a bit more) around the circle in each recursion. I haven't figured out any way to make it non-exponential in S's representation yet.

Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

Yet another simulator version, but maybe it's a little different from the others.

public static IEnumerable<int> JosepheusInverseOrder(int requiredpeeps)
{
Queue<int> people = null;
if (requiredpeeps <= 0)
people = new Queue<int>(new int[] {});
else
{
people = new Queue<int>(new int[] { 0 });
int numpeeps = people.Count() ;
//work it backwards
while (requiredpeeps > numpeeps)
{
int temp;
// use Queue as circular list
temp = people.Dequeue();
people.Enqueue(temp);
temp = people.Dequeue();
people.Enqueue(temp);
people.Enqueue(numpeeps);
numpeeps++;
}
}
return people.ToArray().Reverse();
}

Which, instead of killing the guys, pushes the guys to die in the proper order from Josepheus back and up till the first guy dies. Then all we need to do to get the index of Josepheus (Mr. Zero)...

System.Console.WriteLine("Josepheus needs to be at place {0}.", Array.IndexOf(people.ToArray(), 0)+1);

xeno2009-07-29 23:05

<?php
/**
Sandbox grid solution.
----------------------
This isn't the most efficient algorithm (a computer doesn't need multiple rows), you may
even be able to express this problem as a mathematical equation. However, a person can
execute this algorith by drawing a grid in the sand, as Josephus might have done, using the
rows to avoid losing your place (which would fatally alter the result).

The multiple rows help you keep your place. As you work your way along each row,
"killing soldiers" you strike out the rest of the column (downwards, from the current row).
When you run of the end of the row, go down to the next. I've allocated enough rows in
the function, but if you're working in the sand you can just add more if you run out.
That's just as well, as division was considered complex maths in the 1st century.
*/

$n = $argv[1];
$skip = $argv[2];
echo "The safe spot is #" . josephs_circle($n, $skip) . "\n";

$x = $skip -1; // count zero
$y = 0;
$kills = 0;
while (true)
{
while ($grid[$y][$x] and $x < $n) // column is "dead", still on this row
{
$x++;
}

if ($x >= $n) // have run off the end of the row (above)
{
$x = 0;
$y++;
$grid[$y] = $grid[$y -1]; // strike out downwards
continue;
}

$kills++; // now we're going to kill somebody, unless ...
if ($kills == $n) // ... we're the last man standing
{
return $x +1; // convert from count-zero to count-one and return
}

$grid[$y][$x] = '*'; // hit the soldier with the axe
$x += $skip;

if ($x >= $n) // have skipped off the end of the row
{
$x = $x % $n;
$y++;
$grid[$y] = $grid[$y -1]; // strike out downwards
}
}
}
?>

I have no idea why this is coming out double-spaced. Anyway, Josephus was the third man, like Orson Welles.

Sterge2009-07-29 23:15

import java.util.HashMap;

public class Josephus
{
public static void main(String[] args)
{
// The example of 12 soldiers in a circle is won by spot 10 (index 9).
HashMap<Integer, Boolean> livingSoldiers = new HashMap<Integer, Boolean>();
int numSoldiers = 0;
int numToSkip = 0;
int skipped = 0;

(num_peeps - 1).times do
(num_skip - 1).times do
iterator = iterator.next
end
delete = iterator
iterator = iterator.next
ll.delete(delete)
end

iterator.val
end

Christian2009-07-29 23:21

Here's an attempt with VBScript that simulates a linked list with an array.

Function JosephusSafeSpot(intNumberOfSoldiers, intNumberToSkip)
Dim arrPopulation(), intIndex, intPrevious, intSubIndex
ReDim arrPopulation(intNumberOfSoldiers)
For intIndex = 1 To intNumberOfSoldiers
arrPopulation(intIndex) = (intIndex mod intNumberOfSoldiers) + 1
Next

intIndex = 1
Do Until intIndex = arrPopulation(intIndex)
For intSubIndex = 2 To intNumberToSkip
intPrevious = intIndex
intIndex = arrPopulation(intIndex)
Next

Go ahead and try it with any of the other looping ones. I'll wait.

My very bad F# looping version did that in 42 ms, (25 iterations) if I remove the prints during the loop. Just under a second with them. Not a very long wait either way. Raising the skip makes it much worse though, then the memory reallocations start to hurt.

SurturZ2009-07-29 23:44

Visual Basic 2008, using generic list....

Function joe(ByVal soldiercount As Integer, ByVal skipcount As Integer) As Integer
Dim i As Integer
Dim lst As New List(Of Integer)
For i = 1 To soldiercount
lst.Add(i)
Next i
Do Until lst.Count = 1
'move top two to end
i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
'kill third guy
lst.RemoveAt(0)
Loop
Return lst(0) 'last man standing's original position
End Function

SurturZ2009-07-30 00:02

Oops, got it wrong, here is correct version:

Function joe(ByVal soldiercount As Integer, ByVal skipcount As Integer) As Integer
Dim i As Integer
Dim lst As New List(Of Integer)
For i = 1 To soldiercount
lst.Add(i)
Next i
Do Until lst.Count = 1
'move top guys to end
For j As Integer = 0 To skipcount - 2
i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
Next j
'kill appropriate guy
lst.RemoveAt(0)
Loop
Return lst(0)
End Function

Firestryke312009-07-30 00:07

Perhaps to calculate it quickly he used assembly?

;; Josephus' Circle - Intel 80386-compatible assembly
;; Parameters: eax = number of soldiers, ebx = kill stride
;; returns: eax = safe spot, ecx = original number of soldiers

;; Stuff to make it work with C
global _joseC;
global joseC;

;; I didn't really look into doint this more efficiently
;; but it's not the focus, so it doesn't matter
_joseC:
joseC:
push ebp
mov ebp, esp
push ebx
push ecx
push edx
mov eax, [ebp + 8 ]
mov ebx, [ebp + 12]
call joseASM
pop edx
pop ecx
pop ebx
pop ebp
ret

;; Here's the meat of the program:
joseASM:
;; Save the original number of soldiers for later on
mov ecx, eax
;; we need to check if eax was one, and we need eax - 1 later
;; so subtract the one now
dec eax
;; and check for zero
or eax, eax
;; if it is, we're done.
jz return

;; it wasn't, so let's save the original number of soldiers
push ecx
;; and go through it all again with n-1 soldiers
call joseASM
;; Now we need to add the kill stride
add eax, ebx
;; get the original number of soldiers back
pop ecx
;; zero out edx for the divide
xor edx, edx
;; perform the modulus (div stores % in edx and / in eax)
div eax, ecx
;; put the result in eax to make recursion easier
mov eax, edx
return:
;; leave the function
ret

robsonde2009-07-30 01:13

so it has been a few years since I did any code on the C64.

Not really how MPI is supposed to be used, but it works. At least for smaller values, falls apart with larger.

ikegami2009-07-30 01:43

Functional programming solution in Perl.

#!/usr/bin/perl

use strict;
use warnings;

use List::Util qw( reduce );

# Silence warnings.
$a=$b if 0;

sub step {
my ($k) = @_;
return sub { ($a + $k) % $b };
}

sub J {
my ($n, $stepper) = @_;
return reduce \&$stepper, 0, 2..$n;
}

print( J(12,step(3)), "\n");

bobtherriault@mac.com2009-07-30 01:46

In the tacit form of the J programming language the solution looks like this:

>:@(}.@|.^:({:@]))i. 20 characters

so 2 >:@(}.@|.^:({:@]))i. 41 - returns 31

If you allow an answer for index 0 the solution shortens to:

}.@|.^:({:@])i. 15 characters

and 2 }.@|.^:({:@])i. 41 - returns 30

for more information on J -- Jsoftware.com

Reading the index 1 version right to left

i. creates a list of 0 to n-1 soldiers

({:@]) is a loop counter that initializes to the last number in the soldier list (n-1)

^: symbolizes the power conjunction that will apply a function a specified number of times (in this case n-1).

}.@|. is the function that is applied. The LHS arg shifts the soldier list 2 spaces and then the first soldier in the newly ordered line is dropped. After this has been done n-1 times the remaining number is the soldier number in index 0. For some reason this makes me think of a Monty Python sketch with suicidal Scots (but that would be the case with 0 skips).

>:@ then adds one to the number to convert it to index 1

But then we wouldn't be able to mock God in a unit test!

Well, you could use Supersede Instance Variable pattern for this legacy system.

Chris2009-07-30 02:05

In Javascript:

function SafeSpot(nrOfSoldiers, soldierSkip)
{
var a = new Array(nrOfSoldiers);

for (i=0; i<nrOfSoldiers; i++) a[i] = i+1;
while (a.length > 1)
{
if (a.length > soldierSkip)
{
a = a.slice(soldierSkip).concat(a.slice(0,soldierSkip-1));
}
else if (a.length == soldierSkip)
{
a = a.slice(0,soldierSkip-1);
}
else if (a.length > 1 && (soldierSkip % a.length == 0))
{
a = a.slice(0, a.length-1);
}
else
{
a = a.slice(soldierSkip % a.length).concat(a.slice(0,(soldierSkip % a.length) - 1));
}
}
return a[0];
}

xeno2009-07-30 02:21

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).

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

(deleted for the sake of brevity)

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

I think you're assuming some sort of mathematic trick that hadn't been invented in 1AD. This is the time before arabic numerals or algebra (and certainly before recursion), and division was still an acane artform.

That's why I went for a "grid in sand" algorith. There are some cleverer algorithms here, but I think that it more likely that he might have had a minute or so to scratch in the sand while the other soldiers were talking to God. If I was in his sandles I'd much rather do it like that than solve equations or execute recursive functions in my head.

Of course, you shouldn't mind me if you just want to find that equation. I just think it's unlikely Josephus might have done it that way.

Incidentally, whatever method you're using is periodically wrong from 6 soldiers and up. Captcah: nulla. A count-zero error perhaps?

BTM2009-07-30 02:27

I'd say it even should ba Abstract ;-)

BTM2009-07-30 02:28

foreach(soldier:soldiers){

soldier.kill();

}

God.getInstance().sortOut(soldiers);

Shouldn't God be static?

I'd say it even should ba Abstract ;-)

xeno2009-07-30 02:30

Oops. Jospehus was the 41st soldier, so the safe spot is #41.

That in itself is a hint as to a mathmatical solution. I just checked, and whenever there is prime number of soldiers, the last (prime) place is the safe spot. I imagine that there is some mathematical solution involving finding the largest co-prime, but that's over my head.

xeno2009-07-30 02:39

Now that I think about it a grid-in-sand solution is silly. If he was going to do that, he might as well have just modeled the problem directly with a line or ring of 41 pebbles.

Or maybe he was second to last and wacked the other guy first :-)

bobtherriault@mac.com2009-07-30 02:40

The original WTF graphic that described this problem so well could be the clue to how Josephus would solve this problem.

Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

This model would solve the problem and would seem to be within the technology of the times.

Cheers, bob

bobtherriault@mac.com2009-07-30 02:49

xeno,

I think your last prime solution fails for 3 soldiers when killing of every third soldier :) In this case I think #41 would be the 23rd to die. I'd still want to be #31

Cheers, bob

xeno2009-07-30 02:51

bobtherriault@mac.com:

The original WTF graphic that described this problem so well could be the clue to how Josephus would solve this problem.

Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

This model would solve the problem and would seem to be within the technology of the times.

Snap :-)

Or he might have chosen #41 out of mathematical superstition (a belief that prime numbers are lucky), or just hung back and joined the circle last.

KnoNoth2009-07-30 02:55

#include<stdio.h>

//Good luck, trying to understand this function code( I used almost every mistake here, what I have seen )
int whos_alive(int varaibles, int varaibels){
char variabels[varaibles];
int variables[3]={0,1,0};
for(variables[0]=0;variables[0]<varaibles;variables[0]++)variabels[variables[0]]=1;
for(variables[0]=0;1;variables[0]++)if(variables[0]>=varaibles) variables[0]=-1; else if(variabels[variables[0]]){if(variables[2]==varaibles-1)return variables[0]+1;if(variables[1]==varaibels){variabels[variables[0]]=0;variables[1]=1;variables[2]++;}else variables[1]++;}
}

int main(int argc, const char **argv){
printf("safe spot is %d( if you start counting positions from 1 not 0 )",whos_alive(atoi(argv[1]),atoi(argv[2])));
}

Thorsten M.2009-07-30 03:24

> Ha, now we have a way to stop people from
> posting "Frist!!1".

Cool idea, include a math exercise in each story, and additional to the captcha the solution of the exercise must be provided. This might not totally avoid "first11!1" posts, but we might get less of the very stupid ones :-)

tster2009-07-30 03:26

T-SQL (SQL Server 2008 although I bet 2005 would work too). I tried to avoid just writing "C style" code with variables and really use the database features:

CREATE PROCEDURE Josephus
-- Add the parameters for the stored procedure here
@numSoldiers int,
@numSkip int
AS
BEGIN
SET NOCOUNT ON

CREATE TABLE SoldierList(
[Soldier] int NOT NULL,
CONSTRAINT [IX_SoldierList] UNIQUE CLUSTERED
(
[Soldier] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
)

CREATE TABLE Lineup(
[LineupOrder] [int] IDENTITY(1,1) NOT NULL,
[Soldier] [int] NOT NULL
)

delete from Lineup
delete from SoldierList

-- first make the soldier list
declare @inserter as int
set @inserter = 1
while @inserter <= @numSoldiers
begin
insert into SoldierList(Soldier) values (@inserter)
set @inserter = @inserter + 1
end

insert into Lineup(Soldier) select Soldier from SoldierList
insert into Lineup(Soldier) select Soldier from SoldierList
insert into Lineup(Soldier) select Soldier from SoldierList

declare @axAt int
set @axAt = -1
while 1 < (select COUNT(*) from SoldierList)
begin

declare @minLineupId int
set @minLineupId = (select MIN(LineupOrder) from Lineup)

declare @toKillIndex int
set @toKillIndex = (@axAt + @numSkip + 1) % (select COUNT(*) from Lineup)

declare @toKillLineUp int
set @toKillLineUp = @minLineupId + @toKillIndex

declare @toKill int
set @toKill = (select Soldier from Lineup where LineupOrder = @toKillLineUp)

declare @numInstancesBeforeCurrent int
set @numInstancesBeforeCurrent = (select COUNT(*) from Lineup where Soldier = @toKill and LineupOrder <= @toKillLineUp)

delete from Lineup where Soldier = @toKill
delete from SoldierList where Soldier = @toKill

--line them back up
delete from Lineup
insert into Lineup(Soldier) select Soldier from SoldierList
insert into Lineup(Soldier) select Soldier from SoldierList
insert into Lineup(Soldier) select Soldier from SoldierList

--make the soldier before the one just killed pick up the axe
set @axAt = @axAt + @numSkip + 1
set @axAt = @axAt - @numInstancesBeforeCurrent

if @axAt < 0
begin
set @axAt = @axAt + (select COUNT(*) from SoldierList)
select @axAt as 'AxAt2'
end

set @axAt = @axAt % (select COUNT(*) from SoldierList)
end

select Soldier from SoldierList
drop table SoldierList
drop table Lineup
END
GO

tster2009-07-30 03:33

workmad3:

def joph(n):

return int(bin(n)[2:][1:] + bin(n)[2:][0], 2)

WTF?

Daniel Browne2009-07-30 03:51

I didnt have time to read all the comments so sorry if this is what has already been done...

I think your last prime solution fails for 3 soldiers when killing of every third soldier :) In this case I think #41 would be the 23rd to die. I'd still want to be #31

Hmm, you're right, and so was Wongo. When I correct it so it's a accurate representation of scratching in the sand I get this:

<?php
/**
Sandbox grid solution.
----------------------
This isn't the most efficient algorithm (a computer doesn't need multiple rows), you may
even be able to express this problem as a mathematical equation. However, a person can
execute this algorith by drawing a grid in the sand, as Josephus might have done, using the
rows to avoid losing your place (which would fatally alter the result).

The multiple rows help you keep your place. As you work your way along each row,
"killing soldiers" you strike out the rest of the column (downwards, from the current row).
When you run of the end of the row, go down to the next.
*/

$n = $argv[1];
$skip = $argv[2];
echo "The safe spot is #" . josephs_circle($n, $skip) . "\n";

while ($kills < $n)
{
if ($x == $n) // have run off the end of the row
{
$x = 0;
$y++;
$grid[$y] = $grid[$y -1]; // strike out downwards
}

if (! $grid[$y][$x])
{
$s--;
}

if ($s == 0)
{
$kills++; // now we're going to kill somebody, unless ...
if ($kills < $n) // ... we're the last man standing
{
$grid[$y][$x] = ':-('; // hit the soldier with the axe
$s = $skip;
}
}
$x++;
}
return $x;
}
?>

Which gets the same solution as you. So much for prime numbers!

Thomas2009-07-30 04:00

There are some Haskell solutions, but no oneliner yet:

josephus n s = head $ (!!(n-1)) $ iterate (\x -> let y = drop (s-1) x in filter (/= head y) y) $ concat $ repeat [1..n]

axe user2009-07-30 04:25

Last 2 man standing, one of them has the axe, why the hell would he kill himself?

reol2009-07-30 04:38

LOL!

FST7772009-07-30 05:17

bash + expr:

#!/bin/bash
total=9
count=2

function commence() {
ttotal=$1
if [[ $ttotal = 1 ]]; then
echo 0
else
ttemp1=`expr $ttotal - 1`
ttemp2=`commence $ttemp1`
ttemp3=`expr $ttemp2 + $count`
expr $ttemp3 % $total
fi
}

commence $total

ThiOz2009-07-30 06:02

I think this could be done quicker or with less code but i guess it's solid

Rather boring one, but simple, in php ;)
<?php
function joseph($ile, $jump = 3)
{
$tab = array();
for ($i=0; $i<$ile; $i++)
{
$tab[] = ($i+1);
}
$k = $i = 0;
while (count($tab)>1)
{
if ($i>=count($tab))
{
$i = ($i%count($tab));
}
if ((($k+1)%$jump)==0)
{
array_splice($tab, $i, 1);
$i--;
}
$k++;
$i++;
}
echo 'joseph('.$ile.', '.$jump.') = '.$tab[0].'<br />';
}
?>

Josephus2009-07-30 06:10

# -*- coding: utf-8 -*-
def josephus(n, s):
if n < 2:
raise ValueError("n must be greater than one")
if s < 1:
raise ValueError("s must be greater zero")
positions = range(n)
i = 0
while len(positions) > 1:
i = (i + s - 1) % len(positions)
del positions[i]
return positions[0] + 1

josephus(12,3)

Anonymous2009-07-30 06:12

This programming praxis was let down by its simplicity and the well known nature of the problem. I love the idea of coding challenges but you need to come up with original problems for them.

Sue D. Nymme2009-07-30 06:21

If you call the Frisbeetarian object with a float, it just hangs....

A solution in Clean which starts with a list of soldiers numbered 1 to n and recursively kills soldiers until only one is left:

josephus n s = kill [1..n] (s - 1)
where
kill [j] s = j
kill l s = kill (tl (rotate l s)) s

rotate l s = drop s l ++ take s l

Queex2009-07-30 06:38

Hacky solution in R. Remember that in R all indices begin with 1. Uncomment the cats to see how it works.

josephus <- function (men, kill)
{
list <- 1:men
while(length(list)>2){
tmp.kill <- kill %% men
list <- c(list[-(1:tmp.kill)],list[1:(tmp.kill-1)])
#cat(list)
#cat("\n")
}
tmp.live <- (kill %% 2) + 1
list[tmp.live]
}

John Stracke2009-07-30 07:44

Anonymous Coward:

John Stracke:

Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

Since God is both eternal and unchanging, He must be static const.

Addendum (2009-08-14 23:32): Updated: I have been studying theology and discovered that He is also claimed to be uncreated. Therefore he is static const, and the constructor is private.

lamcro2009-07-30 08:23

BASIC code
SAFE_SPOT is the return parameter.

I'm using a string of "1" characters, instead of an array, which are switched to "0" when dead.

0010 ENTER TOTAL_SOLDIERS,SKIP_COUNT,SAFE_SPOT
0020 LET SOLDIERS$=FILL(TOTAL_SOLDIERS,"1")
0030 LET POSITION=1,SOLDIERS_LEFT=TOTAL_SOLDIERS,COUNT=0
0040 WHILE SOLDIERS_LEFT>1
0050 IF SOLDIERS$(POSITION,1)="1" THEN GOSUB LIVE_OR_DIE ENDIF
0060 LET POSITION=POSITION+1
0070 IF POSITION>TOTAL_SOLDIERS THEN LET POSITION=1 ENDIF
0080 WEND
0090 LET SAFE_SPOT=POS("1"=SOLDIERS$)
0100 EXIT
0110 LIVE_OR_DIE:
0120 LET COUNT=COUNT+1
0130 IF COUNT=SKIP_COUNT THEN LET SOLDIERS$(POSITION,1)="0",COUNT=0,SOLDIERS_LEFT=SOLDIERS_LEFT-1 ENDIF
0140 RETURN

That depends. In this case, it looks like it's a static method on a class, but nothing ensures that God is singleton (as would be required by monotheistic beliefs like Christianity, Judaism and Islam).

If you're a follower of a polytheistic belief, such as Hinduism, you would require a getInstance() method for each god, and perhaps a factory class:

public class GodFactory
{
public static God getInstance( String name ) throws NoSuchGodException
{
// ...
}
}

Finally, if you're Terry Pratchett, you can instantiate God objects with the 'new' operator. If the God object is not used, it will automatically be garbage collected.

However, God objects are considered anti-patterns, and should therefore not be used.

KukkerMan2009-07-30 08:59

let rec josephus soldiers skips = if soldiers < 2 then 0 else (josephus (soldiers-1) skips + skips) mod soldiers;;

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

Very interesting, thanks for the link. Still not something Josephus could have hacked together in the few seconds when the troup gathers (unless the guy was both a soldier AND a polymath, rather a rare occurrence)... Also, he would have to have known the constant K, which I'm not sure was known at the time.

Again, I might be completely wrong in interpreting the problem, maybe that "Josephus quickly found a solution" is just Alex's usual literary embellishment... But darn, those series look eerily simplifiable.

Scarlet Manuka2009-07-30 09:03

I'm currently in the middle of an XML training course, and it's really tempting to try to work out a way of doing this in an XSLT. Unfortunately I have two important work-related tasks that I have to finish tonight and it's 9pm already, so I don't have time to play around with it (and really I shouldn't be on this site at all).

But if the course is going slowly tomorrow, I make no guarantees :D

Short dong silver2009-07-30 09:08

He there

I focused on ... getting it right ... fast. So I wrote down
a pretty stupid piece of JAVA code (plus some debug output
and profiling basics. I calculated that it would be O(n^2) ...
so who cares if there is an O(n) solution anyway ;-)

But well, that one was really neat. Anyway, here we go.

public class Circle
{
public static String toString(boolean people[])
{
String result = "";
for (int i=0; i < people.length; i++) {
result += (people[i]) ? "." : "A";
}
return result;
}

public static int findSpot(int numPeople, int numAxe)
{
boolean people[] = new boolean[numPeople];

int idx = 0;
int counter = 1;
int remaining = numPeople;

while (true)
{
// System.out.println("idx: " + Integer.toString(idx) +
// " / counter: " + Integer.toString(counter) +
// " / remaining: " + Integer.toString(remaining) +
// " field: " + toString(people));
if (! people[idx]) // guy is not dead
{
if (counter == numAxe)
{
people[idx] = true; // kill the guy
remaining--; // one less
counter = 1; // restart counting

if (remaining == 1) break; // all dead
} // if counter == numAxe
else
{
counter++;
}
} // if !people[idx]

idx++;
if (idx == numPeople) idx = 0;
} // while true

for (idx=0; idx < people.length; idx++)
{
if (!people[idx]) break;
}

public static void main(String args[])
{
long start = System.currentTimeMillis();
int spot = findSpot(new Integer(args[0]).intValue(),
new Integer(args[1]).intValue());
long stop = System.currentTimeMillis();

System.out.println("Spot is: " + new Integer(spot).toString() +
" / time is: " + new Long(stop-start).toString() + " ms");
}
}

J2009-07-30 09:09

This should be done with math but I haven't had my coffee yet. So I will use Mathematica. This seems to be a job for NestWhile, and we can use cyclicity and skip to the n'th person by RotateLeft'ing by n-1. So

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

Fascinating. For all those who won't follow the link, here is the gist of it: to calculate Fibo(n+1) given ONLY Fibo(n) (and not, as is usual, Fibo(n-1)), just do Fibo(n+1) = round(Fibo(n)* Phi). It works for all cases where n>1 (Phi is the golden number 1.618...).

There MUST be some similar solution to the Josephus problem...

EnterpriseSolutionsLTD2009-07-30 09:17

C# (4.0):

class Program
{
static void Main(string[] args)
{
Console.WriteLine(JosephusCircle.Solve());
}
}

public enum Vitality
{
Alive,
Dead
}

public class Soldier
{
public Soldier()
{
Vitality = Vitality.Alive;
}

public void Axe()
{
Vitality = Vitality.Dead;
}

public Vitality Vitality { get; private set; }
}

public static class JosephusCircle
{
public const int DefaultSoldierCount = 40;
public const int DefaultSkipAmount = 3;

public static int Solve(int soldierCount = DefaultSoldierCount, int skipAmount = DefaultSkipAmount)
{
var soldiers = new List<Soldier>();

do
{
soldiers.Add(new Soldier());
} while (soldiers.Count < soldierCount);

return Solve(soldiers, skipAmount);
}

public static int Solve(IEnumerable<Soldier> soldiers, int skipAmount = DefaultSkipAmount)
{
var soldierList = soldiers.ToList();

var leftToSkip = skipAmount;
var index = -1;

do
{
if (++index == soldierList.Count)
{
index = 0;
}

if (soldierList[index].Vitality == Vitality.Alive)
{
if (--leftToSkip == 0)
{
soldierList[index].Axe();

Oops. Jospehus was the 41st soldier, so the safe spot is #41.

That in itself is a hint as to a mathmatical solution. I just checked, and whenever there is prime number of soldiers, the last (prime) place is the safe spot. I imagine that there is some mathematical solution involving finding the largest co-prime, but that's over my head.

Actually, the safe spot with 41 soldiers is 31, not 41. And 11 (soldiers) = 7 (safe spot), 13 = 13 (you're right for this one), 17=11, 19=17, 23=8... It doesn't work. I've also tried things like: safe spot = (soldiers - previous prime) * 2, safe spot = soldiers mod previous prime... No luck there either.

Wongo2009-07-30 09:54

xeno:

Now that I think about it a grid-in-sand solution is silly. If he was going to do that, he might as well have just modeled the problem directly with a line or ring of 41 pebbles.

bobtherriault@mac.com:

Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

Yes, but:

1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

Vilx-2009-07-30 09:56

Since this is The Daily WTF, I figured that the solution is worth nothing unless it is a WTF itself. So - here's my attempt at doing it in Microsoft-specific C++. N = the number of men; K = which one to kill (3 means every 3rd). The return value is the number of position (starting at 1).

int josephus(int n , int k)
{
int $_,_$=n,__=2,$$=k;$_^=$_;$_:if(__>_$)goto _$;$_+=$$;$_%=__++;goto $_;_$:return ++$_;
}

int JIter(int n,int k){int v=0,i=2;for(;i<=n;v=(v+k)%i++);return v+1;}

Crunchy, but effective.

Secondly, here's that O(1) implementation, again in C:

#define K3 1.62227050288476731595695
int JLin(int n){return 3*n+1-floor(K3*pow((3.0/2.0),ceil(log((2.0*n+1.0)/K3)/log(3.0/2.0))));}

Please note that this is specific to k=3.

Here's an O(Log N) (to the base k) implementation, C, based on Strilanc's solution.

int JLog(int n,int k) {
if (k==1) return n-1;if (n<=1) return 0;
int t=JLog(n-ceil((double)n/(double)k),k);
t += (k-1) - (n+k-1)%k;t += floor((double)t / ((double)k-1.0));
return t%n;
}

Iterative O(Log(N)) proves difficult, because we have some maths on either side;
the recursive n-ceil(n/k) on input, and the clever stuff after. Anyone have any ideas?

The story is likely to be apocryphal, or at least the part about figuring out where
to stand being either attributed later or pure luck (anthropics!).

Also, bear in mind they were euthanising each other as a kindness. It would have been
fairly easy for him to "do the kindest thing", and accept the last position.

Damage2009-07-30 10:57

import java.util.ArrayList;

public class JosephusCirle {

private static Integer saveSpot(int soldiers, int skipCount) {

/* everyone dies in order, axe is passed from one to another --> last one survives
* or one enters the cave, and one leaves it (no monster found) */
if (skipCount == 0 || soldiers == 1) {
return new Integer(soldiers);
}

// I knew it, a Ghost Army !!!
if (soldiers <= 0) {
return null;
}

for (int i = 0; i < soldiers; i++) {
livingSoldiers.add(new Integer(i + 1));
if (i > 0) {
livingSoldiersBackwards.add(new Integer(soldiers - i + 1));
}
}

for (int i = 0; i < livingSoldiersBackwards.size(); i++) {
System.out.println("RW: " + livingSoldiersBackwards.get(i).intValue());
}
}

// circle axe
{
int axeCount = 0;

while (livingSoldiers.size() > 1) {
for (int i = 0; i < livingSoldiers.size(); i++) {
axeCount++;

if (axeCount == deathCount) {
livingSoldiers.remove(i);
axeCount = 0;

}
/**
* @param args
*/
public static void main(String[] args) {
Integer saveSpot = saveSpot(12, 2);
if (saveSpot == null) {
System.out.println("No Save spot found, only D E A T H!");
}
else {
System.out.println("Save spot: " + saveSpot);
}
}

}

by Damage

jane2009-07-30 11:33

Wongo:

Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

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).

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

Soldiers: 2, Last Spot: 2
Soldiers: 3, Last Spot: 2
Soldiers: 4, Last Spot: 1
Soldiers: 5, Last Spot: 4
Soldiers: 6, Last Spot: 1
Soldiers: 7, Last Spot: 4
Soldiers: 8, Last Spot: 7
Soldiers: 9, Last Spot: 1
Soldiers: 10, Last Spot: 4
Soldiers: 11, Last Spot: 7
Soldiers: 12, Last Spot: 10
Soldiers: 13, Last Spot: 13
Soldiers: 14, Last Spot: 2
Soldiers: 15, Last Spot: 5
Soldiers: 16, Last Spot: 8
Soldiers: 17, Last Spot: 11
Soldiers: 18, Last Spot: 14
Soldiers: 19, Last Spot: 17
Soldiers: 20, Last Spot: 20
Soldiers: 21, Last Spot: 2
Soldiers: 22, Last Spot: 5
Soldiers: 23, Last Spot: 8
Soldiers: 24, Last Spot: 11
Soldiers: 25, Last Spot: 14
Soldiers: 26, Last Spot: 17
Soldiers: 27, Last Spot: 20
Soldiers: 28, Last Spot: 23
Soldiers: 29, Last Spot: 26
Soldiers: 30, Last Spot: 29
Soldiers: 31, Last Spot: 1
Soldiers: 32, Last Spot: 4
Soldiers: 33, Last Spot: 7
Soldiers: 34, Last Spot: 10
Soldiers: 35, Last Spot: 13
Soldiers: 36, Last Spot: 16
Soldiers: 37, Last Spot: 19
Soldiers: 38, Last Spot: 22
Soldiers: 39, Last Spot: 25
Soldiers: 40, Last Spot: 28
Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

----------
Bear in mind that modern historians regard TJF's credibility as "questionable".

And we only have TJF's account of what actually happened.

As Wongo implies there - during the battle, anything could have happened - there was no way TFJ could know in advance there would be exactly 41 individuals present.

So, the possibilities are:

1: there is a *very rapid* shortcut, that no subsequent mathematician has been able to rediscover...

2: he has previously calculated and memorised the answer for multiple scenarios...

3: he works it out just once cycle ahead - "1, 2, argh, 1, 2, glurg" - and moves position to stay alive one move cycle - "I'll just check that Aaron is actually dead there..." walks over, stabs the corpse and stays standing in that new location...

4: he was just genuinely lucky that day...

5: he lied about what happened...

6: he lied about what happened...

< Kryten_mode >
Now I realise the last two suggestions are actually the same point, but I thought it was such a big one it was worth mentioning twice.
< Kryten_mode />

So, in other words, the original documentation is faulty, and everyone here is now coding a solution to something other than the real situation... :)

SteamBoat2009-07-30 13:30

The position that Josephus took was as the executioner.

MArk B.

halcyon12342009-07-30 13:52

Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT

Run pond.bat [NumberofDucks] [skips until kill]

It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

Repeat until the goose lays a golden egg in the pond, and the final position is reported.

========
pond.bat
========
@ECHO OFF
REM usage: pond.bat NumberOfDucks SkipsUntilGoose

SET DUCKS=%1
SET GOOSE=%2

IF %DUCKS%=="" GOTO USAGE
IF %GOOSE%=="" GOTO USAGE

REM *** Begin the spot-check loop ***
:START
REM start the golden goose at position 1
SET GOLDENGOOSE=1

:BREED

REM set the counter at 1
SET DUCKDUCK=1

REM reset the counter
SET COUNT=1

:HATCH

copy liveduck.bat duck%COUNT%.bat >nul

SET /A COUNT=%COUNT%+1

IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

GOTO :HATCH

:ENTERPOND

REM set the number of alive ducks
SET QUACKERS=%DUCKS%

REM set the first calling duck
SET QUACKER=1

:DUCKDUCK

CALL duck%QUACKER%.bat

REM Two ending conditions
IF %POND%==crap GOTO BADRESULT
IF %POND%==gold GOTO GOODRESULT
IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

REM Else the next duck should be called

SET /A QUACKER=%QUACKER%+1

REM loop back to the first duck if needed
IF %QUACKER% GTR %DUCKS% SET QUACKER=1

GOTO DUCKDUCK

:SOMETHINGAWFUL
echo exception all ducks died but the golden goose never crapped
GOTO END

:BADRESULT
REM oh no, the golden goose was killed! Let's start again, but move the
REM goose one higher

ECHO Golden Goose unsafe at position %GOLDENGOOSE%

SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

REM If we've exhausted positions, than this is unwinnable
IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

REM Recreate the ducks
GOTO BREED

:GOODRESULT
REM the golden goose was safe! What position was he in?
ECHO Golden Goose was safe at position %GOLDENGOOSE%
GOTO END

:ROASTDUCK
REM the golden goose was unsafe at any position
ECHO There is no safe spot for the goose. Would you like leg or thigh?
GOTO END

:KILL
del duck%COUNT%.bat
SET /A COUNT=%COUNT%+1
IF %COUNT% LEQ %DUCKS% GOTO :KILL

============
liveduck.bat
============
@ECHO OFF

REM DUCKDUCK = the current loop counter
REM GOLDENGOOSE = the position of the special goose
REM POND = Where to put the return variable
REM GOOSE = The max of the skip counter
REM QUACKER = The last goose to act
REM DUCKS = The number of ducks we started with

REM If the highest counter was hit, this duck dies
IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

REM Otherwise quack and move onto the next duck
SET POND=quack
REM Increase the count by one
SET /A DUCKDUCK=%DUCKDUCK%+1

GOTO END

:FUCKTHATDUCK

SET DUCKDUCK=1

REM This duck must die. If this duck is the last duck alive, the golden
REM goose is safe

IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

REM Kill self
SET POND=dead
copy deadduck.bat %0 >nul
GOTO :END

:GOLDDIGGER

REM The golden goose is about to die. See if it is the last duck alive,
REM it wins. Ohterwise, bad.

SET POND=crap

IF %QUACKERS% EQU 1 SET POND=gold

GOTO END

:END

============
deadduck.bat
============
@ECHO OFF
REM Dead ducks aren't much fun. They don't increase the duckduck counter,
REM since they don't count. Just ignore this duck and move on

SET POND=brains

:END

Schneau2009-07-30 13:55

Simple in Python with a list that gets shorter:

def josephus(n, k):
soldiers = range(0,n)
kill = -1
while n > 1:
kill = (kill + k) % n
soldiers.pop(kill)
n -= 1
kill -= 1
return soldiers[0] + 1

Schneau2009-07-30 13:57

halcyon1234:

Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT

Run pond.bat [NumberofDucks] [skips until kill]

It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

Repeat until the goose lays a golden egg in the pond, and the final position is reported.

========
pond.bat
========
@ECHO OFF
REM usage: pond.bat NumberOfDucks SkipsUntilGoose

SET DUCKS=%1
SET GOOSE=%2

IF %DUCKS%=="" GOTO USAGE
IF %GOOSE%=="" GOTO USAGE

REM *** Begin the spot-check loop ***
:START
REM start the golden goose at position 1
SET GOLDENGOOSE=1

:BREED

REM set the counter at 1
SET DUCKDUCK=1

REM reset the counter
SET COUNT=1

:HATCH

copy liveduck.bat duck%COUNT%.bat >nul

SET /A COUNT=%COUNT%+1

IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

GOTO :HATCH

:ENTERPOND

REM set the number of alive ducks
SET QUACKERS=%DUCKS%

REM set the first calling duck
SET QUACKER=1

:DUCKDUCK

CALL duck%QUACKER%.bat

REM Two ending conditions
IF %POND%==crap GOTO BADRESULT
IF %POND%==gold GOTO GOODRESULT
IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

REM Else the next duck should be called

SET /A QUACKER=%QUACKER%+1

REM loop back to the first duck if needed
IF %QUACKER% GTR %DUCKS% SET QUACKER=1

GOTO DUCKDUCK

:SOMETHINGAWFUL
echo exception all ducks died but the golden goose never crapped
GOTO END

:BADRESULT
REM oh no, the golden goose was killed! Let's start again, but move the
REM goose one higher

ECHO Golden Goose unsafe at position %GOLDENGOOSE%

SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

REM If we've exhausted positions, than this is unwinnable
IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

REM Recreate the ducks
GOTO BREED

:GOODRESULT
REM the golden goose was safe! What position was he in?
ECHO Golden Goose was safe at position %GOLDENGOOSE%
GOTO END

:ROASTDUCK
REM the golden goose was unsafe at any position
ECHO There is no safe spot for the goose. Would you like leg or thigh?
GOTO END

:KILL
del duck%COUNT%.bat
SET /A COUNT=%COUNT%+1
IF %COUNT% LEQ %DUCKS% GOTO :KILL

============
liveduck.bat
============
@ECHO OFF

REM DUCKDUCK = the current loop counter
REM GOLDENGOOSE = the position of the special goose
REM POND = Where to put the return variable
REM GOOSE = The max of the skip counter
REM QUACKER = The last goose to act
REM DUCKS = The number of ducks we started with

REM If the highest counter was hit, this duck dies
IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

REM Otherwise quack and move onto the next duck
SET POND=quack
REM Increase the count by one
SET /A DUCKDUCK=%DUCKDUCK%+1

GOTO END

:FUCKTHATDUCK

SET DUCKDUCK=1

REM This duck must die. If this duck is the last duck alive, the golden
REM goose is safe

IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

REM Kill self
SET POND=dead
copy deadduck.bat %0 >nul
GOTO :END

:GOLDDIGGER

REM The golden goose is about to die. See if it is the last duck alive,
REM it wins. Ohterwise, bad.

SET POND=crap

IF %QUACKERS% EQU 1 SET POND=gold

GOTO END

:END

============
deadduck.bat
============
@ECHO OFF
REM Dead ducks aren't much fun. They don't increase the duckduck counter,
REM since they don't count. Just ignore this duck and move on

SET POND=brains

:END

mad props

Maurits2009-07-30 14:24

Still Not Tim:

Wongo:

2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

2: he has previously calculated and memorised the answer for multiple scenarios...

2) then you keep fighting
2: memorizing 40 numbers is doable, especially if your life depends on it

The number 40 had great significance to Hebrews (it rained for 40 days and 40 nights, etc.) so I wouldn't be surprised if it was standard practice to give up if your fighting force dropped below 40 (assuming your cause was hopeless)

rfdb2009-07-30 14:50

Anon:

Ev:

Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

Aha! That's how he figured it out so quickly!

Using his trusty abacus, he put dirt on one side of each bead. With lightning speed, he rolled beads over one-by-one, and found the correct spot. Brute force wins!

mol11112009-07-30 14:53

He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).

Vilx-2009-07-30 14:59

mol1111:

He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).

It's just amazing now many of you dumbasses are willing to spend time working out and arguing over the workings of this puzzle. Are there really that many of you out of work?

Caveat: I work. I read TDWTF while my work is compiling. I make occasional comments unrelated to the topic.

kastein2009-07-30 17:07

Josephus:

Last

... best "first" post ever. Code Dependent, eat your heart out! :P

RaspenJho2009-07-30 17:19

private static int jcircle(int soldiers, int skip)
{
Queue<int> q = new Queue<int>(Enumerable.Range(0, soldiers).ToList());
while (q.Count > 1)
{
for (int i = 0; i < skip; i++)
q.Enqueue(q.Dequeue());
q.Dequeue();
}
return q.Dequeue() + 1;
}

Naturally, a Queue!

If you add a print statement inside the loop you can almost visualize them lining up to get the axe ;)

Soldiers: 2, Last Spot: 2
Soldiers: 3, Last Spot: 2
Soldiers: 4, Last Spot: 1
Soldiers: 5, Last Spot: 4
...
Soldiers: 39, Last Spot: 25
Soldiers: 40, Last Spot: 28
Soldiers: 41, Last Spot: 31

RaspenJho2009-07-30 17:42

Interesting pattern when you line up the plotted points of the "safe spot" in varying numbers of soldiers...

Here is my C# 3.5 solution. I kept looking for a nice easy few liner for it but ran out of time.

static int Josephus(int numSoldiers, int skipCount)
{
List<int> soldiers = Enumerable.Range(1, numSoldiers).ToList();
var deadMen = new List<int>();
var stillAlive = new List<int>();
int currentCount = 0;
while(true)
{
stillAlive = soldiers.Where(s => !deadMen.Contains(s)).ToList();
if(stillAlive.Count() == 1)
{
break;
}
foreach(var guy in stillAlive)
{
currentCount++;
if(currentCount == skipCount)
{
deadMen.Add(guy);
currentCount = 0;
}
}
}
return soldiers.SkipWhile(s => deadMen.Contains(s)).First();
}

Steve Vance2009-07-30 17:58

$ cat saveJos.c

#include <stArmyFunctions.h>

int main (int argc, const char **argv)
{
if(argc > 0)
{
DefectFromArmy(); //from stArmyFunctions
fprintf ("Josephus successfully defects from the
army and survives!");
}
else
fprintf ("Josephus has nothing to worry about as
they are killing nobody");
return 0;
}

Shadikka2009-07-30 18:02

Here's a XSLT solution - with graphics!
Needs XSLT 2.0 and uses EXSLT for the graphics (which aren't really necessary), so it probably will not run on your browser.
Here's a sample Saxon output.

Takes three parameters - the number of soldiers, the number of people to skip between two victims and the radius of the graphical circles in pixels.

Since the output is done with pixel positioning, your mileage might vary on different operating systems and browsers. And I know that the "copyright" text might be under the circles.

<body>
<h1>Josephus' Circle</h1>
<h2>
<xsl:value-of select="soldiers" /> soldiers, skipping
<xsl:value-of select="skip" /> at a time.
</h2>

<xsl:choose>
<xsl:when test="soldiers < 2 or skip < 1">
<p>More than one soldier and skip of more than zero, please.</p>
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="josephus-circle-init">
<xsl:with-param name="string" select="'aa'" />
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>

<p class="copy">
XSLT Josephus' Circle by Shadikka 2009<br />
Coded for The Daily WTF Programming Praxis just for the sake of it.
</p>
</body>
</html>
</xsl:template>

static int JosephusFunc(int numOfSoldiers, int numToSkip)
{
ArrayList soldierCircle = new ArrayList();

for (int i = 0; i < numOfSoldiers; i++)
{
//Instanitates the ArrayList with index number
soldierCircle.Add(i);
}

//Since we're zero indexed start with this
int soldierToDie = numToSkip-1;

while (soldierCircle.Count > 1)
{
//Since we'll be making multiple loops, we'll need to reset the death index
while (soldierToDie >= soldierCircle.Count)
soldierToDie -= soldierCircle.Count;

//Kills the soldier
soldierCircle.RemoveAt(soldierToDie);

//Subtracts one, since all soldiers move over a place
soldierToDie += numToSkip-1;
}

return (int) soldierCircle.ToArray()[0]+1;
}

Mathias Rav2009-07-30 19:03

I haven't read through all the comments, but a search for Brainfuck on each page of comments didn't return anything, so I decided to give it a go.

I haven't optimised the final code - I took Alex Mont's Python code, expanded the recursivity to a simple for-loop and proceeded to hack my way through in BF.

for (int i = 2; i <= n; ++i) {
result += k;
result %= i;
}

Finally, in Brainfuck: (result in memory cell 0, input in cells 1 and 2 (no. of men, kill-every)).

>++++++++++ 10 men
>+++ kill every 3 places
<[>>+>+<<<-]
>>>[<<<+>>>-]
<-[-
<[<<+>>>>+<<-]
>>[<<+>>-]
<<<[>>>>+>+<<<<<-]
>>>>>[<<<<<+>>>>>-]
<<<[>+>>+<<<-]
>>>[<<<+>>>-]
<<[>-<-]
<<<<[>>>>+<<<<-]
>>>>[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
[-]>[-]>>[-]
<[<<<<<<+>>>>>>-]
<<<
]
The following is for output and can be ignored if running in a debugger
<<[-]<
++++++++
++++++++
++++++++
++++++++
++++++++
++++++++
.

I couldn't find an atoi in Brainfuck, so I added the ordinal of ascii zero (48) and output, so it'll break if the result is >9. (for the reader's convenience, the sequence is 0123456789:;<=>?@ABC...)

Unknown Entity2009-07-30 19:57

The trick to staying alive isn't knowing the safe spot... it's being the man with the axe.

Still Not Tim2009-07-30 22:51

Unknown Entity:

The trick to staying alive isn't knowing the safe spot... it's being the man with the axe.

Addendum (2009-07-31 00:51): I should note. The program takes two arguments on the commandline - the first is the number of men, and the second is the number to skip each time. There's no checking on those, so if you give zero men, you'll get a divide by zero error (don't ask) and if you give zero skip size you'll get an infinite loop.

It prints out a zero-indexed solution.

Roberto M2009-07-31 02:33

A really random solution in Java.

import java.util.*;

public class Josephus {

public static void main(String[] args) {
System.out.println("The zero-based safe spot index is " + joephus(Integer.parseInt(args[0]), Integer.parseInt(args[1])));
}

public static int joephus(int numberOfSoldiers, int soldiersToSkip) {
// prepare data
Vector<String> soldiers = new Vector<String>(numberOfSoldiers);
soldiers.setSize(numberOfSoldiers);
Collections.fill(soldiers, "Soldier");
soldiers.set(0, "Joephus");
--soldiersToSkip;

// random loop
int position = 0;
String last = null;
do {
Vector<String> testset = (Vector<String>) soldiers.clone();
shuffle(testset);
position = testset.indexOf("Joephus");

// kill loop
int soldierToKill = 0;
while (testset.size() > 1) {
soldierToKill += soldiersToSkip;
while (soldierToKill >= testset.size()) {
soldierToKill -= testset.size();
}
testset.remove(soldierToKill);
}
last = testset.get(0);
}
while(!last.equals("Joephus"));

return position;
}

public static void shuffle(Vector<String> array) {
Random rng = new Random();
for (int n = array.size()-1; n > 0; n--) {
int k = rng.nextInt(n + 1);
String tmp = array.get(k);
array.set(k, array.get(n));
array.set(n, tmp);
}
}
}

HV2009-07-31 02:39

Haskell

spot l n = red [1..l] n
red l n = if (length l) /=1 then red (del l n) n else l !! 0
del l n = if (length l) >= n then drop n l ++ take (n-1) l else drop (length l) (del (l ++ l) n)

StinoFasto2009-07-31 03:44

C# implementation:

private int DoTheJosephusCircle(int numberOfSoldiers, int soldiersToSkip)
{
var theCircleOfDeath = new List<bool>();
for (int i = 0; i < numberOfSoldiers; i++ ) theCircleOfDeath.Add(false);

private void Shoot(IList<bool> theCircleOfDeath, int startIndex, int soldiersToSkip)
{
int counter = 0;
while (counter < soldiersToSkip)
{
if (!theCircleOfDeath[startIndex] && (++counter == soldiersToSkip))
{
theCircleOfDeath[startIndex] = true;
break;
}
startIndex = (startIndex >= theCircleOfDeath.Count - 1) ? 0 : ++startIndex;
}
if (theCircleOfDeath.Count(soldier => !soldier) == 1) return;
Shoot(theCircleOfDeath, startIndex, soldiersToSkip);
}

Shadikka2009-07-31 04:34

ponky:

piet

First input is the number of soldiers.
Second input is the number to skip.
Output is the (zero based) index of the survivor.

This is officially awesome. I thought of making a solution in Piet, but thought it'd be too tricky. It's good to be proven wrong, though.

gvainfo2009-07-31 04:44

Bah, the rules are dizzy! Count of three means that I start to count at 1 and number 3 gets killed. In some examples you kill number 2 because you start to count at zero. Don't forget that in those times they did not have arrays yet and people started to count at 1.
What I found particularly difficult was the "hop over the edge", alas what do you do when 10 are in the array and you need to count to 11?

#!/usr/bin/perl -w strict
my $group=$ARGV[0];
my $count=$ARGV[1];
print "$group people count to $count\n";
# Create an array
my @circle;
my $array_length;
for ($i = 1 ; $i < $group+1 ; $i++) {
$array_length=push (@circle,$i);
}
print "Starting circle: @circle\n";
my $victim=0;
while (@circle > 1) {
my $loop=0;
my $nextvictim=($victim)+$count-1;
while ($nextvictim >= @circle) {$nextvictim=$nextvictim-@circle;$loop++;}
$victim=$nextvictim;
print "Remove $victim ($circle[$victim]) from @circle ";
if ($loop > 0) {print" (looped $loop times)"};
print "\n";
splice(@circle,$victim,1);
}
print "Number @circle survives\n";

for 10/3 that gives me
./titus.pl 10 3
10 people count to 3
Starting circle: 1 2 3 4 5 6 7 8 9 10
Remove 2 (3) from 1 2 3 4 5 6 7 8 9 10
Remove 4 (6) from 1 2 4 5 6 7 8 9 10
Remove 6 (9) from 1 2 4 5 7 8 9 10
Remove 1 (2) from 1 2 4 5 7 8 10 (looped 1 times)
Remove 3 (7) from 1 4 5 7 8 10
Remove 0 (1) from 1 4 5 8 10 (looped 1 times)
Remove 2 (8) from 4 5 8 10
Remove 1 (5) from 4 5 10 (looped 1 times)
Remove 1 (10) from 4 10 (looped 1 times)
Number 4 survives

I really don't know if that's correct as I only checked manually for small numbers. I tested though what happens if you put high numbers (40 people kill every 1.000.000 person: Stand in position 36)

And now I will read the wikipedia article ;-)

Gerben2009-07-31 05:40

public static int Josephus(int number, int skip) {
return number == 1 ? 0 : (Josephus(number - 1, skip) + skip) % number;
}

Code Dependent2009-07-31 09:54

kastein:

Josephus:

Last

... best "first" post ever. Code Dependent, eat your heart out! :P

Dang!

Stéphane2009-07-31 10:53

If you want to be REALLY FAST (in your head), here's an algorithm

When you know a last spot for a given number if soldiers, Add 3 to the spot if you add one soldier. If your number is above the number of soldiers, just reduce it (ie: remove by the amount of people in the circle)

ie: For 20 soldiers, the spot is 20 (easy to remember)
Add 3, For 21 soldiers it should be 23, so you are over, substract 21 and you get 2 as the spot.
Add 3, For 22 soldiers the spot is 5
Add 3, For 23 soldiers the spot is 8
...
Add 3, For Soldiers: 30 the spot is 29
Add 3, For 31 soldiers it should be 32, so you are over, substract 31 and you get 1 as the spot.
...

Louis2009-07-31 13:46

Here's dc code implementing the 'obvious' algorithm (fill a stack with soldiers and delete them one by one:

dc -e '12 3 1-s$ddsls#[dS~1-d0<s]dssxs.[l#dsll{xs.]sr[LtS~1-d0<{]s{[ll1-dslL~St0=r]sz[lzx1-d0<}]s}[l$l}xs.L~s.l#1-ds#ll1-dsl0=r1<m]dsmxL~p'

and unobfuscated (well, as unobfuscated as dc can be):

12 # number of soldiers
3 # number to skip each round

1-s$
ddsls#

[
dS~
1-
d0<s
]dssxs. # prepare '~' to hold numbers from 1 to '#', our number of soldiers

[
l#
dsl # save '#' to 'l', the current length of '~'
l{x
s. # drop the top of the stack by storing it in the dummy register '.'
]sr # return [top of stack] soldiers from 't' to '~'
[
LtS~
1-
d0<{
]s{ # utility function for 'r'

[
ll1-dsl
L~St
0=r # if we're out of soldiers in '~', transfer them back.
]sz # transfers one soldier from '~' to 't'
[
lzx
1-
d0<}
]s} # skip [top of stack] soldiers

[
l$l}xs.
L~s.
l#1-ds#
ll1-dsl
0=r
1<m
]dsmx # main function
L~p

And Alex Mont's J function (except de-recursion-ized):

dc -e '12 3 sksm2sn0[lk+ln%ln1+dsnlm!<J]dsJx1+p'

I adjusted it to output one-based instead of 0-based with the 3rd- and 2nd-to-last letters, the '1+'. You can save two characters by deleting those.

causa2009-07-31 16:23

all_dead = [];

class soldier:
def __init__(self, previous,number,first):

self.previous_soldier = previous;
self.number = number;
if first == 0 :
first = self;

if number == 0 :
self.next_soldier = first;
first.previous_soldier = self;
else:
self.next_soldier = soldier(self, number -1, first);

def step(self, step, countdown):
if self.next_soldier == self:
print 'Suiciders, in order:', all_dead;
print 'I can haz LIFE!', self.number;
return;
if countdown == 0 :
self.previous_soldier.next_soldier = self.next_soldier;
self.next_soldier.previous_soldier = self.previous_soldier;
all_dead.append(self.number);
self.next_soldier.step(step, step);
else:
self.next_soldier.step(step, countdown - 1);

Well, here's my try. I'm late to join the party, I know. But its friday night, and I had to do something while getting drunk for the pub. ;) And I figured that making a program in python for the first time would be a good way to spend the time.

If someone feels like it, point out the bad stuff. Heh.

dbkk2009-07-31 16:44

> God.getInstance().sortOut(soldiers);

I disagree with using a singleton pattern here... after all, the story is set in Roman times.

God.get("Mars").sortOut(soldiers);

There, I corrected it for you.

quibus2009-07-31 16:46

Wongo:

xeno:

Now that I think about it a grid-in-sand solution is silly. If he was going to do that, he might as well have just modeled the problem directly with a line or ring of 41 pebbles.

bobtherriault@mac.com:

Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

Yes, but:

1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

When I was a kid, I could actually pick the last spot in circles to be singled out in these games. I cant remember how I did it, but it wasnt overly complicated. I think I counted the size of the circle up backwards from two, two numbers each step and then fixing at the end if it was an odd number of people.

mol11112009-07-31 18:13

Never; saw; so; many; semicolons; in; a; Python; program; :-)
But if it's your first Python program that's OK.

causa2009-07-31 18:37

mol1111:

Never; saw; so; many; semicolons; in; a; Python; program; :-)
But if it's your first Python program that's OK.

Haha, being tipsy prolly didnt help me much either. >.<

for($deathblow = 1; $soldiers[$deathblow] != end($soldiers); $deathblow++) {
if((($deathblow + $skip) % $skip) != 0) array_push($soldiers, $soldiers[$deathblow]);
}
echo "Stand in spot ".(end($soldiers) + 1)." if you want to live!";

}
?>

Wongo2009-07-31 22:12

Stéphane:

If you want to be REALLY FAST (in your head), here's an algorithm

When you know a last spot for a given number if soldiers, Add 3 to the spot if you add one soldier. If your number is above the number of soldiers, just reduce it (ie: remove by the amount of people in the circle)

ie: For 20 soldiers, the spot is 20 (easy to remember)
Add 3, For 21 soldiers it should be 23, so you are over, substract 21 and you get 2 as the spot.
Add 3, For 22 soldiers the spot is 5
Add 3, For 23 soldiers the spot is 8
...
Add 3, For Soldiers: 30 the spot is 29
Add 3, For 31 soldiers it should be 32, so you are over, substract 31 and you get 1 as the spot.
...

Ok, I think you nailed it... Takes a few seconds, doesn't require any knowledge other than adding and subtracting, it's a great solution! Kudos, Stéphane! You win! :)

Andrew2009-08-01 02:09

The goal of this is not to be clever, but to provide a solution in Perl that won't be recognized as being Perl. Here goes:

#!/usr/bin/perl
use MooseX::Declare;
use Moose::Autobox;

class Josephus {
has size => (isa => 'Int', is => 'ro', required => 1);
has stride => (isa => 'Int', is => 'ro', required => 1);
has position => (isa => 'Int', is => 'rw', default => -1);
has soldiers => (is => 'ro', isa => 'ArrayRef[Int]', lazy => 1,
default => sub { [ (0 .. shift->size - 1) ] }
);

method kill {
splice @{ $self->soldiers }, $self->position, 1, ();
# Killing that guy moved the cursor to the guy after him, but we want
# $self->move(1) to land on the guy after him, so move back one.
$self->move(-1);
}

Man,where is the Haskell love? Here's a quick hack.

praxis :: Int -> Int -> Int
praxis 1 k = 0
praxis n k = mod ((praxis (n-1) k)+k) n

coward:: Int-> Int -> IO ()
coward n k = do c <- return (show ((praxis n k)+1))
putStrLn ("With "++show n++" soldiers and "++show k++"soldiers to skip, stay at position "++c)

Addendum (2009-08-02 15:23): This is based on the previous Python solution.

Addendum (2009-08-02 15:24): by Alex Mont.

naren2009-08-01 03:32

javascript.

function life_spot(circle_size, skip_by) {
circle = new Array();

Basic model of computation: you have named random-access registers and an FSM. An (x++) node increments register x and moves to its single successor. An (x--) node first checks whether register x is 0: if so, it moves to the double-arrow successor; otherwise it decrements register x and moves to the single-arrow successor.

This machine takes input in n (number of soldiers) and k (advance) and gives output in r (zero-indexed). It is assumed that r, i, and t are all 0 before computation begins.

The first two HALT nodes are error conditions (respectively k=0 and n=0).

Addendum (2009-08-01 07:35): s/Minski/Minsky/
My apologies.

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.

1. It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

2. I don't think this is an indication of the need for a "more unique problem to solve." I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

Mithious2009-08-01 17:34

Several people were talking about how you could work this out in your head. Well I was thinking about this last night in bed and here is what I was able to come up with:

In your mind split the 41 people up into rows containing 9 soldiers each. This will give you 4 rows of 9 and one row at the end with 5.

One the first round of killing you will lose columns 3, 6 and 9. Two soldiers remain after the last killing (columns 4 and 5) so on the second run through columns 1 and 5 will be taken out. This leaves you with columns 2478 (remember this number!) and 18 soldiers still alive.

Again divide these soliders into 9 columns (which gives you exactly two rows). On the previous run we killed off column 5 last so we will lose columns 3, 6 and 9 again, followed by 4 and 8. This leaves columns 1257 (remember this number) and 8 soldiers still alive.

It is trivial at this stage to work out that the safe spot out of these 8 is position 7 (you may be able to do this visually in your mind, or if you have to, resort to using fingers. Remember the first to die is the 3rd one as we killed off the last guy in the previous round).

We know that the safe position is number 7, but this is from the final 8 soldiers. We need to move back up the grids and work out what the real position is. Thankfully this is easy. The number of surviving columns each time was 4, so see how many 4s you can get into 7, this tells you how many rows to skip, then the remainder is the index of the safe column (from the numbers you remembered).

So:

7 = 4 + 3
Down one row, 3rd safe column (from 1257) so column 5.

9 soldiers per row so safe position is (9 * 1) + 5 = 14

14 = 4 + 4 + 4 + 2
Down three rows, 2nd safe column (from 2478) so column 4
9 soldiers per row so safe position is (9 * 3) + 4 = 31

So there is your final answer, you need to be standing in position 31. And all you had to remember was two four digit numbers and who was first to die between stages.

pjt332009-08-01 17:53

Chris Judge:

I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

Copy-pasting code from Wikipedia is sad, but when you talk about "solving the problem" I find myself disagreeing with you about the point. Programming Praxis was launched as an opportunity "to sharpen your programming skills", not your problem-solving skills. More power to the people who transform it into a tail-recursive solution.

(It's also being used for language one-upmanship, but that's just the TDWTF crowd for you.)

god = God.getInstance();
god.sortOut(theDead);
god.createHeavens();
// etc.

Then you only have to update 1 line of code rather than all of them, like you would with a static class.

God.sortOut(theDead);
God.createHeavens();
// etc.

Brian Hartvigsen2009-08-02 13:23

I always remember being told that you would feel more connected with things if you named them, so I made sure each soldier had a name (I have both Jewish and Roman name lists now, number 31 is Josephus in both.)

import sys

names = []
with open("names2.lst") as f:
names = f.readlines()

sformat = "[#%%0%dd] %%s %%s" % len((str)(number_of_soldiers))
while root_soldier.next != root_soldier:
for i in range(soldiers_to_skip-1):
root_soldier = root_soldier.next

if deaths: print sformat % (root_soldier.index + 1, 'LIVES', root_soldier)
else:
print "With %d soldiers skipping %d, stand in position %d" % (number_of_soldiers, soldiers_to_skip, root_soldier.index + 1)

if __name__ == "__main__":
argc = len(sys.argv)
if argc == 3:
Josephus((int)(sys.argv[1]), (int)(sys.argv[2]))
elif argc == 2:
Josephus((int)(sys.argv[1]))
else:
Josephus()

Example output:

>>> Josephus(41, 3, True)
[#03] DIES Mordechai
[#06] DIES Liron
[#09] DIES Yosef
[#12] DIES Sheraga
[#15] DIES Eliezer
[#18] DIES Gideon
[#21] DIES Itamar
[#24] DIES Efraim
[#27] DIES Yaakov
[#30] DIES Yitzhak
[#33] DIES Avram
[#36] DIES Hevel
[#39] DIES Hayyim
[#01] DIES Lev
[#05] DIES Ron
[#10] DIES Rotem
[#14] DIES Elkan
[#19] DIES Yochanan
[#23] DIES Ofra
[#28] DIES Aryeh
[#32] DIES Yishai
[#37] DIES Moss
[#41] DIES Akiba
[#07] DIES Adi
[#13] DIES Nir
[#20] DIES Tovia
[#26] DIES Lior
[#34] DIES Eyal
[#40] DIES Amir
[#08] DIES Lavi
[#17] DIES Roi
[#29] DIES Avi
[#38] DIES Immanuel
[#11] DIES Gil
[#25] DIES Noach
[#02] DIES Solly
[#22] DIES Aharon
[#04] DIES Abraham
[#35] DIES Asher
[#16] DIES Itzhak
[#31] LIVES Josephus

>>> Josephus(41,3)
With 41 soldiers skipping 3, stand in position 31

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.

1. It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

2. I don't think this is an indication of the need for a "more unique problem to solve." I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

Part of being a good programmer is to know that you are not the best at everything and finding solutions done by someone better at it than you. And then implementing it in code.

The only thing wrong I see with digging the solution up on wikipedia is that there were no credits. I think you should always credit the guy or place you got the solution from.

Indrora2009-08-02 16:05

static int ohgod(int notme/*obfustications*/,int pleasenotme/*they make me happy*/){/*but only when and */if/*its*/(notme/*reading them*/==1){return(0)/*,*/;}else{/*things go bad,*/return/*ing*/((/*to*/ohgod(/*,*/notme--/*, oh,*/,pleasenotme)/*dear programmer,*/+pleasenotme)/*let anyone read this but please,*/%notme);}/*. :)*/}

My C# implementation, with the aformentioned recursion, but with as much /*obfustication*/ that if you read it right is a little poem to the reader.

and no, there are no unnecesary spaces within this.

I'm a little rusty on my lisp but I think the LISP version would be:

(defun j(n,s) (if(= n 1) 0 ( % ( + j( ( - n 1 ) , s) n )s)))

... Just my two cents

Kogle2009-08-02 20:16

Brute C# solution

static int Josephus(int soldiers, int index)
{
//status of the soldiers, true means dead.
bool[] soldierStatus = new bool[soldiers];
int last = 0, deadSoldiers = 0;
//iterate while more than one is alive
for (int i = 0, counter = 0; deadSoldiers + 1 < soldiers; i = (i + 1) % soldiers)
{
if (soldierStatus[i]) /* If this soldier is dead, skip loop */
continue;
if (counter == 2) /* If this soldier is the third, kill him */
{
soldierStatus[i] = true;
deadSoldiers++;
}
else /* If we don't kill him, he might be the last man standing */
last = i;
counter = (counter + 1) % 3;
}
return last + index;
}

greyfade2009-08-02 22:00

HypocriteWorld:

Ha, now we have a way to stop people from posting "Frist!!1".
Anyways, random solution here

josepheus total skip =
head $ head $ dropWhile notDone $ iterate go (cycle [1..total])
where go xs = let y:ys = drop (skip - 1) xs in filter (/=y) ys
notDone (x1:x2:_) = x1 /= x2

A shorter version:

josephus num sk = let gr = [1..num]
iter _ (x:[]) = [x]
iter n (x:xs) = if n == sk
then iter 1 xs
else iter (n+1) $ xs ++ [x]
in head iter 1 gr

Do I get a cookie? :)

death2009-08-03 05:47

Code Dependent:

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

Your socks and shirts are ful of God?

Paul Zaczkiewicz2009-08-03 08:58

Some perl:

#!/bin/perl

use strict;
use integer;

if (@ARGV < 2) {
print "Usage: $0 [number of soldiers] [soldiers to skip]\n";
return 1;
}

if ($ARGV[0] <2) {
print "You must have more than 1 soldier!\n";
return 1;
}

print circle($ARGV[0], $ARGV[1], 0), "\n";

sub circle
{
my ($size, $mod, $offset) = @_;
if ($size <= 2) {
return ($mod+$offset)%2+1;
}
my $kills = ($size+$offset)/$mod;
my $safe = circle($size-$kills, $mod, ($size+$offset)%$mod);
return $safe + ($safe+$offset-1)/($mod-1);
}

Manu2009-08-03 09:41

If someone hasn't figured it out, yet, there is a simple pattern to it, if you read the list at http://thedailywtf.com/Comments/Programming-Praxis-Josephus-Circle.aspx#280029

you can see that with each increasing number of soldiers, the safe spot rises once by the kill factor. if the number is bigger than the current amount of people, simply continue from the bottom, again.

quick C# Implementation:

public static uint Josephus(uint n, uint k)
{
uint safespot = 1;

def josephus(count=40, skip=3):
assert count > 1
soldiers = [i and str(i+1) or 'top' for i in range(count)]
alive, index = count, 0
while soldiers[1:]:
print(', '.join(soldiers))
i = (index + skip - 1) % len(soldiers)
soldiers.pop(i)
index = i
return soldiers[0]

Also, this will still need a bit of brainpower to do in the head, but better than any modulo or recursive calls out there.

Except that your while loop is a modulo operation. Other problems with your code include: failure to use k; performing the operation x % 1; and using the wrong base case. You should initialise safespot to k-1 and start numbers at 2.

It's not super exciting, but since it's my bread and butter I decided to post a .NET (C#) version of this puzzle using a simple generic collection.

using System.Collections.Generic;

public static class JosephusCircle
{
public static int FindSafeSpot(int numberOfSoldiers, int solidersToSkip)
{
Queue<int> theSoliders = new Queue<int>();
for (int i = 0; i < numberOfSoldiers; i++)
theSoliders.Enqueue(i);

while (theSoliders.Count > 1)
{
for (int i = 0; i < solidersToSkip; i++)
theSoliders.Enqueue(theSoliders.Dequeue());
theSoliders.Dequeue();
}

return theSoliders.Dequeue();
}
}

...and to be scientific, I created a test project to run a few scenarios. I came up with the numbers by drawing and working out the answers on paper first, which hurt my eyes after a while!

[TestMethod]
public void Scenarios()
{
int safeIndex = JosephusCircle.FindSafeSpot(12, 2);
Assert.AreEqual(9, safeIndex);

One line Python implementation (true one-liner, no semicolons - needs Python 2.4+):

[poplist.rotate(-(killcounter-1)) or poplist.popleft() for x in locals().__setitem__('soldiers', 12) or locals().__setitem__('killcounter', 3) or locals().__setitem__('poplist', __import__('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and __import__('sys').stdout.write("The only one left is %s\n" % locals().__getitem__('poplist')[0])

You can set the values of 'soldiers' and 'killcounter' appropriately for your situation ;)

Darryl Dixon2009-08-03 23:32

Darryl Dixon:

One line Python implementation (true one-liner, no semicolons - needs Python 2.4+):

[poplist.rotate(-(killcounter-1)) or poplist.popleft() for x in locals().__setitem__('soldiers', 12) or locals().__setitem__('killcounter', 3) or locals().__setitem__('poplist', __import__('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and __import__('sys').stdout.write("The only one left is %s\n" % locals().__getitem__('poplist')[0])

You can set the values of 'soldiers' and 'killcounter' appropriately for your situation ;)

Also, if you prefer to get some output while it runs:

[poplist.rotate(-(killcounter-1)) or __import__('sys').stdout.write("Just killed number: %d\n" % poplist.popleft()) for x in locals().__setitem__('soldiers', 12) or locals().__setitem__('killcounter', 3) or locals().__setitem__('poplist', __import__('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and __import__('sys').stdout.write("The only one left is %s\n" % locals().__getitem__('poplist')[0])

;)

Snakiej2009-08-04 09:10

namespace Josephus
{
internal class Program
{
private static void Main(string[] args)
{
int safeSpot = CalculateSafeSpot(40, 3);
}

private static int CalculateSafeSpot(int numberOfSoldiers, int step)
{
var isAliveBools = new bool[numberOfSoldiers];

for (int index = 0; index < isAliveBools.Length; index++)
{
isAliveBools[index] = true;
}

int currentStep = 1;

for (int x = 0; /* check in body */; /* increment in body */)
{
while (currentStep < step)
{
x++;

if (x >= numberOfSoldiers)
x -= numberOfSoldiers;

if (isAliveBools[x])
{
currentStep++;
}
}

currentStep = 0;
//x += step;

if (CountTrue(isAliveBools) == 1)
{
return x;
}

isAliveBools[x] = false;
}
}

private static int CountTrue(bool[] array)
{
int length = array.Length;
int noOfTrue = 0;

for (int x = 0; x < length; x++)
{
// evil code!
if (array[x] && ++noOfTrue > 1)
{
return noOfTrue;
}
}

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

Noone's pointed this out yet, but that formula is useless computationally, since the constant K can only be calculated by knowing the answers you're trying to generate in advance. See the paper linked to at that OEIS link, "Functional iteration and the Josephus problem" Beginning of section 5.

(WHY DOES THIS KEEP GETTING FLAGGED AS SPAM?? FFFFFFFFFFFFFUUUUUUUUUU LET ME POST DAMMIT)

zzo382009-08-04 16:03

I invented FlogScript for code-golfing, and I did code-golfing this one too:

(\,{ZoAu(;.,(}Fd~\;)

Addendum (2009-08-04 16:21): Please note that this is not an entire program, it is only a part that makes this calculation, and will not make any input/output by itself. To make it input/output, add this code to the beginning of the program:

"~

this allows multiple calculations, one on each line of input. For the program to do only one calculation (it starts after EOF is read from the input), use this instead:

#~

CJBV2009-08-04 19:52

Somebody already put one similar, but here it goes

Sorry not to provide any programming examples but the whole idea inspired the following! :-)

In order to decide who would not pay the tab, the drinkers sat at a circular table and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the the first tab and the counting resumed at one. The process continued until there was no one left. Paddy Joe, who quite agreed with the whole "we should all pay a tab" idea, figured out the perfect way to have a free nights drinking: be the last man standing.

Paul N2009-08-05 17:12

Mark Bohan:

Sorry not to provide any programming examples but the whole idea inspired the following! :-)

In order to decide who would not pay the tab, the drinkers sat at a circular table and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the the first tab and the counting resumed at one. The process continued until there was no one left. Paddy Joe, who quite agreed with the whole "we should all pay a tab" idea, figured out the perfect way to have a free nights drinking: be the last man standing.

If he is standing at the end of a free nights drinking, he isn't trying hard enough

mol11112009-08-06 17:37

If anybody interested, I created index for the entries.
Index. I cannot put it here directly, because it thinks it's a spam.

serious2009-08-09 06:48

using good ol' c and a ring of structs:

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

unsigned int josepus(unsigned int, unsigned int);

struct solider {
unsigned int id;
unsigned int dead;
struct solider* next;
};

while(1) {
if (sol->dead == 0) {
if (i == skip-1) {
sol->dead = 1;
deaths++;

if (deaths == soliders) {
printf("LAST MAN STANDING: %u\n", sol->id);
return sol->id;
}
}
i = (i+1) % skip;
}
sol = sol->next;
}
return 0;
}

Cedric Mamo2009-08-10 04:38

public static int josephus(int numOfSoldiers, int skip)
{
ArrayList<Integer> soldiers = new ArrayList<Integer>();
for (int i = 1; i <= numOfSoldiers; i++)
{
soldiers.add(i);
}

int location = 0;
while (soldiers.size() > 1)
{
location += 2;
if (location >= soldiers.size()) location -= soldiers.size();
if (location != soldiers.size() - 1) soldiers.remove(location);
else
{
soldiers.remove(location);
location = 0;
}
}
return soldiers.get(0);
}

my solution with java... brute forcing it :D

Cedric Mamo2009-08-10 04:42

public static int josephus(int numOfSoldiers, int skip)
{
ArrayList<Integer> soldiers = new ArrayList<Integer>();
for (int i = 1; i <= numOfSoldiers; i++) soldiers.add(i);

int location = 0;
while (soldiers.size() > 1)
{
location += (skip - 1);
if (location >= soldiers.size()) location -= soldiers.size();
if (location != soldiers.size() - 1) soldiers.remove(location);
else
{
soldiers.remove(location);
location = 0;
}
}
return soldiers.get(0);
}

updated version... the last one i posted always skipped counted 3 people regardless of the parameter xD silly mistake xD

Watson Ladd2009-08-10 11:14

Recursion is not a bitch to maintain. You just need to understand what the property of the recursive function is, and how the fixed-point operator works. Loops are a real bitch: Hoare logic is annoying because the hypothesis keeps changing at each line. Recursion is much more natural

Someone2009-08-10 14:38

The obligatory ABAP example:

DATA: numSoldiers TYPE I VALUE 12,
numSkip TYPE I VALUE 3,
soldiers TYPE TABLE OF BOOL WITH HEADER LINE,
soldier TYPE BOOL,
counter TYPE I,
liveCt TYPE I.

WHILE SY-TABIX < numSoldiers. "Build soldier set
APPEND 'X' TO soldiers.
ENDWHILE.

counter = 1.
liveCt = numSoldiers.
WHILE liveCt > 1. "While there is still more than one solider...
LOOP AT soldiers. "Loop through the soldiers
IF soldiers = ' '. "Skip the dead ones
CONTINUE.
ENDIF.

IF counter > numSkip. "Reset counter when it runs over
counter = 1.
ENDIF.

IF counter = numSkip AND liveCt > 1. "Your number is up
soldiers = ' '.
MODIFY soldiers.
liveCt = liveCt - 1.
ENDIF.

counter = counter + 1.

ENDLOOP.
ENDWHILE.

LOOP AT soldiers. "Find position of last soldier
IF soldiers = 'X'.
WRITE SY-TABIX.
ENDIF.
ENDLOOP.

Martin B.2009-08-11 07:19

Nice idea with the plot. I was wondering if there is some pattern - and there is a result:

The x-axis represents step size and y-axis represents number of soldiers int the circle. Both axis are plotted from 1 to 600. Each pixel represents one computed safe spot - plotted from 1 (black) to maximum (white). Since on each line there are results with the same number of soldiers I was able to set maximum for safe spot value to number of soldiers so that the pattern is easy to see. That also means it doesn't make sence to compare colors of pixels on different lines.

/**
* @return 0 if there is only one person left in ring, 1 otherwise.
*/
int KillFromRing(tSoldier ** io_ppSoldier)
{
if (((*io_ppSoldier)->next == *io_ppSoldier)
|| ((*io_ppSoldier)->prev == *io_ppSoldier))
{
printf("Cannot kill last from ring");
return 0;
}
else
{
tSoldier *pNext = (*io_ppSoldier)->next;
tSoldier *pPrev = (*io_ppSoldier)->prev;
tSoldier *pDelMe = *io_ppSoldier;
pNext->prev = pPrev;
pPrev->next = pNext;
*io_ppSoldier = pNext;
printf("x%dx ", pDelMe->pos);
free(pDelMe);
return 1;
}
}

void PassOnSword(tSoldier ** io_ppSoldier, int i_iNumToSkip)
{
int i = 0;
for (i = 0; i < i_iNumToSkip; i++)
{
printf("[%d] ", (*io_ppSoldier)->pos);
*io_ppSoldier = (*io_ppSoldier)->next;
}
}

int GetSaveSpot(int i_iNumOfSoldiers, int i_iNumToSkip)
{
tSoldier *pSoldier = CreateRing(i_iNumOfSoldiers);
do
{
PassOnSword(&pSoldier, i_iNumToSkip);
}
while (KillFromRing(&pSoldier));
return pSoldier->pos;
}

int main(void)
{
int iSaveSpot = GetSaveSpot(41, 2);
printf("\nSave Spot is %d.\n", iSaveSpot);
return 0;
}

Ricardo Custodio .NET Developer2009-08-18 11:42

public static void Main(string[] args)
{
//global vars
int soldiers = 12;
int soldiersToSkip = 3;

//Create List
List<bool> soldiersList = new List<bool>();

//Load List
for (int i = 0; i < soldiers; i++)
{
soldiersList.Add(true);
}

int countAlive;
int SoldierToKill = -1;
while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)
{
for (int i = 0; i < soldiersToSkip; i++)
{
SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);
}
//Kill Soldier
soldiersList[SoldierToKill] = false;
}

Console.WriteLine("Considered the zero as the first position of circle.");
Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));
Console.WriteLine(soldiersList.FindIndex(delegate(bool soldier) { return soldier; }));
Console.ReadLine();
}

private static int returnNextAlive(int index, List<bool> soldiersList)
{
int AliveIndex = 0;
for (int i = index; i < index + soldiersList.Count; i++)
{
if (i >= soldiersList.Count)
{
if (soldiersList[i - soldiersList.Count])
{
AliveIndex = i - soldiersList.Count;
break;
}
}
else
if (soldiersList[i])
{
AliveIndex = i;
break;
}
}
return AliveIndex;
}

Ricardo Custodio .NET Developer2009-08-18 11:56

//updated and parametrized
public static void Main(string[] args)
{
//Test
int soldiers = 40;
int soldiersToSkip = 3;
int SafePos = JosephusSafePos(soldiers, soldiersToSkip);

//Result
Console.WriteLine("Considered the zero as the first position of circle.");
Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));
Console.WriteLine(SafePos);
Console.ReadLine();
}

private static int JosephusSafePos(int soldiers, int soldiersToSkip)
{
//Create List
List<bool> soldiersList = new List<bool>();

//Load
for (int i = 0; i < soldiers; i++)
{
soldiersList.Add(true);
}

int countAlive;
int SoldierToKill = -1;
while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)
{
for (int i = 0; i < soldiersToSkip; i++)
{
SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);
}
//Kill Soldier
soldiersList[SoldierToKill] = false;
}

private static int returnNextAlive(int index, List<bool> soldiersList)
{
int AliveIndex = 0;
for (int i = index; i < index + soldiersList.Count; i++)
{
if (i >= soldiersList.Count)
{
if (soldiersList[i - soldiersList.Count])
{
AliveIndex = i - soldiersList.Count;
break;
}
}
else
if (soldiersList[i])
{
AliveIndex = i;
break;
}
}
return AliveIndex;
}

Wagner Amaral2010-04-17 02:20

I know, old topic... Yeah, I haven't read all the coment either...
Anyway, worth mentioning, this problem appears in D. Knuth's Concrete Mathematics book

oksupra.com 2010-06-19 03:10

Supra shoes are so popular all over the world. Whatever you take on Supra being in the Supra Skytop Shoes market. Now Supra Strapped Shoes also very popular attention. It is nice that they actually took the time to make Supra Skate Shoes that work well. Supra shoes is a brand that has been inspired, designed and marketed by passionate individuals. We have brought to you the fullest selection of Supra footwear at cheapest price.

Pyrexkidd2010-07-31 23:29

package JosephusCircle;
import java.util.Scanner;
public class JosephusCircle {

public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int soldiers;
int counting_index, numAlive;
boolean lastOneStanding = false;
System.out.print("Please Enter the Number of Soilders: ");
numAlive = soldiers = console.nextInt();
System.out.print("Please Enter How Many to skip: ");
counting_index = console.nextInt();
boolean unit[] = new boolean[soldiers];
for (int i = 0; i < unit.length; i++){
unit[i] = true;
}
int counter = 1;
while(!lastOneStanding){
for( int i = 0 ; i < unit.length; i++){
if (unit[i]){
counter++;
if (counter == counting_index){
counter = 1;
numAlive--;
unit[i] = false;
}
}
}
if (numAlive == 1){
lastOneStanding = true;
}
}
System.out.print(unit.length + "\n");
for (int i = 0; i < unit.length; i++){
System.out.print("Index: " + i + " Alive: " + unit[i] + "\n");
}
int i = 0;
for ( ; !unit[i]; i++ ){}
System.out.print("Best Location to Stand: " + (i + 1) + "\n");
}

}

D&G Ladies Leather Watches2010-09-27 23:16

unless you should concerning lAmid A smeach particular, certain equally discount Womens Watches though anyhow having the status of Jaquet Droz Watches Les Lunes, you surround come on the road on the road that the apposite stance. Cartier Watches Montres 21/Chronoscaph offers a deep get hold of of brin addition-name Audemars Piguet Watches Ladies Collection - Danaé at bizarre regards.we hope the so as topgreatest timbre of watch replicas friendly, in force type by the adjoining of side as well as the manufacturers to infer the most straight middling to repeat each one tyle, prepared of towering appraise equipment, afterward also species consideration. we retain crowd very inflexible quality stas well asards & material rudder to all suppliers.
our Jaquet Droz Watches Les Lunes and Womens Watches are in effect the awfully as the primary ones having the status of including the welcoming price, high quality materials and imposing workmanship. sell Breitling Watches Aeromarine Collection - Colt Automatic is also publicized.
our aim is to reserve you with first sort services as well as preeminent impressions watches, and issue your online shopping skill a wonderful one.9088232343002

40 value #soldiers
#soldiers value remain
0 value position
create soldiers #soldiers chars allot

: init ( --)
#soldiers 0 do 1 soldiers i + c! loop
-1 to position #soldiers to remain ;

: soldiers' ( -- addr) soldiers position + ;

: position++ ( --)
position 1+ #soldiers mod to position ;

: kill3rd ( --)
0 begin
position++ soldiers' c@ if 1+ then
dup 3 = until drop
0 soldiers' c! position 1+ . -1 +to remain ;

: killThem ( --) init begin remain 0> while kill3rd repeat
cr ." Last man standing at position " position 1+ . ;

Carrie2014-01-06 06:53

Anon:

Josephus' Circle, AKA Eeny, meeny, miny, moe. The solution is to argue about how many words are in the rhyme and whether the person selected at the end is "it" or "not it".

You mean you don't append 'this means you will not be it' to the end of the rhyme?

fun j(n,k,i) = (if i=1 then k-1 else k+j(n-1,k,i-1)) mod n;

fun J(n,k) = j(n,k,n);

#include <stdio.h>

#include <stdlib.h>

/* f(n,k)=(f(n-1,k)+k) mod n

f(1,k)=0 */

static int f (int n, int k)

{

if (n == 1)

return 0;

return (f (n-1, k) + k) % n;

}

int main (int argc, const char **argv)

{

int n, k;

if (argc != 3)

{

fprintf (stderr, "Usage: %s <N> <K>\n", argv[0]);

return -1;

}

n = atoi (argv[1]);

k = atoi (argv[2]);

fprintf (stdout, "With %d soldiers and killing every %d'th, the safe spot is p

osition %d\n",

n, k, f (n, k) + 1);

return 0;

}

$ gcc -g -O2 -W -Wall -Wextra jos.c -o jos

$ ./jos.exe 12 3

With 12 soldiers and killing every 3'th, the safe spot is position 10

$ ./jos.exe 40 3

With 40 soldiers and killing every 3'th, the safe spot is position 28

$

Anyways, random solution here

ps: TRWTF is the forum software erroring out because I forgot the /code tag.

Fat lotta good that'll do you in a cave full of suicidal men...

I couldn't think of a better name for the function.

If n=1 then clearly we are done, and J(1,k) = 0 for any k. Now consider the case of n>1. We have something like this:

Where the caret marks where the count starts. Now at the next step (assuming again k=3)

So now suppose that J(n-1,k) = x. That means that the surviving soldier is X positions after the caret in the second diagram. But the caret in the second diagram is 3 positions after the caret in the first diagram, so the surviving soldier is X+3 positions after the caret in the first diagram. Of course you have to take the mod of that by n to account for wrap around.

Thus our formula is (code in Python):

Note that because of the way the recursion is set up, at no point do you have to keep track of which positions of soldiers are dead already. And it is an O(n) algorithm.

This is sexy.

twostanding, upon which he said to the other guy, as they were surrounded by corpses, "Maybe surrender isn't so shameful after all?" Not sure if the algorithm for figuring out how to be one of the last two is significantly easier.<code>

<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)#<br/></cfoutput>

<cfset circle=listDeleteAt(circle, x)>

</cfloop>

<cfoutput>The last name standing was in position #circle#<br/></cfoutput>

</code>

def josephus(soldiers:Int, toSkip:Int):Int = {

josephus(soldiers, toSkip, 0)

}

def josephus(soldiers:Int, toSkip:Int, first:Int):Int = {

if(soldiers == 1) {

0

} else {

val position = josephus(soldiers - 1, toSkip, (first + toSkip) % (soldiers - 1));

if(position < first) {

position;

} else {

position + 1;

}

}

}

Beat me to it.

Virtually identical. In my solution, replace with

In that case, I'll find the P Spot.

private int Josephus(int soldiers, int everyOther)

{

List<int> alive = new List<int>();

for (int i = 1; i <= soldiers; i++)

alive.Add(i);

int ndx = 0;

while (alive.Count > 1)

alive.RemoveAt(ndx = (ndx + everyOther - 1) % alive.Count);

return alive[0];

}

He is safe as he is the only one in the game:

f(1,k) = 1

In general you solve the n'th case by reducing the problem by 1 and solving, adding k afterwards:

f(n,k) = f(n-1,k)+ k mod n+1

= f(n-2,k) + 2k mod n

= f(1,k) + (n-1)k mod n

= 1 + (n-1)k mod n

So all you need to do is:

public static int f(int n, int k)

{

return 1 + (((n-1) * k) % n);

}

template <unsigned int s, unsigned int k> struct safe {

static const unsigned int result = (safe<s - 1, k>::result + k) % s;

};

template <unsigned int k> struct safe<1, k> {

static const unsigned int result = 0;

};

unsigned int index = safe<12, 3>::result;

it came out looking exactly like the python implementation

thats 'mod n' ofc and not 'mod n+1' :)

Truly, there is nothing sexier than recursion. It's especially elegant for problems like this one.

Unfortunately, it's a bitch to maintain, and a memory hog for larger functions.

But then we wouldn't be able to mock God in a unit test!

similarly (ruby1.9):

j = lambda { |n,k| n == 1 ? 0 : (j.(n-1, k) + k) % n }

$a = array(); $b = 0;

for ($x = 0; $x < $argv[1]; $x++) { $a[] = $x + 1; }

while (sizeof($a) > 1) {

$c = ($b + $argv[2] - 1) % sizeof($a); $b = $c;

unset($a[$c]); $a = array_values($a);

}

print $a[0];

Sure I could have used a modulus, but I like the notion of representing the circle of soldiers literally.

#include <iostream>

#include <cstdlib>

using namespace std;

/* f(n,k)=(f(n-1,k)+k) mod n

f(1,k)=0

=>

a[n]=a[n-1]%n -> (...(((k%2 +k)%3 +k%4) +k%5... +k)%n

*/

int main (int argc, const char **argv)

{

int n, k;

if (argc != 3)

{

cerr << "Usage: "<< argv[0] << "<N> <K>\n";

return -1;

}

n = atoi (argv[1]);

k = atoi (argv[2]);

int r = 0;

for(int a=2; a<=n; a++)

r= (r+k)%a;

cout<< "With " <<n<<" soldiers and killing every "<< k <<"'th, the safe spot is position "<<r+1<<endl;

return 0;

}

Using the recursion:

yes... the God class is a singleton...

And also, if your grandparents are there, what the word ending in "ger" is. Talk about embarrassing.

def josephus(s,n)c=(0...s).to_a

;i=0;while c.size>1;c[i,1]=nil;i=i+n;i=i%c.size;end;return c[0];end;

or with line breaks instead of ;

def josephus(s,n)c=(0...s).to_a

i=0

while c.size>1

c[i,1]=nil

i=i+n

i=i%c.size

end

return c[0];

end

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).

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

Soldiers: 2, Last Spot: 2

Soldiers: 3, Last Spot: 2

Soldiers: 4, Last Spot: 1

Soldiers: 5, Last Spot: 4

Soldiers: 6, Last Spot: 1

Soldiers: 7, Last Spot: 4

Soldiers: 8, Last Spot: 7

Soldiers: 9, Last Spot: 1

Soldiers: 10, Last Spot: 4

Soldiers: 11, Last Spot: 7

Soldiers: 12, Last Spot: 10

Soldiers: 13, Last Spot: 13

Soldiers: 14, Last Spot: 2

Soldiers: 15, Last Spot: 5

Soldiers: 16, Last Spot: 8

Soldiers: 17, Last Spot: 11

Soldiers: 18, Last Spot: 14

Soldiers: 19, Last Spot: 17

Soldiers: 20, Last Spot: 20

Soldiers: 21, Last Spot: 2

Soldiers: 22, Last Spot: 5

Soldiers: 23, Last Spot: 8

Soldiers: 24, Last Spot: 11

Soldiers: 25, Last Spot: 14

Soldiers: 26, Last Spot: 17

Soldiers: 27, Last Spot: 20

Soldiers: 28, Last Spot: 23

Soldiers: 29, Last Spot: 26

Soldiers: 30, Last Spot: 29

Soldiers: 31, Last Spot: 1

Soldiers: 32, Last Spot: 4

Soldiers: 33, Last Spot: 7

Soldiers: 34, Last Spot: 10

Soldiers: 35, Last Spot: 13

Soldiers: 36, Last Spot: 16

Soldiers: 37, Last Spot: 19

Soldiers: 38, Last Spot: 22

Soldiers: 39, Last Spot: 25

Soldiers: 40, Last Spot: 28

Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

hero!

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

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.

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

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

1 + (n-1)k mod n

$p[$_-1]=$_ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

77 chars :-)

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;

int soldiersSkipped = 0;

while(numLeft > 1){

for( int x = 0; x < stillAlive.length; x++){

//let's go find the next alive person!

if(stillAlive[x] == true){

soldiersSkipped++;

}

if(soldiersSkipped == soldiersToSkip){

stillAlive[x] = false;

numLeft--;

soldiersSkipped = 0;

}

}

}

//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) );

}

}

}

}

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!

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)

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

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.

// 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;

dead++;

}

}

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];

}

If God were static how could He move in mysterious ways?

My own attempt at golfing this (subroutine):

40chars. 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)=@_;" <- 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)

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 :).

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

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

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

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.

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

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

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.

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

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

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

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

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

From where did you get that 860 iterations?

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

static int counter;

int Josephus(int n, int k)

counter++;

...

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()

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)

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

$k = 3;

@a=(1..40);

@a = grep { ++$x % $k } @a while $#a

print @a, "\n";

testedit?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.

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

int Safe(int Soldiers, int Skip)

{

if (Soldiers == 1)

return 0 ;

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

}

<?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 <akoimeexx@gmail.com>

*

* @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);

}

?>

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}

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.

It looks like this works:

n = number of soldiers

k = skip ahead interval (3 in this example)

i = "safe spot" index (1-based)

VBA's bad reputation drives me nuts...it's a good language for what it's intended uses are...so I can't help but be the ass who points out:

1)There's no need to manipulate values on a worksheet, you can use variables and it will run much faster. Each time code touches a worksheet object you pay a large price in speed. Better to do everything in memory and only kick the final result. You can also use Debug.Print to write to the immediate window. Do While Range(checker).Value > 1 will perform much better if replaced by a check against an internal variable, particularly for large loops.

2) You should use Columns("A:D").ClearContents instead of four separate calls; faster to both write and run. No need to clear columns if you keep data in memory. (arrays?)

3) It's a bad habbit to use code like: Range(somthing).Method, doing this will break if you accidentally activate a different worksheet while the code is running. When you reference "Range", you are implictly saying Application.ActiveWorksheet.Range, which users can break easily. It's much better to explictly declare which worksheet you want to operate on, using something like sheet1.Range(something) or Worksheets("ExternalSheetName").Range(something) (and bonus points if you use with blocks to reduce the number references to higher level objects)

4) No need to type cast strings when using & for string concatination. strMyString = "Some Text " & i runs faster than strMyString ="Some text" & Cstr(i)

5) using code to write worksheet functions is a bit much, there are times where that is useful, but you have the values in code so why not just add them in code too?

6) Dim cur As String: cur = "C" & CStr(j), not sure if this is considered bad form or not, but I'd wager dimming a var inside a loop slows things significantly. You're replacing the value of this variable each time, no need to redim it.

No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

Quote fail...that was in reference to the vba post on page 1...

Neither this nor 1+(n-1)k mod n works. Consider case 17 soldiers, the person to count 2 dies. So, n=17, k=2. The correct answer for those is index 2 (3 if indexed from 1).

for 1 + (n-1)k mod n: 1 + (17-1)2 mod 17 = 1 + 32 mod 17 = 16, which is incorrect.

for 1 + (n-1)(k-1) mod n: 1 + (17-1)(2-1) mod 17 = 1 + 16 mod 17 = 17, which is also incorrect.

I assumed you mean % as taking precedence over addition, in C fashion. However, even if you actually meant (1 + (n-1)k) mod n or (1 + (n-1)(k-1)) mod n for 17,2 the results are 16 and 0, respectively. Also incorrect.

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

We begin counting now at 5, which is skipped, so remove 1: {3,5}.

We begin count now at 3, which is skipped, so remove 5: {3}

function josephus3(count, seed)

{

var index = seed % 2 == 0 ? 1 : 2;

for (var i = 3; i <= count; i++)

{

index += seed;

while (index > i)

index -= i;

}

return index;

}

First we determine the starting index based on whether the seed is even or odd.

Next we follow the pattern of the solution above, which is, every time you go up from two you add the seed to the index and if the new index is greater than i (the number of men) you subtract i.

I expected this to work with a seed of 3, but I was surprised when I found out it works with any seed. It was easy for me to write an algorithm to represent the pattern, whereas I don't think I could figure out the other more elegant approaches.

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"...

Most of this function is just the definition for the ax() function.

Non-recursive form:

As mentioned at Wikipedia, a closed form exists for k = 2: j(n, 2) = 2 * (n - 2 ^ log2(n))

There is no closed form for k = 3; a good place to start is OEIS A054995.

unset($roulette[$arrayIndex]);

not unset($roulette[$value]);

Why must comments keep erroring out?

You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

Sexier:Cate Blanchett.Bitch to maintain:Well, possibly Ms Blanchett also, for all I know. Then again, why on earth would a correct recursive procedure be any more of a bitch to maintain than a correct iterative homologue?Memory hog:Tail recursion, my man. Tail recursion.Other than that, all these solutions appear to assume a boolean state for each soldier of dead/alive. Whatever happened to

death_not_found?My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc.

Sorry for wasting yout time :)

And a test session:

Edit: Use one-based index

Addendum (2009-07-29 14:13):(q is "number to skip", so kill every q+1 th) -- I originally had it the other way but then edited it.

"Hey everyone, I'll watch the door while you guys sort this out."

Nah, I knew you were on to something... Couldn't have found it myself anyway (or maybe with lots more time).

Granted, I haven't tested it for other values of k, or for weird edge cases, but I was able to precisely reproduce your list of safe spots by putting a Console.WriteLine() at the bottom of the loop body.

My perl approach:

78 chars :-)

No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

Iterative and runs in logarithmic time

Addendum (2009-07-29 14:08):NOTE: m is number to skip as listed in article -- so every m+1 is killed.

Cut is not absolutely necessary.

Great, I believed there is a very simple solution... Because of "VERY FAST" phrase. This solution has constant time, all others are n dependent.

struct position{

int id;

position * nextGuy;

position * lastGuy;

};

int safe(int people, int count){

position * circle = new position;

position * head = circle;

circle->id = 1;

for ( int c = 2; c < people+1; c++){

position * temp = new position;

temp->id = c;

temp->lastGuy = head;

head->nextGuy = temp;

head = temp;

}

circle->lastGuy = head;

head->nextGuy = circle;

while( circle->lastGuy != circle->nextGuy ){

for(int c = 0;c < count; c++ ){

circle = circle->nextGuy;

}

head=circle;

circle=circle->nextGuy;

head->lastGuy->nextGuy = head->nextGuy;

head->nextGuy->lastGuy = head->lastGuy;

delete head;

}

int result = circle->id;

delete circle;

return result;

}

Give me

nsoldiers and an axe.perl -e"@_=(1..$ARGV[0]);++$c%$ARGV[1]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3

Addendum (2009-07-29 13:24):Shaved off three characters by using "shift" instead of $ARGV[0].

80 characters for the whole thing; 66 between the quotes.

>perl -e"@_=(1..shift);++$c%$ARGV[0]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3

28

http://blogs.msdn.com/matthew_van_eerde/archive/2009/07/29/bad-perl-josephus-problem.aspx

Addendum (2009-07-29 14:00):78/64 dropping the parentheses.

>perl -e"@_=(1..shift);++$c%$ARGV[0]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3

28

Addendum (2009-07-29 14:09):Actually dropping the parentheses.

>perl -e"@_=1..shift;++$c%$ARGV[0]?$i++:splice@_,$i%=@_,1while$#_;print@_" 40 3

28

In LoopSurvay, please change

pos = (pos + k) % n;

to

pos = (pos + k) % (i+1);

{

List<string> soldiers = new List<string>(soldiersCount);

for (int j = 0; j < soldiersCount; j++) soldiers.Add((j+1).ToString());

int i = soldiersToSkip - 1;

do

{

i = GetStep(i, soldiers.Count);

soldiers.RemoveAt(i);

if (i + soldiersToSkip > soldiers.Count) i = i - soldiers.Count;

i = i + soldiersToSkip - 1;

} while (soldiers.Count>1);

return soldiers[0];

}

private int GetStep(int i, int count)

{

if (i < count) return i;

else i = i - count;

return GetStep(i, count);

}

@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 survivor is at index %survivor%

exit /b

:josephus

set soldiers=%1

set /a soldiersnext="soldiers-1"

set count=%2

if %soldiers% neq 1 call :josephus %soldiersnext% %count%

set soldiers=%1

set /a survivor="(count+survivor)%%soldiers"

exit /b

There's a formula in the Online Encyclopaedia of Integer Sequences:

http://www.research.att.com/~njas/sequences/A054995

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

I thought there needed to be three pointers to the same object.

Thank you, CLR.

If I'm going to have a Judeo circle of mass [suicide|assisted suicide], be the one who announces the skip number AFTER the circle is formed.

push into an array all the loosers

with a for loop that counts 3

and inside the for put an if for checking the actual array

if is in the array dont push it and continue checking the array of the standing soldiers

for this u need 2 arrays one for loop and put it into a function and done

my inglish is bad i know

:)

k is the skip, count is k+1. You count to three and thus skip over two guys. 1 2

34 567 89etc. If your count is one, your k is 0 in which case J(5,0) yields 5. But our count is 2 and the k is 1 to skip every other guy.Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

Anyways, here goes my python implementation:

Just for the fun of it: A Haskell version featuring infinite recursion.

Note: m is the "number to skip" as in the spec, so you kill every m+1 th

Addendum (2009-07-29 17:09):This is intended to model the actual chopping process, not to be efficient.

but this seems to work

-- josephus try

joHelper xs = if null (drop 2 xs)

then drop 1 xs

else joHelper ((drop 3 xs) ++ (take 2 xs))

josephus i = head (joHelper [1..i])

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

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

#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[1]);

if(argc>2) step=atoi(argv[2]);

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

That's easy to make iterative.

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.

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.

Code which gives...

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

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

ikegami@adaelis.com

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):

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

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.

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

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

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

Awesome :).

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 ?

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)

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

But I have to confess it's not totally straight forward ;)

{

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()

{

while (dead < (_Soldiers -1))

{

for (int i = 0; i < _Soldiers; i++)

{

if (jews[i].alive)

{

if (counter == _Skip)

{

jews[i].alive = false;

counter = 1;

dead++;

}

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

{

DeathLinkage dl = new DeathLinkage(_Soldiers, _Skip);

return dl.killEachOther().ToString();

}

}

}

}

public class Person

{

public Person()

{

alive = true;

}

public bool alive { get; set; }

}

class Program

{

static void Main(string[] args)

{

DeathLinkage dl = new DeathLinkage(12, 3);

System.Console.WriteLine(dl.circleOfDeath());

}

}

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

//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;

}

}

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[0];

Dispose(Alive);

AliveList.Delete(0);

end;

FreeAndNil(AliveList);

end;

end.

To me, listening to static is indeed mysterious!

public static int Lives(int nSize, int nSkip)

{

int n = 0;

for (int i = 2; i <= nSize; i++)

n = (n + nSkip) % i;

return n;

}

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)

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

Okay... first some ruby code (boring)

And here C with double linked list awesomeness:

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.

I have to say that I agree. Now for the next problem, code up the animations.

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;

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

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

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

All these comments, and not one pointing out the irony of using Python to show... erm...

the Romans didn't do for Titus.

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+(z*c))%%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.

Monotheist, ey?

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.

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

Help?

BTW used some syntax liberties for areas underdefined around arrays

HOW DUZ I JosephusCircle YR soldiers AN YR skip

I HAS A soldier

soldier r 1

I HAS A dead

dead r 0

I HAS A deadsoldiers

deadsoldiers r DIFF OF soldiers AN 1

I HAS A circle

IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers

soldier IN MAH circle r WIN

IM OUTTA YR LOOP

I HAS A skipnum

skipnum r 1

soldier r 1

IM IN YR KILLLOOP UPPIN YR soldier WILE DIFFRINT dead AN BIGGR OF dead AN deadsoldiers

BOTH SAEM soldier IN MAH circle AN WIN, O RLY?

YA RLY

BOTH SAEM skipnum AN skip, O RLY?

YA RLY

soldier IN MAH circle r FAIL

dead r SUM OF 1 AN dead

skipnum r 1

NO WAI, skipnum r SUM OF skipnum AN 1

OIC

OIC

BOTH SAEM soldier AN soldiers, O RLY?

YA RLY, soldier r 0

OIC

IM OUTTA YR KILLLOOP

BOTH SAEM dead AN deadsoldiers, O RLY?

YA RLY

IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers

BOTH SAEM soldier IN MAH circle AN WIN, O RLY?

YA RLY, safespot r soldier

OIC

IM OUTTA YR LOOP

NO WAI, safespot r 0

OIC

FOUND YR safespot

IF U SAY SO

KTHXBYE

I have posted code in Scheme which yielded

(josephus 32767 2) [of 32767 people, skip 2 and then kill the next person] in 27 iterations and (josephus (largest-fixnum) 2) in 98 iterations. [largest-fixnum is 144115188075855871]

Even

(josephus (expt (largest-fixnum) 100) 2)

returns immediately.

The ceiling function in Scheme works on rational numbers as well as floats, so it returns exact answers.

I also made some Scheme code that "models" the situation using circular lists or message-passing, which probably runs slow as !@#$$

My arrogance and I stand corrected.

public static int lastManStanding(int soldiers, int skip) {

if (soldiers == 1)

return 0;

return (lastManStanding(soldiers - 1, skip) + skip) % soldiers;

}

public static void main(String[] args) {

System.out.println(lastManStanding(12, 3));

}

}

2 <= num_soldiers <= 100

and

1 <= step_size <= num_soldiers

Results are plotted as intensity values from 0 (black) to 100 (white). I was surprised how random they look.

Nice.

I can see two ways to save another character:

or

but I can't see a way to combine both tricks.

Addendum (2009-07-29 19:13):Two more characters can be saved if the calling convention is reversed:

called with e.g. 3 40 rather than 40 3.

def circle(N, skip):

p = 0

solders = range(0, N)

while len(solders) > 1:

p = (p + skip - 1) % len(solders)

solders.pop(p)

return solders[0] + 1

Just wanted to say I'm enjoying these little problems. Sure you can find solutions for them in minutes but your only cheating yourself if you do!

"

Okay now everyone, please stand in a circle.

Now take a number.

Here is a stack of papers, every third a memo firing the recipient.

Take the top one and pass the stack.

No cheating.

By fired, we mean leave NOW.

I'll be standing over here off to the side by the doughnuts.

"

When it is down to one person:

"

I see it is finished. What is your number? (person: "42") Oh, by the way, you are fired too.

"

ZX Spectrum BASIC version.Screenshot for finished program (soldiers=10,

skip=2):

TAP file for emulator.

Addendum (2009-07-29 19:36):If you want to start counting including the first soldier (as in article's picture) change the line 220 to LET i=0 .

First input is the number of soldiers.

Second input is the number to skip.

Output is the (zero based) index of the survivor.

No, no, no. For Scrödinger's approach to work you need quantum. Doesn't work without one, everyone knows that.

USAGE = <scriptname> <number in circle>

Error handling non-existant.

#!/bin/sh

NUM=$1;

echo "Starting Number = " $NUM

for (( i = $NUM ; i != 0; i-- ))

do

ARRAY="a $ARRAY"

done

echo $ARRAY

#Killing time

INCREMENTOR=0

ALLDEAD=NUP

while [ $ALLDEAD != YUP ]

do

ARRAY2=""

for ELEMENT in $ARRAY

do

if [ $ELEMENT = a ]

then

INCREMENTOR=`expr $INCREMENTOR + 1`

#echo "Incrementor is $INCREMENTOR"

fi

if [ $INCREMENTOR -eq 3 ]

then

INCREMENTOR=0

ARRAY2="$ARRAY2 d "

else

ARRAY2="$ARRAY2 $ELEMENT"

fi

#echo $ARRAY2

done

ARRAY=$ARRAY2

echo $ARRAY

STILLALIVE=0

for ELEMENT in $ARRAY

do

if [ $ELEMENT = a ]

then

STILLALIVE=`expr $STILLALIVE + 1`

fi

done

if [ $STILLALIVE -eq 1 ]

then

ALLDEAD=YUP

fi

echo "still alive = $STILLALIVE"

done

LUCKYNUM=1

for ELEMENT in $ARRAY

do

if [ $ELEMENT = d ]

then

LUCKYNUM=`expr $LUCKYNUM + 1`

else

echo "Survivor is number $LUCKYNUM"

fi

done

{

if(size <= 1)

return 1; // You have no reason to worry if its just you

// Allocate array of size @size

bool *point = new bool[size];

int axed = 0; // People axed

int seq = 0; // Current skip sequence

int pos = 0; // Current position in circle

// Loop while there is more than 1 person alive

while(axed < size - 1)

{

// if its reached the sequence and that person is still alive...

if(seq == (skip - 1) && point[pos])

{

// Axe the person

point[pos] = false;

axed++;

seq = 0;

}

else

if(point[pos])

seq++; // Else increase the sequence

pos++; // Move to next position

if(pos == size)

pos = 0; // Reset to beginning if reached the end

}

// return the single living position

for(int i = 0; i < size; i++)

if(point[i])

return i;

return -1;

}

Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

Sample output:

And the code...

Here is an algorithm which runs in O(lg(N)*S) time, assuming arithmetic operations are constant time.

It achieves the massive speed up by performing an entire trip (and a bit more) around the circle in each recursion. I haven't figured out any way to make it non-exponential in S's representation yet.

He's a singleton instance. That way, you can still pass him into any CargoCultFollowing(IGod g) function using the IGod interface.

What are you smoking?

Which, instead of killing the guys, pushes the guys to die in the proper order from Josepheus back and up till the first guy dies. Then all we need to do to get the index of Josepheus (Mr. Zero)...

I have no idea why this is coming out double-spaced. Anyway, Josephus was the third man, like Orson Welles.

public class Josephus

{

public static void main(String[] args)

{

// The example of 12 soldiers in a circle is won by spot 10 (index 9).

HashMap<Integer, Boolean> livingSoldiers = new HashMap<Integer, Boolean>();

int numSoldiers = 0;

int numToSkip = 0;

int skipped = 0;

if (args.length != 2)

{

System.out.println("Usage: java Josephus [soldiers] [to skip]");

System.exit(1);

}

try

{

numSoldiers = Integer.parseInt(args[0]);

numToSkip = Integer.parseInt(args[1]);

}

catch (NumberFormatException nfe)

{

System.out.println("Usage: java Josephus [soldiers] [to skip]");

}

int[] soldiers = new int[numSoldiers];

for (int i = 0; i < numSoldiers; i++)

{

soldiers[i] = 1; // Alive.

livingSoldiers.put(i, true);

}

while (livingSoldiers.size() > 1)

{

for (int i = 0; i < numSoldiers; i++)

{

if (soldiers[i] != 0 && skipped == numToSkip)

{

soldiers[i] = 0; // Dead.

livingSoldiers.remove(i);

skipped = 0;

}

else if (soldiers[i] == 1)

{

skipped++;

}

}

}

System.out.println("FTW choose index " + livingSoldiers.keySet().iterator().next() + " in a ZERO based array!");

}

}

At least it works.

My very bad F# looping version did that in 42 ms, (25 iterations) if I remove the prints during the loop. Just under a second with them. Not a very long wait either way. Raising the skip makes it much worse though, then the memory reallocations start to hurt.

so it has been a few years since I did any code on the C64.

but an answer in 6502 assembler is:

SRC:

*=$0800

jmp START

NUM_PEOPLE

.byte 41

NUM_JUMP

.byte 3

NUM_ALIVE

.byte 00

TEMP

.byte 00

START

LDA NUM_PEOPLE

STA NUM_ALIVE

LDA #01

LDX #00

CLEAR

STA $0700,x

INX

CPX NUM_PEOPLE

BNE CLEAR

LDA #00

LDY #00

TOP

LDX #$ff

KILL_LOOP

INX

CPX NUM_PEOPLE

BEQ TOP

LDA $0700,x

CMP #00

BEQ KILL_LOOP

INC TEMP

LDY TEMP

CPY NUM_JUMP

BNE KILL_LOOP

LDA #00

STA $0700,x

STA TEMP

DEC NUM_ALIVE

LDA NUM_ALIVE

CMP #01

BNE KILL_LOOP

BRK

OBJECT CODE:

* = $0800

0800 JMP START 4C 07 08

0803 NUM_PE

0803 .BYTE $29 29

0804 NUM_JU

0804 .BYTE $03 03

0805 NUM_AL

0805 .BYTE $00 00

0806 TEMP

0806 .BYTE $00 00

0807 START

0807 LDA NUM_PE AD 03 08

080A STA NUM_AL 8D 05 08

080D LDA #$01 A9 01

080F LDX #$00 A2 00

0811 CLEAR

0811 STA $0700,X 9D 00 07

0814 INX E8

0815 CPX NUM_PE EC 03 08

0818 BNE CLEAR D0 F7

081A LDA #$00 A9 00

081C LDY #$00 A0 00

081E TOP

081E LDX #$FF A2 FF

0820 KILL_L

0820 INX E8

0821 CPX NUM_PE EC 03 08

0824 BEQ TOP F0 F8

0826 LDA $0700,X BD 00 07

0829 CMP #$00 C9 00

082B BEQ KILL_L F0 F3

082D INC TEMP EE 06 08

0830 LDY TEMP AC 06 08

0833 CPY NUM_JU CC 04 08

0836 BNE KILL_L D0 E8

0838 LDA #$00 A9 00

083A STA $0700,X 9D 00 07

083D STA TEMP 8D 06 08

0840 DEC NUM_AL CE 05 08

0843 LDA NUM_AL AD 05 08

0846 CMP #$01 C9 01

0848 BNE KILL_L D0 D6

084A BRK 00

HEX:

4C 07 08 29 03 00 00 AD

03 08 8D 05 08 A9 01 A2

00 9D 00 07 E8 EC 03 08

D0 F7 A9 00 A0 00 A2 FF

E8 EC 03 08 F0 F8 BD 00

07 C9 00 F0 F3 EE 06 08

AC 06 08 CC 04 08 D0 E8

A9 00 9D 00 07 8D 06 08

CE 05 08 AD 05 08 C9 01

D0 D6 00

I have not written clean input / output code.

but the basic idea is there and the code will run and give correct answer.

Not really how MPI is supposed to be used, but it works. At least for smaller values, falls apart with larger.

>:@(}.@|.^:({:@]))i. 20 characters

so 2 >:@(}.@|.^:({:@]))i. 41 - returns 31

If you allow an answer for index 0 the solution shortens to:

}.@|.^:({:@])i. 15 characters

and 2 }.@|.^:({:@])i. 41 - returns 30

for more information on J -- Jsoftware.com

Reading the index 1 version right to left

i. creates a list of 0 to n-1 soldiers

({:@]) is a loop counter that initializes to the last number in the soldier list (n-1)

^: symbolizes the power conjunction that will apply a function a specified number of times (in this case n-1).

}.@|. is the function that is applied. The LHS arg shifts the soldier list 2 spaces and then the first soldier in the newly ordered line is dropped. After this has been done n-1 times the remaining number is the soldier number in index 0. For some reason this makes me think of a Monty Python sketch with suicidal Scots (but that would be the case with 0 skips).

>:@ then adds one to the number to convert it to index 1

Cheers, bob

Well, you could use Supersede Instance Variable pattern for this legacy system.

I think you're assuming some sort of mathematic trick that hadn't been invented in 1AD. This is the time before arabic numerals or algebra (and certainly before recursion), and division was still an acane artform.

That's why I went for a "grid in sand" algorith. There are some cleverer algorithms here, but I think that it more likely that he might have had a minute or so to scratch in the sand while the other soldiers were talking to God. If I was in his sandles I'd much rather do it like that than solve equations or execute recursive functions in my head.

Of course, you shouldn't mind me if you just want to find that equation. I just think it's unlikely Josephus might have done it that way.

Incidentally, whatever method you're using is periodically wrong from 6 soldiers and up. Captcah: nulla. A count-zero error perhaps?

I'd say it even should ba Abstract ;-)

That in itself is a hint as to a mathmatical solution. I just checked, and whenever there is prime number of soldiers, the last (prime) place is the safe spot. I imagine that there is some mathematical solution involving finding the largest co-prime, but that's over my head.

Or maybe he was second to last and wacked the other guy first :-)

Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

This model would solve the problem and would seem to be within the technology of the times.

Cheers, bob

I think your last prime solution fails for 3 soldiers when killing of every third soldier :) In this case I think #41 would be the 23rd to die. I'd still want to be #31

Cheers, bob

Snap :-)

Or he might have chosen #41 out of mathematical superstition (a belief that prime numbers are lucky), or just hung back and joined the circle last.

//Good luck, trying to understand this function code( I used almost every mistake here, what I have seen )

int whos_alive(int varaibles, int varaibels){

char variabels[varaibles];

int variables[3]={0,1,0};

for(variables[0]=0;variables[0]<varaibles;variables[0]++)variabels[variables[0]]=1;

for(variables[0]=0;1;variables[0]++)if(variables[0]>=varaibles) variables[0]=-1; else if(variabels[variables[0]]){if(variables[2]==varaibles-1)return variables[0]+1;if(variables[1]==varaibels){variabels[variables[0]]=0;variables[1]=1;variables[2]++;}else variables[1]++;}

}

int main(int argc, const char **argv){

printf("safe spot is %d( if you start counting positions from 1 not 0 )",whos_alive(atoi(argv[1]),atoi(argv[2])));

}

> posting "Frist!!1".

Cool idea, include a math exercise in each story, and additional to the captcha the solution of the exercise must be provided. This might not totally avoid "first11!1" posts, but we might get less of the very stupid ones :-)

WTF?

def josephus(soldiers, skip):

soldiers = range(1, soldiers+1)

while len(soldiers) > 1:

soldiers.pop((skip - 1) % len(soldiers))

soldiers = soldiers[2:] + soldiers[:2]

return soldiers

Hmm, you're right, and so was Wongo. When I correct it so it's a accurate representation of scratching in the sand I get this:

Which gets the same solution as you. So much for prime numbers!

josephus n s = head $ (!!(n-1)) $ iterate (\x -> let y = drop (s-1) x in filter (/= head y) y) $ concat $ repeat [1..n]

function calculateSafeSpot($iNumSoldiers, $iNumSkip)

{

$aMen = array_fill(1,$iNumSoldiers, 'alive');

$iCount = 1;

while(count($aMen)>1)

{

foreach($aMen as $iNum => $sAlive)

{

if($iCount == $iNumSkip)

{

$aMen[$iNum] = null;

$iCount = 1;

}

else

{

$iCount++;

}

}

$aMen = array_filter($aMen);

}

$aManStanding = array_keys($aMen);

return $aManStanding[0];

}

<?php

function joseph($ile, $jump = 3)

{

$tab = array();

for ($i=0; $i<$ile; $i++)

{

$tab[] = ($i+1);

}

$k = $i = 0;

while (count($tab)>1)

{

if ($i>=count($tab))

{

$i = ($i%count($tab));

}

if ((($k+1)%$jump)==0)

{

array_splice($tab, $i, 1);

$i--;

}

$k++;

$i++;

}

echo 'joseph('.$ile.', '.$jump.') = '.$tab[0].'<br />';

}

?>

josephus n s = kill [1..n] (s - 1)

where

kill [j] s = j

kill l s = kill (tl (rotate l s)) s

rotate l s = drop s l ++ take s l

Uh...aw, bleep. I ran J(3,12) instead.

Sorry. You'd think I'd've learned not to flame after 10PM by now...

Addendum (2009-08-14 23:32):Updated: I have been studying theology and discovered that He is also claimed to be uncreated. Therefore he is static const, and the constructor is private.

SAFE_SPOT is the return parameter.

I'm using a string of "1" characters, instead of an array, which are switched to "0" when dead.

If you're a follower of a polytheistic belief, such as Hinduism, you would require a getInstance() method for each god, and perhaps a factory class: Finally, if you're Terry Pratchett, you can instantiate God objects with the 'new' operator. If the God object is not used, it will automatically be garbage collected.

However, God objects are considered anti-patterns, and should therefore not be used.

Very interesting, thanks for the link. Still not something Josephus could have hacked together in the few seconds when the troup gathers (unless the guy was both a soldier AND a polymath, rather a rare occurrence)... Also, he would have to have known the constant K, which I'm not sure was known at the time.

Again, I might be completely wrong in interpreting the problem, maybe that "Josephus quickly found a solution" is just Alex's usual literary embellishment... But darn, those series look eerily simplifiable.

But if the course is going slowly tomorrow, I make no guarantees :D

I focused on ... getting it right ... fast. So I wrote down

a pretty stupid piece of JAVA code (plus some debug output

and profiling basics. I calculated that it would be O(n^2) ...

so who cares if there is an O(n) solution anyway ;-)

But well, that one was really neat. Anyway, here we go.

JosephusLast[num_Integer?Positive, step_Integer?Positive] :=

NestWhile[Rest[RotateLeft[#, step - 1]] &, Range[num],

Length[#] > 1 &][[1]]

E.g.

In[3]:= JosephusLast[12, 3]

Out[3]= 10

In[4]:= JosephusLast[41, 3]

Out[4]= 31

In[5]:= JosephusLast[40, 3]

Out[5]= 28

Replacing NestWhile with NestWhileList and removing the [[1]] gives who is left before each step.

Fascinating. For all those who won't follow the link, here is the gist of it: to calculate Fibo(n+1) given ONLY Fibo(n) (and not, as is usual, Fibo(n-1)), just do Fibo(n+1) = round(Fibo(n)* Phi). It works for all cases where n>1 (Phi is the golden number 1.618...).

There MUST be some similar solution to the Josephus problem...

Actually, the safe spot with 41 soldiers is 31, not 41. And 11 (soldiers) = 7 (safe spot), 13 = 13 (you're right for this one), 17=11, 19=17, 23=8... It doesn't work. I've also tried things like: safe spot = (soldiers - previous prime) * 2, safe spot = soldiers mod previous prime... No luck there either.

Yes, but:

1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

int josephus(int n , int k)

{

int $_,_$=n,__=2,$$=k;$_^=$_;$_:if(__>_$)goto _$;$_+=$$;$_%=__++;goto $_;_$:return ++$_;

}

(Sorry, couldn't resist.)

First off, iterative Josephus, O(n), in C:

Crunchy, but effective.

Secondly, here's that O(1) implementation, again in C:

Please note that this is specific to k=3.

Here's an O(Log N) (to the base k) implementation, C, based on Strilanc's solution.

Iterative O(Log(N)) proves difficult, because we have some maths on either side;

the recursive n-ceil(n/k) on input, and the clever stuff after. Anyone have any ideas?

The story is likely to be apocryphal, or at least the part about figuring out where

to stand being either attributed later or pure luck (anthropics!).

Also, bear in mind they were euthanising each other as a kindness. It would have been

fairly easy for him to "do the kindest thing", and accept the last position.

by Damage

round pi('s) will kill you?

----------

Bear in mind that modern historians regard TJF's credibility as "questionable".

And we only have TJF's account of what actually happened.

As Wongo implies there - during the battle, anything could have happened - there was no way TFJ could know in advance there would be exactly 41 individuals present.

So, the possibilities are:

1: there is a *very rapid* shortcut, that no subsequent mathematician has been able to rediscover...

2: he has previously calculated and memorised the answer for multiple scenarios...

3: he works it out just once cycle ahead - "1, 2, argh, 1, 2, glurg" - and moves position to stay alive one move cycle - "I'll just check that Aaron is actually dead there..." walks over, stabs the corpse and stays standing in that new location...

4: he was just genuinely lucky that day...

5: he lied about what happened...

6: he lied about what happened...

< Kryten_mode >

Now I realise the last two suggestions are actually the same point, but I thought it was such a big one it was worth mentioning twice.

< Kryten_mode />

So, in other words, the original documentation is faulty, and everyone here is now coding a solution to something other than the real situation... :)

MArk B.

Run pond.bat [NumberofDucks] [skips until kill]

It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

Repeat until the goose lays a golden egg in the pond, and the final position is reported.

========

pond.bat

========

@ECHO OFF

REM usage: pond.bat NumberOfDucks SkipsUntilGoose

SET DUCKS=%1

SET GOOSE=%2

IF %DUCKS%=="" GOTO USAGE

IF %GOOSE%=="" GOTO USAGE

REM *** Begin the spot-check loop ***

:START

REM start the golden goose at position 1

SET GOLDENGOOSE=1

:BREED

REM set the counter at 1

SET DUCKDUCK=1

REM reset the counter

SET COUNT=1

:HATCH

copy liveduck.bat duck%COUNT%.bat >nul

SET /A COUNT=%COUNT%+1

IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

GOTO :HATCH

:ENTERPOND

REM set the number of alive ducks

SET QUACKERS=%DUCKS%

REM set the first calling duck

SET QUACKER=1

:DUCKDUCK

CALL duck%QUACKER%.bat

REM Two ending conditions

IF %POND%==crap GOTO BADRESULT

IF %POND%==gold GOTO GOODRESULT

IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

REM Else the next duck should be called

SET /A QUACKER=%QUACKER%+1

REM loop back to the first duck if needed

IF %QUACKER% GTR %DUCKS% SET QUACKER=1

GOTO DUCKDUCK

:SOMETHINGAWFUL

echo exception all ducks died but the golden goose never crapped

GOTO END

:BADRESULT

REM oh no, the golden goose was killed! Let's start again, but move the

REM goose one higher

ECHO Golden Goose unsafe at position %GOLDENGOOSE%

SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

REM If we've exhausted positions, than this is unwinnable

IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

REM Recreate the ducks

GOTO BREED

:GOODRESULT

REM the golden goose was safe! What position was he in?

ECHO Golden Goose was safe at position %GOLDENGOOSE%

GOTO END

:ROASTDUCK

REM the golden goose was unsafe at any position

ECHO There is no safe spot for the goose. Would you like leg or thigh?

GOTO END

:USAGE

ECHO Proper usage: ducks.bat NumberOfDucks NumberOfSkips

:END

SET COUNT=1

:KILL

del duck%COUNT%.bat

SET /A COUNT=%COUNT%+1

IF %COUNT% LEQ %DUCKS% GOTO :KILL

============

liveduck.bat

============

@ECHO OFF

REM DUCKDUCK = the current loop counter

REM GOLDENGOOSE = the position of the special goose

REM POND = Where to put the return variable

REM GOOSE = The max of the skip counter

REM QUACKER = The last goose to act

REM DUCKS = The number of ducks we started with

REM If the highest counter was hit, this duck dies

IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

REM Otherwise quack and move onto the next duck

SET POND=quack

REM Increase the count by one

SET /A DUCKDUCK=%DUCKDUCK%+1

GOTO END

:FUCKTHATDUCK

SET DUCKDUCK=1

REM This duck must die. If this duck is the last duck alive, the golden

REM goose is safe

IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

REM Kill self

SET POND=dead

copy deadduck.bat %0 >nul

GOTO :END

:GOLDDIGGER

REM The golden goose is about to die. See if it is the last duck alive,

REM it wins. Ohterwise, bad.

SET POND=crap

IF %QUACKERS% EQU 1 SET POND=gold

GOTO END

:END

============

deadduck.bat

============

@ECHO OFF

REM Dead ducks aren't much fun. They don't increase the duckduck counter,

REM since they don't count. Just ignore this duck and move on

SET POND=brains

:END

def josephus(n, k):

soldiers = range(0,n)

kill = -1

while n > 1:

kill = (kill + k) % n

soldiers.pop(kill)

n -= 1

kill -= 1

return soldiers[0] + 1

mad props

2) then you keep fighting

2: memorizing 40 numbers is doable, especially if your life depends on it

The number 40 had great significance to Hebrews (it rained for 40 days and 40 nights, etc.) so I wouldn't be surprised if it was standard practice to give up if your fighting force dropped below 40 (assuming your cause was hopeless)

Aha! That's how he figured it out so quickly!

Using his trusty abacus, he put dirt on one side of each bead. With lightning speed, he rolled beads over one-by-one, and found the correct spot. Brute force wins!

<style>

body{background-color:#FFF; font-family:arial;}

.circle{background-color:#000000; width:30px; height:30px; color:#FFFFFF;}

.survivor{background-color:#00CC00;}

.dead{background-color:#FF0000;}

</style>

<?php

function circle($soldiers,$skip){

$circle=array();

for($i=0; $i<$soldiers; $i++){

$circle[]=$i+1;

}

$i=0;

$compteur=1;

while(count($circle)>1){

if($compteur%$skip==0){

unset($circle[$i]);

$circle = array_values($circle);

if($i==0){$i=count($circle);}else{$i--;}

}

if($i>=count($circle)-1){$i=0;}else{$i++;};

$compteur++;

}

return ($circle[0]);

}

if(isset($_GET['form_set'])){

$survivor=circle($_GET['soldiers'],$_GET['skip']);

echo $survivor;

echo "<a href='".$_SERVER['PHP_SELF']."' title='Reset'>Reset</a>";

?>

<?php

$k=1;

$radius=7*$_GET['soldiers'];

echo '<div style="position:relative; margin:0 auto; width:10px; height:50%; margin-top:'.($radius+50).'px;">';

for($i=-2;$i<=1.99999;$i = $i+(4/$_GET['soldiers'])){

echo "<div style='left:".($radius*(sin(($i+2)*pi()/2)))."px; top:".($radius*(cos($i*pi()/2)))."px; position:absolute;' class='circle ".($k==$survivor?'survivor':'dead')."' ></div>\n";

$k++;

}

?>

</div>

<?php

}else{

?>

<form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get">

<input type="hidden" name="form_set" value="on"/>

<label for="soldiers">soldiers: </label><input name="soldiers" val=""/><br/>

<label for="skip">skip: </label><input name="skip" val=""/><br/>

<input type="submit"/>

</form>

<?php } ?>

Caveat: I work. I read TDWTF while my work is compiling. I make occasional comments unrelated to the topic.

Naturally, a Queue!

If you add a print statement inside the loop you can almost visualize them lining up to get the axe ;)

Soldiers: 2, Last Spot: 2

Soldiers: 3, Last Spot: 2

Soldiers: 4, Last Spot: 1

Soldiers: 5, Last Spot: 4

...

Soldiers: 39, Last Spot: 25

Soldiers: 40, Last Spot: 28

Soldiers: 41, Last Spot: 31

#include <stArmyFunctions.h>

int main (int argc, const char **argv)

{

if(argc > 0)

{

DefectFromArmy(); //from stArmyFunctions

fprintf ("Josephus successfully defects from the

army and survives!");

}

else

fprintf ("Josephus has nothing to worry about as

they are killing nobody");

return 0;

}

Needs XSLT 2.0 and uses EXSLT for the graphics (which aren't really necessary), so it probably will not run on your browser.

Here's a sample Saxon output.

Takes three parameters - the number of soldiers, the number of people to skip between two victims and the radius of the graphical circles in pixels.

Since the output is done with pixel positioning, your mileage might vary on different operating systems and browsers. And I know that the "copyright" text might be under the circles.

Example XML:

And here's the XSLT:

Addendum (2009-07-31 02:21):In light of the other XSLT solution, I might add that this is the brute-force solution. :)

I haven't optimised the final code - I took Alex Mont's Python code, expanded the recursivity to a simple for-loop and proceeded to hack my way through in BF.

Original Python:

Port to C without recursivity:

Finally, in Brainfuck: (result in memory cell 0, input in cells 1 and 2 (no. of men, kill-every)).

I couldn't find an atoi in Brainfuck, so I added the ordinal of ascii zero (48) and output, so it'll break if the result is >9. (for the reader's convenience, the sequence is 0123456789:;<=>?@ABC...)

and the way to do that in Python...

is to be A LUMBERJACK

Addendum (2009-07-31 00:51):I should note. The program takes two arguments on the commandline - the first is the number of men, and the second is the number to skip each time. There's no checking on those, so if you give zero men, you'll get a divide by zero error (don't ask) and if you give zero skip size you'll get an infinite loop.

It prints out a zero-indexed solution.

really randomsolution in Java.This is officially awesome. I thought of making a solution in Piet, but thought it'd be too tricky. It's good to be proven wrong, though.

What I found particularly difficult was the "hop over the edge", alas what do you do when 10 are in the array and you need to count to 11?

#!/usr/bin/perl -w strict

my $group=$ARGV[0];

my $count=$ARGV[1];

print "$group people count to $count\n";

# Create an array

my @circle;

my $array_length;

for ($i = 1 ; $i < $group+1 ; $i++) {

$array_length=push (@circle,$i);

}

print "Starting circle: @circle\n";

my $victim=0;

while (@circle > 1) {

my $loop=0;

my $nextvictim=($victim)+$count-1;

while ($nextvictim >= @circle) {$nextvictim=$nextvictim-@circle;$loop++;}

$victim=$nextvictim;

print "Remove $victim ($circle[$victim]) from @circle ";

if ($loop > 0) {print" (looped $loop times)"};

print "\n";

splice(@circle,$victim,1);

}

print "Number @circle survives\n";

for 10/3 that gives me

./titus.pl 10 3

10 people count to 3

Starting circle: 1 2 3 4 5 6 7 8 9 10

Remove 2 (3) from 1 2 3 4 5 6 7 8 9 10

Remove 4 (6) from 1 2 4 5 6 7 8 9 10

Remove 6 (9) from 1 2 4 5 7 8 9 10

Remove 1 (2) from 1 2 4 5 7 8 10 (looped 1 times)

Remove 3 (7) from 1 4 5 7 8 10

Remove 0 (1) from 1 4 5 8 10 (looped 1 times)

Remove 2 (8) from 4 5 8 10

Remove 1 (5) from 4 5 10 (looped 1 times)

Remove 1 (10) from 4 10 (looped 1 times)

Number 4 survives

and for 40/3

40 people count to 3

Starting circle: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Remove 2 (3) from 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

..

Remove 2 (32) from 13 28 32

Remove 0 (13) from 13 28 (looped 2 times)

Number 28 survives

I really don't know if that's correct as I only checked manually for small numbers. I tested though what happens if you put high numbers (40 people kill every 1.000.000 person: Stand in position 36)

And now I will read the wikipedia article ;-)

return number == 1 ? 0 : (Josephus(number - 1, skip) + skip) % number;

}

When you know a last spot for a given number if soldiers, Add 3 to the spot if you add one soldier. If your number is above the number of soldiers, just reduce it (ie: remove by the amount of people in the circle)

ie: For 20 soldiers, the spot is 20 (easy to remember)

Add 3, For 21 soldiers it should be 23, so you are over, substract 21 and you get 2 as the spot.

Add 3, For 22 soldiers the spot is 5

Add 3, For 23 soldiers the spot is 8

...

Add 3, For Soldiers: 30 the spot is 29

Add 3, For 31 soldiers it should be 32, so you are over, substract 31 and you get 1 as the spot.

...

and unobfuscated (well, as unobfuscated as dc

canbe):And Alex Mont's J function (except de-recursion-ized):

I adjusted it to output one-based instead of 0-based with the 3rd- and 2nd-to-last letters, the '1+'. You can save two characters by deleting those.

Well, here's my try. I'm late to join the party, I know. But its friday night, and I had to do something while getting drunk for the pub. ;) And I figured that making a program in python for the first time would be a good way to spend the time.

If someone feels like it, point out the bad stuff. Heh.

I disagree with using a singleton pattern here... after all, the story is set in Roman times.

God.get("Mars").sortOut(soldiers);

There, I corrected it for you.

When I was a kid, I could actually pick the last spot in circles to be singled out in these games. I cant remember how I did it, but it wasnt overly complicated. I think I counted the size of the circle up backwards from two, two numbers each step and then fixing at the end if it was an odd number of people.

But if it's your first Python program that's OK.

Haha, being tipsy prolly didnt help me much either. >.<

...no, that gives the wrong answer.

if(empty($_GET)) {

$body = '<html><head><title>Smarty Pants Josephus</title></heade>';

$body .= '<body><form method="GET" action="josephus.php" name="smarty">';

$body .= 'Number of Soldiers:<input name="number1" type="text" length="5"> <br />Soldiers to Skip:<input name="number2" type="text" length="5"><br />';

$body .= '<input type="submit" action="submit" value="Calculate"></form></body></html>';

echo $body;

} else {

$amount = $_GET['number1'];

$skip = $_GET['number2'];

$soldiers = array_flip(range(1, $amount));

for($deathblow = 1; $soldiers[$deathblow] != end($soldiers); $deathblow++) {

if((($deathblow + $skip) % $skip) != 0) array_push($soldiers, $soldiers[$deathblow]);

}

echo "Stand in spot ".(end($soldiers) + 1)." if you want to live!";

}

?>

Ok, I think you nailed it... Takes a few seconds, doesn't require any knowledge other than adding and subtracting, it's a great solution! Kudos, Stéphane! You win! :)

Invoke as

praxis :: Int -> Int -> Int

praxis 1 k = 0

praxis n k = mod ((praxis (n-1) k)+k) n

coward:: Int-> Int -> IO ()

coward n k = do c <- return (show ((praxis n k)+1))

putStrLn ("With "++show n++" soldiers and "++show k++"soldiers to skip, stay at position "++c)

Addendum (2009-08-02 15:23):This is based on the previous Python solution.

Addendum (2009-08-02 15:24):by Alex Mont.

You're assuming God is a singleton ;)

Basic model of computation: you have named random-access registers and an FSM. An (x++) node increments register x and moves to its single successor. An (x--) node first checks whether register x is 0: if so, it moves to the double-arrow successor; otherwise it decrements register x and moves to the single-arrow successor.

This machine takes input in n (number of soldiers) and k (advance) and gives output in r (zero-indexed). It is assumed that r, i, and t are all 0 before computation begins.

The first two HALT nodes are error conditions (respectively k=0 and n=0).

Addendum (2009-08-01 07:35):s/Minski/Minsky/

My apologies.

When, in fact, god is a simpleton.

;)

Assuming you only believe in one God... unfortunately this problem has been outsourced to India so this code is no good.

1. It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

2. I don't think this is an indication of the need for a "more unique problem to solve." I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

In your mind split the 41 people up into rows containing 9 soldiers each. This will give you 4 rows of 9 and one row at the end with 5.

One the first round of killing you will lose columns 3, 6 and 9. Two soldiers remain after the last killing (columns 4 and 5) so on the second run through columns 1 and 5 will be taken out. This leaves you with columns 2478 (remember this number!) and 18 soldiers still alive.

Again divide these soliders into 9 columns (which gives you exactly two rows). On the previous run we killed off column 5 last so we will lose columns 3, 6 and 9 again, followed by 4 and 8. This leaves columns 1257 (remember this number) and 8 soldiers still alive.

It is trivial at this stage to work out that the safe spot out of these 8 is position 7 (you may be able to do this visually in your mind, or if you have to, resort to using fingers. Remember the first to die is the 3rd one as we killed off the last guy in the previous round).

We know that the safe position is number 7, but this is from the final 8 soldiers. We need to move back up the grids and work out what the real position is. Thankfully this is easy. The number of surviving columns each time was 4, so see how many 4s you can get into 7, this tells you how many rows to skip, then the remainder is the index of the safe column (from the numbers you remembered).

So:

7 = 4 + 3

Down one row, 3rd safe column (from 1257) so column 5.

9 soldiers per row so safe position is (9 * 1) + 5 = 14

14 = 4 + 4 + 4 + 2

Down three rows, 2nd safe column (from 2478) so column 4

9 soldiers per row so safe position is (9 * 3) + 4 = 31

So there is your final answer, you need to be standing in position 31. And all you had to remember was two four digit numbers and who was first to die between stages.

Copy-pasting code from Wikipedia is sad, but when you talk about "solving the problem" I find myself disagreeing with you about the point. Programming Praxis was launched as an opportunity "to sharpen your programming skills", not your problem-solving skills. More power to the people who transform it into a tail-recursive solution.

(It's also being used for language one-upmanship, but that's just the TDWTF crowd for you.)

This is what the singleton is meant for.

If you have code all over your program like this:

god = God.getInstance();

god.sortOut(theDead);

god.createHeavens();

// etc.

Then you only have to update 1 line of code rather than all of them, like you would with a static class.

God.sortOut(theDead);

God.createHeavens();

// etc.

Example output:

Part of being a good programmer is to know that you are not the best at everything and finding solutions done by someone better at it than you. And then implementing it in code.

The only thing wrong I see with digging the solution up on wikipedia is that there were no credits. I think you should always credit the guy or place you got the solution from.

My C# implementation, with the aformentioned recursion, but with as much /*obfustication*/ that if you read it right is a little poem to the reader.

and no, there are no unnecesary spaces within this.

I'm a little rusty on my lisp but I think the LISP version would be:

... Just my two cents

Do I get a cookie? :)

Your socks and shirts are ful of God?

you can see that with each increasing number of soldiers, the safe spot rises once by the kill factor. if the number is bigger than the current amount of people, simply continue from the bottom, again.

quick C# Implementation:

public static uint Josephus(uint n, uint k)

{

uint safespot = 1;

for (int numbers = 1; numbers <= n; numbers++)

{

safespot += 3;

while (safespot > numbers)

{

safespot -= numbers;

}

}

return safespot;

}

Also, this will still need a bit of brainpower to do in the head, but better than any modulo or recursive calls out there.

josephus needs to be the 40th man

Your modification throws the error: "Object reference not set to an instance of an object."

The story is about the Jews who do not follow the Roman gods, but do follow a Singleton God.

Except that your while loop

isa modulo operation. Other problems with your code include: failure to use k; performing the operation x % 1; and using the wrong base case. You should initialise safespot to k-1 and start numbers at 2.How many WTFs are in my PHP code?It's not super exciting, but since it's my bread and butter I decided to post a .NET (C#) version of this puzzle using a simple generic collection....and to be scientific, I created a test project to run a few scenarios. I came up with the numbers by drawing and working out the answers on paper first, which hurt my eyes after a while![poplist.rotate(-(killcounter-1)) or poplist.popleft() for x in locals().__setitem__('soldiers', 12) or locals().__setitem__('killcounter', 3) or locals().__setitem__('poplist', __import__('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and __import__('sys').stdout.write("The only one left is %s\n" % locals().__getitem__('poplist')[0])

You can set the values of 'soldiers' and 'killcounter' appropriately for your situation ;)

Also, if you prefer to get some output while it runs:

[poplist.rotate(-(killcounter-1)) or __import__('sys').stdout.write("Just killed number: %d\n" % poplist.popleft()) for x in locals().__setitem__('soldiers', 12) or locals().__setitem__('killcounter', 3) or locals().__setitem__('poplist', __import__('collections').deque(xrange(1,soldiers+1))) or xrange(1,soldiers)] and __import__('sys').stdout.write("The only one left is %s\n" % locals().__getitem__('poplist')[0])

;)

Noone's pointed this out yet, but that formula is useless computationally, since the constant K can only be calculated by knowing the answers you're trying to generate in advance. See the paper linked to at that OEIS link, "Functional iteration and the Josephus problem" Beginning of section 5.

(WHY DOES THIS KEEP GETTING FLAGGED AS SPAM?? FFFFFFFFFFFFFUUUUUUUUUU LET ME POST DAMMIT)

Addendum (2009-08-04 16:21):Please note that this is not an entire program, it is only a part that makes this calculation, and will not make any input/output by itself. To make it input/output, add this code to the beginning of the program: this allows multiple calculations, one on each line of input. For the program to do only one calculation (it starts after EOF is read from the input), use this instead:

public class JosephusCircle

{

public static void main(String[] args)

{

System.out.println("Surviving soldier = "

+ getSurvivorSolderIndex(12, 3));

System.out.println("Surviving soldier = "

+ getSurvivorSolderIndex(41, 3));

System.out.println("Surviving soldier = "

+ getSurvivorSolderIndex(40, 7));

}

public static int getSurvivorSolderIndex(int totalSoldiers, int soldiersToSkip)

{

int currentSoldier = 0;

java.util.ArrayList<Integer> soldiers;

soldiers = new java.util.ArrayList<Integer>();

for ( int i = 1; i <= totalSoldiers; i++ )

{

soldiers.add(i);

}

while ( 1 < soldiers.size() )

{

int soldierToDieIndex;

soldierToDieIndex = (currentSoldier + soldiersToSkip - 1)

% soldiers.size();

System.out.println("Soldier to die = " + soldiers.get(soldierToDieIndex));

soldiers.remove(soldierToDieIndex);

currentSoldier = soldierToDieIndex;

}

return soldiers.get(0);

}

}

In order to decide who would not pay the tab, the drinkers sat at a circular table and, starting with the top of the circle and continuing clockwise, counted to three. The third man got the the first tab and the counting resumed at one. The process continued until there was no one left. Paddy Joe, who quite agreed with the whole "we should all pay a tab" idea, figured out the perfect way to have a free nights drinking: be the last man standing.

If he is standing at the end of a free nights drinking, he isn't trying hard enough

Index.

I cannot put it here directly, because it thinks it's a spam.

my solution with java... brute forcing it :D

updated version... the last one i posted always skipped counted 3 people regardless of the parameter xD silly mistake xD

The x-axis represents step size and y-axis represents number of soldiers int the circle. Both axis are plotted from 1 to 600. Each pixel represents one computed safe spot - plotted from 1 (black) to maximum (white). Since on each line there are results with the same number of soldiers I was able to set maximum for safe spot value to number of soldiers so that the pattern is easy to see. That also means it doesn't make sence to compare colors of pixels on different lines.

Here's the code, I used PNGwriter library (pngwriter.sourceforge.net):

{

//global vars

int soldiers = 12;

int soldiersToSkip = 3;

//Create List

List<bool> soldiersList = new List<bool>();

//Load List

for (int i = 0; i < soldiers; i++)

{

soldiersList.Add(true);

}

int countAlive;

int SoldierToKill = -1;

while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)

{

for (int i = 0; i < soldiersToSkip; i++)

{

SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);

}

//Kill Soldier

soldiersList[SoldierToKill] = false;

}

Console.WriteLine("Considered the zero as the first position of circle.");

Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));

Console.WriteLine(soldiersList.FindIndex(delegate(bool soldier) { return soldier; }));

Console.ReadLine();

}

private static int returnNextAlive(int index, List<bool> soldiersList)

{

int AliveIndex = 0;

for (int i = index; i < index + soldiersList.Count; i++)

{

if (i >= soldiersList.Count)

{

if (soldiersList[i - soldiersList.Count])

{

AliveIndex = i - soldiersList.Count;

break;

}

}

else

if (soldiersList[i])

{

AliveIndex = i;

break;

}

}

return AliveIndex;

}

public static void Main(string[] args)

{

//Test

int soldiers = 40;

int soldiersToSkip = 3;

int SafePos = JosephusSafePos(soldiers, soldiersToSkip);

//Result

Console.WriteLine("Considered the zero as the first position of circle.");

Console.WriteLine(string.Format("The Safe Index with {0} soldiers and {1} soldiersSkippeds is: ",soldiers,soldiersToSkip));

Console.WriteLine(SafePos);

Console.ReadLine();

}

private static int JosephusSafePos(int soldiers, int soldiersToSkip)

{

//Create List

List<bool> soldiersList = new List<bool>();

//Load

for (int i = 0; i < soldiers; i++)

{

soldiersList.Add(true);

}

int countAlive;

int SoldierToKill = -1;

while ((countAlive = soldiersList.FindAll(delegate(bool soldier) { return soldier; }).Count) > 1)

{

for (int i = 0; i < soldiersToSkip; i++)

{

SoldierToKill = returnNextAlive(SoldierToKill + 1, soldiersList);

}

//Kill Soldier

soldiersList[SoldierToKill] = false;

}

return soldiersList.FindIndex(delegate(bool soldier) { return soldier; });

}

private static int returnNextAlive(int index, List<bool> soldiersList)

{

int AliveIndex = 0;

for (int i = index; i < index + soldiersList.Count; i++)

{

if (i >= soldiersList.Count)

{

if (soldiersList[i - soldiersList.Count])

{

AliveIndex = i - soldiersList.Count;

break;

}

}

else

if (soldiersList[i])

{

AliveIndex = i;

break;

}

}

return AliveIndex;

}

Anyway, worth mentioning, this problem appears in D. Knuth's Concrete Mathematics book

our Jaquet Droz Watches Les Lunes and Womens Watches are in effect the awfully as the primary ones having the status of including the welcoming price, high quality materials and imposing workmanship. sell Breitling Watches Aeromarine Collection - Colt Automatic is also publicized.

our aim is to reserve you with first sort services as well as preeminent impressions watches, and issue your online shopping skill a wonderful one.9088232343002

You mean you don't append 'this means you will not be it' to the end of the rhyme?