The Daily WTF: Curious Perversions in Information Technology

Code Dependent · 2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

samanddeanus · 2009-07-29 Reply 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 (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 !@#$$

2009-07-29 Reply Admin

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();
}

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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));
}

}

2009-07-29 Reply 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]

Iago · 2009-07-29 Reply Admin

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.

2009-07-29 Reply 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!

2009-07-29 Reply 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. "

mol1111 · 2009-07-29 Reply Admin

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 .

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

2009-07-29 Reply Admin

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;

        }

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

In dc:

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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;

}

2009-07-29 Reply Admin

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)

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

Paddles · 2009-07-29 Reply Admin

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,"^");
}

2009-07-29 Reply Admin

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";
    
}

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply 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;

	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!");
}

}

2009-07-29 Reply Admin

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

Christian · 2009-07-29 Reply Admin

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.

Stalker · 2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

2009-07-30 Reply 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:

= $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.

Stalker · 2009-07-30 Reply Admin

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.

ikegami · 2009-07-30 Reply Admin

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");

2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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.

2009-07-30 Reply Admin

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];	
}

2009-07-30 Reply Admin

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?

2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

foreach(soldier:soldiers){
 soldier.kill();

}

God.getInstance().sortOut(soldiers);
Shouldn't God be static?

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

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

2009-07-30 Reply Admin

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

2009-07-30 Reply 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

2009-07-30 Reply 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

2009-07-30 Reply Admin

[email protected]:
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.

2009-07-30 Reply 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]==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]))); }

Josephus' Circle

Leave a comment on “Josephus' Circle”