 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
Last
Admin
SML, indexing the men from 0:
fun j(n,k,i) = (if i=1 then k1 else k+j(n1,k,i1)) 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(n1,k)+k) mod n f(1,k)=0 */
static int f (int n, int k) { if (n == 1) return 0; return (f (n1, 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(n1,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 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.
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.skip1"> <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 alivedead 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(n1,k)+ k mod n+1 = f(n2,k) + 2k mod n = f(1,k) + (n1)k mod n = 1 + (n1)k mod n So all you need to do is:
public static int f(int n, int k) { return 1 + (((n1) * 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.(n1, 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(n1,k)+k) mod n f(1,k)=0 => a[n]=a[n1]%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 stackbased 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 ?