• Yanman (unregistered) in reply to Josephus
    Josephus:
    Last

    hero!

  • Robert (Jamie) Munro (unregistered) in reply to Alex Mont

    This simplifies to just

    def J(n,k): return n!=1 and (J(n-1,k)+k)%n

  • (cs) in reply to Code Dependent
    Code Dependent:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    Shouldn't God be static?
    I can't decide whether God being static is bad coding or being inconsiderate towards other religions...

    Also +1 internets for Dave. Made me laugh.

  • SR (unregistered) in reply to d3matt
    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

  • Andreas Kromann (unregistered) in reply to Wongo
    Wongo:
    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

  • (cs)

    python one-liner, 1-based index using skips and not counts:

    f=lambda n,k:(f(n-1,k)+k)%n+1 if n-1 else 1
    
  • (cs)

    Hooray for "Scheme"

    (define josephus
    (lambda (soldiers jump)
        (if (eqv? soldiers 1)
            0
          (modulo (+ (josephus (- soldiers 1) jump) jump) soldiers)
        )
        )
      )
    
  • vang (unregistered)

    Like the braindead PHP solution, here's a rather braindead Perl solution.

    #!/usr/bin/perl
    
    use strict;
    use Getopt::Long;
    
    our $debug;
    my $number = 40;
    my $skip   = 3;
    
    GetOptions(
        "number=i" => \$number,
        "skip=i"   => \$skip,
        "debug"    => \$debug
    );
    
    my $index = josephus( $number, $skip );
    print "Safe Spot: $index\n";
    
    sub josephus {
        my $number = shift;
        my $skip   = shift;
    
        my @people = ();
    
        my $pos = -1;
    
        for ( my $i = 0 ; $i < $number ; $i++ ) {
            push @people, 1;
        }
    
        for ( my $i = 0 ; $i < $number - 1 ; $i++ ) {
            $pos = nextval( $pos, $skip, \@people );
            dbg_print("killed $pos\n");
            $people[$pos] = 0;
        }
    
        $pos = nextval( $pos, 1, \@people );
        return $pos;
    }
    
    sub nextval {
        my $pos       = shift;
        my $skip      = shift;
        my $peopleref = shift;
    
        my @people = @$peopleref;
    
        my $i = 0;
        while ( $i != $skip ) {
            $pos++;
            $pos %= scalar @people;
            if ( $people[$pos] == 1 ) {
                dbg_print("skipped $pos\n");
                $i++;
            }
        }
        return $pos;
    }
    
    sub dbg_print {
        my $message = shift;
        if ($debug) {
            print "DEBUG: " . $message;
        }
    }
    
  • Perl Monk (unregistered)

    Perl Golf'd:

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

    77 chars :-)

  • rm5248 (unregistered)

    Java! There are of course more elegant ways to do this, but that would be defeating the purpose.

    public class JosephusCircle {

    /**Perform a game of Josephus' Circle!  This is a game similar to Russain
     * Roulette, in which the people playing have an unnerving desire to kill 
     * themselves.  
     * 
     * @param args Program arguments; the first is the number of soldiers, the 
     * second argument is the number of soldiers to skip
     */
    public static void main(String[] args) {
    	if( args.length != 2 ){
    		System.err.println("Usage: JosephusCircle <soldiers> <soldiers to skip>");
    		System.exit(0);
    	}
    
    	int soldiers = Integer.parseInt(args[0]);
    	int soldiersToSkip = Integer.parseInt(args[1]);
    	
    	boolean[] stillAlive = new boolean[soldiers];
    	for( int x = 0; x < stillAlive.length; x++){
    		//booleans are initialized to be false!
    		stillAlive[x] = true;
    	}
    	
    	int numLeft = soldiers;
    	int soldiersSkipped = 0;
    	while(numLeft > 1){
    		
    		for( int x = 0; x < stillAlive.length; x++){
    			//let's go find the next alive person!
    			if(stillAlive[x] == true){
    				soldiersSkipped++;
    			}
    			
    			if(soldiersSkipped == soldiersToSkip){
    				stillAlive[x] = false;
    				numLeft--;
    				soldiersSkipped = 0;
    			}
    		}
    	}
    	
    	//loop thru to see who is still true!
    	for( int x = 0; x < stillAlive.length; x++){
    		if(stillAlive[x] == true ){
    			//must add one to the index because arrays are 0 based
    			System.out.println("Joesphus is at: " + (x+1) );
    		}
    	}
    }
    

    }

  • Observer (unregistered)
    Thus our formula is (code in Python):
    def J(n,k):
        if(n==1)
            return 0
        else
            return (J(n-1,k)+k)%n
    

    Congratulations to everyone that found the very elegant solution outlined on wikipedia...

    http://en.wikipedia.org/wiki/Josephus_problem

    When the optimal solution for a problem for a solution gets regurgitated in less than 30 minutes, it might be a sign that you need a more unique problem to solve.

    How about next week we try to find a solution to the infamous TOWER OF HANOI problem or how to find the factorial of a number!

  • Lifacciolo (unregistered)

    Code in Python Instead of looking for a mathematical solution (Like Alex Mont did, I loved that solution) I opted for a more simple straightforward simulation of the process of picking.

    (The solution given by this is the index of the array, thus the "real position" will be the return of the resolve function + 1)

    import itertools
    def resolve(soldiers, skip):
        circle_index = range(soldiers)
        circle_choices = itertools.cycle(circle_index)
        while len(circle_index) > 1:
            print "Current circle: %s" % (circle_index,)
            for i in range(skip):
                to_remove = circle_choices.next()
            index = circle_index.index(to_remove)
            print "Will remove: %s" % (to_remove,)
            circle_index = circle_index[index:] + circle_index[:index]
            circle_index.remove(to_remove)
            circle_choices = itertools.cycle(circle_index)
        return circle_index[0]
    
    print resolve(40,3)
    
    
  • (cs) in reply to Andreas Kromann
    Andreas Kromann:
    Wongo:
    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

    using (5,1) we should get 3, but with your shortcut you get

        1 + (5-1)1 mod 5
    ==> 1 + 4 mod 5
    ==> 1 + 4
    ==> 5
    ==> fail
    
  • (cs)

    A missing point of the article: The reason for such a procedure is because in the Jewish religion it is not permitted to commit suicide.

    There is a story in which an entire Jewish town was about to be captured, so it was decided that the head of the family will use a knife to slay each of his family members, then all the remaining men would kill each other, but never themselves. They would take responsibility for committing murder and suffer in the afterlife as a compassion gift to their families for not having to commit suicide nor having to suffer slavery. However there was no such circle, the men would instead kill each other with the last two killing each other simultaneously.

    So yea, otherwise they would all just slit their own throats.

    Ok back to the programming exercise.

  • scp (unregistered)

    This should work, even with bugs ;) (cpp)

    #include <stdio.h>
    #include <stdlib.h>
    
    struct human
    {
      human *prev, *next;
      int number;
    };
    
    int main(int argc, char * argv[])
    {
      int i,j, n = atoi(argv[1]), k = atoi(argv[2]);
      human * h = (human *) malloc(n * sizeof(human));
      for (i=0;i<n;i++)
      {
       h[i].next = &h[(i+1)%n];
       h[i].prev = (i-1<0) ? &h[n-1] : &h[i-1];
       h[i].number = i+1;
      }
    
      human * _h = &h[n-1];
    
      for (i=1;i<n;i++)
      {
        for (j=0;j<k;j++)
        {
          _h = _h->next;
          printf("%d->", _h->number);
        }
        printf("X \n");
        _h->prev->next = _h->next;
        _h->next->prev = _h->prev;
        _h=_h->prev;
      }
      printf("%d survives\n", _h->number);
      return 0;
    }
    
  • Osno (unregistered)

    Naïve C# implementation:

            private static int JosephusCircle(uint participants)
            {
                int next = -1;
                List<bool> standing = InitArray(participants);
    
                while (!AllDead(standing))
                {
                    next = FindNextToDie(next, standing);
                    KillNext(next, standing);
                }
                Console.WriteLine();
                return next + 1;//list is 0 based, result is 1 based
            }
    
            private static void KillNext(int next, List<bool> standing)
            {
                Console.Write("{0} ", next + 1);
                standing[next] = true;
            }
    
            private static int FindNextToDie(int next, List<bool> standing)
            {
                int count = 0;
                while (count < 3)
                {
                    next++;
                    if (next == standing.Count) next = 0;
                    if (!standing[next]) count++;
                }
                return next;
            }
    
            private static bool AllDead(List<bool> standing)
            {
                return standing.TrueForAll(p => p);
            }
    
            private static List<bool> InitArray(uint participants)
            {
                List<bool> standing = new List<bool>(Convert.ToInt32(participants));
                for (int i = 0; i < participants; i++) standing.Add(false);
                return standing;
            }
    
  • (cs) in reply to astonerbum
    astonerbum:
    A missing point of the article: The reason for such a procedure is because in the Jewish religion it is not permitted to commit suicide.

    There is a story in which an entire Jewish town was about to be captured, so it was decided that the head of the family will use a knife to slay each of his family members, then all the remaining men would kill each other, but never themselves. They would take responsibility for committing murder and suffer in the afterlife as a compassion gift to their families for not having to commit suicide nor having to suffer slavery. However there was no such circle, the men would instead kill each other with the last two killing each other simultaneously.

    So yea, otherwise they would all just slit their own throats.

    Ok back to the programming exercise.

    You're referring to the siege of masada.

  • Osno (unregistered)

    BTW, I love Josephus' books... and I think he actually only wrote those two (and Against the Greeks), and The Antiquities are almost identical to the Wars, IIRC.

  • Chad (unregistered)

    Javascript solution:

    // brute force method function josephus1(count, seed) { var men = new Array(count); var dead = 0; var index = 0; var passes = 0;

    // 1. Loop through an array of men who's values are initially set to false to indicate they are not dead. for (var i = 0; i < count; i++) { men[i] = false; }

    // 2. Keep counting men if they are not already dead and killing them if they are the nth man until the number of dead is one less than the total dead. while (dead < count - 1) { if (men[index] == false) { passes = passes >= seed ? 1 : passes + 1;

      if (passes % seed == 0)
      {
        men[index] = true;
        dead++;
      }
    }
    index = index >= count - 1 ? 0 : index + 1;
    

    }

    // 3. Return the last man standing by looping through the array of men and finding the one who is not dead for (var i = 0; i < count; i++) { // if the man has not been killed return his index plus one to indicate his position (to account for zero based arrays) if (!men[i]) return i + 1; } }

    // an improved version which removes the array elements completely so we don't continually count dead men function josephus2(count, seed) { var men = new Array(count); var index = 0; var passes = 0;

    // initialize the men to their position in the circle for (var i = 0; i < count; i++) { men[i] = i + 1; }

    // keep killing the nth man by removing him from the array until there is only 1 man left while (men.length > 1) { passes = passes >= seed ? 1 : passes + 1; if (passes % seed == 0) { men.splice(index, 1); if (index >= men.length) index = 0; } else { index = index >= men.length - 1 ? 0 : index + 1; } }

    // return the last man standing's position return men[0]; }

  • Ian (unregistered) in reply to Code Dependent
    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?
  • Karol Urbanski (unregistered) 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 own attempt at golfing this (subroutine):

    sub k{$_[0]&&(k($_[0]-1,$_[1])+pop)%pop}
    40 chars. I use $_+indexes and two pops at the end because that ends up being 2 chars less than initialising $a and $b from @_ (which would have to be "my($a,$b)=@_;" <- 13 chars.) "[0][0][1]pp" (the additional chars needed to avoid initialising the vars) is just 11 chars.

    The mandatory one-liner (true one-liner, no semicolons)

    $ perl -E'sub k{$_[0]&&(k($_[0]-1,$_[1])+pop)%pop}say k@ARGV' 12 3
    9
    59 chars + args.

    Indexed from 0. I'm certain it's possible to golf this further, though, I don't like this solution...and I'm loving those little challenges :).

  • Anon (unregistered)

    The obvious solution is tell everybody else that you just need to take a quick bathroom break and they should start without you.

  • Andreas Kromann (unregistered) in reply to halber_mensch
    halber_mensch:
    Andreas Kromann:
    Wongo:
    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

    using (5,1) we should get 3, but with your shortcut you get

        1 + (5-1)1 mod 5
    ==> 1 + 4 mod 5
    ==> 1 + 4
    ==> 5
    ==> fail
    

    No it is 5 not 3 ... you fail ...

    {1,2,3,4,5} => {2,3,4,5} => ... => {5}

  • (cs)

    Here's a straight forward solution in PHP. Not really a function but can be easily converted into one.

    No recursivity, with 1000 soldiers or something like that PHP would probably crap out.

    
    <?
    $nr = 12;
    $step = 3;
    
    $soldiers = array();
    for ($i=1;$i<=$nr;$i++) {
      $soldier = array();
      $soldier['next'] = $i+1;
      $soldier['prev'] = $i-1;
      $soldiers[$i] = $soldier;
    }
    $soldiers[0]['next'] = 1;   // start from here but it's not in the chained list
    $soldiers[$nr]['next'] = 1; // last element is linked to the first to form the circle
    $soldiers[1]['prev'] = $nr; // and first element is linked to the last
    
    $count = $nr;
    $soldiertodie = 0;
    while ($count!=1) {
      for ($i=1;$i<=$step;$i++) {
        $soldiertodie = $soldiers[$soldiertodie]['next'];
      }
      echo 'Soldier '.$soldiertodie.' is killed.<br/>';
      $soldiers[$soldiers[$soldiertodie]['prev']]['next'] = $soldiers[$soldiertodie]['next'];
      $soldiers[$soldiers[$soldiertodie]['next']]['prev'] = $soldiers[$soldiertodie]['prev'];
      $lastsoldier = $soldiers[$soldiertodie]['prev'];
      $count--;
    }
    echo 'The last soldier standing is '.$lastsoldier.'
    '; ?>
  • Anon (unregistered) in reply to Wongo
    Wongo:
    Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

    Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

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

    The shortcut, according to Josephus himself, was luck (or the hand of God). Besides, if he hadn't been the last man (or rather one of the last two) men standing, he wouldn't have been able to write about it later.

  • Yazeran (unregistered) in reply to null
    null:
    You stand as a first one to die and then invert the alive-dead state and you're the only one alive.

    But you do realize that in order to do that you need 'The infinite improbability drive' which incidentally requires a good hot cup of tea.

    But to get a good hot cup of tea is in my experience impossible, had it been coffee, then it could be done... -)

    Yours Yazeran

    Plan: To go to Mars one dya with a hammer

  • Anon (unregistered) in reply to Andreas Kromann
    Andreas Kromann:
    halber_mensch:
    Andreas Kromann:
    Wongo:
    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

    using (5,1) we should get 3, but with your shortcut you get

        1 + (5-1)1 mod 5
    ==> 1 + 4 mod 5
    ==> 1 + 4
    ==> 5
    ==> fail
    

    No it is 5 not 3 ... you fail ...

    {1,2,3,4,5} => {2,3,4,5} => ... => {5}

    I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0. What you have shown is skip 0, in which case you just kill 1 then 2 then 3, etc. If you skip one, you kill 2, then (skip 3) 4, then 1 (skip 5), then 5 (skip 3) leaving 3 alive. {1,2,3,4,5} => {1,3,4,5} => {1,3,5} => {3,5} => {3}

  • (cs)

    Since the recursive solution has been done quite a bit...I thought something more interesting was in order:

    survivalByAlcohol(int soldiersLeft, int deathNumber, Soldier you){
    	Soldier soldierInDanger = getNextLivingSoldier();
    	while (soldiersLeft > 1) {
    		if (soldierInDanger.equals(you)) {
    			offerEveryoneAlcoholicDrink();
    			if (yourNumber != deathNumber) {
    				System.Mouth.say(yourNumber);
    			}else{
    				try {
    					System.Mouth.say(deathNumber - 1);
    				} catch (SomeoneArguesException e) {
    					startAFight();
    				}
    			}
    		}else if (number == deathNumber) {
    			soldiersLeft--;
    			soldierInDanger.setAlive(false);
    			number = 0;
    		}
    		number++;
    		soldierInDanger = getNextLivingSoldier();
    	}
    }
    
  • Andreas Kromann (unregistered) in reply to Anon
    Anon:
    I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0. What you have shown is skip 0, in which case you just kill 1 then 2 then 3, etc. If you skip one, you kill 2, then (skip 3) 4, then 1 (skip 5), then 5 (skip 3) leaving 3 alive. {1,2,3,4,5} => {1,3,4,5} => {1,3,5} => {3,5} => {3}

    Yes indeed. k = 1 means "first one I point at gets the fraking axe" :) So... 1 + (n-1)k mod n

  • (cs)

    Javascript -- Trial 1

    // a size number of indexes exist, we start killing indexes by taking the
    // live index at the offset killed and skipping skip indexes before killing
    // the next one pointed to.
    // the Safe Number is the index that will not be killed.
    // thus is the Josephus' Circle.
    function JosephusCircle(size, skip) {
            // some base conditions
            // one size = safe
            if (size === 1) {
                    return 1;
            }
            // less than zero size cannot exist
            if (size <= 0) {
                    return -1;
            }
    
            // The value of each element in the array is the safe index.
            var arr = [];
            for (var i = 0; i < size; i++){
                    arr[i] = i;
            }
            // Start looking for safe indexes starting at 0.
            var indx = 0;
            while (arr.length > 1) {
                    // skip over skip indexes (-1) and wrap
                    // around the array length for the next index to remove
                    indx = ((indx + skip) - 1 ) % arr.length;
                    // kill the given index from the array, the index now
                    // points to the next element to start counting at
                    arr.splice(indx, 1);
            }
            // The safe number.
            return arr[0];
    }
    

    Yay! <-- apparently this allows me to submit :)

    Edit: The index returned is zero-based. Add 1 to it if you want a 1-based index.

  • (cs) in reply to Ian
    Ian:
    If God were static how could He move in mysterious ways?
    Well, I know that when my socks and shirts come out of the dryer they're full of static, and it makes them move in mysterious ways...
  • (cs) in reply to Anon
    Anon:
    I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0.
    Well, when the algorithm was posted, it was assume k meant "kill every kth person, not skip k persons between skips."

    So, if you want the second letter to be the number of skips, modify the algorithm to: 1 + (n-1)(k-1) mod n

  • Wongo (unregistered) in reply to Osno
    Osno:
    BTW, I love Josephus' books... and I think he actually only wrote those two (and Against the Greeks), and The Antiquities are almost identical to the Wars, IIRC.

    He actually wrote "Teach yourself recursion in VB.Net in 10 days", did you know?

    Anon:
    The shortcut, according to Josephus himself, was luck (or the hand of God). Besides, if he hadn't been the last man (or rather one of the last two) men standing, he wouldn't have been able to write about it later.

    So the "somehow managed to figure out" is a red herring???

    Andreas Kromann:
    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

    Er... nope, it doesn't work:

    33 soldiers: (1 + (33-1) * 3) mod 33 = 31 instead of 7.

  • Phil (unregistered) in reply to Wongo
    Wongo:
    Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

    From where did you get that 860 iterations?

  • IV (unregistered)

    I am taking the Schroedinger approach - instead of using an axe, have everyone climb into a box with a bottle of poison. At that point, everyone is both alive and dead. Thus, the suicide is successful (each person is dead), but our hero has survived (he is alive).

  • (cs)

    A brute force, linked-list-traversal method for the HP 48:

    (Replace != with the built-in not-equals symbol.)

    << 0 { } 0 -> N S P L I
      << 1 N
        FOR C C
        NEXT N ROLL N
    ->LIST 'L' STO N 'I'
    STO
        WHILE 'L' I GET
    I !=
        REPEAT 1 S
          START I 'P'
    STO 'L' I GET 'I'
    STO
          NEXT 'L' P
    'L' I GET PUT
        END I
      >>
    >>
    
  • Wongo (unregistered) in reply to Phil
    Phil:
    Wongo:
    Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

    From where did you get that 860 iterations?

    static int counter;

    int Josephus(int n, int k) counter++; ...

  • Overcaffeinated (unregistered)

    In Python:

    def noKill(people, skip=3): people = range(1,people + 1) skipped = 0 current = -1 while len(people) > 1: skipped += 1 current += 1 if current == len(people): current = 0 pass

    if skipped == skip: print 'killing %s' % (people.pop(current)) skipped = 0 current -= 1 return people.pop()

  • sbrant (unregistered)

    def josephus(soliders, skip): soliders = range(1, soliders + 1) iterations = range(1, len(soliders) * skip) counter = 1 killed = 0 for i in iterations: for n in soliders: if n != 0: if counter == skip: if killed == len(soliders) - 1: return n soliders[soliders.index(n)] = 0 killed += 1 counter = 1 else: counter += 1

    print josephus(41, 3)

  • Blarg (unregistered)

    Say we skip skip soldiers, and have num soldiers in the circle. If skip and num are coprime, then the consecutive sums will be unique, and will eventually get back to num. Thus, -1*skip mod num is the safe spot.

    If they are not coprime, then there are lots of safe spots. Find their gcd, and add 1.

  • silvestrov (unregistered)

    #!/usr/bin/perl

    $k = 3; @a=(1..40); @a = grep { ++$x % $k } @a while $#a print @a, "\n";

  • Overcaffeinated (unregistered)

    Tabbing fail. Again, in Python:

    def noKill(people, skip=3):
     people = range(1,people + 1)
     skipped = 0
     current = -1
     while len(people) > 1:
      skipped += 1
      current += 1
      if current == len(people):
       current = 0
       pass
      
      if skipped == skip:
       print 'killing %s' % (people.pop(current))
       skipped = 0
       current -= 1
     return people.pop()
    
  • time0ut (unregistered) in reply to Josephus

    A terrible, but working solution (more or less) in Java. The test to see if a location is safe is accomplished by running the process until that location is killed. Positions are randomly selected for testing until the safe one is found. Positions can be tested more than once. Emphasis has been placed on writing naive and poorly performing code without going overboard on obscurity.

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    
    /**
     * A solution that might get Josephus killed.
     * @author time0ut
     */
    public class SafetyDance {
      public static void main(String... args) {
        new SafetyDance(Integer.parseInt(args[0]), Integer.parseInt(args[1])).play();
      }
      private int participants;
      private int skip;
    
      public SafetyDance(int participants, int skip) {
        this.participants = participants;
        this.skip = skip;
      }
    
      public void play() {
        DanceMarathon danceMarathon = new DanceMarathon(participants, skip);
        Random rand = new Random();
        while (true) {
          int position = rand.nextInt(participants);
          if (danceMarathon.isSafe(position)) {
            System.out.println("Position " + position + " is safe.");
            break;
          } else {
            System.out.println("Position " + position + " is not safe.");
          }
          danceMarathon.reset();
        }
      }
    
      class DanceMarathon {
        List<Dancer> dancers;
        private int  skip;
    
        public DanceMarathon(int participants, int skip) {
          this.dancers = new ArrayList<Dancer>();
          for (int i = 0; i < participants; i++) {
            this.dancers.add(new Dancer(i));
          }
          this.skip = skip;
        }
    
        public boolean isSafe(int position) {
          int currentPosition = 0;
          while (!this.isOneStanding()) {
            Dancer d = this.getNext(currentPosition);
            if (d.getPosition() == position) {
              return false;
            }
            d.setAlive(false);
            currentPosition = d.getPosition();
          }
          return true;
        }
    
        public void reset() {
          for (Dancer d : this.dancers) {
            d.setAlive(true);
          }
        }
    
        private boolean isOneStanding() {
          int standing = 0;
          for (Dancer d : this.dancers) {
            if (d.isAlive()) {
              standing++;
            }
          }
          return standing == 1;
        }
    
        private Dancer getNext(int currentPosition) {
          int count = 0;
          Dancer d = null;
          while (count < this.skip) {
            if (currentPosition == this.dancers.size() - 1) {
              currentPosition = 0;
            } else {
              currentPosition++;
            }
            d = this.dancers.get(currentPosition);
            if (d.isAlive()) {
              count++;
            }
          }
          return d;
        }
        class Dancer {
          private int     position;
          private boolean alive;
    
          public Dancer(int position) {
            this.position = position;
            this.alive = true;
          }
    
          public int getPosition() {
            return this.position;
          }
    
          public boolean isAlive() {
            return this.alive;
          }
    
          public void setAlive(boolean alive) {
            this.alive = alive;
          }
        }
      }
    }
  • Anders Eurenius (unregistered) in reply to Andreas Kromann

    Have you tested it?

    Because I think I'm not getting the right answers from it. My own version before looking at the comments was:

    def joe3(n, k): x = 0 for i in range(2, n+1): x = (x + k) % i return x

    Which does seem to work. (0-indexed) I tried to eliminate more, but the lower modulos are apparently necessary.

  • CF Guru (unregistered) in reply to Ben Forta

    I am humbled that the great Ben Forta visits this site. In fact, I always feel like bowing when I see or hear his name! You the man Ben!!!

    Ben Forta:
    A not as ugly as the PHP script in CF <cfparam name="url.soldiers" type="numeric" default="12"> <cfparam name="url.skip" type="numeric" default="3"> <cfset circle=""> <cfloop from=1 to=#url.soldiers# index=x> <cfset circle=listAppend(circle,x)> </cfloop> <cfset x=1> <cfloop condition="listLen(circle) gt 1"> <cfset x+=url.skip-1> <cfif x gt listLen(circle)> <cfset x=x mod listLen(circle)> </cfif> <cfoutput>Deleting man at position #listGetAt(circle,x)#
    </cfoutput> <cfset circle=listDeleteAt(circle, x)> </cfloop> <cfoutput>The last name standing was in position #circle#
    </cfoutput>
  • Wongo (unregistered) in reply to Capt. Obvious
    Capt. Obvious:
    Anon:
    I think the disagreement is on the meaning of the 1 in 5,1. Does it mean you skip 1, or skip 0.
    Well, when the algorithm was posted, it was assume k meant "kill every kth person, not skip k persons between skips."

    So, if you want the second letter to be the number of skips, modify the algorithm to: 1 + (n-1)(k-1) mod n

    33 soldiers, interval 2 (equivalent to killEveryKth 3) = 1+(33-1)(2-1) mod 33 = 0 instead of 7.

  • Dave Bush (unregistered)

    Numbering the top position as zero, in 'C': int Safe(int Soldiers, int Skip) { if (Soldiers == 1) return 0 ;

    return (Safe(Soldiers - 1, Skip) + Skip) % Soldiers ; }

  • Akoi Meexx (unregistered)

    In php:

    <?php function LifePosition($indexCount=41, $skipCount=3) { /** * Josephus' Circle calculation function * Written to identify the array index that will be selected * last in a sequence with (x) indices and (y) skip count * @author: Akoi Meexx <[email protected]> * * @attrib: http://thedailywtf.com/Articles/Programming-Praxis-Josephus-Circle.aspx */ $roulette = array_fill(1, $indexCount, 'Alive'); $increment = 1; while(count($roulette) > 1) { foreach($roulette as $arrayIndex=>$value) { if($increment == $skipCount) { unset($roulette[$value]); $increment = 1; } $increment++; } } print_r($roulette); } ?>
  • (cs) in reply to Andreas Kromann
    Andreas Kromann:
    halber_mensch:
    Andreas Kromann:
    Wongo:
    The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

    As I posted earlier its just (n is number of soldiers and k the number of skips):

    1 + (n-1)k mod n

    using (5,1) we should get 3, but with your shortcut you get

        1 + (5-1)1 mod 5
    ==> 1 + 4 mod 5
    ==> 1 + 4
    ==> 5
    ==> fail
    

    No it is 5 not 3 ... you fail ...

    {1,2,3,4,5} => {2,3,4,5} => ... => {5}

    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}

  • Wongo (unregistered) in reply to Blarg
    Blarg:
    Say we skip skip soldiers, and have num soldiers in the circle. If skip and num are coprime, then the consecutive sums will be unique, and will eventually get back to num. Thus, -1*skip mod num is the safe spot.

    If they are not coprime, then there are lots of safe spots. Find their gcd, and add 1.

    skip = 3, soldiers = 11 (coprimes). -1*3 mod 11 = -3 on the windows calculator, although I remember the modding of negative numbers being still under debate (please do not bait...). No -3 spot.

    Not coprime, skip = 3, soldiers = 18, gcd = 3, gcd + 1 = 4 instead of 14. Doesn't work either.

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article