• the pattern (unregistered)

    assuming there are only two people (indices 0 and 1) and killing every third person the safe spot would be 1:

    0 1 0 (kill)

    people safespot 2 1

    if you can't add the nth number to the safe spot without equaling or going over the total number of people you reset the safe spot to 0 or 1 depending on the outcome of the previous results difference as even or odd:

    people = 2 safespot = 1 n = 3

    for people = 3 1 + 3 >= 3 reset safe spot to 1 because (2-1)mod2 = 1 (odd)

    so: people safespot 2 1 3 1

    for people = 4 1 + 3 >= 4 (reset to 0) (3-1)mod2 = event

    so: people safespot 2 1 3 1 4 0

    for people = 5 0 + 3 = 3 (less than 5 so keep it)

    people safespot 2 1 3 1 4 0 5 3

    people = 6 3 + 3 >= 6 reset to 0 (5-3)mod2 = even

    people safespot 2 1 3 1 4 0 5 3 6 0 7 3 8 6

    6+3 >= 9... and so on

  • (cs) in reply to JonsJava
    JonsJava:
    function iWillSurvive($hey,$hay){
    
    I couldn't think of a better name for the function.

    Kudos but screw you for putting that in my head now...

  • IdontDoRecursion (unregistered)

    #include <stdio.h> #include <stdlib.h> int getLastStanding(int num, int step) { int i,j; for(i=1,j=0;i<=num;i++) {j+=step; if(j>=i) j%=i; } return j+1; }

    int main(int argc, char *argv[]) { int num=41, step=3; if(argc>1) num=atoi(argv[1]); if(argc>2) step=atoi(argv[2]); printf("You want to be solder %d of %d for a step of %d\n",getLastStanding(num,step),num,step); return(0); }

    The trick is that it is a step function which repeats when the total exceds N on a modulo basis...

  • (cs) in reply to Alex Mont
    Alex Mont:
    def J(n,k):
        if(n==1)
            return 0
        else
            return (J(n-1,k)+k)%n
    

    That's easy to make iterative.

    # Recursive
    sub J {
        my ($n, $k) = @_;
        return 0 if $n == 1;
        return ( J($n-1, $k) + $k ) % $n;
    }
    
    # Iterative
    sub J {
        my ($n, $k) = @_;
        my $j = 0;
        $j = ($j + $k) % $_ for 2..$n;
        return $j;
    }
    
  • Sue D. Nymme (unregistered)

    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.

  • Detunized Gravity (unregistered)

    Since the sexy one-line mathematical solution has been exposed, I felt I had no other choice than going for the brain dead solution. But since my language of choice is Ruby, I'll also go for the iterator and a bit of "dynamycally modifying a core object class". Just for the fun of it.

    #!/usr/bin/ruby
    class Array
      def kill!(i)
        count = 1
        while self.size > 1
          if count.modulo(i) == 0
            yield self.shift
          else
            self << self.shift
          end
          count += 1
        end
      end
    end
    ARGV.map! { |x| x.to_i }
    puts "Slaughtering #{ARGV[0]} soldiers, chopping one head every #{ARGV[1]}."
    print "Chopping head off of "
    soldiers = (1..ARGV[0]).to_a
    soldiers.kill!(3) { |dead_soldier| print dead_soldier, " " }
    puts
    puts "The last standing is #{soldiers[0]}."

    Code which gives...

    dg@gaia:~/temp$ ./soldier.rb 12 3
    Slaughtering 12 soldiers, chopping one head every 3.
    Chopping head off of 3 6 9 12 4 8 1 7 2 11 5
    The last standing is 10.
    dg@gaia:~/temp$ ./soldier.rb 40 3
    Slaughtering 40 soldiers, chopping one head every 3.
    Chopping head off of 3 6 9 12 15 18 21 24 27 30 33 36 39 2 7 11 16 20 25 29 34 38 4 10 17 23 31 37 5 14 26 35 8 22 40 19 1 32 13
    The last standing is 28.
    dg@gaia:~/temp$ ./soldier.rb 41 3
    Slaughtering 41 soldiers, chopping one head every 3.
    Chopping head off of 3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
    The last standing is 31.
    
  • Sue D. Nymme (unregistered) 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.

    Of course... that's 1-based. If you allow 0-based counting, it's two characters shorter.

  • tony roth (unregistered)

    to many posts to look through so I'm sorry if somebody already posted this but if you read the wiki on this there are two versions and each one comes up with a different answer!

  • (cs)
    Alex Papadimoulis:
    There is no “right” answer and no perfect solution, but some will certainly be better than others. The best of these will get a TDWTF sticker.
    Alex Papadimoulis:
    The comments are most certainly worth a read, if nothing else but to see things like the circuit diagram solution [...]

    Being the author of the linked solution, do I qualify for a TDWTF sticker? That'd be awesome!

    ikegami@adaelis.com

  • (cs)

    Here's the fast way, in Java, based on the Wikipedia article Josephus problem:

       public static int circleSurvivorRecursive(int men, int countTo)
       {
          return (men == 1) ? 
             0 : 
            (circleSurvivorRecursive(men - 1, countTo) + countTo) % men;
       }
    
    

    Unfortunately, this is deficient, since it provides no means to identify the best place for the surviving accomplice. So I decided to go to the even more general function that determines the kill order. The requested survivor is, of course, the last man in the array (and his accomplice next to last):

       public static int[] circleKillOrder(int men, int countTo)
       {
          boolean dead[] = new boolean[men];
          int kills[] = new int[men];
          
          int pos = men;
          for (int i=0; i < men; i++) {
             int steps = countTo;
             while (steps > 0) {
                pos = (pos + 1 >= men) ? 0 : pos + 1;
                if (!dead[pos]) steps--;
             }
             dead[pos] = true;
             kills[i] = pos;
          }
          
          return kills;
       }
    
    

    This next function then uses the above to determine the survival positions for any number of conspriators:

       public static int[] circleConspiringSurvivors(int men,
             int countTo, int conspirators) {
          int kills[] = circleKillOrder(men,countTo);
          int where[] = new int[conspirators];
          for (int i = 0; i < conspirators; i++) {
             where[i] = kills[--men];
          }
          return where;
       }
    
    

    Finally, this next is the most useful function of all. It describes where to put the bright boy who had this stupid idea so he's the first to get the axe. Everyone else survives.

       public static int whereToPutBrightBoy(int men, int countTo) {
          //return circleKillOrder(men,countTo)[0];
          return (countTo + men - 1) % men;
       }
    
  • (cs)

    Here's my python one-liner again :)

    def joph(n):
        return int(bin(n)[2:][1:] + bin(n)[2:][0], 2)
    

    Hopefully the next 'praxis' won't be available in Concrete Mathematics ;)

    Next challenge is trying it without it being solved with string manipulation.

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

    Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.

  • Karol Urbanski (unregistered) in reply to Sue D. Nymme
    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.

    Of course... that's 1-based. If you allow 0-based counting, it's two characters shorter.

    Awesome :).

  • DF (unregistered)

    I wrote a weirdo erlang solution which I think works. I am a functional programming noob and I started looking at erlang yesterday.

    -module(josephus).
    -export([josephus/2]).
    
    josephus(Soldiers, Interval)->
    	josephus(soldier_list(Soldiers),[], Interval, 0).
    
    josephus([Current | Rest], Survivors, Interval, Count) when Count /= Interval->
    	josephus(Rest, [Current | Survivors], Interval, Count + 1);
    
    josephus([_ | Rest], Survivors, Interval, _)->
    	josephus(Rest, Survivors, Interval, 0);
    
    josephus([], Survivors, Interval, Count)->
    	if
    		length(Survivors) > 1 ->
    			josephus(Survivors, [], Interval, Count);
    		true ->
    			[LastMan | _] = Survivors,
    			LastMan
    			
    	end.
    	
    
    
    soldier_list(Soldiers)->
    	soldier_list(Soldiers, []).
    
    soldier_list(Soldiers, List) when Soldiers > 0 ->
    	soldier_list(Soldiers - 1, [Soldiers | List]);
    
    soldier_list(0, List)->
    	[0 | List].
    
  • Matti Helin (unregistered)

    Matlab, using inbuilt circular shift function:

    function alive = josephus(n, k)
      alive =(1:n)';
      shift = 1-k;
      for h = 1:(n-1)
        alive = circshift(alive, shift);
        alive(1) = [];
      end
    
  • thc4k (unregistered)

    When you remove the recursion from j(1,k) = 1 j(n,k) = (j(n-1,k)+k) mod n

    its ( (k mod 2) + k ) mod 3 ) + k ) mod 4 ) ... ) + k mod n )

    can that be further simplified ?

  • Nukeme1 (unregistered)

    This version uses a form and posts the result back to the form.
    Edit1 contains mans Edit2 contains mansToSkip Edit3 gets the result (base 1 result, base 0 calculations) Using an array and a I'm dead indicator (to lazy to use a boolean array)

    procedure TForm1.Button1Click(Sender: TObject);
    var
      i,
      j,
      noMen,
      noMenToSkip: integer;
      circleRepresentation: array of integer;
    begin
      noMen := strToInt(edit1.text);
      noMenToSkip := strToInt(edit2.text);
      Edit3.text := '';
      SetLength(circleRepresentation,noMen);
      i := 0;
      while noMen <> 1 do
      begin
        j := noMenToSkip;
        while j <> 0 do //steps to the next to die
        begin
          if circleRepresentation[i] = 0 then
          begin
            j := j-1;
          end;
          if j <> 0 then
            i := (i+1) mod length(circleRepresentation);
        end;
        circleRepresentation[i] := 1; //kill the current man that is alive
        noMen := noMen - 1;
      end;
      while circleRepresentation[i] = 1 do
        i := (i+1) mod length(circleRepresentation);//go to the last man alive
      Edit3.Text := intToStr(i + 1);
    end;
    
  • (cs)

    AppleScript :

    on run
    	set num_soldiers to 0
    
    	repeat until num_soldiers is greater than 0
    		display dialog "Number of soldiers" default answer 12
    		set text_entered to text returned of the result
    		try
    			set num_soldiers to text_entered as integer
    		end try
    	end repeat
    	
    	set num_to_skip to 0
    	
    	repeat until num_to_skip is greater than 0
    		display dialog "Soldiers to skip" default answer 3
    		set text_entered to text returned of the result
    		try
    			set num_to_skip to text_entered as integer
    		end try
    	end repeat
    	
    	display dialog "Result: " & Josephus(num_soldiers, num_to_skip) & " (from 0 to " & (num_soldiers - 1) & ")" buttons {"WTF?!"} default button 1
    end run
    
    on Josephus(num, skip)
    	if num is 1 then return 0
    	return (Josephus(num - 1, skip) + skip) mod num
    end Josephus
  • Melvis (unregistered) in reply to Ron Moses
    Ron Moses:
    How's about a T-SQL function? I could probably tighten this up considerably but it works.
    CREATE FUNCTION dbo.JosephusFunction
    (
    	@NumberOfSoldiers int,
    	@SoldiersToSkip int
    )
    RETURNS int
    AS
    BEGIN
    
    DECLARE @i int, @TempSkip int;
    DECLARE @Soldiers table (SoldierNumber int, Dead bit);
    
    SET @i = 1;
    WHILE @i <= @NumberOfSoldiers
    BEGIN
    	INSERT INTO @Soldiers VALUES (@i, 0);
    	SET @i = @i + 1;
    END
    
    SET @i = 1;
    WHILE (SELECT COUNT(*) FROM @Soldiers WHERE Dead = 0) > 1
    BEGIN
    	SET @TempSkip = @SoldiersToSkip + 1;
    	WHILE @TempSkip > 0
    	BEGIN
    		SET @i = @i % @NumberOfSoldiers + 1;
    
    		WHILE (SELECT Dead FROM @Soldiers WHERE SoldierNumber = @i) = 1
    		BEGIN
    			SET @i = @i % @NumberOfSoldiers + 1;
    		END
    	
    		SET @TempSkip = @TempSkip - 1;
    	END
    
    	UPDATE @Soldiers
    	SET Dead = 1
    	WHERE SoldierNumber = @i;
    
    END
    
    RETURN (SELECT SoldierNumber - 1 FROM @Soldiers WHERE Dead = 0);
    

    END

    This doesn't seem to work if the answer is equal to the number of soldiers...

  • scott (unregistered) in reply to rm5248

    Same brute force, just using BitSet instead:

    import java.util.BitSet;
    
    public final class JosephusCircle
    {
      public static void main(String[] args)
      {
        JosephusCircle c = new JosephusCircle();
        c.bruteForce(12, 3);
      }
    
      private int bruteForce(int size, int numSkip)
      {
        BitSet s = new BitSet(size);
    
        int axeCounter = 1;
        while (s.cardinality() < size - 1)
        {
          for (int i = s.nextClearBit(0); i < size; i = s.nextClearBit(i + 1))
          {
            if (0 == axeCounter % numSkip)
            {
              s.set(i);
            }
            ++axeCounter;
          }
        }
        int live = s.nextClearBit(0) + 1;
        System.out.println("When axing every " + numSkip + ", you want " + live + " of " + size);
        return live;
      }
    }
    
  • H2 (unregistered)

    My Perl-solution. No recusion, just one loop. But I have to confess it's not totally straight forward ;)

    #/usr/bin/perl
    use strict;
    use warnings;
    
    if ((@ARGV != 2) || ($ARGV[0]!~m/[1-9]/) || ($ARGV[1]!~m/[1-9]/)) {
    	print "Missing or wrong arguments! Need two integers\n";
    	exit(0);
    }
    
    my ($soldiers,$count_val)=@ARGV;
    my @survivors;
    my $initiate=1;
    my $died_this_round=0;
    
    for (my $i=0;(@survivors>1 || $initiate==1);(($i<$soldiers && $initiate==1)?($i++):($i+=$count_val))) {
    	if ($i<$soldiers && $initiate==1) {
    		$survivors[$i]=$i+1;
    	}
    	elsif ($i==$soldiers && $initiate==1) {
    		$initiate=0;
    		$i=0;
    	}
    	else {
    		if ($i>(@survivors+$died_this_round)) {
    			$i-=(@survivors+$died_this_round);
    			$died_this_round=0;
    		}
    		
    		my $delete;
    		if ($i-$died_this_round-1>$#survivors) {
    			$delete=$i-$died_this_round-@survivors-1;
    		}
    		else{
    			$delete=$i-$died_this_round-1;
    		}
    		
    		splice(@survivors,$delete,1);
    		$died_this_round++;
    	}
    }
    print "Lucky one: $survivors[0]\n";
    
    # perl Josephus.pl 12 3
    Lucky one: 10
    
  • Shiftyness (unregistered)

    public class DeathLinkage { static int _Soldiers; static int _Skip; int dead = 0; int index = 0; Person[] jews;

        public DeathLinkage(int numSoldiers, int numSkip)
        {
             _Soldiers = numSoldiers;
             _Skip = numSkip;
             jews = new Person[_Soldiers];
             for (int i = 0; i < _Soldiers; i++)
             {
                 jews[i] = new Person();
             }
        }
        int counter = 1;
        public int killEachOther()
        {
    
            
            while (dead < (_Soldiers -1))
            {
                for (int i = 0; i < _Soldiers; i++)
                {
                    if (jews[i].alive)
                    {
                        if (counter == _Skip)
                        {
                            jews[i].alive = false;
                            counter = 1;
                            dead++;
                        }
                        else counter++;
                    }
                }
                killEachOther();
    
            }
            for (int i = 0; i < _Soldiers; i++)
            {
                if (jews[i].alive) index = i;
            }
            return index;
        }
        public string circleOfDeath()
        {
            
            if (_Soldiers <= 0 || _Skip <= 0)
            {
                return "Neither of the inputs may be 0 or a negative number.  Jews don't believe in counter-clockwise.";
    
            }
            else
            {
                if (_Soldiers == 1) return "1";
                else
                {
                    DeathLinkage dl = new DeathLinkage(_Soldiers, _Skip);
                    return dl.killEachOther().ToString();
                }
            }
        }
    
    
    }
    public class Person
    {
       
        public Person()
        {
            alive = true;
        }
        public bool alive { get; set; }
    }
    class Program
    {
        
        static void Main(string[] args)
        {
            DeathLinkage dl = new DeathLinkage(12, 3);
            System.Console.WriteLine(dl.circleOfDeath());
        }
    

    }

  • (cs)

    A perhaps not very clean but working solution in F#

    #light "off"	// Because I like tabs
    let Josephus num skip =
    begin
    	let mutable soldiers = [| 1 .. num |] in
    	let offset = ref 0 in
    	while Array.length soldiers > 1 do
    		printfn "Solders left standing: %A" soldiers;
    		// Killing
    		soldiers <- Array.mapi (fun i s -> if ((i + 1 + !offset) % skip) > 0 then s else 0) soldiers;
    		offset := ((Array.length soldiers % skip) + !offset) % skip;
    		printfn "Solders after killing: %A" soldiers;
    		// Cleaning
    		soldiers <- Array.filter (fun s -> s <> 0) soldiers;
    	done;
    	if Array.isEmpty soldiers then failwith "Damn...";
    	Array.get soldiers 0;
    end in
    

    (Just discovered F# while reading through the comments to the previous programming problem.)

  • jb somebody (unregistered)

    This is probably a WTF solution in itself. I've purposely not checked other comments so as not to spoil it. Here's my solution in C#:

    //assuming index 0 is top of circle public static int saveMe(int numOfSoldiers, int skip) {

            Boolean[] soldiers = new Boolean[numOfSoldiers];
            int ctr = 0;
            int removedCtr = 0;
    
            //Set all soldiers to a living state
            for (int i = 0; i < numOfSoldiers; i++)
                soldiers[i] = true;
    
                        
            while (removedCtr != numOfSoldiers - 1)
            {
                
                for (int i = 0; i < skip; i++)
                {
                    //If a soldier is dead skip him
                    while(soldiers[ctr] == false)
                    {
                        ctr += 1;
                        if (ctr > numOfSoldiers - 1) ctr = 0;
                    }
    
                    if (i == (skip - 1)  )
                    {
                        soldiers[ctr] = false;
                        removedCtr += 1;
                        Console.WriteLine("Soldier at {0} was removed.", ctr);
                    }
    
                    ctr += 1;
                    if (ctr > numOfSoldiers - 1) ctr = 0;
    
                }
            }
    
            ctr = 0;
            while (soldiers[ctr] == false)
            {
                ctr += 1;
            }           
    
            return ctr;
        }
    }
    
  • (cs)

    Since 2 people have beaten me to it already....

    unit Josephus;

    interface uses Generics.Collections, SysUtils;

    type BoolP = ^Boolean;

    function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer;

    implementation

    function GetJosephusLoc(Soldiers: Integer; Skip: Integer): Integer; var AliveList: TList<BoolP>; I: Integer; SkipI: Integer; Alive: BoolP; AliveCount: Integer; Found: Boolean; begin SkipI := 1; Found := False; AliveList := TList<BoolP>.Create(); for I := 1 to Soldiers do begin new(Alive); Alive^ := True; AliveList.Add(Alive); end; AliveList.TrimExcess; I:= 0; AliveCount := AliveList.Count; while AliveCount > 1 do begin if I = AliveList.Count then I := 0; Alive := AliveList[I]; if Alive^ then begin if SkipI = Skip then begin Alive^ := False; dec(AliveCount); SkipI := 1; end else inc(SkipI); end; inc(I) end; I:= 0; while (I < AliveList.Count) and (not Found) do begin Alive := AliveList[I]; if Alive^ then Found := True else inc(I); end; if Found then Result := I + 1 else I := -1;

    for I := 0 to AliveList.Count - 1 do begin Alive := AliveList[0]; Dispose(Alive); AliveList.Delete(0); end; FreeAndNil(AliveList); end;

    end.

  • odio (unregistered) in reply to Ian
    Ian:
    Code Dependent:
    Dave:

    foreach(soldier:soldiers){

    soldier.kill();

    }

    God.getInstance().sortOut(soldiers);

    Shouldn't God be static?
    If God were static how could He move in mysterious ways?

    To me, listening to static is indeed mysterious!

  • byornski (unregistered)

    The index starting at 0. Seems i've been beaten to the short iterative answer but who cares :P

        public static int Lives(int nSize, int nSkip)
        {
            int n = 0;
            for (int i = 2; i <= nSize; i++)
                n = (n + nSkip) % i;
            return n;
        }
    
  • MadCow42 (unregistered)

    A brute force Python version...

    menCount = 40 men = ["duck"] * menCount goose = 0

    while men.count("goose") < menCount - 1: chopper = ["duck", "duck", "goose"] while chopper != [] and men.count("goose") < (menCount - 1): if men[goose] != "goose": men[goose] = chopper.pop(0) goose = (goose + 1) % menCount print men

    print "Survivor: %s" %(men.index("duck") + 1)

  • MadCow42 (unregistered)

    I hate formatting issues... here's a brute-forced Python one:

    menCount = 40
    men = ["duck"] * menCount
    goose = 0
    
    while men.count("goose") < menCount - 1:
        chopper = ["duck", "duck", "goose"]
        while chopper != [] and men.count("goose") < (menCount - 1):
            if men[goose] != "goose":
                men[goose] = chopper.pop(0)
            goose = (goose + 1) % menCount
        print men
        
    print "Survivor:  %s" %(men.index("duck") + 1)  
    
  • Lerb (unregistered) in reply to nonny nonny

    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

  • Redredredredredred (unregistered)

    Too much recursion in here for my taste.

    Okay... first some ruby code (boring)

    def jc(men, skip)
    c=Array.new()
    men.times do |n| c << n end

    i=0 d=skip while c.length > 1 i = 0 if i==c.length

    d = d - 1
    puts "killed nr. #{c[i]}" if d==0
    c.delete c[i] if d==0
    i=i+1 if d!=0
    d=skip if d==0
    

    end

    c[0] end

    puts jc(12,3)

    And here C with double linked list awesomeness:

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct circle_t 
    {
      unsigned int nr;
      struct circle_t* next;
      struct circle_t* prev;
    } circle;
    
    
    void add(unsigned int nr, struct circle_t* prev)
    {
      struct circle_t* a;
      a=(struct circle_t*)malloc(sizeof(struct circle_t));
      a->nr=nr;
      a->prev=prev;
      prev->next=a;
    }
    
    void del(struct circle_t* ptr) 
    {
      ptr->prev->next=ptr->next;
      ptr->next->prev=ptr->prev;
      free(ptr);
    }
    
    unsigned int jc(unsigned int men, unsigned int skip) 
    {
      struct circle_t* p;
      struct circle_t* start;
      start=malloc(sizeof(struct circle_t));
      p=start;
    
      start->next=start;
      start->prev=start;
      start->nr=0;
    
      int i=1;
      int d=skip;
    
      while (i<men) 
      {
        add(i,p);
        p=p->next;
        i++;
      }
    
      p->next=start;
      start->prev=p;
    
      p=start;
      while (p != p->prev) 
      {
        d--;
        if (d==0) {
          printf("killed nr. %-4u\n",p->nr,p);
          p=p->next;
          del(p->prev);
          d=skip;
        }
        else 
        {
          p=p->next;
        }
      }
    
    
      printf("\n\n");
    
      return p->nr;
    }
    
    int main(int argc, char** argv) 
    {
      if (argc < 3) {
        printf("usage: %s men skip\n",argv[0]);
        return 1;
      }
      printf("safe spot: %u\n",jc(atoi(argv[1]),atoi(argv[2])));
    
      return 0;
    }
  • electrichead (unregistered) in reply to Wongo
    Wongo:
    db2:
    It looks like this works:

    n = number of soldiers k = skip ahead interval (3 in this example) i = "safe spot" index (1-based)

    i = 1;
    for (int c = 2; c <= n; c++) {
      i = (i + k) % c;
      if (i == 0) {
        i = c;
      }
    }
    return i;
    

    Brilliant! It works perfectly! Congrats, db2, you made my day!

    Now, if we could just remove the loop and turn it into a formula, we might find out how Josephus did it "very quickly"...

    The only way I can see for him to succeed in this is for him to have known about the arrangements before-hand so he could prepare. Let's assume that this method of surrender was discussed and agreed-upon before the battle. There would be no way to know how many soldiers were left, so he would have made up the same table we made earlier at the bottom of Page 1 of the comments. He could have memorized this, but could also have used the algorithm that many people here found (but I did not :( ) I am using the one quoted. The important line is "i = (i + k) % c;" This gives us a table that looks kind of like this: (1 + 3) % 2 (2 + 3) % 3 { 3 soldiers, stand at position 2} (2 + 3) % 4 (1 + 3) % 5 (4 + 3) % 6 { 6 soldiers, stand at position 1 } ... ...

    Refer to the comment at the bottom of page 1 of comments for a bigger table. You can see that it resets to 1, 0( which becomes 2), or 2 every now and then. The series on the right climbs by 3 until it "catches up" to the series on the left. So you can jump from one reset straight to the next. (2 + 3) % 15 for 15 is one reset, the next is 6 steps up: (2 + 3 + (3 * 6)) % (15 + 6), or 23 % 21 for 21. This means that if there are 21 soldiers, he should stand as the second. The next jump takes you straight to (2 + 3 + (3 * 9)) % (22 + 9). This resets to 32 % 31 for 31 soldiers. You can now jump straight to (1 + 3 + (3 * 9)) % (32 + 9) which is 31 % 41 for 41 soldiers.

    So as long as he remembered the resetting values i.e. 1 .. 7 1 .. 10 2 .. 15 2 .. 22 1 .. 32 2 .. 48, etc. he would be able to calculate the appropriate position in seconds. So for 41, he would know to use the entry corresponding to 32 since it is less than the next reset at 48. 41 - 32 = 9; and the position he needed to stand on would be (1 + 3) {corresponding to 32 in that table} added to 3 * 9. This would be 31.

  • Herby (unregistered) in reply to RayMarron
    RayMarron:
    I just wanted to say that the animations accompanying these are brilliant. :)
    I have to say that I agree. Now for the next problem, code up the animations.
  • reuven (unregistered)

    Here's my solution in Matlab (only language I really know that well.): function safe_index = josephus(num_soldiers,num_skip)

    survivor_mat=[];

    for i=1:num_soldiers survivor_mat(i)=i;; end

    count = 0; while length(survivor_mat) > 1 count = count + num_skip; while count > length(survivor_mat) count= count-length(survivor_mat); survivor_mat(survivor_mat == 0) = []; end if length(survivor_mat) > 1 survivor_mat(count)=0; end end safe_index = survivor_mat;

  • (cs)

    C#, using regex and strings - for fun.

            private static int GetJosephusSafeSpot(int nSoliderCount, int nSkipValue)
            {
                var sbRegexSkips = new StringBuilder("L");
                nSkipValue--;
                for (int i = 0; i < nSkipValue; i++)
                    sbRegexSkips.Append("D*L");
    
                Regex regKill = new Regex(sbRegexSkips.ToString(), RegexOptions.Compiled);
    
                string strCircleOfDeath = new string('L', nSoliderCount);
    
                int nIndex = 0;
                while (strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).Count(c => c == 'L') > 1)
                {
                    Match match = regKill.Match(strCircleOfDeath, nIndex);
                    strCircleOfDeath = regKill.Replace(strCircleOfDeath, m => { return m.Value.Remove(m.Value.Length - 1) + "D"; }, 1, nIndex);
                    nIndex = match.Index+match.Value.Length;
                    while (strCircleOfDeath.Substring(nIndex).Count(c => c == 'L') <= nSkipValue)
                        strCircleOfDeath += strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount);
                }
    
                return strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).LastIndexOf('L');
            }
    
  • Paul Marfleet (unregistered)

    Solution in F#:

    let josephus numberOfMen skip =
      let men = [1..numberOfMen]
      let rec doTurn men position =
        match men with
        | hd :: [] -> hd
        | _ ->
          let newPosition = (position + skip) % men.Length
          doTurn (List.mapi (fun i man -> if i = newPosition then 0 else man) men 
          |> List.filter(fun man -> man > 0)) (newPosition - 1)
      doTurn men -1
    
  • Wongo (unregistered) in reply to Maurits
    Maurits:
    Wongo:
    Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

    Maybe he worked it out beforehand. Maybe it was his idea... if so, everyone else wound up with an earful of cider.

    OK, so here's another solution to the problem, this time in BabyTalk :

    Josephus - Eenie Meenie Miiii...(skip himself)...iiiny Moe.

  • Kevin M (unregistered)

    Here's a brute force solution in Java that I don't think anyone else has posted. It follows the problem description by treating a Vector as a circular buffer. Each vector element is the initial index of each soldier.

    int josephus(Vector<Integer> v) {
      if (v.size() == 1)
        return v.elementAt(0).intValue();
    
      v.add(v.remove(0));
      v.add(v.remove(0));
      v.remove(0);
      return josephus(v);
    }
    
  • (cs) in reply to Lerb
    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

    GodFactory.getGods(GodFactory.AGNOSTIC) = throw Unknown Exception

  • JHolland (unregistered)

    This is such a simple algorithm I am not sure how to make my solution THAT much more complicated. I did manage to use two subroutines, not counting josephus(), as well as recursion. And I broke LOTS of Perl Best Practices. Maybe tomorrow I'll try to figure this one out using only Regexes.

    sub josephus {
      my ($circle, $skip) = @_;
      return 1 + calc_j(0, $skip, 0 .. $circle-1);
    }
    
    sub calc_j {
      sub array_except {
        my $except = pop @_;
        my @array = @_;
        splice @array, $except, 1;
        return @array;
      }
      ($idx, $skip, @array) = @_;
      return @array == 1 ?
             $array[0] :
             calc_j($new_idx=($idx+$skip-1) % @array, $skip, array_except(@array, $new_idx));
    }
    
    print "josephus(12, 3) = ", josephus(12, 3), "\n";
  • God (unregistered) in reply to Lerb
    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

    Zeus is Greek not Roman... that would be Jupiter

  • Jedi (unregistered)

    *v,n;main(s,f){for(n=1;atoi(1[v=f])-s;n=(n+atoi(2[v=f]))%++s);printf("%d\n",n);}

  • Still Not Tim (unregistered)

    So 39 soldiers were done for, but Titus escaped.

    All these comments, and not one pointing out the irony of using Python to show... erm... the Romans didn't do for Titus.

  • Oscar Olim (unregistered)

    I'd say the safe spot is in the middle, as only the people in the circle get killed :P

  • Dr. Batch (unregistered)

    Looking at the table of reset values idea that is discussed in earlier comments, I see that finding those helpful values is quite easy.

    Pseudocode:

    X is a placeholder for the last reset value, starts at 1 Y is a placeholder for what you have to reset to at X, starts at 0 function is called with variables S(oldiors) and C(ount)

    -startloop distanceToNextX = ( (X-Y)/(C-1) rounded up )

    if S is less than nextX return Y + (S-X)*c else X = nextX Y = (Y + (distance to next X * C)) mod x -endloop

    Batch file:

    @echo off rem - argument 1 is number of soldiers, argument 2 is the number to count to each time

    call :josephus %1 %2

    echo the servivor is at index %j%

    exit /b

    :josephus set s=%1 set c=%2 set x=1 set y=0

    :loopbegin echo begin loop set /a z="(((2*(x-y))/(c-1))+1)/2" set /a xn="x+z" if %s% lss %xn% ( set /a j="y+((s-x)c)" ) else ( set x=%xn% set /a y="(y+(zc))%%x" goto :loopbegin )

    exit /b

    This algoritem is more efficient than any of the other looping or recursion alborithems I have seen implemented thus far. Even as a (ineficient) batch file it finds the servivor in a group of 32727 (#6132) in the blink of an eye while looping only two dozen times.

    Trying that will overflow the stack on any of the recursive programs. Go ahead and try it with any of the other looping ones. I'll wait.

  • Gary Hall (unregistered) in reply to Dave
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    

    Monotheist, ey?

    DeityRepo.FindBySpecialisation(DeitySpecialisations.War).SortOut(soldiers);
    
  • Dr. Batch (unregistered) in reply to Dr. Batch

    find and replace "servivor" with "survivor". How embarrassing.

  • Michael van der Gulik (unregistered)

    I tried to go for good readability.

    In Smalltalk, comments are delimited using double-quotes. Variables are declared between verticle bars. The caret returns a value from the method. Otherwise it's pretty much like Python, but with a built-in debugger.

    Interestingly, if you want to give the survivors names, you can replace:

    circle := OrderedCollection withAll: (1 to: n).

    with:

    circle := OrderedCollection withAll: #('Phillipus' 'Caesor' 'Nero' 'Josephus' 'Cactus').

    and then this method will return the name of the survivor.

    survivorInCircleOfSize: n
    	| circle victim |
    	circle := OrderedCollection withAll: (1 to: n).
    	victim := 0.
    	[circle size > 1] whileTrue: [
    		victim := victim + 3.
    		victim := victim rem: (circle size). " rem means 'mod' "
    		(victim = 0) ifTrue: [ victim := circle size ].
    		" Murder! "
    		circle removeAt: victim.
    		victim := victim - 1. " Make sure that we take the removal into account. "
    	]. 
    	^ circle anyOne. " There should only be one dude left. "
    
  • (cs)

    Really modeling the situation using Scheme message passsing OOP.

    (define (make-person num)
      (let ((alive true)
    	(next 'nobody))
        (lambda (op)
          (cond ((eq? op 'alive?) alive)
    	    ((eq? op 'dead?) (not alive))
    	    ((eq? op 'position) num)
    	    ((eq? op 'next) next)
    	    ((eq? op 'stand-next-to) (lambda (person)
    				       (set! next person)))
    	    ((eq? op 'kill) (if (not alive)
    				(error "Cannot kill PERSON" num "-- already dead")
    				(set! alive false)))
    	    (else (error "Unknown operation -- PERSON" num))))))
    
    (define (make-circle n)
      (let ((first-person (make-person n)))
        (let iter ((n (- n 1))
    	       (current-person first-person))
          (if (zero? n)
    	  (begin 
    	    ((first-person 'stand-next-to) current-person)
    	    current-person)
    	  (iter (- n 1) (let ((new-person (make-person n)))
    			  ((new-person 'stand-next-to) current-person)
    			  new-person))))))
    
    (define (josephus n m)
      (define (skip-m-and-kill circleptr)
        (let iter ((i m)
    	       (cur-person circleptr))
          (cond ((cur-person 'dead?) (iter i (cur-person 'next)))
    	    ((zero? i) (cur-person 'kill) cur-person)
    	    (else (iter (- i 1) (cur-person 'next))))))
      (let ((circle (make-circle n)))
        (let iter ((number-alive n)
    	       (curpos circle))
          (if (zero? number-alive)
    	  (curpos 'position)
    	  (iter (- number-alive 1) (skip-m-and-kill curpos))))))
    
  • Comp Sci Student (unregistered) in reply to God
    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?

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article