• (cs) in reply to Comp Sci Student
    Comp Sci Student:
    Lerb:
    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

    I tried to call GodFactory.getGods(GodFactory.AGNOSTIC), but the call keeps blocking.

    Help?

    Frisbeetarian isn't working, either... it keeps getting stuck somewhere.

  • corvi (unregistered)

    HAI 1.2

    BTW used some syntax liberties for areas underdefined around arrays

    HOW DUZ I JosephusCircle YR soldiers AN YR skip

    I HAS A soldier 
    soldier r 1
    
    I HAS A dead
    dead r 0
    
    I HAS A deadsoldiers
    deadsoldiers r DIFF OF soldiers AN 1
    
    I HAS A circle 
    IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers 
    	soldier IN MAH circle r WIN 
    IM OUTTA YR LOOP 
    
    I HAS A skipnum
    skipnum r 1
    
    soldier r 1	
    IM IN YR KILLLOOP UPPIN YR soldier WILE DIFFRINT dead AN BIGGR OF dead AN deadsoldiers 
    	BOTH SAEM soldier IN MAH circle AN WIN, O RLY?
    	  YA RLY
    		BOTH SAEM skipnum AN skip, O RLY?
    		 	YA RLY
    				soldier IN MAH circle r FAIL
    				dead r SUM OF 1 AN dead
    				skipnum r 1
    			NO WAI, skipnum r SUM OF skipnum AN 1					 	
    		OIC
    
    	OIC
    
    	BOTH SAEM soldier AN soldiers, O RLY?
    	  YA RLY, soldier r 0
    	OIC
    
    IM OUTTA YR KILLLOOP
    
    
    BOTH SAEM dead AN deadsoldiers, O RLY?
    	YA RLY
    		
    			IM IN YR LOOP UPPIN YR soldier TIL BOTH SAEM soldier AN soldiers 
    			BOTH SAEM soldier IN MAH circle AN WIN, O RLY?
    	   		YA RLY, safespot r soldier
    			OIC
    		IM OUTTA YR LOOP 	
    	NO WAI, safespot r 0
    OIC
    
    FOUND YR safespot
    

    IF U SAY SO

    KTHXBYE

  • (cs) in reply to Dr. Batch

    @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 (largest-fixnum) 2) in 98 iterations. [largest-fixnum is 144115188075855871]

    Even (josephus (expt (largest-fixnum) 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 message-passing, which probably runs slow as !@#$$

  • Kevin M (unregistered) in reply to Kevin M

    An iterative version of my previous solution, also handles arbitrary count value k (kill every k'th element):

    int josephus(Vector<Integer> v, int k) {
      while (v.size() > 1) {
        for (int i = 0; i < k - 1; i++) {
          v.add(v.remove(0));
        }
        v.remove(0);
      }
    
      return v.elementAt(0).intValue();
    }
    
  • Dr. Batch (unregistered) in reply to samanddeanus
    Bob:
    @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 (largest-fixnum) 2) in 98 iterations. [largest-fixnum is 144115188075855871]

    Even (josephus (expt (largest-fixnum) 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 message-passing, which probably runs slow as !@#$$

    My arrogance and I stand corrected.

  • dvrslype (unregistered)

    public class JosephusCircle {

    public static int lastManStanding(int soldiers, int skip) {
    	if (soldiers == 1)
    		return 0;
    
    	return (lastManStanding(soldiers - 1, skip) + skip) % soldiers;
    }
    
    public static void main(String[] args) {
    	System.out.println(lastManStanding(12, 3));
    }
    

    }

  • phil (unregistered)

    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]

  • (cs) in reply to Sue D. Nymme
    Sue D. Nymme:
    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.

    Nice.

    I can see two ways to save another character:

    $k=pop;map$s=($s+$k)%$_,1..pop;say$s+1
    or
    $k=pop;($s+=$k)%=$_ for 1..pop;say$s+1
    but I can't see a way to combine both tricks.

    Addendum (2009-07-29 19:13): Two more characters can be saved if the calling convention is reversed:

    ($s+="@ARGV")%=$_ for 1..pop;say$s+1
    called with e.g. 3 40 rather than 40 3.
  • Edinburgh Mike (unregistered)

    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!

  • Qwertyuiopas (unregistered)

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

  • (cs)

    ZX Spectrum BASIC version.

    Screenshot for finished program (soldiers=10, skip=2): [image]

    TAP file for emulator.

       1 REM **********************
       2 REM *                    *
       3 REM *  Josephus' CIRCLE  *
       4 REM *                    *
       5 REM *  TheDailyWTF.com   *
       6 REM *                    *
       7 REM *     by mol1111     *
       8 REM *                    *
       9 REM * Greets go to       *
      10 REM * Alex,the organizer *
      11 REM * Yorick             *
      12 REM * Lamac, for his ROM *
      13 REM *                    *
      14 REM **********************
      15 REM .
      45 REM Bigger number makes 
      46 REM it slower. Set to zero
      47 REM to wait for keypress
      48 REM after each step.
      50 LET wait=20
      60 PAPER 0
      70 INK 7
      80 BORDER 0
      90 CLS 
     100 INPUT "How many soldiers?",n
     110 INPUT "How many to skip", skip
     112 IF n>0 AND skip>=0 THEN  GO TO 119
     114 PRINT "There should be at least one    soldier and the skip should be  0 or more."
     116 GO TO 100
     119 REM .
     120 REM Draw soldiers
     121 REM .
     125 CLS 
     130 LET angle=2*PI/n
     132 LET scale=60
     140 FOR i=1 TO n
     150 GO SUB 1000
     160 CIRCLE x, y, 10
     165 GO SUB 1100
     170 NEXT i
     180 REM .
     190 REM Play.
     200 REM .
     204 REM Modulo function.
     205 DEF FN m(a,b)=a-(INT (a/b)*b)
     208 INK 2
     210 DIM s(n)
     220 LET i=1
     230 LET lasts=n
     240 IF lasts=0 THEN  GO TO 500
     250 LET stilltoskip=skip+1
     260 IF stilltoskip=0 THEN  GO TO 320
     270 LET i=1+FN m(i,n)
     280 IF s(i) THEN  GO TO 270
     300 LET stilltoskip=stilltoskip-1
     310 GO TO 260
     320 LET s(i)=1
     322 LET lasts=lasts-1
     324 IF lasts=0 THEN  INK 4
     330 GO SUB 1000
     335 PAUSE wait
     340 CIRCLE x,y,10
     345 GO SUB 1100
     350 GO TO 240
     500 REM The End.
     980 INK 7: REM reset to white
     990 STOP 
    1000 REM .
    1001 REM Compute middle of the CIRCLE .
    1002 REM .
    1010 LET x=128+scale*COS (angle*i)
    1020 LET y=96+scale*SIN (angle*i)
    1030 RETURN 
    1100 REM .
    1101 REM Prints soldier's number
    1102 REM It's not exact because
    1103 REM print works just with
    1104 REM rows and columns, not
    1105 REM pixels.
    1106 REM .
    1110 LET column=x*(33/256)-1
    1120 LET row=22-y*(25/192)
    1130 PRINT AT row,column;i
    1140 RETURN

    Addendum (2009-07-29 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 .

  • ponky (unregistered)

    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.

  • Bradley Dean (unregistered)

    C# / generics:

    
            static int Josephus(int numSoldiers, int soldiersToSkip)
            {
    
                // create soldiers
                List<int> Soldiers = new List<int>();
                for (int i = 0; i < numSoldiers; i++)
                {
                    Soldiers.Add(i);
                }
    
                // kill soldiers
                int iSoldier = 0;
                while (Soldiers.Count() > 1)
                {
    
                    // skip ahead by the requested number of soldiers
                    iSoldier = iSoldier + soldiersToSkip;
                    
                    // if we've gone over, then wrap back around to the top
                    while (iSoldier > Soldiers.Count())
                    {
                        iSoldier -= Soldiers.Count();
                    }
    
                    // kill the choosen soldier
                    Soldiers.RemoveAt(iSoldier - 1);
                }
    
                // return answer
                return Soldiers[0] - 1;
    
            }    
    
    
  • Utunga (unregistered) in reply to IV
    IV:
    I am taking the Schroedinger approach - instead of using an axe, have everyone climb into a box with a bottle of poison. At that point, everyone is both alive and dead. Thus, the suicide is successful (each person is dead), but our hero has survived (he is alive).

    No, no, no. For Scrödinger's approach to work you need quantum. Doesn't work without one, everyone knows that.

  • Goglu (unregistered) in reply to Code Dependent

    If it were, many wars would have been avoided...

  • bwross (unregistered)

    In dc:

    [ Lks. Lns. ] SR
    [ lRx 0 q ] SX
    [
        Sk Sn
        1 ln =X
        ln 1- lk lJx lk+ ln%
        lRx
    ] SJ
    
  • Veltyen (unregistered)

    Shellscript. With graphical output. :)

    USAGE = <scriptname> <number in circle> Error handling non-existant.

    #!/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 fi

    done

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

    done

  • Strange Quark (unregistered)

    int josephus(int size, int skip) { if(size <= 1) return 1; // You have no reason to worry if its just you

    //	Allocate array of size @size
    bool *point = new bool[size];
    
    int axed = 0;	//	People axed
    int seq = 0;	//	Current skip sequence
    int pos = 0;	//	Current position in circle
    
    //	Loop while there is more than 1 person alive
    while(axed < size - 1)
    {
        //	if its reached the sequence and that person is still alive...
    	if(seq == (skip - 1) && point[pos])
        {
            //	Axe the person
    		point[pos] = false;
            axed++;
            seq = 0;
        }
        else
        if(point[pos])
            seq++;	//	Else increase the sequence
    
        pos++;	//	Move to next position
    
        if(pos == size)
            pos = 0;	//	Reset to beginning if reached the end
    
    }
    
    //	return the single living position
    for(int i = 0; i < size; i++)
        if(point[i])
            return i;
    
    return -1;
    

    }

  • John Stracke (unregistered)
    j delta n = step [1..n] 1
        where step [x] _ = x
              step (x:xs) i = if i == delta
                              then step xs 1
                              else step (xs++[x]) (i+1)
    
  • Chris (unregistered) in reply to steenbergh

    Okay, that does it-- Almost killed me. Too funny.

  • John Stracke (unregistered) in reply to Addison
    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.

    Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

  • (cs)

    Here it is, in awk. A more awk-ish 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:

    C:\Temp>gawk -f josephus.awk -vVERBOSE=1
    12
    vvvvvvvvv^vv
    10
    12 3
    vvvvvvvvv^vv
    10
    12 5
    ^vvvvvvvvvvv
    1
    14
    v^vvvvvvvvvvvv
    2
    
    
    C:\Temp>
    

    And the code...

    # josephus.awk
    # set VERBOSE to 1 for a very-low-budget snuff ASCII-art snuff movie.
    
    NF == 0 {exit; }
    NF >= 2 { interval = int($2); }
    NF == 1 || interval <0 { interval = 3;}
    
    int($1)>0 {
    	troopsize =$1;
    	troops = "";
    	for (i=1;i<=troopsize;i++) troops = troops "^";
    	lastmember = 0;
    	for (i=1;i<troopsize;i++) {
    		for (j=1;j<=interval;j++) {
    			nextmember=index(substr(troops,lastmember+1),"^");
    			if (nextmember==0) nextmember=index(troops,"^")
    			else nextmember += lastmember;
    			lastmember = nextmember;
    		}
    		troops = substr(troops,1,lastmember-1) "v" substr(troops,lastmember+1);
    		if (VERBOSE>0) {
    			printf("%s\r",troops); 	# Prints a pretty progressive display of alive and dead members marked by ^ and v.
    			for (k=1;k<=300000;k++) {foo=sin(k);} 	# In lieu of a sleep command. 
    		}
    	}
    	if (VERBOSE >0) print "";
    	print index(troops,"^");
    }
    
  • horuskol (unregistered)

    My PHP offering:

    function allbutone($num, $skip) {
        
        $circle = array();
        for ($i = 0; $i < $num; $i++) {
            
            $circle[$i] = $i+1;
            
        }
        
        $step = $skip - 1;
        
    
        $idx = $step;    
        while (sizeof($circle) > 1) {
    
            do {
                
                unset($circle[$idx]);
                sort($circle);
                $idx += $step;
                
            } while ($idx < sizeof($circle) && sizeof($circle) > 1);
            
            while ($idx  >= sizeof($circle)) {
            
                $idx -= sizeof($circle);
                
            }  
          
        }       
    
        return $circle[0];
        
    }
    
    $tests = array(
        array(12, 3),
        array(40, 3),
        array(41, 3),
        array(5,  1),
    );
    
    foreach ($tests as $t) {
        
        echo $t[0] . "\t" . $t[1] . "\t" . allbutone($t[0], $t[1]) . "\n";
        
    }
  • Strilanc (unregistered)

    I feel like pointing out that O(n) is a horrible running time in this case. It's pseudo-linear (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.

    function f(int n, int s) as int:
        if n < 1 or s < 1 then error
        if s == 1 then return n - 1 #special case
        if n == 1 then return 0 #end condition
        
        #recurse on sub-group obtained after a cycle completed
        var t = f(n - ceiling(n / s), s)
        
        #map sub-result to current group
        t += -n mod s #assumes mod result is in [0, s)
        t += floor(t / (s-1))
        return t mod n
    

    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 non-exponential in S's representation yet.

  • Anonymous Coward (unregistered) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    He's a singleton instance. That way, you can still pass him into any CargoCultFollowing(IGod g) function using the IGod interface.
  • Anonymous Coward (unregistered) in reply to John Stracke
    John Stracke:
    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.

    Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

    What are you smoking?

    >>> def j(n,k):
    ...     if(n==1): return 0
    ...     else: return (j(n-1,k)+k)%n
    ...
    >>> j(12,3)
    9
    >>>
    
  • JayC (unregistered)

    Yet another simulator version, but maybe it's a little different from the others.

            public static IEnumerable<int> JosepheusInverseOrder(int requiredpeeps)
            {
                Queue<int> people = null;
                if (requiredpeeps <= 0)
                    people = new Queue<int>(new int[] {});
                else
                {
                    people = new Queue<int>(new int[] { 0 });
                    int numpeeps = people.Count() ;
                    //work it backwards 
                    while (requiredpeeps > numpeeps)
                    {
                        int temp;
                        // use Queue as circular list
                        temp = people.Dequeue();
                        people.Enqueue(temp);
                        temp = people.Dequeue();
                        people.Enqueue(temp);
                        people.Enqueue(numpeeps);
                        numpeeps++;
                    }
                }
                return people.ToArray().Reverse();
            }
    

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

    System.Console.WriteLine("Josepheus needs to be at place {0}.", Array.IndexOf(people.ToArray(), 0)+1);
    
  • xeno (unregistered)
    <?php
    /**
    Sandbox grid solution.
    ----------------------
    This isn't the most efficient algorithm (a computer doesn't need multiple rows), you may
    even be able to express this problem as a mathematical equation.  However, a person can
    execute this algorith by drawing a grid in the sand, as Josephus might have done, using the
    rows to avoid losing your place (which would fatally alter the result).
    
    The multiple rows help you keep your place.  As you work your way along each row,
    "killing soldiers" you strike out the rest of the column (downwards, from the current row).
    When you run of the end of the row, go down to the next.  I've allocated enough rows in
    the function, but if you're working in the sand you can just add more if you run out.
    That's just as well, as division was considered complex maths in the 1st century.
    */
    
    $n    = $argv[1];
    $skip = $argv[2];
    echo "The safe spot is #" . josephs_circle($n, $skip) . "\n";
    
    function josephs_circle($n = 40, $skip = 3)
    {
            $num_rows = ceil($n / $skip) + 1;
            $row      = array_pad(array(), $n, '');
            $grid     = array_pad(array(), $num_rows, $row);
    
            $x = $skip -1; // count zero
            $y = 0;
            $kills = 0;
            while (true)
            {
                    while ($grid[$y][$x] and $x < $n) // column is "dead", still on this row
                    {
                            $x++;
                    }
    
                    if ($x >= $n) // have run off the end of the row (above)
                    {
                            $x = 0;
                            $y++;
                            $grid[$y] = $grid[$y -1]; // strike out downwards
                            continue;
                    }
    
                    $kills++;        // now we're going to kill somebody, unless ...
                    if ($kills == $n) // ... we're the last man standing
                    {
                            return $x +1; // convert from count-zero to count-one and return
                    }
    
                    $grid[$y][$x] = '*'; // hit the soldier with the axe
                    $x += $skip;
    
                    if ($x >= $n) // have skipped off the end of the row
                    {
                            $x = $x % $n;
                            $y++;
                            $grid[$y] = $grid[$y -1]; // strike out downwards
                    }
            }
    }
    ?>
    

    I have no idea why this is coming out double-spaced. Anyway, Josephus was the third man, like Orson Welles.

  • Sterge (unregistered)

    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;

    	if (args.length != 2)
    	{
    		System.out.println("Usage: java Josephus [soldiers] [to skip]");
    		System.exit(1);
    	}
    
    	try
    	{
    		numSoldiers = Integer.parseInt(args[0]);
    		numToSkip = Integer.parseInt(args[1]);
    	}
    	catch (NumberFormatException nfe)
    	{
    		System.out.println("Usage: java Josephus [soldiers] [to skip]");
    	}
    
    	int[] soldiers = new int[numSoldiers];
    
    	for (int i = 0; i < numSoldiers; i++)
    	{
    		soldiers[i] = 1;	// Alive.
    		livingSoldiers.put(i, true);
    	}
    
    	while (livingSoldiers.size() > 1)
    	{
    		for (int i = 0; i < numSoldiers; i++)
    		{
    			if (soldiers[i] != 0 && skipped == numToSkip)
    			{
    				soldiers[i] = 0;	// Dead.
    				livingSoldiers.remove(i);
    				skipped = 0;
    			}
    			else if (soldiers[i] == 1)
    				{
    					skipped++;
    				}
    		}
    	}
    
    	System.out.println("FTW choose index " + livingSoldiers.keySet().iterator().next() + " in a ZERO based array!");
    }
    

    }

  • Ransom (unregistered)

    Not counting my linked list implementation - not as fast as the functional ones - but maybe a little more comprehensible

    def josephl(num_peeps, num_skip)
      ll = LinkList.new
      num_peeps.times {|i| ll.append(i)}
      iterator = ll.head
    
      (num_peeps - 1).times do
        (num_skip - 1).times do
          iterator = iterator.next
        end
        delete = iterator
        iterator = iterator.next
        ll.delete(delete)
      end
    
      iterator.val
    end
    
  • (cs)

    Here's an attempt with VBScript that simulates a linked list with an array.

       Function JosephusSafeSpot(intNumberOfSoldiers, intNumberToSkip)
          Dim arrPopulation(), intIndex, intPrevious, intSubIndex
          ReDim arrPopulation(intNumberOfSoldiers)
          For intIndex = 1 To intNumberOfSoldiers
             arrPopulation(intIndex) = (intIndex mod intNumberOfSoldiers) + 1
          Next
    
          intIndex = 1
          Do Until intIndex = arrPopulation(intIndex)
             For intSubIndex = 2 To intNumberToSkip
                intPrevious = intIndex
                intIndex = arrPopulation(intIndex)
             Next
    
             arrPopulation(intPrevious) = arrPopulation(intIndex)
             intIndex = arrPopulation(intPrevious)
          Loop
    
          JosephusSafeSpot = intIndex
       End Function
    

    At least it works.

  • (cs) in reply to Dr. Batch
    Dr. Batch:
    Go ahead and try it with any of the other looping ones. I'll wait.
    My very bad F# looping version did that in 42 ms, (25 iterations) if I remove the prints during the loop. Just under a second with them. Not a very long wait either way. Raising the skip makes it much worse though, then the memory reallocations start to hurt.
  • SurturZ (unregistered)

    Visual Basic 2008, using generic list....

      Function joe(ByVal soldiercount As Integer, ByVal skipcount As Integer) As Integer
        Dim i As Integer
        Dim lst As New List(Of Integer)
        For i = 1 To soldiercount
          lst.Add(i)
        Next i
        Do Until lst.Count = 1
          'move top two to end
          i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
          i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
          'kill third guy
          lst.RemoveAt(0)
        Loop
        Return lst(0) 'last man standing's original position
      End Function
    
  • SurturZ (unregistered) in reply to SurturZ

    Oops, got it wrong, here is correct version:

      Function joe(ByVal soldiercount As Integer, ByVal skipcount As Integer) As Integer
        Dim i As Integer
        Dim lst As New List(Of Integer)
        For i = 1 To soldiercount
          lst.Add(i)
        Next i
        Do Until lst.Count = 1
          'move top guys to end
          For j As Integer = 0 To skipcount - 2
            i = lst(0) : lst.RemoveAt(0) : lst.Add(i)
          Next j
          'kill appropriate guy
          lst.RemoveAt(0)
        Loop
        Return lst(0)
      End Function
    
  • Firestryke31 (unregistered)

    Perhaps to calculate it quickly he used assembly?

    ;; Josephus' Circle - Intel 80386-compatible assembly
    ;; Parameters: eax = number of soldiers, ebx = kill stride
    ;; returns: eax = safe spot, ecx = original number of soldiers
    
    ;; Stuff to make it work with C
    global _joseC;
    global joseC;
    
    ;; I didn't really look into doint this more efficiently
    ;; but it's not the focus, so it doesn't matter
    _joseC:
    joseC:
    	push ebp
    	mov ebp, esp
    	push ebx
    	push ecx
    	push edx
    	mov eax, [ebp + 8 ]
    	mov ebx, [ebp + 12]
    	call joseASM
    	pop edx
    	pop ecx
    	pop ebx
    	pop ebp
    	ret
    
    ;; Here's the meat of the program:
    joseASM:
    	;; Save the original number of soldiers for later on
    	mov ecx, eax
    	;; we need to check if eax was one, and we need eax - 1 later
    	;; so subtract the one now
    	dec eax
    	;; and check for zero
    	or eax, eax
    	;; if it is, we're done.
    	jz return
    
    	;; it wasn't, so let's save the original number of soldiers
    	push ecx
    	;; and go through it all again with n-1 soldiers
    	call joseASM
    	;; Now we need to add the kill stride
    	add eax, ebx
    	;; get the original number of soldiers back
    	pop ecx
    	;; zero out edx for the divide
    	xor edx, edx
    	;; perform the modulus (div stores % in edx and / in eax)
    	div eax, ecx
    	;; put the result in eax to make recursion easier
    	mov eax, edx
    return:
    	;; leave the function
    	ret
    
  • robsonde (unregistered)

    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:

    • = $0800 0800 JMP START 4C 07 08 0803 NUM_PE 0803 .BYTE $29 29 0804 NUM_JU 0804 .BYTE $03 03 0805 NUM_AL 0805 .BYTE $00 00 0806 TEMP
      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.

  • (cs)

    Didn't feel right to pack all soldiers into one process, so here they each get their own.

    #include <mpi.h>
    
    #include <stdio.h>
    
    #define SKIP	3
    
    typedef struct _Axe
    {
    	int lastToHold;
    	int counter;
    	int goAway;
    } Axe;
    
    int main( int argc, char** argv )
    {
    	int soldierId, numSoldiers, stillAlive, neighborR, neighborL;
    	Axe axe;
    	MPI_Status status;
    
    	MPI_Init( &argc, &argv );
    
    	MPI_Comm_rank( MPI_COMM_WORLD, &soldierId );
    	neighborR = soldierId - 1;
    	MPI_Comm_size( MPI_COMM_WORLD, &numSoldiers );
    	neighborL = (soldierId + 1) % numSoldiers;
    
    	stillAlive = 1;
    	if( soldierId == 0 )
    	{
    		neighborR = numSoldiers - 1;
    		axe.counter = SKIP - 1;
    		axe.lastToHold = 0;
    		axe.goAway = 0;
    		printf( "Axe starting to go round\n" );
    		printf( "[%d] Sending to %d\n", soldierId, neighborL );
    		MPI_Send( &axe, 3, MPI_INT, neighborL, 0, MPI_COMM_WORLD );
    	}
    	
    	while( 1 )
    	{
    		printf( "[%d] Waiting to receive from %d\n", soldierId, neighborR );
    		MPI_Recv( &axe, 3, MPI_INT, neighborR, 0, 
    			MPI_COMM_WORLD, &status );
    		
    		if( axe.lastToHold == soldierId )
    		{
    			// Only one left
    			axe.goAway = 1;
    			MPI_Send( &axe, 3, MPI_INT, (soldierId + 1) % numSoldiers, 0,
    				MPI_COMM_WORLD );
    			printf( "[%d] I won!\n", soldierId );
    			break;
    		}
    		if( stillAlive && --axe.counter == 0 )
    		{
    			// Our turn to die
    			axe.counter = SKIP;
    			stillAlive = 0;
    			printf( "[%d] Oh noes! I died!\n", soldierId );
    		}
    		if( stillAlive )
    		{
    			axe.lastToHold = soldierId;
    		}
    		printf( "[%d] Sending to %d\n", soldierId, neighborL );
    		MPI_Send( &axe, 3, MPI_INT, neighborL, 0,
    			MPI_COMM_WORLD );
    		if( axe.goAway )
    		{
    			printf( "[%d] Game over\n", soldierId );
    			break;
    		}
    	}
    
    	MPI_Finalize();
    
    	return( 0 );
    }
    

    Not really how MPI is supposed to be used, but it works. At least for smaller values, falls apart with larger.

  • (cs)

    Functional programming solution in Perl.

    #!/usr/bin/perl
    
    use strict;
    use warnings;
    
    use List::Util qw( reduce );
    
    # Silence warnings.
    $a=$b if 0;
    
    sub step {
       my ($k) = @_;
       return sub { ($a + $k) % $b };
    }
    
    sub J {
        my ($n, $stepper) = @_;
        return reduce \&$stepper, 0, 2..$n;
    }
    
    print( J(12,step(3)), "\n");
    
  • bobtherriault@mac.com (unregistered)

    In the tacit form of the J programming language the solution looks like this:

    :@(}.@|.^:({:@]))i. 20 characters

    so 2 >:@(}.@|.^:({:@]))i. 41 - returns 31

    If you allow an answer for index 0 the solution shortens to:

    }.@|.^:({:@])i. 15 characters

    and 2 }.@|.^:({:@])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 n-1 soldiers

    ({:@]) is a loop counter that initializes to the last number in the soldier list (n-1)

    ^: symbolizes the power conjunction that will apply a function a specified number of times (in this case n-1).

    }.@|. 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 n-1 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).

    :@ then adds one to the number to convert it to index 1

    Cheers, bob

  • bynio (unregistered) in reply to Scope
    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!

    Well, you could use Supersede Instance Variable pattern for this legacy system.

  • Chris (unregistered)

    In Javascript:

    function SafeSpot(nrOfSoldiers, soldierSkip)
    {
    	var a = new Array(nrOfSoldiers);
    
    	for (i=0; i<nrOfSoldiers; i++) a[i] = i+1;
    	while (a.length > 1)
    	{
    		if (a.length > soldierSkip)
    		{
    			a = a.slice(soldierSkip).concat(a.slice(0,soldierSkip-1));
    		}
    		else if (a.length == soldierSkip)
    		{
    			a = a.slice(0,soldierSkip-1);
    		}
    		else if (a.length > 1 && (soldierSkip % a.length == 0))
    		{
    			a = a.slice(0, a.length-1);
    		}
    		else
    		{
    			a = a.slice(soldierSkip % a.length).concat(a.slice(0,(soldierSkip % a.length) - 1));
    		}
    	}
    	return a[0];	
    }
    
  • xeno (unregistered) in reply to Wongo
    Wongo:
    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):

    (deleted for the sake of brevity)

    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    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 count-zero error perhaps?

  • BTM (unregistered) in reply to Code Dependent

    I'd say it even should ba Abstract ;-)

  • BTM (unregistered) in reply to Code Dependent
    foreach(soldier:soldiers){
     soldier.kill();
    
    }
    
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    I'd say it even should ba Abstract ;-)
  • xeno (unregistered) in reply to xeno

    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 co-prime, but that's over my head.

  • xeno (unregistered) in reply to xeno

    Now that I think about it a grid-in-sand 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 :-)

  • bobtherriault@mac.com (unregistered)

    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

  • bobtherriault@mac.com (unregistered) in reply to xeno

    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

  • xeno (unregistered) in reply to bobtherriault@mac.com
    bobtherriault@mac.com:
    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.

    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.

  • KnoNoth (unregistered)

    #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]==varaibles-1)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]))); }

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article