The Daily WTF: Curious Perversions in Information Technology

2009-07-29 Reply Admin

Josephus:
Last

hero!

2009-07-29 Reply Admin

This simplifies to just

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

DOA · 2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

halber_mensch · 2009-07-29 Reply Admin

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

Quicksilver · 2009-07-29 Reply Admin

Hooray for "Scheme"

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

Perl Golf'd:

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

77 chars :-)

2009-07-29 Reply Admin

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

}

2009-07-29 Reply Admin

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!

2009-07-29 Reply Admin

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)

halber_mensch · 2009-07-29 Reply Admin

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

astonerbum · 2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

halber_mensch · 2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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?

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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}

mariushm · 2009-07-29 Reply Admin

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

?>

2009-07-29 Reply Admin

Wongo:
Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".
Unless Ole Joe had a phenomenal stack-based brain, he simply couldn't recurse through the 860 iterations required for a 41 soldiers circle (starting at 2).

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

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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}

Knux2 · 2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

astonerbum · 2009-07-29 Reply Admin

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.

Code Dependent · 2009-07-29 Reply Admin

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

Capt. Obvious · 2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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?

2009-07-29 Reply Admin

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

db2 · 2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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)

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

#!/usr/bin/perl

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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>

2009-07-29 Reply Admin

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.

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

halber_mensch · 2009-07-29 Reply Admin

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}

2009-07-29 Reply Admin

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.

Josephus' Circle

Leave a comment on “Josephus' Circle”