 Feature Articles

CodeSOD
 Most Recent Articles
 Ordering Off This Menu
 Duplication
 A Tip
 Around 20 Meg
 Image Uploading
 Junior Reordering
 A Sniff
 Classical Solutions
 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
Admin
HAI 1.2
BTW used some syntax liberties for areas underdefined around arrays
HOW DUZ I JosephusCircle YR soldiers AN YR skip
IF U SAY SO
KTHXBYE
Admin
@Dr. Batch:
I have posted code in Scheme which yielded (josephus 32767 2) [of 32767 people, skip 2 and then kill the next person] in 27 iterations and (josephus (largestfixnum) 2) in 98 iterations. [largestfixnum is 144115188075855871]
Even (josephus (expt (largestfixnum) 100) 2) returns immediately.
The ceiling function in Scheme works on rational numbers as well as floats, so it returns exact answers.
I also made some Scheme code that "models" the situation using circular lists or messagepassing, which probably runs slow as [email protected]#$$
Admin
An iterative version of my previous solution, also handles arbitrary count value k (kill every k'th element):
Admin
My arrogance and I stand corrected.
Admin
public class JosephusCircle {
}
Admin
Just for fun, here's a plot of the solutions for 2 <= num_soldiers <= 100 and 1 <= step_size <= num_soldiers
Results are plotted as intensity values from 0 (black) to 100 (white). I was surprised how random they look. [image]
Admin
I can see two ways to save another character:
or but I can't see a way to combine both tricks.Addendum (20090729 19:13): Two more characters can be saved if the calling convention is reversed:
called with e.g. 3 40 rather than 40 3.Admin
Reasonably good Python solution.
def circle(N, skip): p = 0 solders = range(0, N)
while len(solders) > 1: p = (p + skip  1) % len(solders) solders.pop(p)
return solders[0] + 1
Just wanted to say I'm enjoying these little problems. Sure you can find solutions for them in minutes but your only cheating yourself if you do!
Admin
PHB method:
" Okay now everyone, please stand in a circle.
Now take a number.
Here is a stack of papers, every third a memo firing the recipient.
Take the top one and pass the stack.
No cheating.
By fired, we mean leave NOW.
I'll be standing over here off to the side by the doughnuts. "
When it is down to one person:
" I see it is finished. What is your number? (person: "42") Oh, by the way, you are fired too. "
Admin
ZX Spectrum BASIC version.
Screenshot for finished program (soldiers=10, skip=2): [image]
TAP file for emulator.
Addendum (20090729 19:36): If you want to start counting including the first soldier (as in article's picture) change the line 220 to LET i=0 .
Admin
piet
[image]First input is the number of soldiers. Second input is the number to skip. Output is the (zero based) index of the survivor.
Admin
C# / generics:
Admin
No, no, no. For Scrödinger's approach to work you need quantum. Doesn't work without one, everyone knows that.
Admin
If it were, many wars would have been avoided...
Admin
In dc:
Admin
Shellscript. With graphical output. :)
USAGE = <scriptname> <number in circle> Error handling nonexistant.
#!/bin/sh
NUM=$1;
echo "Starting Number = " $NUM
for (( i = $NUM ; i != 0; i )) do ARRAY="a $ARRAY" done
echo $ARRAY
#Killing time
INCREMENTOR=0 ALLDEAD=NUP
while [ $ALLDEAD != YUP ] do
ARRAY2=""
for ELEMENT in $ARRAY do if [ $ELEMENT = a ] then INCREMENTOR=
expr $INCREMENTOR + 1
#echo "Incrementor is $INCREMENTOR" fi if [ $INCREMENTOR eq 3 ] then INCREMENTOR=0 ARRAY2="$ARRAY2 d " else ARRAY2="$ARRAY2 $ELEMENT" fi#echo $ARRAY2 done
ARRAY=$ARRAY2 echo $ARRAY
STILLALIVE=0 for ELEMENT in $ARRAY do if [ $ELEMENT = a ] then STILLALIVE=
expr $STILLALIVE + 1
fidone
if [ $STILLALIVE eq 1 ] then ALLDEAD=YUP fi
echo "still alive = $STILLALIVE"
done
LUCKYNUM=1 for ELEMENT in $ARRAY do if [ $ELEMENT = d ] then LUCKYNUM=
expr $LUCKYNUM + 1
else echo "Survivor is number $LUCKYNUM" fidone
Admin
int josephus(int size, int skip) { if(size <= 1) return 1; // You have no reason to worry if its just you
}
Admin
Admin
Okay, that does it Almost killed me. Too funny.
Admin
Admin
Here it is, in awk. A more awkish implementation would replace the troops string with an associative array, deleting (how appropriate!) elements until there was only one left  but that would come at the cost of making the snuff movie a bit harder.
Sample output:
And the code...
Admin
My PHP offering:
Admin
I feel like pointing out that O(n) is a horrible running time in this case. It's pseudolinear (linear in the numeric value of the input but exponential in the size of the input). We can do much better than exponential in N's representation.
Here is an algorithm which runs in O(lg(N)*S) time, assuming arithmetic operations are constant time.
It achieves the massive speed up by performing an entire trip (and a bit more) around the circle in each recursion. I haven't figured out any way to make it nonexponential in S's representation yet.
Admin
Admin
What are you smoking?
Admin
Yet another simulator version, but maybe it's a little different from the others.
Which, instead of killing the guys, pushes the guys to die in the proper order from Josepheus back and up till the first guy dies. Then all we need to do to get the index of Josepheus (Mr. Zero)...
Admin
I have no idea why this is coming out doublespaced. Anyway, Josephus was the third man, like Orson Welles.
Admin
import java.util.HashMap;
public class Josephus { public static void main(String[] args) { // The example of 12 soldiers in a circle is won by spot 10 (index 9). HashMap<Integer, Boolean> livingSoldiers = new HashMap<Integer, Boolean>(); int numSoldiers = 0; int numToSkip = 0; int skipped = 0;
}
Admin
Not counting my linked list implementation  not as fast as the functional ones  but maybe a little more comprehensible
Admin
Here's an attempt with VBScript that simulates a linked list with an array.
At least it works.
Admin
Admin
Visual Basic 2008, using generic list....
Admin
Oops, got it wrong, here is correct version:
Admin
Perhaps to calculate it quickly he used assembly?
Admin
so it has been a few years since I did any code on the C64.
but an answer in 6502 assembler is:
SRC:
*=$0800 jmp START NUM_PEOPLE .byte 41 NUM_JUMP .byte 3 NUM_ALIVE .byte 00 TEMP .byte 00
START LDA NUM_PEOPLE STA NUM_ALIVE LDA #01 LDX #00 CLEAR STA $0700,x INX CPX NUM_PEOPLE BNE CLEAR LDA #00 LDY #00
TOP LDX #$ff KILL_LOOP INX CPX NUM_PEOPLE BEQ TOP LDA $0700,x CMP #00 BEQ KILL_LOOP INC TEMP LDY TEMP CPY NUM_JUMP BNE KILL_LOOP LDA #00 STA $0700,x STA TEMP DEC NUM_ALIVE LDA NUM_ALIVE CMP #01 BNE KILL_LOOP BRK
OBJECT CODE:
0806 .BYTE $00 00
0807 START
0807 LDA NUM_PE AD 03 08 080A STA NUM_AL 8D 05 08 080D LDA #$01 A9 01 080F LDX #$00 A2 00 0811 CLEAR
0811 STA $0700,X 9D 00 07 0814 INX E8 0815 CPX NUM_PE EC 03 08 0818 BNE CLEAR D0 F7 081A LDA #$00 A9 00 081C LDY #$00 A0 00
081E TOP
081E LDX #$FF A2 FF 0820 KILL_L 0820 INX E8 0821 CPX NUM_PE EC 03 08 0824 BEQ TOP F0 F8 0826 LDA $0700,X BD 00 07 0829 CMP #$00 C9 00 082B BEQ KILL_L F0 F3 082D INC TEMP EE 06 08 0830 LDY TEMP AC 06 08 0833 CPY NUM_JU CC 04 08 0836 BNE KILL_L D0 E8 0838 LDA #$00 A9 00 083A STA $0700,X 9D 00 07 083D STA TEMP 8D 06 08 0840 DEC NUM_AL CE 05 08 0843 LDA NUM_AL AD 05 08 0846 CMP #$01 C9 01 0848 BNE KILL_L D0 D6 084A BRK 00
HEX: 4C 07 08 29 03 00 00 AD 03 08 8D 05 08 A9 01 A2 00 9D 00 07 E8 EC 03 08 D0 F7 A9 00 A0 00 A2 FF E8 EC 03 08 F0 F8 BD 00 07 C9 00 F0 F3 EE 06 08 AC 06 08 CC 04 08 D0 E8 A9 00 9D 00 07 8D 06 08 CE 05 08 AD 05 08 C9 01 D0 D6 00
I have not written clean input / output code. but the basic idea is there and the code will run and give correct answer.
Admin
Didn't feel right to pack all soldiers into one process, so here they each get their own.
Not really how MPI is supposed to be used, but it works. At least for smaller values, falls apart with larger.
Admin
Functional programming solution in Perl.
Admin
In the tacit form of the J programming language the solution looks like this:
so 2 >:@(}[email protected].^:({:@]))i. 41  returns 31
If you allow an answer for index 0 the solution shortens to:
}[email protected].^:({:@])i. 15 characters
and 2 }[email protected].^:({:@])i. 41  returns 30
for more information on J  Jsoftware.com
Reading the index 1 version right to left
i. creates a list of 0 to n1 soldiers
({:@]) is a loop counter that initializes to the last number in the soldier list (n1)
^: symbolizes the power conjunction that will apply a function a specified number of times (in this case n1).
}[email protected]. is the function that is applied. The LHS arg shifts the soldier list 2 spaces and then the first soldier in the newly ordered line is dropped. After this has been done n1 times the remaining number is the soldier number in index 0. For some reason this makes me think of a Monty Python sketch with suicidal Scots (but that would be the case with 0 skips).
Cheers, bob
Admin
Well, you could use Supersede Instance Variable pattern for this legacy system.
Admin
In Javascript:
Admin
I think you're assuming some sort of mathematic trick that hadn't been invented in 1AD. This is the time before arabic numerals or algebra (and certainly before recursion), and division was still an acane artform.
That's why I went for a "grid in sand" algorith. There are some cleverer algorithms here, but I think that it more likely that he might have had a minute or so to scratch in the sand while the other soldiers were talking to God. If I was in his sandles I'd much rather do it like that than solve equations or execute recursive functions in my head.
Of course, you shouldn't mind me if you just want to find that equation. I just think it's unlikely Josephus might have done it that way.
Incidentally, whatever method you're using is periodically wrong from 6 soldiers and up. Captcah: nulla. A countzero error perhaps?
Admin
I'd say it even should ba Abstract ;)
Admin
Admin
Oops. Jospehus was the 41st soldier, so the safe spot is #41.
That in itself is a hint as to a mathmatical solution. I just checked, and whenever there is prime number of soldiers, the last (prime) place is the safe spot. I imagine that there is some mathematical solution involving finding the largest coprime, but that's over my head.
Admin
Now that I think about it a gridinsand solution is silly. If he was going to do that, he might as well have just modeled the problem directly with a line or ring of 41 pebbles.
Or maybe he was second to last and wacked the other guy first :)
Admin
The original WTF graphic that described this problem so well could be the clue to how Josephus would solve this problem.
Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.
This model would solve the problem and would seem to be within the technology of the times.
Cheers, bob
Admin
xeno,
I think your last prime solution fails for 3 soldiers when killing of every third soldier :) In this case I think #41 would be the 23rd to die. I'd still want to be #31
Cheers, bob
Admin
Snap :)
Or he might have chosen #41 out of mathematical superstition (a belief that prime numbers are lucky), or just hung back and joined the circle last.
Admin
#include<stdio.h>
//Good luck, trying to understand this function code( I used almost every mistake here, what I have seen ) int whos_alive(int varaibles, int varaibels){ char variabels[varaibles]; int variables[3]={0,1,0}; for(variables[0]=0;variables[0]<varaibles;variables[0]++)variabels[variables[0]]=1; for(variables[0]=0;1;variables[0]++)if(variables[0]>=varaibles) variables[0]=1; else if(variabels[variables[0]]){if(variables[2]==varaibles1)return variables[0]+1;if(variables[1]==varaibels){variabels[variables[0]]=0;variables[1]=1;variables[2]++;}else variables[1]++;} }
int main(int argc, const char **argv){ printf("safe spot is %d( if you start counting positions from 1 not 0 )",whos_alive(atoi(argv[1]),atoi(argv[2]))); }