• Brad (unregistered)

    Delphi

    program Josephus;
    
    {$APPTYPE CONSOLE}
    
    uses
      SysUtils;
    
    
    { SafeIndex : Returns zero-based index of safe location in Josephus' Circle.
      - soldierCount : number of soldiers in initial circle
      - killEvery : interval at which to kill off soldiers
    }
    function SafeIndex(
      soldierCount : Integer;
      killEvery : Integer
    ) : Integer;
    var
      count : Integer;
      safe : Integer;
    begin
      count := 1;
      safe := 0;
    
      while (count < soldierCount) do begin
        Inc( count );
        safe := (safe + killEvery) mod count;
      end;
    
      Result := safe;
    end; // SafeIndex
    
    
    procedure WriteUsage;
    begin
      WriteLn('Usage: Josephus <soldierCount> <killEvery>');
    end;
    
    
    var
      killEvery : Integer;
      killEveryStr : String;
      safe : Integer;
      soldierCount : Integer;
      soldierCountStr : String;
    
    begin
      if ParamCount < 2 then begin
        WriteUsage;
        Exit;
      end;
    
      soldierCountStr := ParamStr( 1 );
      killEveryStr := ParamStr( 2 );
    
      try
        soldierCount := StrToInt( soldierCountStr );
        killEvery := StrToInt( killEveryStr );
    
      except
        on EConvertError do begin
          WriteLn('Arguments must be numeric.');
          WriteUsage;
          Exit;
        end;
      end;
    
      safe := SafeIndex( soldierCount, killEvery );
      WriteLn('Safe index: ' + IntToStr( safe ));
    end.
    
  • (cs) in reply to Wongo
    Wongo:
    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 ...snip... 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 ?

    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;
    
  • justsomedude (unregistered) in reply to steenbergh

    Of course that is Excel + VBA, not pure VBA.

    VBA's bad reputation drives me nuts...it's a good language for what it's intended uses are...so I can't help but be the ass who points out:

    1)There's no need to manipulate values on a worksheet, you can use variables and it will run much faster. Each time code touches a worksheet object you pay a large price in speed. Better to do everything in memory and only kick the final result. You can also use Debug.Print to write to the immediate window. Do While Range(checker).Value > 1 will perform much better if replaced by a check against an internal variable, particularly for large loops.

    1. You should use Columns("A:D").ClearContents instead of four separate calls; faster to both write and run. No need to clear columns if you keep data in memory. (arrays?)

    2. It's a bad habbit to use code like: Range(somthing).Method, doing this will break if you accidentally activate a different worksheet while the code is running. When you reference "Range", you are implictly saying Application.ActiveWorksheet.Range, which users can break easily. It's much better to explictly declare which worksheet you want to operate on, using something like sheet1.Range(something) or Worksheets("ExternalSheetName").Range(something) (and bonus points if you use with blocks to reduce the number references to higher level objects)

    3. No need to type cast strings when using & for string concatination. strMyString = "Some Text " & i runs faster than strMyString ="Some text" & Cstr(i)

    4. using code to write worksheet functions is a bit much, there are times where that is useful, but you have the values in code so why not just add them in code too?

    5. Dim cur As String: cur = "C" & CStr(j), not sure if this is considered bad form or not, but I'd wager dimming a var inside a loop slows things significantly. You're replacing the value of this variable each time, no need to redim it.

  • Wongo (unregistered) in reply to halber_mensch
    halber_mensch:
    Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

    {1,2,3,4,5} {1,3,5} {3}

    No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

    In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

  • justsomedude (unregistered) in reply to justsomedude
    justsomedude:
    Of course that is Excel + VBA, not pure VBA..

    {snip}

    Quote fail...that was in reference to the vba post on page 1...

  • Karol Urbanski (unregistered) in reply to Capt. Obvious
    Capt. Obvious:
    1 + (n-1)(k-1) mod n
    Neither this nor 1+(n-1)k mod n works. Consider case 17 soldiers, the person to count 2 dies. So, n=17, k=2. The correct answer for those is index 2 (3 if indexed from 1).

    for 1 + (n-1)k mod n: 1 + (17-1)2 mod 17 = 1 + 32 mod 17 = 16, which is incorrect. for 1 + (n-1)(k-1) mod n: 1 + (17-1)(2-1) mod 17 = 1 + 16 mod 17 = 17, which is also incorrect.

    I assumed you mean % as taking precedence over addition, in C fashion. However, even if you actually meant (1 + (n-1)k) mod n or (1 + (n-1)(k-1)) mod n for 17,2 the results are 16 and 0, respectively. Also incorrect.

  • DesGrieux (unregistered) in reply to Wongo
    Wongo:
    halber_mensch:
    Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

    {1,2,3,4,5} {1,3,5} {3}

    No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

    In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

    {1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

  • Chad (unregistered) in reply to Wongo

    By looking at that sequence I was able to come up with the following javascript solution:

    function josephus3(count, seed) { var index = seed % 2 == 0 ? 1 : 2;

    for (var i = 3; i <= count; i++)
    {
      index += seed;
      while (index > i)
        index -= i;
    }
    
    return index;
    

    }

    First we determine the starting index based on whether the seed is even or odd.

    Next we follow the pattern of the solution above, which is, every time you go up from two you add the seed to the index and if the new index is greater than i (the number of men) you subtract i.

    I expected this to work with a seed of 3, but I was surprised when I found out it works with any seed. It was easy for me to write an algorithm to represent the pattern, whereas I don't think I could figure out the other more elegant approaches.

  • Ron Moses (unregistered)

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

  • C Sebold (unregistered)

    Clojure!

    (defn josephus [num-soldiers skip]
      (let [ax (fn [soldiers index]
                 (let [real-index (if (> index (count soldiers))
                                    (rem index (count soldiers))
                                    index)]
                   (concat (nthnext soldiers real-index)
                           (take (dec real-index) soldiers))))]
        (loop [alive (range 1 (inc num-soldiers))]
          (if (= (count alive) 1)
            (first alive)
            (recur (ax alive skip))))))

    Most of this function is just the definition for the ax() function.

  • Ed (unregistered)

    JavaScript 1.8:

        function j(n, k) n <= 1 ? 0 : (j(n - 1, k) + k) % n;
    

    Non-recursive form:

        function j(n, k) { let p = 0, i = 1; while (i < n) p += k, p %= ++i; return p }
    

    As mentioned at Wikipedia, a closed form exists for k = 2: j(n, 2) = 2 * (n - 2 ^ log2(n)) There is no closed form for k = 3; a good place to start is OEIS A054995.

  • Akoi Meexx (unregistered) in reply to Akoi Meexx

    Woops, that should be unset($roulette[$arrayIndex]); not unset($roulette[$value]);

    Why must comments keep erroring out?

  • Wongo (unregistered) in reply to DesGrieux
    DesGrieux:
    Wongo:
    halber_mensch:
    Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

    {1,2,3,4,5} {1,3,5} {3}

    No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

    In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

    {1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

    You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

  • Bim Job (unregistered) in reply to Satanicpuppy
    Satanicpuppy:
    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.

    Truly, there is nothing sexier than recursion. It's especially elegant for problems like this one.

    Unfortunately, it's a bitch to maintain, and a memory hog for larger functions.

    Sexier: Cate Blanchett. Bitch to maintain: Well, possibly Ms Blanchett also, for all I know. Then again, why on earth would a correct recursive procedure be any more of a bitch to maintain than a correct iterative homologue? Memory hog: Tail recursion, my man. Tail recursion.

    Other than that, all these solutions appear to assume a boolean state for each soldier of dead/alive. Whatever happened to death_not_found?

  • Andreas Kromann (unregistered) in reply to Wongo
    Wongo:
    DesGrieux:
    Wongo:
    halber_mensch:
    Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

    {1,2,3,4,5} {1,3,5} {3}

    No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

    In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

    {1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

    You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

    My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc. Sorry for wasting yout time :)

  • (cs)

    Naive, very much to the letter solution in Scheme:

    (define josephus
      (lambda (n skip)
        (let ([S (build-list n #t)]
    	  [a n])
          (letrec ([inner
    		(lambda (i c)
    		  (if (> a 1)
    		      (if (car (list-ref S i))
    			  (if (< c skip)
    			      (begin
    				(inner (modulo (1+ i) n) (1+ c)))
    			      (begin
    				(set-car! (list-ref S i) #f)
    				(set! a (- a 1))
    				(inner (modulo (1+ i) n) 0)))
    			  (inner (modulo (1+ i) n) c))
    		      (get-alive 0)))]
    	       [get-alive
    		(lambda (i)
    		  (if (eq? (car (list-ref S i)) #f)
    		      (get-alive (1+ i))
    		      (begin (display "With ")
    			     (display n)
    			     (display " soldiers and killing every ")
    			     (display (1+ skip))
    			     (display "th, the safe spot is: ")
    			     (1+ i))))])
    	(inner 0 0)))))
    
    (define build-list
      (lambda (n val)
        (if (zero? n)
    	'()
    	(cons (cons val '()) (build-list (- n 1) val)))))
    

    And a test session:

    Petite Chez Scheme Version 7.4
    Copyright (c) 1985-2007 Cadence Research Systems
    
    > (load "josephus.scm")
    > (josephus 12 2)
    With 12 soldiers and killing every 3th, the safe spot is: 10
    > (josephus 41 2)
    With 41 soldiers and killing every 3th, the safe spot is: 31
    > 
    
  • (cs)
    (define (josephus n q)
      (let solve ((i 1) (jn 0))
        (if (< n i)
    	(+ 1 jn)
    	(solve (+ i 1) (remainder (+ jn q 1) i)))))
    

    Edit: Use one-based index

    Addendum (2009-07-29 14:13): (q is "number to skip", so kill every q+1 th) -- I originally had it the other way but then edited it.

  • Mr. Bob (unregistered)

    The solution is:

    "Hey everyone, I'll watch the door while you guys sort this out."

  • Wongo (unregistered) in reply to Andreas Kromann
    Andreas Kromann:
    My formula is wrong, because I forgot about the modulus :) It changes when you reduce the problem in size... mod n, mod n-1 etc. Sorry for wasting yout time :)

    Nah, I knew you were on to something... Couldn't have found it myself anyway (or maybe with lots more time).

  • (cs) in reply to Wongo
    Wongo:
    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"...

    Granted, I haven't tested it for other values of k, or for weird edge cases, but I was able to precisely reproduce your list of safe spots by putting a Console.WriteLine() at the bottom of the loop body.

  • Ev (unregistered)

    Sure, all these new language codes are pretty good, but I'd really like to see somebody come up with a Turing Machine solution.

  • (cs) in reply to Perl Monk
    Perl Monk:
    Perl Golf'd:

    $p[$-1]=$ for 1..$ARGV[0];splice@p,$k=($k+$ARGV[1]-1)%@p,1while@p>1;print@p

    77 chars :-)

    My perl approach:

    '@A=(1..$ARGV[0]);while($A[1]){$j=shift@A;push(@A,$j)if(++$i)%$ARGV[1]}print@A
    

    78 chars :-)

  • Anon (unregistered) in reply to Wongo
    Wongo:
    DesGrieux:
    Wongo:
    halber_mensch:
    Um, you're doing it wrong.. if you have 5 soldiers and kill every other one (not the first one in every round) you get:

    {1,2,3,4,5} {1,3,5} {3}

    No no, he's right, you don't start over after each round, it's round robin! The last spot is 5!

    In any case, if there are n soldiers and you kill every kth, there one position where you should never ever stand: kth.

    {1,2,3,4,5} => {1,3,4,5} => {1,3,5}. We begin counting now at 5, which is skipped, so remove 1: {3,5}. We begin count now at 3, which is skipped, so remove 5: {3}

    You're right, I misunderstood the original reasoning from halber_mensch (and yours too). The last spot is indeed 3.

    No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

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

  • (cs)
    (define (josephus n m)
      (let loop ((d 1))
        (if (> d (* m n))
    	(- (+ (* n m) n 1) d)
    	(loop (ceiling (* d (/ (+ m 1) m)))))))
    

    Iterative and runs in logarithmic time

    Addendum (2009-07-29 14:08): NOTE: m is number to skip as listed in article -- so every m+1 is killed.

  • Korkut (unregistered)

    Why Prolog gets no love... K is step size, I is 0 based index, N is number of unluckies.

    josephus(0,1,_).
    josephus(I,N,K) :- M is N-1, josephus(J,M,K), I is (J+K) mod N, !.
    

    Cut is not absolutely necessary.

  • Srki (unregistered) in reply to horizon
    horizon:
    assuming that the starting position is 0:
    int f(int numberOfSoldiert, int numberOfSkips)
    {
       return ((numberOfSoldiers-1)*numberOfSkips)%numberOfSoldiers;
    }
    
    Great, I believed there is a very simple solution... Because of "VERY FAST" phrase. This solution has constant time, all others are n dependent.
  • Ramūns (unregistered)

    Here's another javascript version

    function josephus(n,k){
      if ( n <= 1 ) {
        return 1;
      }
      var data = [];
      for ( var i = 0; i < n; i++ ) {
        data[i] = i+1;
      }
      var l = n;
      for ( var i = (k-1)%l; l > 1; i = (i+k-1)%(--l) ) {
        data.splice(i,1);
      }
      return data[0];
    }
    
  • Phil (unregistered)

    Good old C. Still no 860 iterations. First method 398 steps; recursive method does n-1 recursions; iterative solution loops n-1 times.

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int StrSurvive (int n, int k)
    {
    	char *soldiers;
    	int surv, i, pos, count = 0;
    
    	soldiers = (char *) malloc (n+1);
    	memset (soldiers, 'O', n);
    	soldiers[n] = 0;
    	for (pos = 0, surv = n; surv > 1; surv--)
    	{
    		for (i = 0; ;)
    		{
    			count++;
    			if (soldiers[pos] == 'O')
    				if (i == k)
    					break;
    				else if (++i == k)
    					soldiers[pos] = 'X';
    			if (++pos == n)
    				pos = 0;
    		}
    		printf ("%s\n", soldiers);
    	}
    	printf ("Count = %d\n", count);
    	return pos;
    }
    
    int RecSurvive (int n, int k)
    {
    	if (n == 1)
    		return 0;
    	else
    		return (RecSurvive(n-1,k)+k)%n;
    }
    
    int LoopSurvive (int n, int k)
    {
    	int i, pos = 0;
    
    	for (i = 1; i < n; i++)
    		pos = (pos + k) % n;
    	return pos;
    }
    
    void main(void)
    {
    	printf ("Pos = %d\n", StrSurvive (41, 3));
    	printf ("Pos = %d\n", RecSurvive (41, 3));
    	printf ("Pos = %d\n", LoopSurvive (41, 3));
    }
    
  • Ryan (unregistered) in reply to Satanicpuppy

    Here's another Python version that replaces the recursion with a for loop. Same basic solution, but without the potential memory issue.

    def jos(soldiers, skip):
        safe = 0
        for x in xrange(2, soldiers+1):
            safe = (safe + skip) % x
        return safe
    
  • riotopsys (unregistered)

    this should be fitting for the daily wtf

    struct position{ int id; position * nextGuy; position * lastGuy; };

    int safe(int people, int count){ position * circle = new position; position * head = circle;

    circle->id = 1; for ( int c = 2; c < people+1; c++){ position * temp = new position; temp->id = c; temp->lastGuy = head; head->nextGuy = temp; head = temp; } circle->lastGuy = head; head->nextGuy = circle;

    while( circle->lastGuy != circle->nextGuy ){ for(int c = 0;c < count; c++ ){ circle = circle->nextGuy; } head=circle; circle=circle->nextGuy;

      head->lastGuy->nextGuy = head->nextGuy;
    
      head->nextGuy->lastGuy = head->lastGuy;
    
      delete head;
    

    }

    int result = circle->id; delete circle; return result; }

  • aehiilrs (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.

    Give me n soldiers and an axe.

  • (cs)

    Perl Golf. 83 characters including perl -e and the two given arguments 40 and 3. 69 characters between the quotes.

    perl -e"@=(1..$ARGV[0]);++$c%$ARGV[1]?$i++:splice@,$i%=@,1while$#;print@_" 40 3

    Addendum (2009-07-29 13:24): Shaved off three characters by using "shift" instead of $ARGV[0].

    80 characters for the whole thing; 66 between the quotes.

    perl -e"@=(1..shift);++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

    http://blogs.msdn.com/matthew_van_eerde/archive/2009/07/29/bad-perl-josephus-problem.aspx

    Addendum (2009-07-29 14:00): 78/64 dropping the parentheses.

    perl -e"@=(1..shift);++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

    Addendum (2009-07-29 14:09): Actually dropping the parentheses.

    perl -e"@=1..shift;++$c%$ARGV[0]?$i++:splice@,$i%=@,1while$#;print@_" 40 3 28

  • Phil (unregistered)

    Ops!

    In LoopSurvay, please change

    pos = (pos + k) % n;

    to

    pos = (pos + k) % (i+1);

  • (cs)

    public string DoJosephus(int soldiersCount, int soldiersToSkip) { List<string> soldiers = new List<string>(soldiersCount); for (int j = 0; j < soldiersCount; j++) soldiers.Add((j+1).ToString()); int i = soldiersToSkip - 1; do { i = GetStep(i, soldiers.Count); soldiers.RemoveAt(i); if (i + soldiersToSkip > soldiers.Count) i = i - soldiers.Count; i = i + soldiersToSkip - 1;

            } while (soldiers.Count>1);
            return soldiers[0];
        }
    
        private int GetStep(int i, int count)
        {
            if (i < count) return i;
            else i = i - count;
            return GetStep(i, count);
        }
    
  • Dr. Batch (unregistered)

    A batch file solution:

    @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 survivor is at index %survivor% exit /b

    :josephus set soldiers=%1 set /a soldiersnext="soldiers-1" set count=%2 if %soldiers% neq 1 call :josephus %soldiersnext% %count% set soldiers=%1 set /a survivor="(count+survivor)%%soldiers" exit /b

  • Anonymous (unregistered)

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

  • nonny nonny (unregistered) in reply to SR
    SR:
    d3matt:
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    yes... the God class is a singleton...

    d3matt: I've got a billion or so Hindus on the phone who don't agree

    I thought there needed to be three pointers to the same object.

  • Jean-Paul (unregistered)

    Wrote this during my lunch break. Compiles in Turbo Pascal 5.0, uses pointers...

    Program JosephusCircle;
    Type
      Jptr = ^ Jnode;
      Jnode = record
                Number : integer;
                Next : Jptr;
                Prev : Jptr;
              end;
    var
      n : integer;
      s : integer;
    
    Function MakeCircle(Size : integer) : Jptr;
    var
     lcv : integer;
     lst : Jptr;
     fst : Jptr;
     prv : Jptr;
    begin
     new(fst);
     fst^.Next := nil;
     fst^.Prev := nil;
     fst^.Number := 1;
     prv := fst;
     for lcv := 2 to Size do
       begin
         new(lst);
         prv^.Next := lst;
         lst^.Prev := prv;
         lst^.Next := nil;
         prv := lst;
         lst^.Number := lcv;
       end;
     lst^.Next := fst;
     fst^.Prev := lst;
     MakeCircle := fst;
    end;
    
    Function Kill(var Doomed : Jptr) : Jptr;
    begin
      Doomed^.Prev^.Next := Doomed^.Next;
      Doomed^.Next^.Prev := Doomed^.Prev;
      Kill := Doomed^.Next;
      Doomed^.Next := nil;
      Doomed^.Prev := nil;
      Dispose(Doomed);
    end;
    
    Function Josephus(Number,Skip : integer) : integer;
    var
      cur : Jptr;
      lcv : integer;
    begin
      cur := MakeCircle(Number);
      repeat
        for lcv := 1 to Skip do cur := cur^.next;
        cur := kill(cur);
      until cur^.next = cur;
      Josephus := cur^.Number;
      cur := kill(cur);
    end;
    
    begin
      Write('Number of Soldiers: ');
      Readln(n);
      Write('Number to Skip: ');
      Readln(s);
      Writeln('Safe Spot: ',Josephus(n,s));
    end.
    
  • John Evans, btradish@earthlink.net (unregistered)
    #include <stdio.h>
    int f(n,k){return n<=1?0:(f(n-1,k)+k)%n;}
    main() {
      int g; for (g = 0; g < 48; ++g)
        printf("josephus %d skip %d = %d\n", (int)(g/3)+1, (g%3)+2, f((int)(g/3)+1,(g%3)+2));
    }
    

    Thank you, CLR.

  • Jadawin (unregistered)

    What have I learned today?

    If I'm going to have a Judeo circle of mass [suicide|assisted suicide], be the one who announces the skip number AFTER the circle is formed.

  • marco (unregistered) in reply to Josephus

    yes the last

    push into an array all the loosers with a for loop that counts 3 and inside the for put an if for checking the actual array if is in the array dont push it and continue checking the array of the standing soldiers

    for this u need 2 arrays one for loop and put it into a function and done

    my inglish is bad i know

    :)

  • (cs) in reply to Anon
    Anon:
    No, you were right the first time. 5 is the last man standing because you eliminate the person on the kth count, which in this case is 1, so you just kill everybody from the start of the list. You don't skip 1. Look at the animated GIF in the article to confirm this. It counts to three and kills the guy on 3, not the guy after 3.

    k is the skip, count is k+1. You count to three and thus skip over two guys. 1 2 3 4 5 6 7 8 9 etc. If your count is one, your k is 0 in which case J(5,0) yields 5. But our count is 2 and the k is 1 to skip every other guy.

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

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

  • mtu (unregistered)

    God, that took me so much longer than it should have - and I'm not even proud of the code :-(

    Anyways, here goes my python implementation:

    def josephus(n, s):
      soldiers = range(1,n+1)
      position = 0
      counter = 1
    
      while soldiers.count(0) < n - 1:
        position += 1
        if position == n:
          position = 0
        
        if not soldiers[position] == 0:
          counter += 1
          
        if counter == s:
          soldiers[position] = 0
          counter = 0
    
      soldiers.sort(reverse=True)
      print "The safe spot was number %i of %i." % (soldiers[0], n)
  • PeterW (unregistered)
    jos n = rfilter [1..n] !! (2*n-5) 
      where rfilter xs = filter (xs ++ rfilter xs)
            filter (x:y:z:rs) = x:y:filter rs

    Just for the fun of it: A Haskell version featuring infinite recursion.

  • Matthew (unregistered)

    powershell

    function josephus {
    	param([int] $soldiers = 41, [int]$skip = 2)
    	$alive = [System.Collections.ArrayList] (1 .. $soldiers)
    	$dead = $skip
    	while ($alive.count -ne 1) {
    		$alive.removeAt($dead)
    		$dead = ($dead + $skip) % $alive.count
    	}
    	$alive
    }
  • (cs)
    (define (create-circle n)
      (let ((initial-pair (list n)))
        (let iter ((i (- n 1)) (accum initial-pair))
          (if (zero? i)
              (begin (set-cdr! initial-pair accum) accum)
              (iter (- i 1) (cons i accum))))))
    
    (define (josephus n m)
      (let iter ((circle (create-circle n)))
        (if (eq? (car circle)
    	     (cadr circle))
    	(car circle)
    	(let ((skipped-m (list-tail circle m)))
    	  (set-car! skipped-m (cadr skipped-m))
    	  (set-cdr! skipped-m (cddr skipped-m))
    	  (iter skipped-m)))))
    

    Note: m is the "number to skip" as in the spec, so you kill every m+1 th

    Addendum (2009-07-29 17:09): This is intended to model the actual chopping process, not to be efficient.

  • neo (unregistered)

    Just started learning Haskell so ... but this seems to work

    -- josephus try

    joHelper xs = if null (drop 2 xs) then drop 1 xs else joHelper ((drop 3 xs) ++ (take 2 xs))

    josephus i = head (joHelper [1..i])

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article