The Daily WTF: Curious Perversions in Information Technology

2009-07-29 Reply Admin

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

0 1 0 (kill)

people safespot 2 1

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

people = 2 safespot = 1 n = 3

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

so: people safespot 2 1 3 1

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

so: people safespot 2 1 3 1 4 0

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

people safespot 2 1 3 1 4 0 5 3

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

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

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

DeLos · 2009-07-29 Reply Admin

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

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

2009-07-29 Reply Admin

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

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

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

ikegami · 2009-07-29 Reply Admin

Alex Mont:

def J(n,k):
    if(n==1)
        return 0
    else
        return (J(n-1,k)+k)%n

That's easy to make iterative.

# Recursive
sub J {
    my ($n, $k) = @_;
    return 0 if $n == 1;
    return ( J($n-1, $k) + $k ) % $n;
}

# Iterative
sub J {
    my ($n, $k) = @_;
    my $j = 0;
    $j = ($j + $k) % $_ for 2..$n;
    return $j;
}

2009-07-29 Reply Admin

I love a good perl golf challenge!

perl -E '$k=pop;$s=($s+$k)%$_ for 1..pop;say$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

2009-07-29 Reply Admin

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

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

Code which gives...

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

2009-07-29 Reply Admin

Sue D. Nymme:
I love a good perl golf challenge!
perl -E '$k=pop;$s=($s+$k)%$_ for 1..pop;say$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

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

2009-07-29 Reply Admin

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

ikegami · 2009-07-29 Reply Admin

Alex Papadimoulis:
There is no “right” answer and no perfect solution, but some will certainly be better than others. The best of these will get a TDWTF sticker.

Alex Papadimoulis:
The comments are most certainly worth a read, if nothing else but to see things like the circuit diagram solution [...]

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

[email protected]

Coyne · 2009-07-29 Reply Admin

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

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

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

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

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

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

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

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

workmad3 · 2009-07-29 Reply Admin

Here's my python one-liner again :)

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

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

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

Maurits · 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".

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

2009-07-29 Reply Admin

Sue D. Nymme:
Sue D. Nymme:
I love a good perl golf challenge!
perl -E '$k=pop;$s=($s+$k)%$_ for 1..pop;say$s+1' 12 3 10

39 characters between the quotes; 54 on the whole command line.

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

Awesome :).

2009-07-29 Reply Admin

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

-module(josephus).
-export([josephus/2]).

josephus(Soldiers, Interval)->
	josephus(soldier_list(Soldiers),[], Interval, 0).

josephus([Current | Rest], Survivors, Interval, Count) when Count /= Interval->
	josephus(Rest, [Current | Survivors], Interval, Count + 1);

josephus([_ | Rest], Survivors, Interval, _)->
	josephus(Rest, Survivors, Interval, 0);

josephus([], Survivors, Interval, Count)->
	if
		length(Survivors) > 1 ->
			josephus(Survivors, [], Interval, Count);
		true ->
			[LastMan | _] = Survivors,
			LastMan
			
	end.
	


soldier_list(Soldiers)->
	soldier_list(Soldiers, []).

soldier_list(Soldiers, List) when Soldiers > 0 ->
	soldier_list(Soldiers - 1, [Soldiers | List]);

soldier_list(0, List)->
	[0 | List].

2009-07-29 Reply Admin

Matlab, using inbuilt circular shift function:

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

2009-07-29 Reply Admin

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

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

can that be further simplified ?

2009-07-29 Reply Admin

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

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

VinDuv · 2009-07-29 Reply Admin

AppleScript :

on run
	set num_soldiers to 0

	repeat until num_soldiers is greater than 0
		display dialog "Number of soldiers" default answer 12
		set text_entered to text returned of the result
		try
			set num_soldiers to text_entered as integer
		end try
	end repeat
	
	set num_to_skip to 0
	
	repeat until num_to_skip is greater than 0
		display dialog "Soldiers to skip" default answer 3
		set text_entered to text returned of the result
		try
			set num_to_skip to text_entered as integer
		end try
	end repeat
	
	display dialog "Result: " & Josephus(num_soldiers, num_to_skip) & " (from 0 to " & (num_soldiers - 1) & ")" buttons {"WTF?!"} default button 1
end run

on Josephus(num, skip)
	if num is 1 then return 0
	return (Josephus(num - 1, skip) + skip) mod num
end Josephus

2009-07-29 Reply Admin

Ron Moses:

How's about a T-SQL function? I could probably tighten this up considerably but it works.

CREATE FUNCTION dbo.JosephusFunction
(
	@NumberOfSoldiers int,
	@SoldiersToSkip int
)
RETURNS int
AS
BEGIN
DECLARE @i int, @TempSkip int;
DECLARE @Soldiers table (SoldierNumber int, Dead bit);

SET @i = 1;
WHILE @i <= @NumberOfSoldiers
BEGIN
	INSERT INTO @Soldiers VALUES (@i, 0);
	SET @i = @i + 1;
END

SET @i = 1;
WHILE (SELECT COUNT(*) FROM @Soldiers WHERE Dead = 0) > 1
BEGIN
	SET @TempSkip = @SoldiersToSkip + 1;
	WHILE @TempSkip > 0
	BEGIN
		SET @i = @i % @NumberOfSoldiers + 1;

		WHILE (SELECT Dead FROM @Soldiers WHERE SoldierNumber = @i) = 1
		BEGIN
			SET @i = @i % @NumberOfSoldiers + 1;
		END
	
		SET @TempSkip = @TempSkip - 1;
	END

	UPDATE @Soldiers
	SET Dead = 1
	WHERE SoldierNumber = @i;

END

RETURN (SELECT SoldierNumber - 1 FROM @Soldiers WHERE Dead = 0);

END

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

2009-07-29 Reply Admin

Same brute force, just using BitSet instead:

import java.util.BitSet;

public final class JosephusCircle
{
  public static void main(String[] args)
  {
    JosephusCircle c = new JosephusCircle();
    c.bruteForce(12, 3);
  }

  private int bruteForce(int size, int numSkip)
  {
    BitSet s = new BitSet(size);

    int axeCounter = 1;
    while (s.cardinality() < size - 1)
    {
      for (int i = s.nextClearBit(0); i < size; i = s.nextClearBit(i + 1))
      {
        if (0 == axeCounter % numSkip)
        {
          s.set(i);
        }
        ++axeCounter;
      }
    }
    int live = s.nextClearBit(0) + 1;
    System.out.println("When axing every " + numSkip + ", you want " + live + " of " + size);
    return live;
  }
}

2009-07-29 Reply Admin

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

#/usr/bin/perl
use strict;
use warnings;

if ((@ARGV != 2) || ($ARGV[0]!~m/[1-9]/) || ($ARGV[1]!~m/[1-9]/)) {
	print "Missing or wrong arguments! Need two integers\n";
	exit(0);
}

my ($soldiers,$count_val)=@ARGV;
my @survivors;
my $initiate=1;
my $died_this_round=0;

for (my $i=0;(@survivors>1 || $initiate==1);(($i<$soldiers && $initiate==1)?($i++):($i+=$count_val))) {
	if ($i<$soldiers && $initiate==1) {
		$survivors[$i]=$i+1;
	}
	elsif ($i==$soldiers && $initiate==1) {
		$initiate=0;
		$i=0;
	}
	else {
		if ($i>(@survivors+$died_this_round)) {
			$i-=(@survivors+$died_this_round);
			$died_this_round=0;
		}
		
		my $delete;
		if ($i-$died_this_round-1>$#survivors) {
			$delete=$i-$died_this_round-@survivors-1;
		}
		else{
			$delete=$i-$died_this_round-1;
		}
		
		splice(@survivors,$delete,1);
		$died_this_round++;
	}
}
print "Lucky one: $survivors[0]\n";

# perl Josephus.pl 12 3
Lucky one: 10

2009-07-29 Reply Admin

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

    public DeathLinkage(int numSoldiers, int numSkip)
    {
         _Soldiers = numSoldiers;
         _Skip = numSkip;
         jews = new Person[_Soldiers];
         for (int i = 0; i < _Soldiers; i++)
         {
             jews[i] = new Person();
         }
    }
    int counter = 1;
    public int killEachOther()
    {

        
        while (dead < (_Soldiers -1))
        {
            for (int i = 0; i < _Soldiers; i++)
            {
                if (jews[i].alive)
                {
                    if (counter == _Skip)
                    {
                        jews[i].alive = false;
                        counter = 1;
                        dead++;
                    }
                    else counter++;
                }
            }
            killEachOther();

        }
        for (int i = 0; i < _Soldiers; i++)
        {
            if (jews[i].alive) index = i;
        }
        return index;
    }
    public string circleOfDeath()
    {
        
        if (_Soldiers <= 0 || _Skip <= 0)
        {
            return "Neither of the inputs may be 0 or a negative number.  Jews don't believe in counter-clockwise.";

        }
        else
        {
            if (_Soldiers == 1) return "1";
            else
            {
                DeathLinkage dl = new DeathLinkage(_Soldiers, _Skip);
                return dl.killEachOther().ToString();
            }
        }
    }


}
public class Person
{
   
    public Person()
    {
        alive = true;
    }
    public bool alive { get; set; }
}
class Program
{
    
    static void Main(string[] args)
    {
        DeathLinkage dl = new DeathLinkage(12, 3);
        System.Console.WriteLine(dl.circleOfDeath());
    }

}

Stalker · 2009-07-29 Reply Admin

A perhaps not very clean but working solution in F#

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

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

2009-07-29 Reply Admin

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

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

        Boolean[] soldiers = new Boolean[numOfSoldiers];
        int ctr = 0;
        int removedCtr = 0;

        //Set all soldiers to a living state
        for (int i = 0; i < numOfSoldiers; i++)
            soldiers[i] = true;

                    
        while (removedCtr != numOfSoldiers - 1)
        {
            
            for (int i = 0; i < skip; i++)
            {
                //If a soldier is dead skip him
                while(soldiers[ctr] == false)
                {
                    ctr += 1;
                    if (ctr > numOfSoldiers - 1) ctr = 0;
                }

                if (i == (skip - 1)  )
                {
                    soldiers[ctr] = false;
                    removedCtr += 1;
                    Console.WriteLine("Soldier at {0} was removed.", ctr);
                }

                ctr += 1;
                if (ctr > numOfSoldiers - 1) ctr = 0;

            }
        }

        ctr = 0;
        while (soldiers[ctr] == false)
        {
            ctr += 1;
        }           

        return ctr;
    }
}

mduffey · 2009-07-29 Reply Admin

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

unit Josephus;

interface uses Generics.Collections, SysUtils;

type BoolP = ^Boolean;

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

implementation

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

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

end.

2009-07-29 Reply Admin

Ian:
Code Dependent:
Dave:

foreach(soldier:soldiers){

soldier.kill();

}

God.getInstance().sortOut(soldiers);

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

To me, listening to static is indeed mysterious!

2009-07-29 Reply Admin

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

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

2009-07-29 Reply Admin

A brute force Python version...

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

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

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

2009-07-29 Reply Admin

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

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

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

2009-07-29 Reply Admin

Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:

GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

2009-07-29 Reply Admin

Too much recursion in here for my taste.

Okay... first some ruby code (boring)

def jc(men, skip)
c=Array.new()
men.times do |n| c << n end
i=0
d=skip
while c.length > 1
i = 0 if i==c.length
d = d - 1
puts "killed nr. #{c[i]}" if d==0
c.delete c[i] if d==0
i=i+1 if d!=0
d=skip if d==0

end
c[0]
end
puts jc(12,3)

And here C with double linked list awesomeness:

#include <stdio.h>
#include <stdlib.h>
typedef struct circle_t 
{
  unsigned int nr;
  struct circle_t* next;
  struct circle_t* prev;
} circle;


void add(unsigned int nr, struct circle_t* prev)
{
  struct circle_t* a;
  a=(struct circle_t*)malloc(sizeof(struct circle_t));
  a->nr=nr;
  a->prev=prev;
  prev->next=a;
}

void del(struct circle_t* ptr) 
{
  ptr->prev->next=ptr->next;
  ptr->next->prev=ptr->prev;
  free(ptr);
}

unsigned int jc(unsigned int men, unsigned int skip) 
{
  struct circle_t* p;
  struct circle_t* start;
  start=malloc(sizeof(struct circle_t));
  p=start;

  start->next=start;
  start->prev=start;
  start->nr=0;

  int i=1;
  int d=skip;

  while (i<men) 
  {
    add(i,p);
    p=p->next;
    i++;
  }

  p->next=start;
  start->prev=p;

  p=start;
  while (p != p->prev) 
  {
    d--;
    if (d==0) {
      printf("killed nr. %-4u\n",p->nr,p);
      p=p->next;
      del(p->prev);
      d=skip;
    }
    else 
    {
      p=p->next;
    }
  }


  printf("\n\n");

  return p->nr;
}

int main(int argc, char** argv) 
{
  if (argc < 3) {
    printf("usage: %s men skip\n",argv[0]);
    return 1;
  }
  printf("safe spot: %u\n",jc(atoi(argv[1]),atoi(argv[2])));

  return 0;
}

2009-07-29 Reply Admin

Wongo:
db2:
It looks like this works:
n = number of soldiers k = skip ahead interval (3 in this example) i = "safe spot" index (1-based)
i = 1;
for (int c = 2; c <= n; c++) {
  i = (i + k) % c;
  if (i == 0) {
    i = c;
  }
}
return i;
Brilliant! It works perfectly! Congrats, db2, you made my day!

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

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

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

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

2009-07-29 Reply Admin

RayMarron:
I just wanted to say that the animations accompanying these are brilliant. :)

I have to say that I agree. Now for the next problem, code up the animations.

2009-07-29 Reply Admin

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

survivor_mat=[];

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

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

PatrickBeebe · 2009-07-29 Reply Admin

C#, using regex and strings - for fun.

        private static int GetJosephusSafeSpot(int nSoliderCount, int nSkipValue)
        {
            var sbRegexSkips = new StringBuilder("L");
            nSkipValue--;
            for (int i = 0; i < nSkipValue; i++)
                sbRegexSkips.Append("D*L");

            Regex regKill = new Regex(sbRegexSkips.ToString(), RegexOptions.Compiled);

            string strCircleOfDeath = new string('L', nSoliderCount);

            int nIndex = 0;
            while (strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).Count(c => c == 'L') > 1)
            {
                Match match = regKill.Match(strCircleOfDeath, nIndex);
                strCircleOfDeath = regKill.Replace(strCircleOfDeath, m => { return m.Value.Remove(m.Value.Length - 1) + "D"; }, 1, nIndex);
                nIndex = match.Index+match.Value.Length;
                while (strCircleOfDeath.Substring(nIndex).Count(c => c == 'L') <= nSkipValue)
                    strCircleOfDeath += strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount);
            }

            return strCircleOfDeath.Substring(strCircleOfDeath.Length - nSoliderCount).LastIndexOf('L');
        }

2009-07-29 Reply Admin

Solution in F#:

let josephus numberOfMen skip =
  let men = [1..numberOfMen]
  let rec doTurn men position =
    match men with
    | hd :: [] -> hd
    | _ ->
      let newPosition = (position + skip) % men.Length
      doTurn (List.mapi (fun i man -> if i = newPosition then 0 else man) men 
      |> List.filter(fun man -> man > 0)) (newPosition - 1)
  doTurn men -1

2009-07-29 Reply Admin

Maurits:
Wongo:
Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".

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

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

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

2009-07-29 Reply Admin

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

int josephus(Vector<Integer> v) {
  if (v.size() == 1)
    return v.elementAt(0).intValue();

  v.add(v.remove(0));
  v.add(v.remove(0));
  v.remove(0);
  return josephus(v);
}

Code Dependent · 2009-07-29 Reply Admin

Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:
GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

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

2009-07-29 Reply Admin

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

sub josephus {
  my ($circle, $skip) = @_;
  return 1 + calc_j(0, $skip, 0 .. $circle-1);
}

sub calc_j {
  sub array_except {
    my $except = pop @_;
    my @array = @_;
    splice @array, $except, 1;
    return @array;
  }
  ($idx, $skip, @array) = @_;
  return @array == 1 ?
         $array[0] :
         calc_j($new_idx=($idx+$skip-1) % @array, $skip, array_except(@array, $new_idx));
}

print "josephus(12, 3) = ", josephus(12, 3), "\n";

2009-07-29 Reply Admin

Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:
GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

So 39 soldiers were done for, but Titus escaped.

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

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

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

Pseudocode:

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

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

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

Batch file:

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

call :josephus %1 %2

echo the servivor is at index %j%

exit /b

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

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

exit /b

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

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

2009-07-29 Reply Admin

Dave:

foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);

Monotheist, ey?

DeityRepo.FindBySpecialisation(DeitySpecialisations.War).SortOut(soldiers);

2009-07-29 Reply Admin

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

2009-07-29 Reply Admin

I tried to go for good readability.

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

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

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

with:

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

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

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

samanddeanus · 2009-07-29 Reply Admin

Really modeling the situation using Scheme message passsing OOP.

(define (make-person num)
  (let ((alive true)
	(next 'nobody))
    (lambda (op)
      (cond ((eq? op 'alive?) alive)
	    ((eq? op 'dead?) (not alive))
	    ((eq? op 'position) num)
	    ((eq? op 'next) next)
	    ((eq? op 'stand-next-to) (lambda (person)
				       (set! next person)))
	    ((eq? op 'kill) (if (not alive)
				(error "Cannot kill PERSON" num "-- already dead")
				(set! alive false)))
	    (else (error "Unknown operation -- PERSON" num))))))

(define (make-circle n)
  (let ((first-person (make-person n)))
    (let iter ((n (- n 1))
	       (current-person first-person))
      (if (zero? n)
	  (begin 
	    ((first-person 'stand-next-to) current-person)
	    current-person)
	  (iter (- n 1) (let ((new-person (make-person n)))
			  ((new-person 'stand-next-to) current-person)
			  new-person))))))

(define (josephus n m)
  (define (skip-m-and-kill circleptr)
    (let iter ((i m)
	       (cur-person circleptr))
      (cond ((cur-person 'dead?) (iter i (cur-person 'next)))
	    ((zero? i) (cur-person 'kill) cur-person)
	    (else (iter (- i 1) (cur-person 'next))))))
  (let ((circle (make-circle n)))
    (let iter ((number-alive n)
	       (curpos circle))
      (if (zero? number-alive)
	  (curpos 'position)
	  (iter (- number-alive 1) (skip-m-and-kill curpos))))))

2009-07-29 Reply Admin

Lerb:
Are we going to need a GodFactory, which returns an array of God pointers? Horrible pseudocode follows:
GodFactory.getGods(GodFactory.JEWISH) = [God] GodFactory.getGods(GodFactory.CHRISTIAN) = [God, God, God] GodFactory.getGods(GodFactory.ATHIEST) = null GodFactory.getGods(GodFactory.ROMAN) = [Zeus, ...] GodFactory.getGods(GodFactory.PASTAFARIAN) = [FSM]

and so on

I tried to call GodFactory.getGods(GodFactory.AGNOSTIC), but the call keeps blocking.

Help?

Josephus' Circle

Leave a comment on “Josephus' Circle”