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

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;
}<p>
<p>n = atoi (argv[1]);
k = atoi (argv[2]);</p>
<p>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;
}</p>
<p>$ gcc -g -O2 -W -Wall -Wextra jos.c -o jos</p>
<p>$ ./jos.exe 12 3
With 12 soldiers and killing every 3'th, the safe spot is position 10</p>
<p>$ ./jos.exe 40 3
With 40 soldiers and killing every 3'th, the safe spot is position 28</p>
<p>$</p>
</k></n>

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.

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

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

* * * * * * * * * *
^

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

* * * * * X * * * *
^

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

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

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

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

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.

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]

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;
};<p>
<p>unsigned int index = safe<12, 3>::result;</p>
<p>it came out looking exactly like the python implementation</p>
</unsigned>

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

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.

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 ?

Admin

Last

Admin

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

Admin

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

Admin

$ 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; }<p> <p>n = atoi (argv[1]); k = atoi (argv[2]);</p> <p>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; }</p> <p>$ gcc -g -O2 -W -Wall -Wextra jos.c -o jos</p> <p>$ ./jos.exe 12 3 With 12 soldiers and killing every 3'th, the safe spot is position 10</p> <p>$ ./jos.exe 40 3 With 40 soldiers and killing every 3'th, the safe spot is position 28</p> <p>$</p> </k></n>

Admin

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

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

Admin

Admin

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

Admin

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

Admin

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

Admin

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

Admin

An ugly script to handle this (via PHP)

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

Admin

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)

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

Thus our formula is (code in Python):

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

Admin

This is sexy.

Admin

Admin

If I'm remembering right, Josephus was actually one of the last

twostanding, upon which he said to the other guy, as they were surrounded by corpses, "Maybe surrender isn't so shameful after all?" Not sure if the algorithm for figuring out how to be one of the last two is significantly easier.Admin

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)"> </cfset></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)=""> </cfset></cfif> <cfoutput>Deleting man at position #listGetAt(circle,x)#<br></cfoutput> <cfset circle="listDeleteAt(circle," x)=""> </cfset></cfset></cfloop> <cfoutput>The last name standing was in position #circle#<br></cfoutput> </cfset></cfset></cfparam></cfparam>`

Admin

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

Admin

Sorry messed up the code tag

Admin

ColdFusion

Admin

a simple python solution:

Admin

Beat me to it.

Admin

Admin

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

Admin

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

Admin

PHP:

Admin

Admin

C#: private int Josephus(int soldiers, int everyOther) { List<int> alive = new List<int>(); for (int i = 1; i <= soldiers; i++) alive.Add(i);<p> <pre><code>int ndx = 0; while (alive.Count > 1) alive.RemoveAt(ndx = (ndx + everyOther - 1) % alive.Count); return alive[0]; </code></pre> <p>}</p> </int></int>

Admin

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

Admin

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

Admin

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

Admin

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; };<p> <p>unsigned int index = safe<12, 3>::result;</p> <p>it came out looking exactly like the python implementation</p> </unsigned>

Admin

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

Admin

Admin

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.

Admin

Javascript (0 starting index):

Admin

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

Admin

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

Admin

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

Admin

assuming that the starting position is 0:

Admin

similarly (ruby1.9):

j = lambda { |n,k| n == 1 ? 0 : (j.(n-1, k) + k) % n }

Admin

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

Admin

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

Admin

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

#include <iostream> #include <cstdlib><p> <p>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 */</p> <p>int main (int argc, const char **argv) { int n, k; if (argc != 3) { cerr << "Usage: "<< argv[0] << "<n> <k>\n"; return -1; }<p> <p>n = atoi (argv[1]); k = atoi (argv[2]);</p> <p>int r = 0; for(int a=2; a<=n; a++) r= (r+k)%a;</p> <p>cout<< "With " <<n<<" soldiers and killing every "<< k <<"'th, the safe spot is position "<<r+1<<endl; return 0; }</p> </k></n></cstdlib></iostream>

Admin

In Java, using Lists:

Using the recursion:

Admin

Admin

Vba:

Admin

Admin

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

Admin

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

Admin

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 ?