• Thorsten M. (unregistered) in reply to HypocriteWorld

    Ha, now we have a way to stop people from posting "Frist!!1".

    Cool idea, include a math exercise in each story, and additional to the captcha the solution of the exercise must be provided. This might not totally avoid "first11!1" posts, but we might get less of the very stupid ones :-)

  • (cs)

    T-SQL (SQL Server 2008 although I bet 2005 would work too). I tried to avoid just writing "C style" code with variables and really use the database features:

    
    CREATE PROCEDURE  Josephus 
    	-- Add the parameters for the stored procedure here
    	@numSoldiers int, 
    	@numSkip int
    AS
    BEGIN
    	SET NOCOUNT ON
    	
    	CREATE TABLE SoldierList(
    	[Soldier] int NOT NULL,
     CONSTRAINT [IX_SoldierList] UNIQUE CLUSTERED 
    (
    	[Soldier] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) 
    
    CREATE TABLE Lineup(
    	[LineupOrder] [int] IDENTITY(1,1) NOT NULL,
    	[Soldier] [int] NOT NULL
    ) 
    	
    	
    	delete from Lineup
    	delete from SoldierList
    	
    	-- first make the soldier list
    	declare @inserter as int
        set @inserter = 1
        while @inserter <= @numSoldiers
        begin
          insert into SoldierList(Soldier) values (@inserter)
          set @inserter = @inserter + 1
        end
        
        insert into Lineup(Soldier) select Soldier from SoldierList
        insert into Lineup(Soldier) select Soldier from SoldierList
        insert into Lineup(Soldier) select Soldier from SoldierList
        
        declare @axAt int
        set @axAt = -1
        while 1 < (select COUNT(*) from SoldierList)
        begin
        
    		declare @minLineupId int
    		set @minLineupId = (select MIN(LineupOrder) from Lineup)
    
    		
    		declare @toKillIndex int
    		set @toKillIndex = (@axAt + @numSkip + 1) % (select COUNT(*) from Lineup)
    
    		
    		declare @toKillLineUp int
    		set @toKillLineUp = @minLineupId + @toKillIndex
    
    		
    		declare @toKill int
    		set @toKill = (select Soldier from Lineup where LineupOrder = @toKillLineUp)
    		
    		declare @numInstancesBeforeCurrent int
    		set @numInstancesBeforeCurrent = (select COUNT(*) from Lineup where Soldier = @toKill and LineupOrder <= @toKillLineUp)
    		
    		delete from Lineup where Soldier = @toKill
    		delete from SoldierList where Soldier = @toKill
    		
    		--line them back up
    		delete from Lineup
    		insert into Lineup(Soldier) select Soldier from SoldierList
    		insert into Lineup(Soldier) select Soldier from SoldierList
    		insert into Lineup(Soldier) select Soldier from SoldierList
    		
    		--make the soldier before the one just killed pick up the axe
    		set @axAt = @axAt + @numSkip + 1
    		set @axAt = @axAt - @numInstancesBeforeCurrent
    
    		if @axAt < 0 
    		begin
    		  set @axAt = @axAt + (select COUNT(*) from SoldierList)
    		  select @axAt as 'AxAt2'
    		end
    		
    		set @axAt = @axAt % (select COUNT(*) from SoldierList)
        end
        
        select Soldier from SoldierList
        drop table SoldierList
        drop table Lineup
    END
    GO
    
    
  • (cs) in reply to workmad3
    workmad3:
    def joph(n):
    return int(bin(n)[2:][1:] + bin(n)[2:][0], 2)
    
    WTF?
  • Daniel Browne (unregistered)

    I didnt have time to read all the comments so sorry if this is what has already been done...

    def josephus(soldiers, skip): soldiers = range(1, soldiers+1)
    while len(soldiers) > 1:
    soldiers.pop((skip - 1) % len(soldiers))
    soldiers = soldiers[2:] + soldiers[:2]
    return soldiers

  • xeno (unregistered) in reply to [email protected]
    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

    Hmm, you're right, and so was Wongo. When I correct it so it's a accurate representation of scratching in the sand I get this:

    <?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.
    */
    
    $n    = $argv[1];
    $skip = $argv[2];
    echo "The safe spot is #" . josephs_circle($n, $skip) . "\n";
    
    function josephs_circle($n = 40, $skip = 3)
    {
            $row      = array_pad(array(), $n, '');
            $grid     = array($row);
    
            $x     =  0;
            $y     =  0;
            $kills =  0;
            $s     =  $skip;
    
            while ($kills < $n)
            {
                    if ($x == $n) // have run off the end of the row
                    {
                            $x = 0;
                            $y++;
                            $grid[$y] = $grid[$y -1]; // strike out downwards
                    }
    
                    if (! $grid[$y][$x])
                    {
                            $s--;
                    }
    
                    if ($s == 0)
                    {
                            $kills++;         // now we're going to kill somebody, unless ...
                            if ($kills < $n)  // ... we're the last man standing
                            {
                                    $grid[$y][$x] = ':-(';  // hit the soldier with the axe
                                    $s            = $skip;
                            }
                    }
                    $x++;
            }
            return $x;
    }
    ?>

    Which gets the same solution as you. So much for prime numbers!

  • Thomas (unregistered)

    There are some Haskell solutions, but no oneliner yet:

    josephus n s = head $ (!!(n-1)) $ iterate (\x -> let y = drop (s-1) x in filter (/= head y) y) $ concat $ repeat [1..n]

  • axe user (unregistered)

    Last 2 man standing, one of them has the axe, why the hell would he kill himself?

  • reol (unregistered) in reply to steenbergh

    LOL!

  • FST777 (unregistered)

    bash + expr:

    #!/bin/bash
    total=9
    count=2
    
    function commence() {
        ttotal=$1
        if [[ $ttotal = 1 ]]; then
            echo 0
        else
            ttemp1=`expr $ttotal - 1`
            ttemp2=`commence $ttemp1`
            ttemp3=`expr $ttemp2 + $count`
            expr $ttemp3 % $total
        fi
    }
    
    commence $total
  • ThiOz (unregistered)

    I think this could be done quicker or with less code but i guess it's solid

    function calculateSafeSpot($iNumSoldiers, $iNumSkip) { $aMen = array_fill(1,$iNumSoldiers, 'alive'); $iCount = 1; while(count($aMen)>1) {

        foreach($aMen as $iNum => $sAlive)
        {
            if($iCount == $iNumSkip)
            {
                $aMen[$iNum] = null;
                $iCount = 1;
            }
            else
            {
                $iCount++;    
            }
            
        }
        $aMen = array_filter($aMen);
    }
    
    $aManStanding = array_keys($aMen);
    return $aManStanding[0];
    

    }

  • TheNewOne (unregistered)

    Rather boring one, but simple, in php ;)

    <?php function joseph($ile, $jump = 3) { $tab = array(); for ($i=0; $i<$ile; $i++) { $tab[] = ($i+1); } $k = $i = 0; while (count($tab)>1) { if ($i>=count($tab)) { $i = ($i%count($tab)); } if ((($k+1)%$jump)==0) { array_splice($tab, $i, 1); $i--; } $k++; $i++; } echo 'joseph('.$ile.', '.$jump.') = '.$tab[0].'
    '; } ?>
  • Josephus (unregistered)
    # -*- coding: utf-8 -*-
    def josephus(n, s):
    	if n < 2:
    		raise ValueError("n must be greater than one")
    	if s < 1:
    		raise ValueError("s must be greater zero")
    	positions = range(n)
    	i = 0
    	while len(positions) > 1:
    		i = (i + s - 1) % len(positions)
    		del positions[i]
    	return positions[0] + 1
    
    josephus(12,3)
  • Anonymous (unregistered)

    This programming praxis was let down by its simplicity and the well known nature of the problem. I love the idea of coding challenges but you need to come up with original problems for them.

  • Sue D. Nymme (unregistered) in reply to Code Dependent

    If you call the Frisbeetarian object with a float, it just hangs....

  • (cs)

    Have one in sed with some help from bash.

    #!/bin/bash
    usage() { 
        echo "Usage: shooter.sh <people> <shootevery>"
        exit 
    }
    
    [ "$1" != "" ] && [ "$2" != "" ] || usage
    echo "$1$2" | grep -qv '[^0-9]'  || usage
    [ "$1" -gt 0 ] && [ "$2" -gt 0 ] || usage
    
    PERSON="{[0-9][0-9]*}"
    PEOPLE=$1
    while [ $PEOPLE -ne 0 ]; do 
        INPUT="{${PEOPLE}}${INPUT}"
        PEOPLE=$((PEOPLE - 1))
    done
    
    SHOOTEVERY=$2
    while [ $SHOOTEVERY -ne 1 ]; do 
        SKIP=${SKIP}${PERSON}
        SHOOTEVERY=$((SHOOTEVERY - 1))
    done
    
    echo
    echo "Line up: ${INPUT}, firing on $2"
    echo
    
    echo "$INPUT" | sed -e 'p
    :cull
    /^'"${PERSON}"'$/boneleft
    /'"${SKIP}"''"${PERSON}"'/{s/\('"${SKIP}"'\)'"${PERSON}"'\(.*\)/\2\1/p;tcull}
    /^'"${PERSON}"'$/boneleft
    :clone
    /'"${SKIP}"''"${PERSON}"'/!{s/\(.*\)/\1\1/;tclone}
    s/\('"${SKIP}"'\)\('"${PERSON}"'\)/x\2x\1/
    :bury
    s/x\('"${PERSON}"'\)x\(.*\)\1/x\1x\2/;tbury
    s/x'"${PERSON}"'x//;
    :declone
    s/\('"${PERSON}"'\)\(.*\)\(\1\)/\1\2/;tdeclone;p
    :oneleft
    /^'"${PERSON}"'$/{s/{\('".*"'\)}/Winner: \1/;tend}
    bclone
    :end'
    
    
  • Bas (unregistered)

    A solution in Clean which starts with a list of soldiers numbered 1 to n and recursively kills soldiers until only one is left:

    josephus n s = kill [1..n] (s - 1) where kill [j] s = j kill l s = kill (tl (rotate l s)) s

    rotate l s = drop s l ++ take s l

  • Queex (unregistered)

    Hacky solution in R. Remember that in R all indices begin with 1. Uncomment the cats to see how it works.

    josephus <- function (men, kill) 
    {
            list <- 1:men
            while(length(list)>2){
                    tmp.kill <- kill %% men
                    list <- c(list[-(1:tmp.kill)],list[1:(tmp.kill-1)])
                    #cat(list)
                    #cat("\n")
            }
            tmp.live <- (kill %% 2) + 1
            list[tmp.live]
    }
  • John Stracke (unregistered) in reply to Anonymous Coward
    Anonymous Coward:
    John Stracke:
    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
    >>>
    

    Uh...aw, bleep. I ran J(3,12) instead.

    Sorry. You'd think I'd've learned not to flame after 10PM by now...

  • Josephus (unregistered)

    Python one-liner:

    josephus = lambda n, s, r=None, i=0: josephus(n, s, range(n)) if r is None else (r[0] + 1 if len(r) == 1 else josephus(n,s,r[:(i + s - 1) % len(r)] + r[(i + s - 1) % len(r) + 1:], (i + s - 1) % len(r)))
    
    print josephus(12,3)
  • (cs) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    Since God is both eternal and unchanging, He must be static const.

    Addendum (2009-08-14 23:32): Updated: I have been studying theology and discovered that He is also claimed to be uncreated. Therefore he is static const, and the constructor is private.

  • lamcro (unregistered)

    BASIC code SAFE_SPOT is the return parameter.

    I'm using a string of "1" characters, instead of an array, which are switched to "0" when dead.

    0010 ENTER TOTAL_SOLDIERS,SKIP_COUNT,SAFE_SPOT
    0020 LET SOLDIERS$=FILL(TOTAL_SOLDIERS,"1")
    0030 LET POSITION=1,SOLDIERS_LEFT=TOTAL_SOLDIERS,COUNT=0
    0040 WHILE SOLDIERS_LEFT>1
    0050 IF SOLDIERS$(POSITION,1)="1" THEN GOSUB LIVE_OR_DIE ENDIF
    0060 LET POSITION=POSITION+1
    0070 IF POSITION>TOTAL_SOLDIERS THEN LET POSITION=1 ENDIF
    0080 WEND
    0090 LET SAFE_SPOT=POS("1"=SOLDIERS$)
    0100 EXIT
    0110 LIVE_OR_DIE:
    0120 LET COUNT=COUNT+1
    0130 IF COUNT=SKIP_COUNT THEN LET SOLDIERS$(POSITION,1)="0",COUNT=0,SOLDIERS_LEFT=SOLDIERS_LEFT-1 ENDIF
    0140 RETURN
    
  • asd (unregistered)

    javascript with caching to make it run fast ;)

    function j(n,k){
        if(j[n] != undefined && j[n][k] != undefined){
            return j[n][k];
        }
        if(n==1){
            return 0;
        }
        if(j[n] == undefined){
            j[n] = [];
        }
        var jj = (j(n-1,k) + k) % n;
        j[n][k] = jj;
        return jj;
    
    };
    
  • (cs) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    Shouldn't God be static?
    That depends. In this case, it looks like it's a static method on a class, but nothing ensures that God is singleton (as would be required by monotheistic beliefs like Christianity, Judaism and Islam).

    If you're a follower of a polytheistic belief, such as Hinduism, you would require a getInstance() method for each god, and perhaps a factory class:

    public class GodFactory
    {
    public static God getInstance( String name ) throws NoSuchGodException
    {
    // ...
    }
    }
    Finally, if you're Terry Pratchett, you can instantiate God objects with the 'new' operator. If the God object is not used, it will automatically be garbage collected.

    However, God objects are considered anti-patterns, and should therefore not be used.

  • KukkerMan (unregistered)
    let rec josephus soldiers skips = if soldiers < 2 then 0 else (josephus (soldiers-1) skips + skips) mod soldiers;;
    
  • Wongo (unregistered) in reply to Anonymous
    Anonymous:
    In response to Wongo:

    There's a formula in the Online Encyclopaedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A054995

    Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

    Very interesting, thanks for the link. Still not something Josephus could have hacked together in the few seconds when the troup gathers (unless the guy was both a soldier AND a polymath, rather a rare occurrence)... Also, he would have to have known the constant K, which I'm not sure was known at the time.

    Again, I might be completely wrong in interpreting the problem, maybe that "Josephus quickly found a solution" is just Alex's usual literary embellishment... But darn, those series look eerily simplifiable.

  • (cs)

    I'm currently in the middle of an XML training course, and it's really tempting to try to work out a way of doing this in an XSLT. Unfortunately I have two important work-related tasks that I have to finish tonight and it's 9pm already, so I don't have time to play around with it (and really I shouldn't be on this site at all).

    But if the course is going slowly tomorrow, I make no guarantees :D

  • Short dong silver (unregistered)

    He there

    I focused on ... getting it right ... fast. So I wrote down a pretty stupid piece of JAVA code (plus some debug output and profiling basics. I calculated that it would be O(n^2) ... so who cares if there is an O(n) solution anyway ;-)

    But well, that one was really neat. Anyway, here we go.

    public class Circle
    {
        public static String toString(boolean people[])
        {
            String result = "";
            for (int i=0; i < people.length; i++) {
                result += (people[i]) ? "." : "A";
            }
            return result;
        }
    
        public static int findSpot(int numPeople, int numAxe)
        {
            boolean people[] = new boolean[numPeople];
    
            int idx = 0;
            int counter = 1;
            int remaining = numPeople;
    
            while (true) 
            {
    //            System.out.println("idx: " + Integer.toString(idx) +
    //                               " / counter: " + Integer.toString(counter) +
    //                               " / remaining: " + Integer.toString(remaining) +
    //                               " field: " + toString(people));
                if (! people[idx]) // guy is not dead
                {
                    if (counter == numAxe) 
                    {
                        people[idx] = true; // kill the guy
                        remaining--;        // one less
                        counter = 1;        // restart counting
    
                        if (remaining == 1) break; // all dead
                    } // if counter == numAxe
                    else
                    {
                        counter++;
                    }
                } // if !people[idx]
    
                idx++;
                if (idx == numPeople) idx = 0;
            } // while true
    
            for (idx=0; idx < people.length; idx++) 
            {
                if (!people[idx]) break;
            }
    
    //        System.out.println("idx: " + Integer.toString(idx) +
    //                           " / counter: " + Integer.toString(counter) +
    //                           " / remaining: " + Integer.toString(remaining) +
    //                           " field: " + toString(people));
            return idx+1;
        } // findSpot()
    
        public static void main(String args[])
        {
            long start = System.currentTimeMillis();
            int spot = findSpot(new Integer(args[0]).intValue(),
                                new Integer(args[1]).intValue());
            long stop = System.currentTimeMillis();
    
            System.out.println("Spot is: " + new Integer(spot).toString() +
                               " / time is: " + new Long(stop-start).toString() + " ms");
        }
    }
    
  • J (unregistered)

    This should be done with math but I haven't had my coffee yet. So I will use Mathematica. This seems to be a job for NestWhile, and we can use cyclicity and skip to the n'th person by RotateLeft'ing by n-1. So

    JosephusLast[num_Integer?Positive, step_Integer?Positive] := NestWhile[Rest[RotateLeft[#, step - 1]] &, Range[num], Length[#] > 1 &][[1]]

    E.g.

    In[3]:= JosephusLast[12, 3]

    Out[3]= 10

    In[4]:= JosephusLast[41, 3]

    Out[4]= 31

    In[5]:= JosephusLast[40, 3]

    Out[5]= 28

    Replacing NestWhile with NestWhileList and removing the [[1]] gives who is left before each step.

  • Wongo (unregistered) in reply to TGV
    TGV:
    Anonymous:
    In response to Wongo:

    There's a formula in the Online Encyclopaedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A054995

    Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

    Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

    Fascinating. For all those who won't follow the link, here is the gist of it: to calculate Fibo(n+1) given ONLY Fibo(n) (and not, as is usual, Fibo(n-1)), just do Fibo(n+1) = round(Fibo(n)* Phi). It works for all cases where n>1 (Phi is the golden number 1.618...).

    There MUST be some similar solution to the Josephus problem...

  • (cs)

    C# (4.0):

    class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine(JosephusCircle.Solve());
            }
        }
    
        public enum Vitality
        {
            Alive,
            Dead
        }
    
        public class Soldier
        {
            public Soldier()
            {
                Vitality = Vitality.Alive;
            }
    
            public void Axe()
            {
                Vitality = Vitality.Dead;
            }
    
            public Vitality Vitality { get; private set; }
        }
    
        public static class JosephusCircle
        {
            public const int DefaultSoldierCount = 40;
            public const int DefaultSkipAmount = 3;
    
            public static int Solve(int soldierCount = DefaultSoldierCount, int skipAmount = DefaultSkipAmount)
            {
                var soldiers = new List<Soldier>();
    
                do
                {
                    soldiers.Add(new Soldier());
                } while (soldiers.Count < soldierCount);
    
                return Solve(soldiers, skipAmount);
            }
    
            public static int Solve(IEnumerable<Soldier> soldiers, int skipAmount = DefaultSkipAmount)
            {
                var soldierList = soldiers.ToList();
    
                var leftToSkip = skipAmount;
                var index = -1;
    
                do
                {
                    if (++index == soldierList.Count)
                    {
                        index = 0;
                    }
    
                    if (soldierList[index].Vitality == Vitality.Alive)
                    {
                        if (--leftToSkip == 0)
                        {
                            soldierList[index].Axe();
    
                            leftToSkip = skipAmount;
                        }
                    }
                    else
                    {
                        continue;
                    }
                } while (soldierList.Where(soldier => soldier.Vitality == Vitality.Alive).Count() > 1);
    
                return soldierList.IndexOf(soldierList.Single(soldier => soldier.Vitality == Vitality.Alive));
            }
        }
  • Wongo (unregistered) in reply to xeno
    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.

    Actually, the safe spot with 41 soldiers is 31, not 41. And 11 (soldiers) = 7 (safe spot), 13 = 13 (you're right for this one), 17=11, 19=17, 23=8... It doesn't work. I've also tried things like: safe spot = (soldiers - previous prime) * 2, safe spot = soldiers mod previous prime... No luck there either.

  • Wongo (unregistered) in reply to xeno
    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.
    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.

    Yes, but:

    1. That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

    2. What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

    As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

    In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

  • (cs)

    Since this is The Daily WTF, I figured that the solution is worth nothing unless it is a WTF itself. So - here's my attempt at doing it in Microsoft-specific C++. N = the number of men; K = which one to kill (3 means every 3rd). The return value is the number of position (starting at 1).

    int josephus(int n , int k) { int $,$=n,=2,$$=k;$^=$;$_:if(>$)goto $;$+=$$;$%=__++;goto $;$:return ++$_; }

  • (cs)

    First! (for 4, 9, 31, 70, 105, 355, 799, 1798, 2697 etc soldiers...)

    (Sorry, couldn't resist.)

    First off, iterative Josephus, O(n), in C:

    int JIter(int n,int k){int v=0,i=2;for(;i<=n;v=(v+k)%i++);return v+1;}
    

    Crunchy, but effective.

    Secondly, here's that O(1) implementation, again in C:

    #define K3 1.62227050288476731595695
    int JLin(int n){return 3*n+1-floor(K3*pow((3.0/2.0),ceil(log((2.0*n+1.0)/K3)/log(3.0/2.0))));}
    

    Please note that this is specific to k=3.

    Here's an O(Log N) (to the base k) implementation, C, based on Strilanc's solution.

    int JLog(int n,int k) {
    	if (k==1) return n-1;if (n<=1) return 0;
    	int t=JLog(n-ceil((double)n/(double)k),k);
    	t += (k-1) - (n+k-1)%k;t += floor((double)t / ((double)k-1.0));
    	return t%n;
    }
    

    Iterative O(Log(N)) proves difficult, because we have some maths on either side; the recursive n-ceil(n/k) on input, and the clever stuff after. Anyone have any ideas?

    The story is likely to be apocryphal, or at least the part about figuring out where to stand being either attributed later or pure luck (anthropics!).

    Also, bear in mind they were euthanising each other as a kindness. It would have been fairly easy for him to "do the kindest thing", and accept the last position.

  • Damage (unregistered)
    import java.util.ArrayList;
    
    public class JosephusCirle {
    
    	private static Integer saveSpot(int soldiers, int skipCount) {
    
    		/* everyone dies in order, axe is passed from one to another --> last one survives 
    		 * or one enters the cave, and one leaves it (no monster found) */
    		if (skipCount == 0 || soldiers == 1) {
    			return new Integer(soldiers);
    		}
    
    		// I knew it, a Ghost Army !!!
    		if (soldiers <= 0) {
    			return null;
    		}
    
    		int deathCount = (((skipCount < 0) ? (skipCount * -1) : skipCount)) + 1;
    
    		ArrayList<Integer> livingSoldiers = new ArrayList<Integer>();
    		ArrayList<Integer> livingSoldiersBackwards = new ArrayList<Integer>();
    
    		// build cirle
    		{
    			livingSoldiersBackwards.add(new Integer(1));
    
    			for (int i = 0; i < soldiers; i++) {
    				livingSoldiers.add(new Integer(i + 1));
    				if (i > 0) {
    					livingSoldiersBackwards.add(new Integer(soldiers - i + 1));
    				}
    			}
    			
    			for (int i = 0; i < livingSoldiersBackwards.size(); i++) {
    				System.out.println("RW: " + livingSoldiersBackwards.get(i).intValue());
    			}
    		}
    
    		// circle axe
    		{
    			int axeCount = 0;
    
    			while (livingSoldiers.size() > 1) {
    				for (int i = 0; i < livingSoldiers.size(); i++) {
    					axeCount++;
    
    					if (axeCount == deathCount) {
    						livingSoldiers.remove(i);
    						axeCount = 0;
    
    						i--;
    					}
    				}
    			}
    		}
    		
    		return ((skipCount < 0) ? livingSoldiersBackwards.get(livingSoldiers.get(0).intValue() - 1) : livingSoldiers.get(0));
    		
    	}
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		Integer saveSpot = saveSpot(12, 2);
    		if (saveSpot == null) {
    			System.out.println("No Save spot found, only D E A T H!");
    		}
    		else {
    			System.out.println("Save spot: " + saveSpot);
    		}
    	}
    
    }
    

    by Damage

  • jane (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".

    So there must be some kind of shortcut (e.g. to know whether a number is divisible by 5, you don't have to actually divide it, just check whether the final digit is 5 or 0).

    Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

    Soldiers: 2, Last Spot: 2 Soldiers: 3, Last Spot: 2 Soldiers: 4, Last Spot: 1 Soldiers: 5, Last Spot: 4 Soldiers: 6, Last Spot: 1 Soldiers: 7, Last Spot: 4 Soldiers: 8, Last Spot: 7 Soldiers: 9, Last Spot: 1 Soldiers: 10, Last Spot: 4 Soldiers: 11, Last Spot: 7 Soldiers: 12, Last Spot: 10 Soldiers: 13, Last Spot: 13 Soldiers: 14, Last Spot: 2 Soldiers: 15, Last Spot: 5 Soldiers: 16, Last Spot: 8 Soldiers: 17, Last Spot: 11 Soldiers: 18, Last Spot: 14 Soldiers: 19, Last Spot: 17 Soldiers: 20, Last Spot: 20 Soldiers: 21, Last Spot: 2 Soldiers: 22, Last Spot: 5 Soldiers: 23, Last Spot: 8 Soldiers: 24, Last Spot: 11 Soldiers: 25, Last Spot: 14 Soldiers: 26, Last Spot: 17 Soldiers: 27, Last Spot: 20 Soldiers: 28, Last Spot: 23 Soldiers: 29, Last Spot: 26 Soldiers: 30, Last Spot: 29 Soldiers: 31, Last Spot: 1 Soldiers: 32, Last Spot: 4 Soldiers: 33, Last Spot: 7 Soldiers: 34, Last Spot: 10 Soldiers: 35, Last Spot: 13 Soldiers: 36, Last Spot: 16 Soldiers: 37, Last Spot: 19 Soldiers: 38, Last Spot: 22 Soldiers: 39, Last Spot: 25 Soldiers: 40, Last Spot: 28 Soldiers: 41, Last Spot: 31

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

    round pi('s) will kill you?

  • Paul N (unregistered)

    Here are 4 variations in C#

            private static int Josephus1(int numberOfSoldiers, int soldiersToSkip)
            {
                char livingSoldier = '|';
                string deadSoldier = "_";
                string circleOfSoldiers = string.Empty.PadLeft(numberOfSoldiers, livingSoldier);
                int indexOfAxe = -1;
                while (circleOfSoldiers.IndexOf(livingSoldier) != circleOfSoldiers.LastIndexOf(livingSoldier))
                {
                    for (int skippedSoldiers = 0; skippedSoldiers <= soldiersToSkip; skippedSoldiers++)
                    {
                        indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier, indexOfAxe + 1);
                        if (indexOfAxe == -1)
                        {
                            indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier);
                        }
                    }
                    circleOfSoldiers = circleOfSoldiers.Remove(indexOfAxe, 1).Insert(indexOfAxe, deadSoldier);
                }
                return circleOfSoldiers.IndexOf(livingSoldier) + 1;
            }
    
            private static int Josephus2(int numberOfSoldiers, int soldiersToSkip)
            {
                Queue<int> circleOfSoldiers = new Queue<int>();
                for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
                {
                    circleOfSoldiers.Enqueue(soldier);
                }
                while (circleOfSoldiers.Count > 1)
                {
                    for (int skip = 1; skip <= soldiersToSkip; skip++)
                    {
                        circleOfSoldiers.Enqueue(circleOfSoldiers.Dequeue());
                    }
                    int deadSoldier = circleOfSoldiers.Dequeue();
                
                }
                return circleOfSoldiers.Dequeue();
            }
    
            private static int Josephus3(int numberOfSoldiers, int soldiersToSkip)
            {
                List<int> circleOfSoldiers = new List<int>();
                for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
                {
                    circleOfSoldiers.Add(soldier);
                }
                int indexOfDeadSoldier = 0;
                while (circleOfSoldiers.Count > 1)
                {
                    indexOfDeadSoldier += soldiersToSkip;
                    while (indexOfDeadSoldier >= circleOfSoldiers.Count || indexOfDeadSoldier < 0)
                    {
                        if (indexOfDeadSoldier >= circleOfSoldiers.Count)
                        {
                            indexOfDeadSoldier -= circleOfSoldiers.Count;
                        }
                        if (indexOfDeadSoldier < 0)
                        {
                            indexOfDeadSoldier += circleOfSoldiers.Count;
                        }
                    }
                    circleOfSoldiers.RemoveAt(indexOfDeadSoldier);
                }
                return circleOfSoldiers[0];
            }
    
            private static int Josephus4(int numberOfSoldiers, int soldiersToSkip)
            {
                LinkedList<int> circleOfSoldiers = new LinkedList<int>();
    
                for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
                {
                    circleOfSoldiers.AddLast(soldier);
                }
                LinkedListNode<int> currentSoldierWithAxe = circleOfSoldiers.First;
                while (circleOfSoldiers.Count > 1)
                {
                    for (int passAxe = 0; passAxe < soldiersToSkip; passAxe++)
                    {
                        currentSoldierWithAxe = currentSoldierWithAxe.Next;
                        if (currentSoldierWithAxe == null)
                        {
                            currentSoldierWithAxe = circleOfSoldiers.First;
                        } 
                    }
                    LinkedListNode<int> deadSoldier = currentSoldierWithAxe;
                    currentSoldierWithAxe = deadSoldier.Next;
                    circleOfSoldiers.Remove(deadSoldier);
                    if (currentSoldierWithAxe == null)
                    {
                        currentSoldierWithAxe = circleOfSoldiers.First;
                    } 
                }
                return currentSoldierWithAxe.Value;
            }
    
  • Still Not Tim (unregistered) in reply to Wongo
    Wongo:
    1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").
    1. What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

    As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

    In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

    Bear in mind that modern historians regard TJF's credibility as "questionable".

    And we only have TJF's account of what actually happened.

    As Wongo implies there - during the battle, anything could have happened - there was no way TFJ could know in advance there would be exactly 41 individuals present.

    So, the possibilities are:

    1: there is a very rapid shortcut, that no subsequent mathematician has been able to rediscover...

    2: he has previously calculated and memorised the answer for multiple scenarios...

    3: he works it out just once cycle ahead - "1, 2, argh, 1, 2, glurg" - and moves position to stay alive one move cycle - "I'll just check that Aaron is actually dead there..." walks over, stabs the corpse and stays standing in that new location...

    4: he was just genuinely lucky that day...

    5: he lied about what happened...

    6: he lied about what happened...

    < Kryten_mode > Now I realise the last two suggestions are actually the same point, but I thought it was such a big one it was worth mentioning twice. < Kryten_mode />

    So, in other words, the original documentation is faulty, and everyone here is now coding a solution to something other than the real situation... :)

  • (cs)

    The position that Josephus took was as the executioner.

    MArk B.

  • (cs)

    Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT

    Run pond.bat [NumberofDucks] [skips until kill]

    It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

    If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

    Repeat until the goose lays a golden egg in the pond, and the final position is reported.

    ======== pond.bat

    @ECHO OFF REM usage: pond.bat NumberOfDucks SkipsUntilGoose

    SET DUCKS=%1 SET GOOSE=%2

    IF %DUCKS%=="" GOTO USAGE IF %GOOSE%=="" GOTO USAGE

    REM *** Begin the spot-check loop *** :START REM start the golden goose at position 1 SET GOLDENGOOSE=1

    :BREED

    REM set the counter at 1 SET DUCKDUCK=1

    REM reset the counter SET COUNT=1

    :HATCH

    copy liveduck.bat duck%COUNT%.bat >nul

    SET /A COUNT=%COUNT%+1

    IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

    GOTO :HATCH

    :ENTERPOND

    REM set the number of alive ducks SET QUACKERS=%DUCKS%

    REM set the first calling duck SET QUACKER=1

    :DUCKDUCK

    CALL duck%QUACKER%.bat

    REM Two ending conditions IF %POND%==crap GOTO BADRESULT IF %POND%==gold GOTO GOODRESULT IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

    IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

    REM Else the next duck should be called

    SET /A QUACKER=%QUACKER%+1

    REM loop back to the first duck if needed IF %QUACKER% GTR %DUCKS% SET QUACKER=1

    GOTO DUCKDUCK

    :SOMETHINGAWFUL echo exception all ducks died but the golden goose never crapped GOTO END

    :BADRESULT REM oh no, the golden goose was killed! Let's start again, but move the REM goose one higher

    ECHO Golden Goose unsafe at position %GOLDENGOOSE%

    SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

    REM If we've exhausted positions, than this is unwinnable IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

    REM Recreate the ducks GOTO BREED

    :GOODRESULT REM the golden goose was safe! What position was he in? ECHO Golden Goose was safe at position %GOLDENGOOSE% GOTO END

    :ROASTDUCK REM the golden goose was unsafe at any position ECHO There is no safe spot for the goose. Would you like leg or thigh? GOTO END

    :USAGE ECHO Proper usage: ducks.bat NumberOfDucks NumberOfSkips

    :END SET COUNT=1

    :KILL del duck%COUNT%.bat SET /A COUNT=%COUNT%+1 IF %COUNT% LEQ %DUCKS% GOTO :KILL

    ============ liveduck.bat

    @ECHO OFF

    REM DUCKDUCK = the current loop counter REM GOLDENGOOSE = the position of the special goose REM POND = Where to put the return variable REM GOOSE = The max of the skip counter REM QUACKER = The last goose to act REM DUCKS = The number of ducks we started with

    REM If the highest counter was hit, this duck dies IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

    REM Otherwise quack and move onto the next duck SET POND=quack REM Increase the count by one SET /A DUCKDUCK=%DUCKDUCK%+1

    GOTO END

    :FUCKTHATDUCK

    SET DUCKDUCK=1

    REM This duck must die. If this duck is the last duck alive, the golden REM goose is safe

    IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

    REM Kill self SET POND=dead copy deadduck.bat %0 >nul GOTO :END

    :GOLDDIGGER

    REM The golden goose is about to die. See if it is the last duck alive, REM it wins. Ohterwise, bad.

    SET POND=crap

    IF %QUACKERS% EQU 1 SET POND=gold

    GOTO END

    :END

    ============ deadduck.bat

    @ECHO OFF REM Dead ducks aren't much fun. They don't increase the duckduck counter, REM since they don't count. Just ignore this duck and move on

    SET POND=brains

    :END

  • (cs)

    Simple in Python with a list that gets shorter:

    def josephus(n, k): soldiers = range(0,n) kill = -1 while n > 1: kill = (kill + k) % n soldiers.pop(kill) n -= 1 kill -= 1 return soldiers[0] + 1

  • (cs) in reply to halcyon1234
    halcyon1234:
    Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT

    Run pond.bat [NumberofDucks] [skips until kill]

    It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

    If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

    Repeat until the goose lays a golden egg in the pond, and the final position is reported.

    ======== pond.bat

    @ECHO OFF REM usage: pond.bat NumberOfDucks SkipsUntilGoose

    SET DUCKS=%1 SET GOOSE=%2

    IF %DUCKS%=="" GOTO USAGE IF %GOOSE%=="" GOTO USAGE

    REM *** Begin the spot-check loop *** :START REM start the golden goose at position 1 SET GOLDENGOOSE=1

    :BREED

    REM set the counter at 1 SET DUCKDUCK=1

    REM reset the counter SET COUNT=1

    :HATCH

    copy liveduck.bat duck%COUNT%.bat >nul

    SET /A COUNT=%COUNT%+1

    IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

    GOTO :HATCH

    :ENTERPOND

    REM set the number of alive ducks SET QUACKERS=%DUCKS%

    REM set the first calling duck SET QUACKER=1

    :DUCKDUCK

    CALL duck%QUACKER%.bat

    REM Two ending conditions IF %POND%==crap GOTO BADRESULT IF %POND%==gold GOTO GOODRESULT IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

    IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

    REM Else the next duck should be called

    SET /A QUACKER=%QUACKER%+1

    REM loop back to the first duck if needed IF %QUACKER% GTR %DUCKS% SET QUACKER=1

    GOTO DUCKDUCK

    :SOMETHINGAWFUL echo exception all ducks died but the golden goose never crapped GOTO END

    :BADRESULT REM oh no, the golden goose was killed! Let's start again, but move the REM goose one higher

    ECHO Golden Goose unsafe at position %GOLDENGOOSE%

    SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

    REM If we've exhausted positions, than this is unwinnable IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

    REM Recreate the ducks GOTO BREED

    :GOODRESULT REM the golden goose was safe! What position was he in? ECHO Golden Goose was safe at position %GOLDENGOOSE% GOTO END

    :ROASTDUCK REM the golden goose was unsafe at any position ECHO There is no safe spot for the goose. Would you like leg or thigh? GOTO END

    :USAGE ECHO Proper usage: ducks.bat NumberOfDucks NumberOfSkips

    :END SET COUNT=1

    :KILL del duck%COUNT%.bat SET /A COUNT=%COUNT%+1 IF %COUNT% LEQ %DUCKS% GOTO :KILL

    ============ liveduck.bat

    @ECHO OFF

    REM DUCKDUCK = the current loop counter REM GOLDENGOOSE = the position of the special goose REM POND = Where to put the return variable REM GOOSE = The max of the skip counter REM QUACKER = The last goose to act REM DUCKS = The number of ducks we started with

    REM If the highest counter was hit, this duck dies IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

    REM Otherwise quack and move onto the next duck SET POND=quack REM Increase the count by one SET /A DUCKDUCK=%DUCKDUCK%+1

    GOTO END

    :FUCKTHATDUCK

    SET DUCKDUCK=1

    REM This duck must die. If this duck is the last duck alive, the golden REM goose is safe

    IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

    REM Kill self SET POND=dead copy deadduck.bat %0 >nul GOTO :END

    :GOLDDIGGER

    REM The golden goose is about to die. See if it is the last duck alive, REM it wins. Ohterwise, bad.

    SET POND=crap

    IF %QUACKERS% EQU 1 SET POND=gold

    GOTO END

    :END

    ============ deadduck.bat

    @ECHO OFF REM Dead ducks aren't much fun. They don't increase the duckduck counter, REM since they don't count. Just ignore this duck and move on

    SET POND=brains

    :END

    mad props

  • (cs) in reply to Still Not Tim
    Still Not Tim:
    Wongo:
    2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")
    2: he has previously calculated and memorised the answer for multiple scenarios...
    1. then you keep fighting 2: memorizing 40 numbers is doable, especially if your life depends on it

    The number 40 had great significance to Hebrews (it rained for 40 days and 40 nights, etc.) so I wouldn't be surprised if it was standard practice to give up if your fighting force dropped below 40 (assuming your cause was hopeless)

  • rfdb (unregistered) in reply to Anon
    Anon:
    Ev:
    Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

    I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

    Aha! That's how he figured it out so quickly!

    Using his trusty abacus, he put dirt on one side of each bead. With lightning speed, he rolled beads over one-by-one, and found the correct spot. Brute force wins!

  • (cs)

    He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).

  • Vilx- (unregistered) in reply to mol1111
    mol1111:
    He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).
    And, all in all, maybe he just got lucky? :)
  • Mathieu Savage (unregistered)

    In PHP, with a nice visual representation

    <style> body{background-color:#FFF; font-family:arial;} .circle{background-color:#000000; width:30px; height:30px; color:#FFFFFF;} .survivor{background-color:#00CC00;} .dead{background-color:#FF0000;} </style> <?php function circle($soldiers,$skip){ $circle=array(); for($i=0; $i<$soldiers; $i++){ $circle[]=$i+1; } $i=0; $compteur=1; while(count($circle)>1){ if($compteur%$skip==0){ unset($circle[$i]); $circle = array_values($circle); if($i==0){$i=count($circle);}else{$i--;} } if($i>=count($circle)-1){$i=0;}else{$i++;}; $compteur++; } return ($circle[0]); } if(isset($_GET['form_set'])){ $survivor=circle($_GET['soldiers'],$_GET['skip']); echo $survivor; echo "Reset"; ?> <?php $k=1; $radius=7*$_GET['soldiers']; echo '<div style="position:relative; margin:0 auto; width:10px; height:50%; margin-top:'.($radius+50).'px;">'; for($i=-2;$i<=1.99999;$i = $i+(4/$_GET['soldiers'])){ echo "
    \n"; $k++; } ?> <?php }else{ ?> <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get"> <input type="hidden" name="form_set" value="on"/> <label for="soldiers">soldiers: </label><input name="soldiers" val=""/>
    <label for="skip">skip: </label><input name="skip" val=""/>
    <input type="submit"/> </form> <?php } ?>
  • (cs)

    It's just amazing now many of you dumbasses are willing to spend time working out and arguing over the workings of this puzzle. Are there really that many of you out of work?

    Caveat: I work. I read TDWTF while my work is compiling. I make occasional comments unrelated to the topic.

  • (cs) in reply to Josephus
    Josephus:
    Last
    ... best "first" post ever. Code Dependent, eat your heart out! :P
  • (cs)
    private static int jcircle(int soldiers, int skip)
    {
        Queue<int> q = new Queue<int>(Enumerable.Range(0, soldiers).ToList());
        while (q.Count > 1)
        {
            for (int i = 0; i < skip; i++)
                q.Enqueue(q.Dequeue());
            q.Dequeue();
        }
        return q.Dequeue() + 1;
    }
    

    Naturally, a Queue!

    If you add a print statement inside the loop you can almost visualize them lining up to get the axe ;)

    Soldiers: 2, Last Spot: 2 Soldiers: 3, Last Spot: 2 Soldiers: 4, Last Spot: 1 Soldiers: 5, Last Spot: 4 ... Soldiers: 39, Last Spot: 25 Soldiers: 40, Last Spot: 28 Soldiers: 41, Last Spot: 31

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article