• Josephus (unregistered)

    Last

  • (cs)

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

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

  • (cs)

    $ 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

    $

  • (cs)

    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.

  • (cs) in reply to DaveK
    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 (unregistered)

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

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

  • (cs)

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

  • (cs) in reply to Code Dependent
    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 (unregistered)

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

    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 (unregistered) in reply to Alex Mont
    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 (unregistered) 
    foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
  • jfruh (unregistered)

    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 (unregistered) in reply to JonsJava

    A not as ugly as the PHP script in CF

    <cfparam name="url.soldiers" type="numeric" default="12"> <cfparam name="url.skip" type="numeric" default="3"> <cfset circle=""> <cfloop from=1 to=#url.soldiers# index=x> <cfset circle=listAppend(circle,x)> </cfloop> <cfset x=1> <cfloop condition="listLen(circle) gt 1"> <cfset x+=url.skip-1> <cfif x gt listLen(circle)> <cfset x=x mod listLen(circle)> </cfif> <cfoutput>Deleting man at position #listGetAt(circle,x)#
    </cfoutput> <cfset circle=listDeleteAt(circle, x)> </cfloop> <cfoutput>The last name standing was in position #circle#
    </cfoutput>
  • QSR (unregistered)

    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 (unregistered) in reply to Ben Forta

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

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

    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 (unregistered) in reply to Alex Mont
    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
  • (cs) in reply to jfruh
    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 (unregistered) in reply to steenbergh
    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 (unregistered)

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

  • Robert Kosten (unregistered)

    PHP:

    function j($n, $k) {
 if ( $n == 1 ) {
  return 0;
 } else {
  return ((j($n-1,$k)+$k)%$n);
 }
}
  • (cs) in reply to Dave
    Dave:
    foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
  • PJ (unregistered)

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

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

  • Andreas Kromann (unregistered)

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

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

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

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

  • Andreas Kromann (unregistered) in reply to Andreas Kromann
    Andreas Kromann:
    f(n,k) = f(n-1,k)+ k mod n+1
    thats 'mod n' ofc and not 'mod n+1' :)
  • (cs) in reply to Addison
    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 (unregistered)

    Javascript (0 starting index):

    (function(n,s){
    return (n === 1 ? 0 : (arguments.callee(n-1,s) + s) % n);
})(12,3);
  • Scope (unregistered) in reply to Code Dependent

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

  • Scope (unregistered) in reply to Code Dependent
    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!

  • (cs)

    I just wanted to say that the animations accompanying these are brilliant. :)

  • horizon (unregistered)

    assuming that the starting position is 0:

    int f(int numberOfSoldiert, int numberOfSkips)
{
   return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers;
}
  • guns (unregistered) in reply to David
    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 (unregistered)

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

  • (cs) 
    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 (unregistered) in reply to DaveK

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

    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; 
    }
  • (cs) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    yes... the God class is a singleton...
  • (cs)

    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
  • (cs) in reply to Scope
    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 (unregistered) in reply to Anon
    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.

  • (cs)

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

    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 ?

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article