Comment On Josephus' Circle

Last

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

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

$ 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

$

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:

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

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

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

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

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

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.

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.

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.

foreach(soldier:soldiers){

 soldier.kill();

}

God.getInstance().sortOut(soldiers);

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.

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>

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

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>

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>

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

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

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

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.

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

PHP:

function j($n, $k) {

 if ( $n == 1 ) {

  return 0;

 } else {

  return ((j($n-1,$k)+$k)%$n);

 }

}

Dave:

foreach(soldier:soldiers){

 soldier.kill();

}

God.getInstance().sortOut(soldiers);

Shouldn't God be static?

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

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

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

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]

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

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

Andreas Kromann:

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

thats 'mod n' ofc and not 'mod n+1' :)

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.

Javascript (0 starting index):

(function(n,s){

    return (n === 1 ? 0 : (arguments.callee(n-1,s) + s) % n);

})(12,3);

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

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!

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

assuming that the starting position is 0:

int f(int numberOfSoldiert, int numberOfSkips)

{

   return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers;

}

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 }

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

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.

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

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; 

    }

Code Dependent:

Dave:

foreach(soldier:soldiers){

 soldier.kill();

}

God.getInstance().sortOut(soldiers);

Shouldn't God be static?

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

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

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.

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.

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

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 ?