Josephus' Circle

« Return to Article
  • Josephus 2009-07-29 09:12
    Last
  • pjt33 2009-07-29 09:16
    SML, indexing the men from 0:

    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);
  • Anon 2009-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".
  • DaveK 2009-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

    $

  • HypocriteWorld 2009-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.
  • DaveK 2009-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
  • Engival 2009-07-29 09:26
    This is pretty brain dead, but coffee hasn't done it's job yet:

    function jcircle($men, $skip)
    
    {
    $mans = array();
    for($i=1; $i<=$men; $i++)
    $mans[$i] = $i;

    $i = 0;
    print "Killing: ";
    while(count($mans) > 1)
    foreach($mans as $idx=>$junk) {
    $i++;
    if ($i == $skip) {
    print $idx.", ";
    unset($mans[$idx]);
    $i=0;
    }
    }
    reset($mans);
    print " left alive: ".current($mans)."\n";
    return(current($mans));
    }

    print "Who's left: ".jcircle(40,3)."\n";
  • silent d 2009-07-29 09:31
    I think this is more about being the guy who decides where the "top of the circle" is than anything else.
  • Code Dependent 2009-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.
  • steenbergh 2009-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...
  • JonsJava 2009-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 Mont 2009-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.

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n


    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.
  • Addison 2009-07-29 09:50
    Alex Mont:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    This is sexy.
  • Dave 2009-07-29 09:54

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
  • jfruh 2009-07-29 09:56
    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.
  • Ben Forta 2009-07-29 09:56
    A not as ugly as the PHP script in CF

    <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>
  • QSR 2009-07-29 09:57
    A little bit of scala:

    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;
    }
    }
    }
  • Ben Forta 2009-07-29 09:57
    Sorry messed up the code tag


    <cfparam name="url.soldiers" type="numeric" default="41">
    <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>
  • SR 2009-07-29 09:59
    ColdFusion


    <cffunction name="JosephusSafeSpot" returntype="numeric">
    <!--- some arguments --->
    <cfargument name="total" required="Yes" type="numeric">
    <cfargument name="interval" required="Yes" type="numeric">

    <!--- 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 Tentakyl 2009-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] ) )

  • Kyle 2009-07-29 10:02
    Alex Mont:


    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    Beat me to it.


    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
  • pjt33 2009-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 Independent 2009-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.
  • null 2009-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 Kosten 2009-07-29 10:05
    PHP:
    function j($n, $k) {
    
    if ( $n == 1 ) {
    return 0;
    } else {
    return ((j($n-1,$k)+$k)%$n);
    }
    }
  • Code Dependent 2009-07-29 10:06
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
  • PJ 2009-07-29 10:08
    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];
    }
  • SR 2009-07-29 10:09
    Pipped at the post by the one and only Ben Forta. I'm half livid, half honoured :)
  • Andreas Kromann 2009-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 Parker 2009-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]
  • Kman 2009-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
  • Ahox 2009-07-29 10:17
    What happened to the locker problem comment? I can't find it anymore, and I had such a nice solution
  • Andreas Kromann 2009-07-29 10:17
    Andreas Kromann:

    f(n,k) = f(n-1,k)+ k mod n+1

    thats 'mod n' ofc and not 'mod n+1' :)
  • Satanicpuppy 2009-07-29 10:18
    Addison:
    Alex Mont:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    This is sexy.


    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.
  • David 2009-07-29 10:20
    Javascript (0 starting index):

    (function(n,s){
    
    return (n === 1 ? 0 : (arguments.callee(n-1,s) + s) % n);
    })(12,3);
  • Scope 2009-07-29 10:20
    But then we wouldn't be able to mock God in a unit test!
  • Scope 2009-07-29 10:22
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?


    But then we wouldn't be able to mock God in a unit test!
  • RayMarron 2009-07-29 10:23
    I just wanted to say that the animations accompanying these are brilliant. :)
  • horizon 2009-07-29 10:24
    assuming that the starting position is 0:

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

  • guns 2009-07-29 10:24
    David:
    Javascript (0 starting index):

    (function(n,s){
    
    return (n === 1 ? 0 : (arguments.callee(n-1,s) + s) % n);
    })(12,3);


    similarly (ruby1.9):

    j = lambda { |n,k| n == 1 ? 0 : (j.(n-1, k) + k) % n }
  • Ralfe Poisson 2009-07-29 10:27
    Here is a solution in PHP:

    $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];
  • dkf 2009-07-29 10:29
    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 Poster 2009-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;
    }
  • DesGrieux 2009-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);
    }

    int currentIndex = 0;
    while(aliveMen.size() > 1) {
    currentIndex = (currentIndex - 1 + step) % aliveMen.size();
    aliveMen.remove(currentIndex);
    }
    return aliveMen.get(0);
    }


    Using the recursion:

    public static int j(int n, int k) {
    return (n == 1) ? 0 : (j(n-1, k) + k) % n;
    }
  • d3matt 2009-07-29 10:31
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?

    yes... the God class is a singleton...
  • steenbergh 2009-07-29 10:33
    Vba:

    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
  • Code Dependent 2009-07-29 10:34
    Scope:
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    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.
  • aehiilrs 2009-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.
  • jonnyq 2009-07-29 10:38
    99 characters of ruby on the wall...

    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
  • Wongo 2009-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 ?
  • Yanman 2009-07-29 10:39
    Josephus:
    Last


    hero!
  • Robert (Jamie) Munro 2009-07-29 10:39
    This simplifies to just

    def J(n,k): return n!=1 and (J(n-1,k)+k)%n
  • DOA 2009-07-29 10:41
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?

    I can't decide whether God being static is bad coding or being inconsiderate towards other religions...

    Also +1 internets for Dave. Made me laugh.
  • SR 2009-07-29 10:43
    d3matt:
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?

    yes... the God class is a singleton...


    d3matt: I've got a billion or so Hindus on the phone who don't agree
  • Andreas Kromann 2009-07-29 10:45
    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
  • halber_mensch 2009-07-29 10:46
    python one-liner, 1-based index using skips and not counts:


    f=lambda n,k:(f(n-1,k)+k)%n+1 if n-1 else 1
  • Quicksilver 2009-07-29 10:46
    Hooray for "Scheme"


    (define josephus
    (lambda (soldiers jump)
    (if (eqv? soldiers 1)
    0
    (modulo (+ (josephus (- soldiers 1) jump) jump) soldiers)
    )
    )
    )
  • vang 2009-07-29 10:49
    Like the braindead PHP solution, here's a rather braindead Perl solution.

    #!/usr/bin/perl

    use strict;
    use Getopt::Long;

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

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

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

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

    my @people = ();

    my $pos = -1;

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

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

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

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

    my @people = @$peopleref;

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

    sub dbg_print {
    my $message = shift;
    if ($debug) {
    print "DEBUG: " . $message;
    }
    }
  • Perl Monk 2009-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 :-)
  • rm5248 2009-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++;
    }

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

    }
  • Observer 2009-07-29 10:52

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



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

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

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

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

  • Lifacciolo 2009-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_mensch 2009-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
  • astonerbum 2009-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.
  • scp 2009-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;
    }

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

    for (i=1;i<n;i++)
    {
    for (j=0;j<k;j++)
    {
    _h = _h->next;
    printf("%d->", _h->number);
    }
    printf("X \n");
    _h->prev->next = _h->next;
    _h->next->prev = _h->prev;
    _h=_h->prev;
    }
    printf("%d survives\n", _h->number);
    return 0;
    }
  • Osno 2009-07-29 10:57
    Naïve C# implementation:


    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 void KillNext(int next, List<bool> standing)
    {
    Console.Write("{0} ", next + 1);
    standing[next] = true;
    }

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

    private static bool AllDead(List<bool> standing)
    {
    return standing.TrueForAll(p => p);
    }

    private static List<bool> InitArray(uint participants)
    {
    List<bool> standing = new List<bool>(Convert.ToInt32(participants));
    for (int i = 0; i < participants; i++) standing.Add(false);
    return standing;
    }
  • halber_mensch 2009-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.

    Ok back to the programming exercise.


    You're referring to the siege of masada.
  • Osno 2009-07-29 11:00
    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.
  • Chad 2009-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];
    }
  • Ian 2009-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 Urbanski 2009-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)
    $ perl -E'sub k{$_[0]&&(k($_[0]-1,$_[1])+pop)%pop}say k@ARGV' 12 3
    
    9

    59 chars + args.

    Indexed from 0. I'm certain it's possible to golf this further, though, I don't like this solution...and I'm loving those little challenges :).
  • Anon 2009-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 Kromann 2009-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}
  • mariushm 2009-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/>';

    ?>

  • Anon 2009-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.
  • Yazeran 2009-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
  • Anon 2009-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}
  • Knux2 2009-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 Kromann 2009-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
  • astonerbum 2009-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 Dependent 2009-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. Obvious 2009-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
  • Wongo 2009-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.
  • Phil 2009-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?
  • IV 2009-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).
  • db2 2009-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
    >>
    >>

  • Wongo 2009-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++;
    ...
  • Overcaffeinated 2009-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()
  • sbrant 2009-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)
  • Blarg 2009-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.
  • silvestrov 2009-07-29 11:39
    #!/usr/bin/perl

    $k = 3;
    @a=(1..40);
    @a = grep { ++$x % $k } @a while $#a
    print @a, "\n";
  • Overcaffeinated 2009-07-29 11:39
    Tabbing fail. Again, in Python:

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

    if skipped == skip:
    print 'killing %s' % (people.pop(current))
    skipped = 0
    current -= 1
    return people.pop()
  • time0ut 2009-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.

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

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

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

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

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

    public DanceMarathon(int participants, int skip) {
    this.dancers = new ArrayList<Dancer>();
    for (int i = 0; i < participants; i++) {
    this.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;

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

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

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

    public void setAlive(boolean alive) {
    this.alive = alive;
    }
    }
    }
    }
  • Anders Eurenius 2009-07-29 11:42
    Have you tested it?

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

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

    Which does seem to work. (0-indexed) I tried to eliminate more, but the lower modulos are apparently necessary.
  • CF Guru 2009-07-29 11:42
    I am humbled that the great Ben Forta visits this site. In fact, I always feel like bowing when I see or hear his name! You the man Ben!!!

    Ben Forta:
    A not as ugly as the PHP script in CF

    <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>
  • Wongo 2009-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 Bush 2009-07-29 11:44
    Numbering the top position as zero, in 'C':
    int Safe(int Soldiers, int Skip)
    {
    if (Soldiers == 1)
    return 0 ;

    return (Safe(Soldiers - 1, Skip) + Skip) % Soldiers ;
    }
  • Akoi Meexx 2009-07-29 11:52
    In php:

    <?php
    function LifePosition($indexCount=41, $skipCount=3)
    { /**
    * Josephus' Circle calculation function
    * Written to identify the array index that will be selected
    * last in a sequence with (x) indices and (y) skip count
    * @author: Akoi Meexx <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);
    }
    ?>
  • halber_mensch 2009-07-29 11:52
    Andreas Kromann:
    halber_mensch:
    Andreas Kromann:
    Wongo:

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


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

    1 + (n-1)k mod n


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

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


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

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


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

    {1,2,3,4,5}
    {1,3,5}
    {3}
  • Wongo 2009-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.
  • Brad 2009-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;


    var
    killEvery : Integer;
    killEveryStr : String;
    safe : Integer;
    soldierCount : Integer;
    soldierCountStr : String;

    begin
    if ParamCount < 2 then begin
    WriteUsage;
    Exit;
    end;

    soldierCountStr := ParamStr( 1 );
    killEveryStr := ParamStr( 2 );

    try
    soldierCount := StrToInt( soldierCountStr );
    killEvery := StrToInt( killEveryStr );

    except
    on EConvertError do begin
    WriteLn('Arguments must be numeric.');
    WriteUsage;
    Exit;
    end;
    end;

    safe := SafeIndex( soldierCount, killEvery );
    WriteLn('Safe index: ' + IntToStr( safe ));
    end.
  • db2 2009-07-29 11:58
    Wongo:
    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;
  • justsomedude 2009-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.


  • Wongo 2009-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.
  • justsomedude 2009-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 Urbanski 2009-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.
  • DesGrieux 2009-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}
  • Chad 2009-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 Moses 2009-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

    DECLARE @i int, @TempSkip int;
    DECLARE @Soldiers table (SoldierNumber int, Dead bit);

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

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

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

    SET @TempSkip = @TempSkip - 1;
    END

    UPDATE @Soldiers
    SET Dead = 1
    WHERE SoldierNumber = @i;

    END

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

    END
  • Wongo 2009-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"...
  • C Sebold 2009-07-29 12:13
    Clojure!

    (defn josephus [num-soldiers skip]
    
    (let [ax (fn [soldiers index]
    (let [real-index (if (> index (count soldiers))
    (rem index (count soldiers))
    index)]
    (concat (nthnext soldiers real-index)
    (take (dec real-index) soldiers))))]
    (loop [alive (range 1 (inc num-soldiers))]
    (if (= (count alive) 1)
    (first alive)
    (recur (ax alive skip))))))


    Most of this function is just the definition for the ax() function.
  • Ed 2009-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 Meexx 2009-07-29 12:17
    Woops, that should be
    unset($roulette[$arrayIndex]);
    not unset($roulette[$value]);

    Why must comments keep erroring out?
  • Wongo 2009-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.
  • Bim Job 2009-07-29 12:23
    Satanicpuppy:
    Addison:
    Alex Mont:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    This is sexy.


    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 Kromann 2009-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 :)
  • MHolt 2009-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
    >
  • samanddeanus 2009-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. Bob 2009-07-29 12:31
    The solution is:

    "Hey everyone, I'll watch the door while you guys sort this out."
  • Wongo 2009-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).
  • db2 2009-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.
  • Ev 2009-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.
  • s0be 2009-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

    77 chars :-)


    My perl approach:

    '@A=(1..$ARGV[0]);while($A[1]){$j=shift@A;push(@A,$j)if(++$i)%$ARGV[1]}print@A

    78 chars :-)
  • Anon 2009-07-29 12:50
    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.


    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.
  • Anon 2009-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.
  • samanddeanus 2009-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.
  • Korkut 2009-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.
  • Srki 2009-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ūns 2009-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];
    }
  • Phil 2009-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.


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

    int StrSurvive (int n, int k)
    {
    char *soldiers;
    int surv, i, pos, count = 0;

    soldiers = (char *) malloc (n+1);
    memset (soldiers, 'O', n);
    soldiers[n] = 0;
    for (pos = 0, surv = n; surv > 1; surv--)
    {
    for (i = 0; ;)
    {
    count++;
    if (soldiers[pos] == 'O')
    if (i == k)
    break;
    else if (++i == k)
    soldiers[pos] = 'X';
    if (++pos == n)
    pos = 0;
    }
    printf ("%s\n", soldiers);
    }
    printf ("Count = %d\n", count);
    return pos;
    }

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

    int LoopSurvive (int n, int k)
    {
    int i, pos = 0;

    for (i = 1; i < n; i++)
    pos = (pos + k) % n;
    return pos;
    }

    void main(void)
    {
    printf ("Pos = %d\n", StrSurvive (41, 3));
    printf ("Pos = %d\n", RecSurvive (41, 3));
    printf ("Pos = %d\n", LoopSurvive (41, 3));
    }

  • Ryan 2009-07-29 13:07
    Here's another Python version that replaces the recursion with a for loop. Same basic solution, but without the potential memory issue.


    def jos(soldiers, skip):
    safe = 0
    for x in xrange(2, soldiers+1):
    safe = (safe + skip) % x
    return safe
  • riotopsys 2009-07-29 13:11
    this should be fitting for the daily wtf

    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;
    }
  • aehiilrs 2009-07-29 13:11
    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.


    Give me n soldiers and an axe.
  • Maurits 2009-07-29 13:13
    Perl Golf. 83 characters including perl -e and the two given arguments 40 and 3. 69 characters between the quotes.

    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
  • Phil 2009-07-29 13:14
    Ops!

    In LoopSurvay, please change

    pos = (pos + k) % n;

    to

    pos = (pos + k) % (i+1);
  • herosp 2009-07-29 13:17
    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. Batch 2009-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
  • Anonymous 2009-07-29 13:27
    In response to Wongo:

    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).
  • nonny nonny 2009-07-29 13:28
    SR:
    d3matt:
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?

    yes... the God class is a singleton...


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


    I thought there needed to be three pointers to the same object.
  • Jean-Paul 2009-07-29 13:33
    Wrote this during my lunch break. Compiles in Turbo Pascal 5.0, uses pointers...


    Program JosephusCircle;
    Type
    Jptr = ^ Jnode;
    Jnode = record
    Number : integer;
    Next : Jptr;
    Prev : Jptr;
    end;
    var
    n : integer;
    s : integer;

    Function MakeCircle(Size : integer) : Jptr;
    var
    lcv : integer;
    lst : Jptr;
    fst : Jptr;
    prv : Jptr;
    begin
    new(fst);
    fst^.Next := nil;
    fst^.Prev := nil;
    fst^.Number := 1;
    prv := fst;
    for lcv := 2 to Size do
    begin
    new(lst);
    prv^.Next := lst;
    lst^.Prev := prv;
    lst^.Next := nil;
    prv := lst;
    lst^.Number := lcv;
    end;
    lst^.Next := fst;
    fst^.Prev := lst;
    MakeCircle := fst;
    end;

    Function Kill(var Doomed : Jptr) : Jptr;
    begin
    Doomed^.Prev^.Next := Doomed^.Next;
    Doomed^.Next^.Prev := Doomed^.Prev;
    Kill := Doomed^.Next;
    Doomed^.Next := nil;
    Doomed^.Prev := nil;
    Dispose(Doomed);
    end;

    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.net 2009-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.
  • Jadawin 2009-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.

  • marco 2009-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_mensch 2009-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.
  • TGV 2009-07-29 13:53
    Anonymous:
    In response to Wongo:

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

    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...
  • mtu 2009-07-29 13:54
    God, that took me so much longer than it should have - and I'm not even proud of the code :-(

    Anyways, here goes my python implementation:

    def josephus(n, s):
    
    soldiers = range(1,n+1)
    position = 0
    counter = 1

    while soldiers.count(0) < n - 1:
    position += 1
    if position == n:
    position = 0

    if not soldiers[position] == 0:
    counter += 1

    if counter == s:
    soldiers[position] = 0
    counter = 0

    soldiers.sort(reverse=True)
    print "The safe spot was number %i of %i." % (soldiers[0], n)
  • PeterW 2009-07-29 13:57
    jos n = rfilter [1..n] !! (2*n-5) 
    
    where rfilter xs = filter (xs ++ rfilter xs)
    filter (x:y:z:rs) = x:y:filter rs


    Just for the fun of it: A Haskell version featuring infinite recursion.
  • Matthew 2009-07-29 14:04
    powershell

    function josephus {
    
    param([int] $soldiers = 41, [int]$skip = 2)
    $alive = [System.Collections.ArrayList] (1 .. $soldiers)
    $dead = $skip
    while ($alive.count -ne 1) {
    $alive.removeAt($dead)
    $dead = ($dead + $skip) % $alive.count
    }
    $alive
    }
  • samanddeanus 2009-07-29 14:06

    (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.
  • neo 2009-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 pattern 2009-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
  • DeLos 2009-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...
  • IdontDoRecursion 2009-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...

  • ikegami 2009-07-29 14:34
    Alex Mont:

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n


    That's easy to make iterative.


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

    # Iterative
    sub J {
    my ($n, $k) = @_;
    my $j = 0;
    $j = ($j + $k) % $_ for 2..$n;
    return $j;
    }

  • Sue D. Nymme 2009-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 Gravity 2009-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. Nymme 2009-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 roth 2009-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!
  • ikegami 2009-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

  • Coyne 2009-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;
    }
  • workmad3 2009-07-29 14:59
    Here's my python one-liner again :)


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


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

    Next challenge is trying it without it being solved with string manipulation.
  • Maurits 2009-07-29 15:10
    Wongo:
    Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".


    Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.
  • Karol Urbanski 2009-07-29 15:13
    Sue D. Nymme:
    Sue D. Nymme:
    I love a good perl golf challenge!

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

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


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

    Awesome :).
  • DF 2009-07-29 15:18
    I wrote a weirdo erlang solution which I think works. I am a functional programming noob and I started looking at erlang yesterday.


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

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

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

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

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

    end.



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

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

    soldier_list(0, List)->
    [0 | List].

  • Matti Helin 2009-07-29 15:21
    Matlab, using inbuilt circular shift function:

    function alive = josephus(n, k)
    
    alive =(1:n)';
    shift = 1-k;
    for h = 1:(n-1)
    alive = circshift(alive, shift);
    alive(1) = [];
    end
  • thc4k 2009-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 ?
  • Nukeme1 2009-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;
  • VinDuv 2009-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
  • Melvis 2009-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

    DECLARE @i int, @TempSkip int;
    DECLARE @Soldiers table (SoldierNumber int, Dead bit);

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

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

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

    SET @TempSkip = @TempSkip - 1;
    END

    UPDATE @Soldiers
    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...
  • scott 2009-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;
    }
    }
  • H2 2009-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;

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

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

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

    # perl Josephus.pl 12 3
    Lucky one: 10
  • Shiftyness 2009-07-29 15:52
    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.";

    }
    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());
    }
    }
  • Stalker 2009-07-29 15:53
    A perhaps not very clean but working solution in F#


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


    (Just discovered F# while reading through the comments to the previous programming problem.)
  • jb somebody 2009-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);
    }

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

    }
    }

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

    return ctr;
    }
    }
  • mduffey 2009-07-29 16:05
    Since 2 people have beaten me to it already....

    unit Josephus;

    interface
    uses Generics.Collections, SysUtils;

    type
    BoolP = ^Boolean;

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

    implementation

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

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

    end.
  • odio 2009-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!
  • byornski 2009-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;
    }
  • MadCow42 2009-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)
  • MadCow42 2009-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)
  • Lerb 2009-07-29 16:21
    Are we going to need a GodFactory, which returns an array of God pointers?
    Horrible pseudocode follows:

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

    and so on
  • Redredredredredred 2009-07-29 16:23
    Too much recursion in here for my taste.

    Okay... first some ruby code (boring)

    def jc(men, skip)
    c=Array.new()
    men.times do |n| c << n end

    i=0
    d=skip
    while c.length > 1
    i = 0 if i==c.length

    d = d - 1
    puts "killed nr. #{c[i]}" if d==0
    c.delete c[i] if d==0
    i=i+1 if d!=0
    d=skip if d==0
    end

    c[0]
    end


    puts jc(12,3)


    And here C with double linked list awesomeness:

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


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

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

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

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

    int i=1;
    int d=skip;

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

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

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


    printf("\n\n");

    return p->nr;
    }

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

    return 0;
    }
  • electrichead 2009-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.
  • Herby 2009-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.
  • reuven 2009-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;
  • PatrickBeebe 2009-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);
    }

    return strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).LastIndexOf('L');
    }
  • Paul Marfleet 2009-07-29 16:47
    Solution in F#:


    let josephus numberOfMen skip =
    let men = [1..numberOfMen]
    let rec doTurn men position =
    match men with
    | hd :: [] -> hd
    | _ ->
    let newPosition = (position + skip) % men.Length
    doTurn (List.mapi (fun i man -> if i = newPosition then 0 else man) men
    |> List.filter(fun man -> man > 0)) (newPosition - 1)
    doTurn men -1
  • Wongo 2009-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 :

    Josephus - Eenie Meenie Miiii...(skip himself)...iiiny Moe.
  • Kevin M 2009-07-29 17:11
    Here's a brute force solution in Java that I don't think anyone else has posted. It follows the problem description by treating a Vector as a circular buffer. Each vector element is the initial index of each soldier.

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

    v.add(v.remove(0));
    v.add(v.remove(0));
    v.remove(0);
    return josephus(v);
    }
  • Code Dependent 2009-07-29 17:13
    Lerb:
    Are we going to need a GodFactory, which returns an array of God pointers?
    Horrible pseudocode follows:

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

    and so on
    GodFactory.getGods(GodFactory.AGNOSTIC) = throw Unknown Exception
  • JHolland 2009-07-29 17:16
    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));
    }

    print "josephus(12, 3) = ", josephus(12, 3), "\n";

  • God 2009-07-29 17:22
    Lerb:
    Are we going to need a GodFactory, which returns an array of God pointers?
    Horrible pseudocode follows:

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

    and so on


    Zeus is Greek not Roman... that would be Jupiter
  • Jedi 2009-07-29 17:27
    *v,n;main(s,f){for(n=1;atoi(1[v=f])-s;n=(n+atoi(2[v=f]))%++s);printf("%d\n",n);}
  • Still Not Tim 2009-07-29 17:35
    So 39 soldiers were done for, but Titus escaped.

    All these comments, and not one pointing out the irony of using Python to show... erm...
    the Romans didn't do for Titus.
  • Oscar Olim 2009-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. Batch 2009-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.
  • Gary Hall 2009-07-29 17:55
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);


    Monotheist, ey?


    DeityRepo.FindBySpecialisation(DeitySpecialisations.War).SortOut(soldiers);
  • Dr. Batch 2009-07-29 17:57
    find and replace "servivor" with "survivor". How embarrassing.
  • Michael van der Gulik 2009-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. "


  • samanddeanus 2009-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))))))

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

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

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

    and so on


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

    Help?
  • Code Dependent 2009-07-29 18:10
    Comp Sci Student:
    Lerb:
    Are we going to need a GodFactory, which returns an array of God pointers?
    Horrible pseudocode follows:

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

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

    Help?
    Frisbeetarian isn't working, either... it keeps getting stuck somewhere.
  • corvi 2009-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
  • samanddeanus 2009-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 M 2009-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. Batch 2009-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.
  • dvrslype 2009-07-29 18:31
    public class JosephusCircle {

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

    }
  • phil 2009-07-29 18:43
    Just for fun, here's a plot of the solutions for
    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.
  • Iago 2009-07-29 18:43
    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.

    Nice.

    I can see two ways to save another character:
    $k=pop;map$s=($s+$k)%$_,1..pop;say$s+1
    or
    $k=pop;($s+=$k)%=$_ for 1..pop;say$s+1
    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:
    ($s+="@ARGV")%=$_ for 1..pop;say$s+1
    called with e.g. 3 40 rather than 40 3.
  • Edinburgh Mike 2009-07-29 18:57
    Reasonably good Python solution.

    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!
  • Qwertyuiopas 2009-07-29 19:02
    PHB method:

    "
    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.
    "
  • mol1111 2009-07-29 19:12
    ZX Spectrum BASIC version.

    Screenshot for finished program (soldiers=10,
    skip=2):


    TAP file for emulator.

       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 .
  • ponky 2009-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 Dean 2009-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;

    }

  • Utunga 2009-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.
  • Goglu 2009-07-29 21:00
    If it were, many wars would have been avoided...
  • bwross 2009-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

  • Veltyen 2009-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 Quark 2009-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 Stracke 2009-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)
  • Chris 2009-07-29 22:08
    Okay, that does it-- Almost killed me. Too funny.
  • John Stracke 2009-07-29 22:11
    Addison:
    Alex Mont:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    This is sexy.

    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).
  • Paddles 2009-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.

    Sample output:

    C:\Temp>gawk -f josephus.awk -vVERBOSE=1
    12
    vvvvvvvvv^vv
    10
    12 3
    vvvvvvvvv^vv
    10
    12 5
    ^vvvvvvvvvvv
    1
    14
    v^vvvvvvvvvvvv
    2


    C:\Temp>


    And the code...


    # josephus.awk
    # set VERBOSE to 1 for a very-low-budget snuff ASCII-art snuff movie.

    NF == 0 {exit; }
    NF >= 2 { interval = int($2); }
    NF == 1 || interval <0 { interval = 3;}

    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,"^");
    }

  • horuskol 2009-07-29 22:34
    My PHP offering:

    function allbutone($num, $skip) {
    

    $circle = array();
    for ($i = 0; $i < $num; $i++) {

    $circle[$i] = $i+1;

    }

    $step = $skip - 1;


    $idx = $step;
    while (sizeof($circle) > 1) {

    do {

    unset($circle[$idx]);
    sort($circle);
    $idx += $step;

    } while ($idx < sizeof($circle) && sizeof($circle) > 1);

    while ($idx >= sizeof($circle)) {

    $idx -= sizeof($circle);

    }

    }

    return $circle[0];

    }

    $tests = array(
    array(12, 3),
    array(40, 3),
    array(41, 3),
    array(5, 1),
    );

    foreach ($tests as $t) {

    echo $t[0] . "\t" . $t[1] . "\t" . allbutone($t[0], $t[1]) . "\n";

    }
  • Strilanc 2009-07-29 22:41
    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.
  • Anonymous Coward 2009-07-29 22:43
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?

    He's a singleton instance. That way, you can still pass him into any CargoCultFollowing(IGod g) function using the IGod interface.
  • Anonymous Coward 2009-07-29 22:48
    John Stracke:
    Addison:
    Alex Mont:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



    This is sexy.

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


    What are you smoking?


    >>> def j(n,k):
    ... if(n==1): return 0
    ... else: return (j(n-1,k)+k)%n
    ...
    >>> j(12,3)
    9
    >>>

  • JayC 2009-07-29 23:03
    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);
  • xeno 2009-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";

    function josephs_circle($n = 40, $skip = 3)
    {
    $num_rows = ceil($n / $skip) + 1;
    $row = array_pad(array(), $n, '');
    $grid = array_pad(array(), $num_rows, $row);

    $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.
  • Sterge 2009-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;

    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!");
    }
    }
  • Ransom 2009-07-29 23:17
    Not counting my linked list implementation - not as fast as the functional ones - but maybe a little more comprehensible


    def josephl(num_peeps, num_skip)
    ll = LinkList.new
    num_peeps.times {|i| ll.append(i)}
    iterator = ll.head

    (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
  • Christian 2009-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

    arrPopulation(intPrevious) = arrPopulation(intIndex)
    intIndex = arrPopulation(intPrevious)
    Loop

    JosephusSafeSpot = intIndex
    End Function


    At least it works.
  • Stalker 2009-07-29 23:35
    Dr. Batch:
    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.
  • SurturZ 2009-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
  • SurturZ 2009-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
  • Firestryke31 2009-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
  • robsonde 2009-07-30 01:13

    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.




  • Stalker 2009-07-30 01:16
    Didn't feel right to pack all soldiers into one process, so here they each get their own.


    #include <mpi.h>

    #include <stdio.h>

    #define SKIP 3

    typedef struct _Axe
    {
    int lastToHold;
    int counter;
    int goAway;
    } Axe;

    int main( int argc, char** argv )
    {
    int soldierId, numSoldiers, stillAlive, neighborR, neighborL;
    Axe axe;
    MPI_Status status;

    MPI_Init( &argc, &argv );

    MPI_Comm_rank( MPI_COMM_WORLD, &soldierId );
    neighborR = soldierId - 1;
    MPI_Comm_size( MPI_COMM_WORLD, &numSoldiers );
    neighborL = (soldierId + 1) % numSoldiers;

    stillAlive = 1;
    if( soldierId == 0 )
    {
    neighborR = numSoldiers - 1;
    axe.counter = SKIP - 1;
    axe.lastToHold = 0;
    axe.goAway = 0;
    printf( "Axe starting to go round\n" );
    printf( "[%d] Sending to %d\n", soldierId, neighborL );
    MPI_Send( &axe, 3, MPI_INT, neighborL, 0, MPI_COMM_WORLD );
    }

    while( 1 )
    {
    printf( "[%d] Waiting to receive from %d\n", soldierId, neighborR );
    MPI_Recv( &axe, 3, MPI_INT, neighborR, 0,
    MPI_COMM_WORLD, &status );

    if( axe.lastToHold == soldierId )
    {
    // Only one left
    axe.goAway = 1;
    MPI_Send( &axe, 3, MPI_INT, (soldierId + 1) % numSoldiers, 0,
    MPI_COMM_WORLD );
    printf( "[%d] I won!\n", soldierId );
    break;
    }
    if( stillAlive && --axe.counter == 0 )
    {
    // Our turn to die
    axe.counter = SKIP;
    stillAlive = 0;
    printf( "[%d] Oh noes! I died!\n", soldierId );
    }
    if( stillAlive )
    {
    axe.lastToHold = soldierId;
    }
    printf( "[%d] Sending to %d\n", soldierId, neighborL );
    MPI_Send( &axe, 3, MPI_INT, neighborL, 0,
    MPI_COMM_WORLD );
    if( axe.goAway )
    {
    printf( "[%d] Game over\n", soldierId );
    break;
    }
    }

    MPI_Finalize();

    return( 0 );
    }

    Not really how MPI is supposed to be used, but it works. At least for smaller values, falls apart with larger.
  • ikegami 2009-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.com 2009-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

    Cheers, bob
  • bynio 2009-07-30 02:01
    Scope:
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?


    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.
  • Chris 2009-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];
    }
  • xeno 2009-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?
  • BTM 2009-07-30 02:27
    I'd say it even should ba Abstract ;-)
  • BTM 2009-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 ;-)
  • xeno 2009-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.
  • xeno 2009-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.com 2009-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.com 2009-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
  • xeno 2009-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.
  • KnoNoth 2009-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 :-)
  • tster 2009-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

  • tster 2009-07-30 03:33
    workmad3:
    def joph(n):

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

    WTF?
  • Daniel Browne 2009-07-30 03:51
    I didnt have time to read all the comments so sorry if this is what has already been done...

    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
  • xeno 2009-07-30 03:58
    bobtherriault@mac.com:
    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";

    function josephs_circle($n = 40, $skip = 3)
    {
    $row = array_pad(array(), $n, '');
    $grid = array($row);

    $x = 0;
    $y = 0;
    $kills = 0;
    $s = $skip;

    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!
  • Thomas 2009-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 user 2009-07-30 04:25
    Last 2 man standing, one of them has the axe, why the hell would he kill himself?
  • reol 2009-07-30 04:38
    LOL!
  • FST777 2009-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
  • ThiOz 2009-07-30 06:02
    I think this could be done quicker or with less code but i guess it's solid

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

    }
  • TheNewOne 2009-07-30 06:03
    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 />';
    }
    ?>
  • Josephus 2009-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)
  • Anonymous 2009-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. Nymme 2009-07-30 06:21
    If you call the Frisbeetarian object with a float, it just hangs....
  • SpaceDog 2009-07-30 06:36
    Have one in sed with some help from bash.

    #!/bin/bash
    usage() {
    echo "Usage: shooter.sh <people> <shootevery>"
    exit
    }

    [ "$1" != "" ] && [ "$2" != "" ] || usage
    echo "$1$2" | grep -qv '[^0-9]' || usage
    [ "$1" -gt 0 ] && [ "$2" -gt 0 ] || usage

    PERSON="{[0-9][0-9]*}"
    PEOPLE=$1
    while [ $PEOPLE -ne 0 ]; do
    INPUT="{${PEOPLE}}${INPUT}"
    PEOPLE=$((PEOPLE - 1))
    done

    SHOOTEVERY=$2
    while [ $SHOOTEVERY -ne 1 ]; do
    SKIP=${SKIP}${PERSON}
    SHOOTEVERY=$((SHOOTEVERY - 1))
    done

    echo
    echo "Line up: ${INPUT}, firing on $2"
    echo

    echo "$INPUT" | sed -e 'p
    :cull
    /^'"${PERSON}"'$/boneleft
    /'"${SKIP}"''"${PERSON}"'/{s/\('"${SKIP}"'\)'"${PERSON}"'\(.*\)/\2\1/p;tcull}
    /^'"${PERSON}"'$/boneleft
    :clone
    /'"${SKIP}"''"${PERSON}"'/!{s/\(.*\)/\1\1/;tclone}
    s/\('"${SKIP}"'\)\('"${PERSON}"'\)/x\2x\1/
    :bury
    s/x\('"${PERSON}"'\)x\(.*\)\1/x\1x\2/;tbury
    s/x'"${PERSON}"'x//;
    :declone
    s/\('"${PERSON}"'\)\(.*\)\(\1\)/\1\2/;tdeclone;p
    :oneleft
    /^'"${PERSON}"'$/{s/{\('".*"'\)}/Winner: \1/;tend}
    bclone
    :end'

  • Bas 2009-07-30 06:36
    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
  • Queex 2009-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 Stracke 2009-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).


    What are you smoking?


    >>> def j(n,k):
    ... if(n==1): return 0
    ... else: return (j(n-1,k)+k)%n
    ...
    >>> j(12,3)
    9
    >>>



    Uh...aw, bleep. I ran J(3,12) instead.

    Sorry. You'd think I'd've learned not to flame after 10PM by now...
  • Josephus 2009-07-30 08:03
    Python one-liner:

    josephus = lambda n, s, r=None, i=0: josephus(n, s, range(n)) if r is None else (r[0] + 1 if len(r) == 1 else josephus(n,s,r[:(i + s - 1) % len(r)] + r[(i + s - 1) % len(r) + 1:], (i + s - 1) % len(r)))
    

    print josephus(12,3)
  • DaveK 2009-07-30 08:09
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    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.

  • lamcro 2009-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
  • asd 2009-07-30 08:39
    javascript with caching to make it run fast ;)


    function j(n,k){
    if(j[n] != undefined && j[n][k] != undefined){
    return j[n][k];
    }
    if(n==1){
    return 0;
    }
    if(j[n] == undefined){
    j[n] = [];
    }
    var jj = (j(n-1,k) + k) % n;
    j[n][k] = jj;
    return jj;

    };
  • Severity One 2009-07-30 08:59
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    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.
  • KukkerMan 2009-07-30 08:59

    let rec josephus soldiers skips = if soldiers < 2 then 0 else (josephus (soldiers-1) skips + skips) mod soldiers;;
  • Wongo 2009-07-30 08:59
    Anonymous:
    In response to Wongo:

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


    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 Manuka 2009-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 silver 2009-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;
    }

    // System.out.println("idx: " + Integer.toString(idx) +
    // " / counter: " + Integer.toString(counter) +
    // " / remaining: " + Integer.toString(remaining) +
    // " field: " + toString(people));
    return idx+1;
    } // findSpot()

    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");
    }
    }
  • J 2009-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

    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.
  • Wongo 2009-07-30 09:11
    TGV:
    Anonymous:
    In response to Wongo:

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

    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...
  • EnterpriseSolutionsLTD 2009-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();

    leftToSkip = skipAmount;
    }
    }
    else
    {
    continue;
    }
    } while (soldierList.Where(soldier => soldier.Vitality == Vitality.Alive).Count() > 1);

    return soldierList.IndexOf(soldierList.Single(soldier => soldier.Vitality == Vitality.Alive));
    }
    }
  • Wongo 2009-07-30 09:42
    xeno:
    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.
  • Wongo 2009-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 ++$_;
    }
  • DaveGamble 2009-07-30 10:44
    First! (for 4, 9, 31, 70, 105, 355, 799, 1798, 2697 etc soldiers...)

    (Sorry, couldn't resist.)

    First off, iterative Josephus, O(n), in C:

    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.
  • Damage 2009-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;
    }

    int deathCount = (((skipCount < 0) ? (skipCount * -1) : skipCount)) + 1;

    ArrayList<Integer> livingSoldiers = new ArrayList<Integer>();
    ArrayList<Integer> livingSoldiersBackwards = new ArrayList<Integer>();

    // build cirle
    {
    livingSoldiersBackwards.add(new Integer(1));

    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;

    i--;
    }
    }
    }
    }

    return ((skipCount < 0) ? livingSoldiersBackwards.get(livingSoldiers.get(0).intValue() - 1) : livingSoldiers.get(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
  • jane 2009-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 ?


    round pi('s) will kill you?
  • Paul N 2009-07-30 13:02
    Here are 4 variations in C#


    private static int Josephus1(int numberOfSoldiers, int soldiersToSkip)
    {
    char livingSoldier = '|';
    string deadSoldier = "_";
    string circleOfSoldiers = string.Empty.PadLeft(numberOfSoldiers, livingSoldier);
    int indexOfAxe = -1;
    while (circleOfSoldiers.IndexOf(livingSoldier) != circleOfSoldiers.LastIndexOf(livingSoldier))
    {
    for (int skippedSoldiers = 0; skippedSoldiers <= soldiersToSkip; skippedSoldiers++)
    {
    indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier, indexOfAxe + 1);
    if (indexOfAxe == -1)
    {
    indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier);
    }
    }
    circleOfSoldiers = circleOfSoldiers.Remove(indexOfAxe, 1).Insert(indexOfAxe, deadSoldier);
    }
    return circleOfSoldiers.IndexOf(livingSoldier) + 1;
    }

    private static int Josephus2(int numberOfSoldiers, int soldiersToSkip)
    {
    Queue<int> circleOfSoldiers = new Queue<int>();
    for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
    {
    circleOfSoldiers.Enqueue(soldier);
    }
    while (circleOfSoldiers.Count > 1)
    {
    for (int skip = 1; skip <= soldiersToSkip; skip++)
    {
    circleOfSoldiers.Enqueue(circleOfSoldiers.Dequeue());
    }
    int deadSoldier = circleOfSoldiers.Dequeue();

    }
    return circleOfSoldiers.Dequeue();
    }

    private static int Josephus3(int numberOfSoldiers, int soldiersToSkip)
    {
    List<int> circleOfSoldiers = new List<int>();
    for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
    {
    circleOfSoldiers.Add(soldier);
    }
    int indexOfDeadSoldier = 0;
    while (circleOfSoldiers.Count > 1)
    {
    indexOfDeadSoldier += soldiersToSkip;
    while (indexOfDeadSoldier >= circleOfSoldiers.Count || indexOfDeadSoldier < 0)
    {
    if (indexOfDeadSoldier >= circleOfSoldiers.Count)
    {
    indexOfDeadSoldier -= circleOfSoldiers.Count;
    }
    if (indexOfDeadSoldier < 0)
    {
    indexOfDeadSoldier += circleOfSoldiers.Count;
    }
    }
    circleOfSoldiers.RemoveAt(indexOfDeadSoldier);
    }
    return circleOfSoldiers[0];
    }

    private static int Josephus4(int numberOfSoldiers, int soldiersToSkip)
    {
    LinkedList<int> circleOfSoldiers = new LinkedList<int>();

    for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
    {
    circleOfSoldiers.AddLast(soldier);
    }
    LinkedListNode<int> currentSoldierWithAxe = circleOfSoldiers.First;
    while (circleOfSoldiers.Count > 1)
    {
    for (int passAxe = 0; passAxe < soldiersToSkip; passAxe++)
    {
    currentSoldierWithAxe = currentSoldierWithAxe.Next;
    if (currentSoldierWithAxe == null)
    {
    currentSoldierWithAxe = circleOfSoldiers.First;
    }
    }
    LinkedListNode<int> deadSoldier = currentSoldierWithAxe;
    currentSoldierWithAxe = deadSoldier.Next;
    circleOfSoldiers.Remove(deadSoldier);
    if (currentSoldierWithAxe == null)
    {
    currentSoldierWithAxe = circleOfSoldiers.First;
    }
    }
    return currentSoldierWithAxe.Value;
    }
  • Still Not Tim 2009-07-30 13:29
    Wongo:

    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... :)
  • SteamBoat 2009-07-30 13:30
    The position that Josephus took was as the executioner.

    MArk B.
  • halcyon1234 2009-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

    :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

  • Schneau 2009-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
  • Schneau 2009-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

    :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



    mad props
  • Maurits 2009-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)
  • rfdb 2009-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!
  • mol1111 2009-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).
    And, all in all, maybe he just got lucky? :)
  • Mathieu Savage 2009-07-30 15:10
    In PHP, with a nice visual representation

    <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 } ?>
  • Code Dependent 2009-07-30 16:01
    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.
  • kastein 2009-07-30 17:07
    Josephus:
    Last
    ... best "first" post ever. Code Dependent, eat your heart out! :P
  • RaspenJho 2009-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
  • RaspenJho 2009-07-30 17:42
    Interesting pattern when you line up the plotted points of the "safe spot" in varying numbers of soldiers...


    1
    12
    123
    1234
    12345
    123456
    1234567
    12345678
    123456789
    1234567890
    12345678901
    123456789012
    1234567890123
    12345678901234
    123456789012345
    1234567890123456
  • Justin Drury 2009-07-30 17:57
    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 Vance 2009-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;
    }
  • Shadikka 2009-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.

    Example XML:
    <?xml version="1.0" encoding="UTF-8"?>
    
    <!-- XSLT Josephus' Circle ~ (C) Shadikka 2009 -->
    <?xml-stylesheet type="text/xsl" href="josephus.xsl"?>

    <circle>
    <soldiers>29</soldiers>
    <skip>2</skip>
    <radius>90</radius>
    </circle>


    And here's the XSLT:
    <?xml version="1.0" encoding="UTF-8"?>
    
    <xsl:stylesheet version="2.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:math="http://exslt.org/math"
    xmlns="http://www.w3.org/1999/xhtml">

    <!-- XSLT Josephus' Circle ~ (C) Shadikka 2009 -->

    <xsl:output method="html" indent="no" version="4.0" />

    <xsl:variable name="pi" select="3.141592653589793" />

    <xsl:template match="/circle">
    <html>
    <head>
    <title>XSLT Josephus' Circle</title>
    <style type="text/css">
    BODY { background-color: white; }
    DIV { border: 1px dashed black; }
    H1 { font: bold 1.2em sans-serif; color: black; text-align: center; }
    H2 { font: bold 1em sans-serif; color: black; text-align: center; }
    P { font: bold 1em monospace; text-align: center; }
    .d { color: red; }
    .a { color: green; }
    .copy { font: 0.7em sans-serif; text-align: center; }
    </style>
    </head>

    <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 &lt; 2 or skip &lt; 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>

    <xsl:template name="josephus-circle-init">
    <xsl:param name="string" />

    <xsl:choose>
    <xsl:when test="string-length($string) = soldiers">
    <xsl:call-template name="josephus-circle">
    <xsl:with-param name="alive" select="$string" />
    <xsl:with-param name="pos" select="1" />
    </xsl:call-template>
    </xsl:when>
    <xsl:otherwise>
    <xsl:call-template name="josephus-circle-init">
    <xsl:with-param name="string" select="concat($string, 'a')" />
    </xsl:call-template>
    </xsl:otherwise>
    </xsl:choose>
    </xsl:template>

    <xsl:template name="josephus-circle">
    <xsl:param name="alive" />
    <xsl:param name="pos" />

    <xsl:choose>
    <xsl:when test="count(index-of(string-to-codepoints($alive), 97)) = 1">
    <p>The survivor is soldier #<xsl:value-of select="index-of(string-to-codepoints($alive), 97)" />.</p>
    </xsl:when>
    <xsl:otherwise>
    <xsl:call-template name="josephus-step">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="$pos" />
    <xsl:with-param name="past" select="0" />
    </xsl:call-template>
    </xsl:otherwise>
    </xsl:choose>
    </xsl:template>

    <xsl:template name="josephus-step">
    <xsl:param name="alive" />
    <xsl:param name="pos" />
    <xsl:param name="past" />

    <xsl:choose>
    <xsl:when test="$pos > soldiers">
    <xsl:call-template name="josephus-step">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="1" />
    <xsl:with-param name="past" select="$past" />
    </xsl:call-template>
    </xsl:when>

    <xsl:when test="substring($alive, $pos, 1) = 'd'">
    <xsl:call-template name="josephus-step">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="$pos+1" />
    <xsl:with-param name="past" select="$past" />
    </xsl:call-template>
    </xsl:when>

    <xsl:when test="$past = skip">
    <xsl:variable name="new_alive" select="concat(substring($alive, 1, $pos - 1), 'd', substring($alive, $pos + 1, string-length($alive)-$pos))" />
    <xsl:call-template name="josephus-draw">
    <xsl:with-param name="alive" select="$new_alive" />
    <xsl:with-param name="y" select="count(index-of(string-to-codepoints($alive), 100))" />
    </xsl:call-template>
    <xsl:call-template name="josephus-circle">
    <xsl:with-param name="alive" select="$new_alive" />
    <xsl:with-param name="pos" select="$pos" />
    </xsl:call-template>
    </xsl:when>

    <xsl:otherwise>
    <xsl:call-template name="josephus-step">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="$pos + 1" />
    <xsl:with-param name="past" select="$past + 1" />
    </xsl:call-template>
    </xsl:otherwise>
    </xsl:choose>
    </xsl:template>

    <xsl:template name="josephus-draw">
    <xsl:param name="alive" />
    <xsl:param name="y" />

    <xsl:variable name="xpos" select="105 + (3*radius) * ($y mod 3)" />
    <xsl:variable name="ypos" select="floor($y div 3) * (3*radius) + radius + 100" />
    <xsl:element name="p">
    <xsl:attribute name="style">position:absolute;left:<xsl:value-of select="$xpos - 5" />px;top:<xsl:value-of select="$ypos" />px;</xsl:attribute>
    #<xsl:value-of select="$y + 1" />
    </xsl:element>
    <xsl:call-template name="josephus-draw-soldier">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="1" />
    <xsl:with-param name="ypos" select="$ypos" />
    <xsl:with-param name="xpos" select="$xpos" />
    <xsl:with-param name="step" select="(2 * $pi) div string-length($alive)" />
    </xsl:call-template>
    </xsl:template>

    <xsl:template name="josephus-draw-soldier">
    <xsl:param name="alive" />
    <xsl:param name="pos" />
    <xsl:param name="ypos" />
    <xsl:param name="xpos" />
    <xsl:param name="step" />

    <xsl:variable name="angle" select="($pos - 1) * $step" />
    <xsl:variable name="ypos2" select="round($ypos + math:sin($angle) * radius)" />
    <xsl:variable name="xpos2" select="round($xpos + math:cos($angle) * radius)" />
    <xsl:variable name="class" select="substring($alive, $pos, 1)" />

    <xsl:element name="p">
    <xsl:attribute name="class">
    <xsl:value-of select="$class" />
    </xsl:attribute>
    <xsl:attribute name="style">position:absolute;top:<xsl:value-of select="$ypos2" />px;left:<xsl:value-of select="$xpos2" />px;</xsl:attribute>
    <xsl:choose>
    <xsl:when test="$class = 'a'">
    <xsl:value-of select="$pos" />
    </xsl:when>
    <xsl:otherwise>X</xsl:otherwise>
    </xsl:choose>
    </xsl:element>

    <xsl:if test="$pos &lt; string-length($alive)">
    <xsl:call-template name="josephus-draw-soldier">
    <xsl:with-param name="alive" select="$alive" />
    <xsl:with-param name="pos" select="$pos + 1" />
    <xsl:with-param name="ypos" select="$ypos" />
    <xsl:with-param name="xpos" select="$xpos" />
    <xsl:with-param name="step" select="$step" />
    </xsl:call-template>
    </xsl:if>
    </xsl:template>

    </xsl:stylesheet>


    Addendum (2009-07-31 02:21):
    In light of the other XSLT solution, I might add that this is the brute-force solution. :)
  • John Stracke 2009-07-30 18:11
    <?xml version="1.0" encoding="UTF-8" standalone="no"?>
    
    <xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns="http://www.w3.org/2000/html">

    <xsl:template match="/many/j">

    <html>
    <head>
    <title>Josephus</title>
    </head>
    <body>
    <h1>Josephus</h1>

    <xsl:variable name="n"><xsl:value-of select="./@n"/></xsl:variable>
    <xsl:variable name="k"><xsl:value-of select="./@k"/></xsl:variable>

    <xsl:function name="j">
    <xsl:param name="n"/>
    <xsl:param name="k"/>
    <xsl:choose>
    <xsl:when test="$n=1">
    <xsl:sequence select="0"/>
    </xsl:when>
    <xsl:otherwise>
    <xsl:sequence select="(j($n-1,$k)+$k) mod $n"/>
    </xsl:otherwise>
    </xsl:choose>
    </xsl:function>

    <p><xsl:value-of select="$n"/></p>
    <p><xsl:value-of select="$k"/></p>
    <xsl:value-of select="j($n,$k)"/>
    </body>
    </html>
    </xsl:template>
    </xsl:stylesheet>
  • JettingSpike 2009-07-30 18:45
    Brute Force C#


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

    Original Python:

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n


    Port to C without recursivity:


    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 Entity 2009-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 Tim 2009-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.

    and the way to do that in Python...

    is to be A LUMBERJACK
  • curtmack 2009-07-31 00:41
    A somewhat juvenile Perl solution.

    #!/usr/bin/perl
    
    sub josephus {
    ($m, $s) = @_;
    @l= 1..
    $m; $c=0;
    $n=$m; $k=1;
    while ($n>
    1){ do{
    $c= ($c
    +1)% $m}
    until $l
    [$c]; $k++;
    if ($k
    == $s)
    {$k =0;
    $l [$c]
    =0; $n
    --; }}
    $c ++
    until $l[$c];$c
    }
    $r = &josephus ( (@ARGV)[0,1] );
    print "$r\n";


    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 M 2009-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);
    }
    }
    }
  • HV 2009-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)
  • StinoFasto 2009-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);

    Shoot(theCircleOfDeath, 0, soldiersToSkip);
    return theCircleOfDeath.IndexOf(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);
    }
  • Shadikka 2009-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.
  • gvainfo 2009-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

    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 ;-)
  • Gerben 2009-07-31 05:40
    public static int Josephus(int number, int skip) {
    return number == 1 ? 0 : (Josephus(number - 1, skip) + skip) % number;
    }
  • Code Dependent 2009-07-31 09:54
    kastein:
    Josephus:
    Last
    ... best "first" post ever. Code Dependent, eat your heart out! :P
    Dang!
  • Stéphane 2009-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.
    ...


  • Louis 2009-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.
  • causa 2009-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);

    first_soldier = soldier(0,40,0);
    first_soldier.step(2, 2);


    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.
  • dbkk 2009-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.
  • quibus 2009-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.
  • mol1111 2009-07-31 18:13
    Never; saw; so; many; semicolons; in; a; Python; program; :-)
    But if it's your first Python program that's OK.
  • causa 2009-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. >.<
  • John Stracke 2009-07-31 18:40
    John Stracke:
    <?xml version="1.0" encoding="UTF-8" standalone="no"?>


    ...no, that gives the wrong answer.
  • Dean Mitchell 2009-07-31 19:45
    <?php
    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!";

    }
    ?>
  • Wongo 2009-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! :)
  • Andrew 2009-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 move (Int $spaces) {
    $self->position(
    ($self->position + $spaces) % $self->soldiers->length
    );
    }

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

    method josephus {
    while ($self->soldiers->length > 1) {
    $self->move( $self->stride );
    $self->kill;
    }
    return $self->soldiers->[0];
    }
    }


    Invoke as
    $safe_pos = Josephus->new(size => 12, stride => 3)->josephus
  • the_duke 2009-08-01 02:35
    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.
  • naren 2009-08-01 03:32
    javascript.


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

    for(i=1; i <= circle_size; i++)
    circle.push(i);

    while(circle.length > 1) {
    value = circle.shift();
    if(counter == skip_by)
    counter = 1;
    else {
    counter++;
    circle.push(value);
    }
    }
    alert(circle.shift());
    }
  • MF 2009-08-01 04:59
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);

    You're assuming God is a singleton ;)
  • pjt33 2009-08-01 05:36
    Minski register machine:

    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.
  • plaga 2009-08-01 06:11
    MF:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);

    You're assuming God is a singleton ;)


    When, in fact, god is a simpleton.
    ;)
  • Josephus 2009-08-01 09:49
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);


    Assuming you only believe in one God... unfortunately this problem has been outsourced to India so this code is no good.
  • Chris Judge 2009-08-01 16:37
    Observer:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



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

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

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



    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.
  • Mithious 2009-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.
  • pjt33 2009-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.)
  • savar 2009-08-02 10:13
    MF:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);

    You're assuming God is a singleton ;)


    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.
  • Brian Hartvigsen 2009-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()

    class Soldier(object):
    def __init__(self, idx, name, next_soldier = None, prev_soldier = None):
    self.__next = next_soldier
    self.__prev = prev_soldier
    self.__idx = idx
    self.__name = name

    def __str__(self): return self.__name

    def get_next(self): return self.__next
    def set_next(self, next_soldier): self.__next = next_soldier
    next = property(get_next, set_next)

    def get_prev(self): return self.__prev
    def set_prev(self, prev_soldier): self.__prev = prev_soldier
    prev = property(get_prev, set_prev)

    @property
    def index(self): return self.__idx

    def die(self):
    self.prev.next = self.next
    self.next.prev = self.prev
    return self.next


    def Josephus(number_of_soldiers=12, soldiers_to_skip=3, deaths=False):
    root_soldier = None
    node_soldier = None

    for i in range(number_of_soldiers):
    next_soldier = Soldier(i, names[i].strip())
    if root_soldier == None:
    root_soldier = next_soldier
    else:
    node_soldier.next = next_soldier
    next_soldier.prev = node_soldier

    node_soldier = next_soldier

    root_soldier.prev = node_soldier
    node_soldier.next = root_soldier
    node_soldier = None

    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

    root_soldier.die()

    if deaths: print sformat % (root_soldier.index + 1, 'DIES', root_soldier)
    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
  • amet 2009-08-02 14:02
    Chris Judge:
    Observer:

    Thus our formula is (code in Python):

    def J(n,k):
    if(n==1)
    return 0
    else
    return (J(n-1,k)+k)%n



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

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

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



    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.
  • Indrora 2009-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
  • Kogle 2009-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;
    }
  • greyfade 2009-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? :)
  • death 2009-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 Zaczkiewicz 2009-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);
    }
  • Manu 2009-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;

    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.
  • Manu 2009-08-03 09:50
    Damn. Forgot BBCodes, also forgot to set 3 to k. fix:

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

    for (int numbers = 1; numbers <= n; numbers++)
    {
    safespot += k;
    while (safespot > numbers)
    {
    safespot -= numbers;
    }
    }

    return safespot;
    }
  • 14mWtF 2009-08-03 09:54
    most of the solutions are wtfs...

    josephus needs to be the 40th man
  • inky 2009-08-03 10:00
    Quick Python solution:

    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]

    >>> print(josephus())
    
    top, 2, 3, 4, 5, ..., 37, 38, 39, 40
    top, 2, 4, 5, ..., 37, 38, 39, 40
    ...
    top, 13, 19, 28, 32
    top, 13, 28, 32
    13, 28, 32
    13, 28
    28
  • Paul N 2009-08-03 10:49
    dbkk:
    > 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.

    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.
  • pjt33 2009-08-03 11:07
    Manu:
    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.

    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.
  • Wladimir Palant 2009-08-03 11:44
    Something for the Perl haters here:

    #!/usr/bin/perl
    

    @soldiers = (1..$ARGV[0]);
    @soldiers = grep {++$i % $ARGV[1]} @soldiers while @soldiers > 1;
    print @soldiers;

  • n00b 2009-08-03 14:58
    How many WTFs are in my PHP code?
    <?php
    
    function theLastOneAlive($soldiers, $skip){
    for($i=1; $i<=$soldiers; $i++){
    $arr[$i]=$i;
    }
    $key=0;
    for($i=0; $i<$soldiers; $i++){
    unset($alive);
    foreach($arr as $v){
    if($v!==null)
    $alive[]=$v;
    }
    $key=$key+$skip-1;
    $key=$key%count($alive);
    $arr[array_search($alive[$key], $arr)]=null;
    }
    return $alive[0];
    }
    echo theLastOneAlive(12,3);
    ?>
  • Leilock 2009-08-03 17:24
    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);

    safeIndex = JosephusCircle.FindSafeSpot(17, 3);
    Assert.AreEqual(4, safeIndex);

    safeIndex = JosephusCircle.FindSafeSpot(40, 2);
    Assert.AreEqual(27, safeIndex);
    }
  • Darryl Dixon 2009-08-03 23:03
    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 Dixon 2009-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])

    ;)
  • Snakiej 2009-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;
    }
    }

    return noOfTrue;
    }
    }
    }
  • David D. Davidson 2009-08-04 11:59
    Anonymous:
    In response to Wongo:

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


    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)
  • zzo38 2009-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:
    #~

  • CJBV 2009-08-04 19:52
    Somebody already put one similar, but here it goes

    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);
    }
    }
  • Mark Bohan 2009-08-05 07:05
    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 N 2009-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
  • mol1111 2009-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.
  • serious 2009-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;
    };

    int main(int argc, char** argv)
    {
    if (argc <= 2) {
    printf("USAGE: %s <soliders> <skip>\n", argv[0]);
    } else {
    josepus(atoi(argv[1]), atoi(argv[2]));
    }

    return 0;
    }


    unsigned int josepus(unsigned int soliders, unsigned int skip)
    {
    unsigned int i;
    unsigned int deaths = 0;
    struct solider* solfirst;
    struct solider* solnew;
    struct solider* sol;

    solfirst = (struct solider*) calloc(1,sizeof(struct solider));
    solfirst->id = 0;
    solfirst->dead = 0;

    sol = solfirst;

    for (i=1; i<soliders; i++) {
    solnew = (struct solider*) calloc(1, sizeof(struct solider));

    solnew->id = i;
    solnew->dead = 0;

    sol->next = solnew;
    sol = solnew;
    }

    sol->next = solfirst;

    sol = solfirst;
    i=0;

    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 Mamo 2009-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 Mamo 2009-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 Ladd 2009-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
  • Someone 2009-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.

    Here's the code, I used PNGwriter library (pngwriter.sourceforge.net):


    #include <pngwriter.h>

    void make_png(int s_max, int n_max, const char* filename)
    {
    int safe_index = 0;
    double r,g,b; // colors

    pngwriter png(s_max,n_max,0,filename);

    for (int s=1; s<=s_max; s++) {
    for (int n=1; n<=n_max; n++) {
    safe_index = (safe_index + s) % n;
    r = g = b = (double)(safe_index + 1)/n;
    png.plot(s,n,r,g,b);
    }
    }

    png.close();
    }

    int main(int argc, char**argv)
    {
    make_png(600,600,"wtf.josephus.600x600.linear-n.png");
    return 0;
    }
  • Tom 2009-08-14 19:19
    Yeah, I know it is lame, long, counting from zero etc. At least I got to brush up on linked lists...



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

    struct _tSoldier
    {
    int pos;
    struct _tSoldier *next;
    struct _tSoldier *prev;
    };
    typedef struct _tSoldier tSoldier;

    tSoldier *CreateRing(int i_iNumOfSoldiers)
    {
    if (i_iNumOfSoldiers < 1)
    {
    printf("no.\n");
    return NULL;
    }
    tSoldier *pFirst = (tSoldier *) malloc(sizeof(tSoldier));
    pFirst->pos = 0;
    pFirst->prev = NULL;
    pFirst->next = NULL;
    tSoldier *pCreatedLast = pFirst;
    int i = 1;
    tSoldier *pNew;
    while (i < i_iNumOfSoldiers)
    {
    pNew = (tSoldier *) malloc(sizeof(tSoldier));
    pNew->pos = i;
    pNew->prev = pCreatedLast;
    pCreatedLast->next = pNew;
    pNew->next = NULL;
    pCreatedLast = pNew;
    i++;
    }
    /* closing the circle */
    pNew->next = pFirst;
    pFirst->prev = pNew;
    return pFirst;
    }


    /**
    * @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 Developer 2009-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 Developer 2009-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;
    }

    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;
    }
  • Wagner Amaral 2010-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.


  • Pyrexkidd 2010-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 Watches 2010-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
  • Sean 2013-08-20 10:49
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){
    soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    nah, just make sure God is a singleton.
  • Mark Wills 2013-12-24 07:38
    Here it is in Forth:


    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+ . ;
  • Carrie 2014-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?