# Comment On Josephus' Circle

With nearly 750 responses, and solutions written in everything from ABAP to MUMPS to XSLT, I’d say that last week’s Programming Praxis (Russian Peasant Multiplication) was certainly a success. The comments are most certainly worth a read, if nothing else but to see things like the circuit diagram solution, something done entirely using regular expressions, and some obscure childrens' language called Baltie 3. That said, I'm excited to present this next Programming Praxis. [expand full text]
 « Prev Page 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 Next »

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:12 • by Josephus (unregistered)
 Last

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:16 • by pjt33
 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);

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:18 • by 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".

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:18 • by DaveK
 \$ cat jos.c #include #include /* 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", 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 \$

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:20 • by 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 ``` ps: TRWTF is the forum software erroring out because I forgot the /code tag.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:22 • by 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

### No coffee solution in PHP

2009-07-29 09:26 • by 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";```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:31 • by silent d (unregistered)
 I think this is more about being the guy who decides where the "top of the circle" is than anything else.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:34 • by Code Dependent
 I doubt I could find the safe spot very quickly, but I've always been good at finding the G spot.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:40 • by 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...

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:42 • by JonsJava (unregistered)
 An ugly script to handle this (via PHP) ``` 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:47 • by 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:50 • by Addison (unregistered)
 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:54 • by Dave (unregistered)
 ```foreach(soldier:soldiers){ soldier.kill(); } God.getInstance().sortOut(soldiers); ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:56 • by 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:56 • by Ben Forta (unregistered)
 A not as ugly as the PHP script in CF Deleting man at position #listGetAt(circle,x)#
The last name standing was in position #circle#

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:57 • by 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; } } }

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:57 • by Ben Forta (unregistered)
 Sorry messed up the code tag ``` Deleting man at position #listGetAt(circle,x)#
The last name standing was in position #circle#
```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:59 • by SR (unregistered)
 ColdFusion ``` ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 09:59 • by 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] ) ) ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:02 • by Kyle (unregistered)
 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 ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:03 • by pjt33
 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);`

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:03 • by Code Independent (unregistered)
 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:05 • by null (unregistered)
 You stand as a first one to die and then invert the alive-dead state and you're the only one alive.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:05 • by Robert Kosten (unregistered)
 PHP: ```function j(\$n, \$k) { if ( \$n == 1 ) { return 0; } else { return ((j(\$n-1,\$k)+\$k)%\$n); } }```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:06 • by Code Dependent
 Dave:```foreach(soldier:soldiers){ soldier.kill(); } God.getInstance().sortOut(soldiers); ```Shouldn't God be static?

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:08 • by PJ (unregistered)
 C#: private int Josephus(int soldiers, int everyOther) { List alive = new List(); 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]; }

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:09 • by SR (unregistered)
 Pipped at the post by the one and only Ben Forta. I'm half livid, half honoured :)

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:15 • by 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); }

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:15 • by 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] ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:17 • by Kman (unregistered)
 c++ templates template struct safe { static const unsigned int result = (safe::result + k) % s; }; template 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

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:17 • by Ahox (unregistered)
 What happened to the locker problem comment? I can't find it anymore, and I had such a nice solution

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:17 • by Andreas Kromann (unregistered)
 Andreas Kromann: f(n,k) = f(n-1,k)+ k mod n+1 thats 'mod n' ofc and not 'mod n+1' :)

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:18 • by 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:20 • by David (unregistered)
 Javascript (0 starting index): ```(function(n,s){ return (n === 1 ? 0 : (arguments.callee(n-1,s) + s) % n); })(12,3);```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:20 • by Scope (unregistered)
 But then we wouldn't be able to mock God in a unit test!

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:22 • by Scope (unregistered)
 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!

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:23 • by RayMarron
 I just wanted to say that the animations accompanying these are brilliant. :)

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:24 • by horizon (unregistered)
 assuming that the starting position is 0: ```int f(int numberOfSoldiert, int numberOfSkips) { return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers; } ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:24 • by guns (unregistered)
 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 }

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:27 • by 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];

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:29 • by dkf
 ```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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:29 • by Random Net Poster (unregistered)
 I prefer to avoid recursion if possible (and in C++ for no good reason): #include #include 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"; 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 " <

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:29 • by DesGrieux (unregistered)
 In Java, using Lists: ``` public static int getLastManStanding(int count, int step) { List aliveMen = new ArrayList(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; } ```

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:31 • by 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...

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:33 • by steenbergh
 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 ```

### Re: Programming Praxis: Josephus' Circle

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

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:36 • by aehiilrs (unregistered)
 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.

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:38 • by jonnyq
 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

### Re: Programming Praxis: Josephus' Circle

2009-07-29 10:39 • by 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 ?
 « Prev Page 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 Next »