 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
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
assuming there are only two people (indices 0 and 1) and killing every third person the safe spot would be 1:
0 1 0 (kill)
people safespot 2 1
if you can't add the nth number to the safe spot without equaling or going over the total number of people you reset the safe spot to 0 or 1 depending on the outcome of the previous results difference as even or odd:
people = 2 safespot = 1 n = 3
for people = 3 1 + 3 >= 3 reset safe spot to 1 because (21)mod2 = 1 (odd)
so: people safespot 2 1 3 1
for people = 4 1 + 3 >= 4 (reset to 0) (31)mod2 = event
so: people safespot 2 1 3 1 4 0
for people = 5 0 + 3 = 3 (less than 5 so keep it)
people safespot 2 1 3 1 4 0 5 3
people = 6 3 + 3 >= 6 reset to 0 (53)mod2 = even
people safespot 2 1 3 1 4 0 5 3 6 0 7 3 8 6
6+3 >= 9... and so on
Admin
Kudos but screw you for putting that in my head now...
Admin
#include <stdio.h> #include <stdlib.h> int getLastStanding(int num, int step) { int i,j; for(i=1,j=0;i<=num;i++) {j+=step; if(j>=i) j%=i; } return j+1; }
int main(int argc, char *argv[]) { int num=41, step=3; if(argc>1) num=atoi(argv[1]); if(argc>2) step=atoi(argv[2]); printf("You want to be solder %d of %d for a step of %d\n",getLastStanding(num,step),num,step); return(0); }
The trick is that it is a step function which repeats when the total exceds N on a modulo basis...
Admin
That's easy to make iterative.
Admin
I love a good perl golf challenge!
perl E '$k=pop;$s=($s+$k)%$_ for 1..pop;say$s+1' 12 3 10
39 characters between the quotes; 54 on the whole command line.
Admin
Since the sexy oneline mathematical solution has been exposed, I felt I had no other choice than going for the brain dead solution. But since my language of choice is Ruby, I'll also go for the iterator and a bit of "dynamycally modifying a core object class". Just for the fun of it.
Code which gives...
Admin
Of course... that's 1based. If you allow 0based counting, it's two characters shorter.
Admin
to many posts to look through so I'm sorry if somebody already posted this but if you read the wiki on this there are two versions and each one comes up with a different answer!
Admin
Being the author of the linked solution, do I qualify for a TDWTF sticker? That'd be awesome!
[email protected]
Admin
Here's the fast way, in Java, based on the Wikipedia article Josephus problem:
Unfortunately, this is deficient, since it provides no means to identify the best place for the surviving accomplice. So I decided to go to the even more general function that determines the kill order. The requested survivor is, of course, the last man in the array (and his accomplice next to last):
This next function then uses the above to determine the survival positions for any number of conspriators:
Finally, this next is the most useful function of all. It describes where to put the bright boy who had this stupid idea so he's the first to get the axe. Everyone else survives.
Admin
Here's my python oneliner again :)
Hopefully the next 'praxis' won't be available in Concrete Mathematics ;)
Next challenge is trying it without it being solved with string manipulation.
Admin
Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.
Admin
Admin
I wrote a weirdo erlang solution which I think works. I am a functional programming noob and I started looking at erlang yesterday.
Admin
Matlab, using inbuilt circular shift function:
Admin
When you remove the recursion from j(1,k) = 1 j(n,k) = (j(n1,k)+k) mod n
its ( (k mod 2) + k ) mod 3 ) + k ) mod 4 ) ... ) + k mod n )
can that be further simplified ?
Admin
This version uses a form and posts the result back to the form.
Edit1 contains mans Edit2 contains mansToSkip Edit3 gets the result (base 1 result, base 0 calculations) Using an array and a I'm dead indicator (to lazy to use a boolean array)
Admin
AppleScript :
Admin
This doesn't seem to work if the answer is equal to the number of soldiers...
Admin
Same brute force, just using BitSet instead:
Admin
My Perlsolution. No recusion, just one loop. But I have to confess it's not totally straight forward ;)
Admin
public class DeathLinkage { static int _Soldiers; static int _Skip; int dead = 0; int index = 0; Person[] jews;
}
Admin
A perhaps not very clean but working solution in F#
(Just discovered F# while reading through the comments to the previous programming problem.)
Admin
This is probably a WTF solution in itself. I've purposely not checked other comments so as not to spoil it. Here's my solution in C#:
//assuming index 0 is top of circle public static int saveMe(int numOfSoldiers, int skip) {
Admin
Since 2 people have beaten me to it already....
unit Josephus;
interface uses Generics.Collections, SysUtils;
type BoolP = ^Boolean;
function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer;
implementation
function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer; var AliveList: TList<BoolP>; I: Integer; SkipI: Integer; Alive: BoolP; AliveCount: Integer; Found: Boolean; begin SkipI := 1; Found := False; AliveList := TList<BoolP>.Create(); for I := 1 to Soldiers do begin new(Alive); Alive^ := True; AliveList.Add(Alive); end; AliveList.TrimExcess; I:= 0; AliveCount := AliveList.Count; while AliveCount > 1 do begin if I = AliveList.Count then I := 0; Alive := AliveList[I]; if Alive^ then begin if SkipI = Skip then begin Alive^ := False; dec(AliveCount); SkipI := 1; end else inc(SkipI); end; inc(I) end; I:= 0; while (I < AliveList.Count) and (not Found) do begin Alive := AliveList[I]; if Alive^ then Found := True else inc(I); end; if Found then Result := I + 1 else I := 1;
for I := 0 to AliveList.Count  1 do begin Alive := AliveList[0]; Dispose(Alive); AliveList.Delete(0); end; FreeAndNil(AliveList); end;
end.
Admin
To me, listening to static is indeed mysterious!
Admin
The index starting at 0. Seems i've been beaten to the short iterative answer but who cares :P
Admin
A brute force Python version...
menCount = 40 men = ["duck"] * menCount goose = 0
while men.count("goose") < menCount  1: chopper = ["duck", "duck", "goose"] while chopper != [] and men.count("goose") < (menCount  1): if men[goose] != "goose": men[goose] = chopper.pop(0) goose = (goose + 1) % menCount print men
print "Survivor: %s" %(men.index("duck") + 1)
Admin
I hate formatting issues... here's a bruteforced Python one:
Admin
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:
GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]
and so on
Admin
Too much recursion in here for my taste.
Okay... first some ruby code (boring)
And here C with double linked list awesomeness:
Admin
The only way I can see for him to succeed in this is for him to have known about the arrangements beforehand so he could prepare. Let's assume that this method of surrender was discussed and agreedupon before the battle. There would be no way to know how many soldiers were left, so he would have made up the same table we made earlier at the bottom of Page 1 of the comments. He could have memorized this, but could also have used the algorithm that many people here found (but I did not :( ) I am using the one quoted. The important line is "i = (i + k) % c;" This gives us a table that looks kind of like this: (1 + 3) % 2 (2 + 3) % 3 { 3 soldiers, stand at position 2} (2 + 3) % 4 (1 + 3) % 5 (4 + 3) % 6 { 6 soldiers, stand at position 1 } ... ...
Refer to the comment at the bottom of page 1 of comments for a bigger table. You can see that it resets to 1, 0( which becomes 2), or 2 every now and then. The series on the right climbs by 3 until it "catches up" to the series on the left. So you can jump from one reset straight to the next. (2 + 3) % 15 for 15 is one reset, the next is 6 steps up: (2 + 3 + (3 * 6)) % (15 + 6), or 23 % 21 for 21. This means that if there are 21 soldiers, he should stand as the second. The next jump takes you straight to (2 + 3 + (3 * 9)) % (22 + 9). This resets to 32 % 31 for 31 soldiers. You can now jump straight to (1 + 3 + (3 * 9)) % (32 + 9) which is 31 % 41 for 41 soldiers.
So as long as he remembered the resetting values i.e. 1 .. 7 1 .. 10 2 .. 15 2 .. 22 1 .. 32 2 .. 48, etc. he would be able to calculate the appropriate position in seconds. So for 41, he would know to use the entry corresponding to 32 since it is less than the next reset at 48. 41  32 = 9; and the position he needed to stand on would be (1 + 3) {corresponding to 32 in that table} added to 3 * 9. This would be 31.
Admin
Admin
Here's my solution in Matlab (only language I really know that well.): function safe_index = josephus(num_soldiers,num_skip)
survivor_mat=[];
for i=1:num_soldiers survivor_mat(i)=i;; end
count = 0; while length(survivor_mat) > 1 count = count + num_skip; while count > length(survivor_mat) count= countlength(survivor_mat); survivor_mat(survivor_mat == 0) = []; end if length(survivor_mat) > 1 survivor_mat(count)=0; end end safe_index = survivor_mat;
Admin
C#, using regex and strings  for fun.
Admin
Solution in F#:
Admin
OK, so here's another solution to the problem, this time in BabyTalk :
Josephus  Eenie Meenie Miiii...(skip himself)...iiiny Moe.
Admin
Here's a brute force solution in Java that I don't think anyone else has posted. It follows the problem description by treating a Vector as a circular buffer. Each vector element is the initial index of each soldier.
Admin
Admin
This is such a simple algorithm I am not sure how to make my solution THAT much more complicated. I did manage to use two subroutines, not counting josephus(), as well as recursion. And I broke LOTS of Perl Best Practices. Maybe tomorrow I'll try to figure this one out using only Regexes.
Admin
Zeus is Greek not Roman... that would be Jupiter
Admin
*v,n;main(s,f){for(n=1;atoi(1[v=f])s;n=(n+atoi(2[v=f]))%++s);printf("%d\n",n);}
Admin
So 39 soldiers were done for, but Titus escaped.
All these comments, and not one pointing out the irony of using Python to show... erm... the Romans didn't do for Titus.
Admin
I'd say the safe spot is in the middle, as only the people in the circle get killed :P
Admin
Looking at the table of reset values idea that is discussed in earlier comments, I see that finding those helpful values is quite easy.
Pseudocode:
X is a placeholder for the last reset value, starts at 1 Y is a placeholder for what you have to reset to at X, starts at 0 function is called with variables S(oldiors) and C(ount)
startloop distanceToNextX = ( (XY)/(C1) rounded up )
if S is less than nextX return Y + (SX)*c else X = nextX Y = (Y + (distance to next X * C)) mod x endloop
Batch file:
@echo off rem  argument 1 is number of soldiers, argument 2 is the number to count to each time
call :josephus %1 %2
echo the servivor is at index %j%
exit /b
:josephus set s=%1 set c=%2 set x=1 set y=0
:loopbegin echo begin loop set /a z="(((2*(xy))/(c1))+1)/2" set /a xn="x+z" if %s% lss %xn% ( set /a j="y+((sx)c)" ) else ( set x=%xn% set /a y="(y+(zc))%%x" goto :loopbegin )
exit /b
This algoritem is more efficient than any of the other looping or recursion alborithems I have seen implemented thus far. Even as a (ineficient) batch file it finds the servivor in a group of 32727 (#6132) in the blink of an eye while looping only two dozen times.
Trying that will overflow the stack on any of the recursive programs. Go ahead and try it with any of the other looping ones. I'll wait.
Admin
Monotheist, ey?
Admin
find and replace "servivor" with "survivor". How embarrassing.
Admin
I tried to go for good readability.
In Smalltalk, comments are delimited using doublequotes. Variables are declared between verticle bars. The caret returns a value from the method. Otherwise it's pretty much like Python, but with a builtin debugger.
Interestingly, if you want to give the survivors names, you can replace:
circle := OrderedCollection withAll: (1 to: n).
with:
circle := OrderedCollection withAll: #('Phillipus' 'Caesor' 'Nero' 'Josephus' 'Cactus').
and then this method will return the name of the survivor.
Admin
Really modeling the situation using Scheme message passsing OOP.
Admin
I tried to call GodFactory.getGods(GodFactory.AGNOSTIC), but the call keeps blocking.
Help?