======== pond.bat

2009-07-30 Reply Admin

Ha, now we have a way to stop people from posting "Frist!!1".

Cool idea, include a math exercise in each story, and additional to the captcha the solution of the exercise must be provided. This might not totally avoid "first11!1" posts, but we might get less of the very stupid ones :-)

tster · 2009-07-30 Reply Admin

T-SQL (SQL Server 2008 although I bet 2005 would work too). I tried to avoid just writing "C style" code with variables and really use the database features:


CREATE PROCEDURE  Josephus 
	-- Add the parameters for the stored procedure here
	@numSoldiers int, 
	@numSkip int
AS
BEGIN
	SET NOCOUNT ON
	
	CREATE TABLE SoldierList(
	[Soldier] int NOT NULL,
 CONSTRAINT [IX_SoldierList] UNIQUE CLUSTERED 
(
	[Soldier] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) 

CREATE TABLE Lineup(
	[LineupOrder] [int] IDENTITY(1,1) NOT NULL,
	[Soldier] [int] NOT NULL
) 
	
	
	delete from Lineup
	delete from SoldierList
	
	-- first make the soldier list
	declare @inserter as int
    set @inserter = 1
    while @inserter <= @numSoldiers
    begin
      insert into SoldierList(Soldier) values (@inserter)
      set @inserter = @inserter + 1
    end
    
    insert into Lineup(Soldier) select Soldier from SoldierList
    insert into Lineup(Soldier) select Soldier from SoldierList
    insert into Lineup(Soldier) select Soldier from SoldierList
    
    declare @axAt int
    set @axAt = -1
    while 1 < (select COUNT(*) from SoldierList)
    begin
    
		declare @minLineupId int
		set @minLineupId = (select MIN(LineupOrder) from Lineup)

		
		declare @toKillIndex int
		set @toKillIndex = (@axAt + @numSkip + 1) % (select COUNT(*) from Lineup)

		
		declare @toKillLineUp int
		set @toKillLineUp = @minLineupId + @toKillIndex

		
		declare @toKill int
		set @toKill = (select Soldier from Lineup where LineupOrder = @toKillLineUp)
		
		declare @numInstancesBeforeCurrent int
		set @numInstancesBeforeCurrent = (select COUNT(*) from Lineup where Soldier = @toKill and LineupOrder <= @toKillLineUp)
		
		delete from Lineup where Soldier = @toKill
		delete from SoldierList where Soldier = @toKill
		
		--line them back up
		delete from Lineup
		insert into Lineup(Soldier) select Soldier from SoldierList
		insert into Lineup(Soldier) select Soldier from SoldierList
		insert into Lineup(Soldier) select Soldier from SoldierList
		
		--make the soldier before the one just killed pick up the axe
		set @axAt = @axAt + @numSkip + 1
		set @axAt = @axAt - @numInstancesBeforeCurrent

		if @axAt < 0 
		begin
		  set @axAt = @axAt + (select COUNT(*) from SoldierList)
		  select @axAt as 'AxAt2'
		end
		
		set @axAt = @axAt % (select COUNT(*) from SoldierList)
    end
    
    select Soldier from SoldierList
    drop table SoldierList
    drop table Lineup
END
GO

tster · 2009-07-30 Reply Admin

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

WTF?

2009-07-30 Reply Admin

I didnt have time to read all the comments so sorry if this is what has already been done...

def josephus(soldiers, skip): soldiers = range(1, soldiers+1)
while len(soldiers) > 1:
soldiers.pop((skip - 1) % len(soldiers))
soldiers = soldiers[2:] + soldiers[:2]
return soldiers

2009-07-30 Reply Admin

[email protected]:
I think your last prime solution fails for 3 soldiers when killing of every third soldier :) In this case I think #41 would be the 23rd to die. I'd still want to be #31

Hmm, you're right, and so was Wongo. When I correct it so it's a accurate representation of scratching in the sand I get this:

<?php
/**
Sandbox grid solution.
----------------------
This isn't the most efficient algorithm (a computer doesn't need multiple rows), you may
even be able to express this problem as a mathematical equation.  However, a person can
execute this algorith by drawing a grid in the sand, as Josephus might have done, using the
rows to avoid losing your place (which would fatally alter the result).

The multiple rows help you keep your place.  As you work your way along each row,
"killing soldiers" you strike out the rest of the column (downwards, from the current row).
When you run of the end of the row, go down to the next.
*/

$n    = $argv[1];
$skip = $argv[2];
echo "The safe spot is #" . josephs_circle($n, $skip) . "\n";

function josephs_circle($n = 40, $skip = 3)
{
        $row      = array_pad(array(), $n, '');
        $grid     = array($row);

        $x     =  0;
        $y     =  0;
        $kills =  0;
        $s     =  $skip;

        while ($kills < $n)
        {
                if ($x == $n) // have run off the end of the row
                {
                        $x = 0;
                        $y++;
                        $grid[$y] = $grid[$y -1]; // strike out downwards
                }

                if (! $grid[$y][$x])
                {
                        $s--;
                }

                if ($s == 0)
                {
                        $kills++;         // now we're going to kill somebody, unless ...
                        if ($kills < $n)  // ... we're the last man standing
                        {
                                $grid[$y][$x] = ':-(';  // hit the soldier with the axe
                                $s            = $skip;
                        }
                }
                $x++;
        }
        return $x;
}
?>

Which gets the same solution as you. So much for prime numbers!

2009-07-30 Reply Admin

There are some Haskell solutions, but no oneliner yet:

josephus n s = head $ (!!(n-1)) $ iterate (\x -> let y = drop (s-1) x in filter (/= head y) y) $ concat $ repeat [1..n]

2009-07-30 Reply Admin

Last 2 man standing, one of them has the axe, why the hell would he kill himself?

2009-07-30 Reply Admin

LOL!

2009-07-30 Reply Admin

bash + expr:

#!/bin/bash
total=9
count=2

function commence() {
    ttotal=$1
    if [[ $ttotal = 1 ]]; then
        echo 0
    else
        ttemp1=`expr $ttotal - 1`
        ttemp2=`commence $ttemp1`
        ttemp3=`expr $ttemp2 + $count`
        expr $ttemp3 % $total
    fi
}

commence $total

2009-07-30 Reply Admin

I think this could be done quicker or with less code but i guess it's solid

function calculateSafeSpot($iNumSoldiers, $iNumSkip) { $aMen = array_fill(1,$iNumSoldiers, 'alive'); $iCount = 1; while(count($aMen)>1) {

    foreach($aMen as $iNum => $sAlive)
    {
        if($iCount == $iNumSkip)
        {
            $aMen[$iNum] = null;
            $iCount = 1;
        }
        else
        {
            $iCount++;    
        }
        
    }
    $aMen = array_filter($aMen);
}

$aManStanding = array_keys($aMen);
return $aManStanding[0];

}

2009-07-30 Reply Admin

Rather boring one, but simple, in php ;)

<?php function joseph($ile, $jump = 3) { $tab = array(); for ($i=0; $i<$ile; $i++) { $tab[] = ($i+1); } $k = $i = 0; while (count($tab)>1) { if ($i>=count($tab)) { $i = ($i%count($tab)); } if ((($k+1)%$jump)==0) { array_splice($tab, $i, 1); $i--; } $k++; $i++; } echo 'joseph('.$ile.', '.$jump.') = '.$tab[0].'
'; } ?>

2009-07-30 Reply Admin

# -*- coding: utf-8 -*-
def josephus(n, s):
	if n < 2:
		raise ValueError("n must be greater than one")
	if s < 1:
		raise ValueError("s must be greater zero")
	positions = range(n)
	i = 0
	while len(positions) > 1:
		i = (i + s - 1) % len(positions)
		del positions[i]
	return positions[0] + 1

josephus(12,3)

2009-07-30 Reply Admin

This programming praxis was let down by its simplicity and the well known nature of the problem. I love the idea of coding challenges but you need to come up with original problems for them.

2009-07-30 Reply Admin

If you call the Frisbeetarian object with a float, it just hangs....

SpaceDog · 2009-07-30 Reply Admin

Have one in sed with some help from bash.

#!/bin/bash
usage() { 
    echo "Usage: shooter.sh <people> <shootevery>"
    exit 
}

[ "$1" != "" ] && [ "$2" != "" ] || usage
echo "$1$2" | grep -qv '[^0-9]'  || usage
[ "$1" -gt 0 ] && [ "$2" -gt 0 ] || usage

PERSON="{[0-9][0-9]*}"
PEOPLE=$1
while [ $PEOPLE -ne 0 ]; do 
    INPUT="{${PEOPLE}}${INPUT}"
    PEOPLE=$((PEOPLE - 1))
done

SHOOTEVERY=$2
while [ $SHOOTEVERY -ne 1 ]; do 
    SKIP=${SKIP}${PERSON}
    SHOOTEVERY=$((SHOOTEVERY - 1))
done

echo
echo "Line up: ${INPUT}, firing on $2"
echo

echo "$INPUT" | sed -e 'p
:cull
/^'"${PERSON}"'$/boneleft
/'"${SKIP}"''"${PERSON}"'/{s/\('"${SKIP}"'\)'"${PERSON}"'\(.*\)/\2\1/p;tcull}
/^'"${PERSON}"'$/boneleft
:clone
/'"${SKIP}"''"${PERSON}"'/!{s/\(.*\)/\1\1/;tclone}
s/\('"${SKIP}"'\)\('"${PERSON}"'\)/x\2x\1/
:bury
s/x\('"${PERSON}"'\)x\(.*\)\1/x\1x\2/;tbury
s/x'"${PERSON}"'x//;
:declone
s/\('"${PERSON}"'\)\(.*\)\(\1\)/\1\2/;tdeclone;p
:oneleft
/^'"${PERSON}"'$/{s/{\('".*"'\)}/Winner: \1/;tend}
bclone
:end'

2009-07-30 Reply Admin

A solution in Clean which starts with a list of soldiers numbered 1 to n and recursively kills soldiers until only one is left:

josephus n s = kill [1..n] (s - 1) where kill [j] s = j kill l s = kill (tl (rotate l s)) s

rotate l s = drop s l ++ take s l

2009-07-30 Reply Admin

Hacky solution in R. Remember that in R all indices begin with 1. Uncomment the cats to see how it works.

josephus <- function (men, kill) 
{
        list <- 1:men
        while(length(list)>2){
                tmp.kill <- kill %% men
                list <- c(list[-(1:tmp.kill)],list[1:(tmp.kill-1)])
                #cat(list)
                #cat("\n")
        }
        tmp.live <- (kill %% 2) + 1
        list[tmp.live]
}

2009-07-30 Reply Admin

Anonymous Coward:
John Stracke:
Sexy, but wrong. J(12,3) returns 0; look at the animation and you'll see that it should be either 9 or 10 (depending on whether you're counting from 0 or 1).

What are you smoking?
>>> def j(n,k):
...     if(n==1): return 0
...     else: return (j(n-1,k)+k)%n
...
>>> j(12,3)
9
>>>

Uh...aw, bleep. I ran J(3,12) instead.

Sorry. You'd think I'd've learned not to flame after 10PM by now...

2009-07-30 Reply Admin

Python one-liner:

josephus = lambda n, s, r=None, i=0: josephus(n, s, range(n)) if r is None else (r[0] + 1 if len(r) == 1 else josephus(n,s,r[:(i + s - 1) % len(r)] + r[(i + s - 1) % len(r) + 1:], (i + s - 1) % len(r)))

print josephus(12,3)

DaveK · 2009-07-30 Reply Admin

Code Dependent:
Dave:
foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
Shouldn't God be static?

Since God is both eternal and unchanging, He must be static const.

Addendum (2009-08-14 23:32): Updated: I have been studying theology and discovered that He is also claimed to be uncreated. Therefore he is static const, and the constructor is private.

2009-07-30 Reply Admin

BASIC code SAFE_SPOT is the return parameter.

I'm using a string of "1" characters, instead of an array, which are switched to "0" when dead.

0010 ENTER TOTAL_SOLDIERS,SKIP_COUNT,SAFE_SPOT
0020 LET SOLDIERS$=FILL(TOTAL_SOLDIERS,"1")
0030 LET POSITION=1,SOLDIERS_LEFT=TOTAL_SOLDIERS,COUNT=0
0040 WHILE SOLDIERS_LEFT>1
0050 IF SOLDIERS$(POSITION,1)="1" THEN GOSUB LIVE_OR_DIE ENDIF
0060 LET POSITION=POSITION+1
0070 IF POSITION>TOTAL_SOLDIERS THEN LET POSITION=1 ENDIF
0080 WEND
0090 LET SAFE_SPOT=POS("1"=SOLDIERS$)
0100 EXIT
0110 LIVE_OR_DIE:
0120 LET COUNT=COUNT+1
0130 IF COUNT=SKIP_COUNT THEN LET SOLDIERS$(POSITION,1)="0",COUNT=0,SOLDIERS_LEFT=SOLDIERS_LEFT-1 ENDIF
0140 RETURN

2009-07-30 Reply Admin

javascript with caching to make it run fast ;)

function j(n,k){
    if(j[n] != undefined && j[n][k] != undefined){
        return j[n][k];
    }
    if(n==1){
        return 0;
    }
    if(j[n] == undefined){
        j[n] = [];
    }
    var jj = (j(n-1,k) + k) % n;
    j[n][k] = jj;
    return jj;

};

Severity One · 2009-07-30 Reply Admin

Code Dependent:
Dave:
foreach(soldier:soldiers){
 soldier.kill();
}
God.getInstance().sortOut(soldiers);
Shouldn't God be static?

That depends. In this case, it looks like it's a static method on a class, but nothing ensures that God is singleton (as would be required by monotheistic beliefs like Christianity, Judaism and Islam).

If you're a follower of a polytheistic belief, such as Hinduism, you would require a getInstance() method for each god, and perhaps a factory class:

public class GodFactory
{
public static God getInstance( String name ) throws NoSuchGodException
{
// ...
}
}

Finally, if you're Terry Pratchett, you can instantiate God objects with the 'new' operator. If the God object is not used, it will automatically be garbage collected.

However, God objects are considered anti-patterns, and should therefore not be used.

2009-07-30 Reply Admin

let rec josephus soldiers skips = if soldiers < 2 then 0 else (josephus (soldiers-1) skips + skips) mod soldiers;;

2009-07-30 Reply Admin

Anonymous:
In response to Wongo:
There's a formula in the Online Encyclopaedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A054995

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).

Very interesting, thanks for the link. Still not something Josephus could have hacked together in the few seconds when the troup gathers (unless the guy was both a soldier AND a polymath, rather a rare occurrence)... Also, he would have to have known the constant K, which I'm not sure was known at the time.

Again, I might be completely wrong in interpreting the problem, maybe that "Josephus quickly found a solution" is just Alex's usual literary embellishment... But darn, those series look eerily simplifiable.

Scarlet Manuka · 2009-07-30 Reply Admin

I'm currently in the middle of an XML training course, and it's really tempting to try to work out a way of doing this in an XSLT. Unfortunately I have two important work-related tasks that I have to finish tonight and it's 9pm already, so I don't have time to play around with it (and really I shouldn't be on this site at all).

But if the course is going slowly tomorrow, I make no guarantees :D

2009-07-30 Reply Admin

He there

I focused on ... getting it right ... fast. So I wrote down a pretty stupid piece of JAVA code (plus some debug output and profiling basics. I calculated that it would be O(n^2) ... so who cares if there is an O(n) solution anyway ;-)

But well, that one was really neat. Anyway, here we go.

public class Circle
{
    public static String toString(boolean people[])
    {
        String result = "";
        for (int i=0; i < people.length; i++) {
            result += (people[i]) ? "." : "A";
        }
        return result;
    }

    public static int findSpot(int numPeople, int numAxe)
    {
        boolean people[] = new boolean[numPeople];

        int idx = 0;
        int counter = 1;
        int remaining = numPeople;

        while (true) 
        {
//            System.out.println("idx: " + Integer.toString(idx) +
//                               " / counter: " + Integer.toString(counter) +
//                               " / remaining: " + Integer.toString(remaining) +
//                               " field: " + toString(people));
            if (! people[idx]) // guy is not dead
            {
                if (counter == numAxe) 
                {
                    people[idx] = true; // kill the guy
                    remaining--;        // one less
                    counter = 1;        // restart counting

                    if (remaining == 1) break; // all dead
                } // if counter == numAxe
                else
                {
                    counter++;
                }
            } // if !people[idx]

            idx++;
            if (idx == numPeople) idx = 0;
        } // while true

        for (idx=0; idx < people.length; idx++) 
        {
            if (!people[idx]) break;
        }

//        System.out.println("idx: " + Integer.toString(idx) +
//                           " / counter: " + Integer.toString(counter) +
//                           " / remaining: " + Integer.toString(remaining) +
//                           " field: " + toString(people));
        return idx+1;
    } // findSpot()

    public static void main(String args[])
    {
        long start = System.currentTimeMillis();
        int spot = findSpot(new Integer(args[0]).intValue(),
                            new Integer(args[1]).intValue());
        long stop = System.currentTimeMillis();

        System.out.println("Spot is: " + new Integer(spot).toString() +
                           " / time is: " + new Long(stop-start).toString() + " ms");
    }
}

2009-07-30 Reply Admin

This should be done with math but I haven't had my coffee yet. So I will use Mathematica. This seems to be a job for NestWhile, and we can use cyclicity and skip to the n'th person by RotateLeft'ing by n-1. So

JosephusLast[num_Integer?Positive, step_Integer?Positive] := NestWhile[Rest[RotateLeft[#, step - 1]] &, Range[num], Length[#] > 1 &][[1]]

E.g.

In[3]:= JosephusLast[12, 3]

Out[3]= 10

In[4]:= JosephusLast[41, 3]

Out[4]= 31

In[5]:= JosephusLast[40, 3]

Out[5]= 28

Replacing NestWhile with NestWhileList and removing the [[1]] gives who is left before each step.

2009-07-30 Reply Admin

TGV:
Anonymous:
In response to Wongo:
There's a formula in the Online Encyclopaedia of Integer Sequences: http://www.research.att.com/~njas/sequences/A054995

Not the simplest looking thing, but still not bad (compared to what I usually have to look at).
Looks like a solution to a recurrent series to me. They all have this weird power in it somewhere. E.g., the formula for the Fibonacci sequence has one: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#formula. This one, however, must have been harder to crack. It's nice to see that some mathematically gifted man took his time to solve it. I like it better than the hacks I've seen in the responses here...

Fascinating. For all those who won't follow the link, here is the gist of it: to calculate Fibo(n+1) given ONLY Fibo(n) (and not, as is usual, Fibo(n-1)), just do Fibo(n+1) = round(Fibo(n)* Phi). It works for all cases where n>1 (Phi is the golden number 1.618...).

There MUST be some similar solution to the Josephus problem...

EnterpriseSolutionsLTD · 2009-07-30 Reply Admin

C# (4.0):

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(JosephusCircle.Solve());
        }
    }

    public enum Vitality
    {
        Alive,
        Dead
    }

    public class Soldier
    {
        public Soldier()
        {
            Vitality = Vitality.Alive;
        }

        public void Axe()
        {
            Vitality = Vitality.Dead;
        }

        public Vitality Vitality { get; private set; }
    }

    public static class JosephusCircle
    {
        public const int DefaultSoldierCount = 40;
        public const int DefaultSkipAmount = 3;

        public static int Solve(int soldierCount = DefaultSoldierCount, int skipAmount = DefaultSkipAmount)
        {
            var soldiers = new List<Soldier>();

            do
            {
                soldiers.Add(new Soldier());
            } while (soldiers.Count < soldierCount);

            return Solve(soldiers, skipAmount);
        }

        public static int Solve(IEnumerable<Soldier> soldiers, int skipAmount = DefaultSkipAmount)
        {
            var soldierList = soldiers.ToList();

            var leftToSkip = skipAmount;
            var index = -1;

            do
            {
                if (++index == soldierList.Count)
                {
                    index = 0;
                }

                if (soldierList[index].Vitality == Vitality.Alive)
                {
                    if (--leftToSkip == 0)
                    {
                        soldierList[index].Axe();

                        leftToSkip = skipAmount;
                    }
                }
                else
                {
                    continue;
                }
            } while (soldierList.Where(soldier => soldier.Vitality == Vitality.Alive).Count() > 1);

            return soldierList.IndexOf(soldierList.Single(soldier => soldier.Vitality == Vitality.Alive));
        }
    }

2009-07-30 Reply Admin

xeno:
Oops. Jospehus was the 41st soldier, so the safe spot is #41.
That in itself is a hint as to a mathmatical solution. I just checked, and whenever there is prime number of soldiers, the last (prime) place is the safe spot. I imagine that there is some mathematical solution involving finding the largest co-prime, but that's over my head.

Actually, the safe spot with 41 soldiers is 31, not 41. And 11 (soldiers) = 7 (safe spot), 13 = 13 (you're right for this one), 17=11, 19=17, 23=8... It doesn't work. I've also tried things like: safe spot = (soldiers - previous prime) * 2, safe spot = soldiers mod previous prime... No luck there either.

2009-07-30 Reply Admin

xeno:
Now that I think about it a grid-in-sand solution is silly. If he was going to do that, he might as well have just modeled the problem directly with a line or ring of 41 pebbles.

[email protected]:
Draw a circle and place 41 stones around it just touching the circle. Starting at one move every third stone that is outside the circle across the line to the inside of the circle so that the order of the stones is maintained. Continue til there is only one stone left outside the circle. That is the last soldier position and that is where you should stand.

Yes, but:

That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").
What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

Vilx- · 2009-07-30 Reply Admin

Since this is The Daily WTF, I figured that the solution is worth nothing unless it is a WTF itself. So - here's my attempt at doing it in Microsoft-specific C++. N = the number of men; K = which one to kill (3 means every 3rd). The return value is the number of position (starting at 1).

int josephus(int n , int k) { int $,$=n,=2,$$=k;$^=$;$_:if(>$)goto $;$+=$$;$%=__++;goto $;$:return ++$_; }

DaveGamble · 2009-07-30 Reply Admin

First! (for 4, 9, 31, 70, 105, 355, 799, 1798, 2697 etc soldiers...)

(Sorry, couldn't resist.)

First off, iterative Josephus, O(n), in C:

int JIter(int n,int k){int v=0,i=2;for(;i<=n;v=(v+k)%i++);return v+1;}

Crunchy, but effective.

Secondly, here's that O(1) implementation, again in C:

#define K3 1.62227050288476731595695
int JLin(int n){return 3*n+1-floor(K3*pow((3.0/2.0),ceil(log((2.0*n+1.0)/K3)/log(3.0/2.0))));}

Please note that this is specific to k=3.

Here's an O(Log N) (to the base k) implementation, C, based on Strilanc's solution.

int JLog(int n,int k) {
	if (k==1) return n-1;if (n<=1) return 0;
	int t=JLog(n-ceil((double)n/(double)k),k);
	t += (k-1) - (n+k-1)%k;t += floor((double)t / ((double)k-1.0));
	return t%n;
}

Iterative O(Log(N)) proves difficult, because we have some maths on either side; the recursive n-ceil(n/k) on input, and the clever stuff after. Anyone have any ideas?

The story is likely to be apocryphal, or at least the part about figuring out where to stand being either attributed later or pure luck (anthropics!).

Also, bear in mind they were euthanising each other as a kindness. It would have been fairly easy for him to "do the kindest thing", and accept the last position.

2009-07-30 Reply Admin

import java.util.ArrayList;

public class JosephusCirle {

	private static Integer saveSpot(int soldiers, int skipCount) {

		/* everyone dies in order, axe is passed from one to another --> last one survives 
		 * or one enters the cave, and one leaves it (no monster found) */
		if (skipCount == 0 || soldiers == 1) {
			return new Integer(soldiers);
		}

		// I knew it, a Ghost Army !!!
		if (soldiers <= 0) {
			return null;
		}

		int deathCount = (((skipCount < 0) ? (skipCount * -1) : skipCount)) + 1;

		ArrayList<Integer> livingSoldiers = new ArrayList<Integer>();
		ArrayList<Integer> livingSoldiersBackwards = new ArrayList<Integer>();

		// build cirle
		{
			livingSoldiersBackwards.add(new Integer(1));

			for (int i = 0; i < soldiers; i++) {
				livingSoldiers.add(new Integer(i + 1));
				if (i > 0) {
					livingSoldiersBackwards.add(new Integer(soldiers - i + 1));
				}
			}
			
			for (int i = 0; i < livingSoldiersBackwards.size(); i++) {
				System.out.println("RW: " + livingSoldiersBackwards.get(i).intValue());
			}
		}

		// circle axe
		{
			int axeCount = 0;

			while (livingSoldiers.size() > 1) {
				for (int i = 0; i < livingSoldiers.size(); i++) {
					axeCount++;

					if (axeCount == deathCount) {
						livingSoldiers.remove(i);
						axeCount = 0;

						i--;
					}
				}
			}
		}
		
		return ((skipCount < 0) ? livingSoldiersBackwards.get(livingSoldiers.get(0).intValue() - 1) : livingSoldiers.get(0));
		
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Integer saveSpot = saveSpot(12, 2);
		if (saveSpot == null) {
			System.out.println("No Save spot found, only D E A T H!");
		}
		else {
			System.out.println("Save spot: " + saveSpot);
		}
	}

}

by Damage

2009-07-30 Reply Admin

Wongo:
Mmh, these solutions overlook one important point: "Josephus somehow managed to figure out — very quickly — where to stand with forty others".
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).

Indeed, here is the list of safe spots according to the number of soldiers (assuming a skip of 3):

Soldiers: 2, Last Spot: 2 Soldiers: 3, Last Spot: 2 Soldiers: 4, Last Spot: 1 Soldiers: 5, Last Spot: 4 Soldiers: 6, Last Spot: 1 Soldiers: 7, Last Spot: 4 Soldiers: 8, Last Spot: 7 Soldiers: 9, Last Spot: 1 Soldiers: 10, Last Spot: 4 Soldiers: 11, Last Spot: 7 Soldiers: 12, Last Spot: 10 Soldiers: 13, Last Spot: 13 Soldiers: 14, Last Spot: 2 Soldiers: 15, Last Spot: 5 Soldiers: 16, Last Spot: 8 Soldiers: 17, Last Spot: 11 Soldiers: 18, Last Spot: 14 Soldiers: 19, Last Spot: 17 Soldiers: 20, Last Spot: 20 Soldiers: 21, Last Spot: 2 Soldiers: 22, Last Spot: 5 Soldiers: 23, Last Spot: 8 Soldiers: 24, Last Spot: 11 Soldiers: 25, Last Spot: 14 Soldiers: 26, Last Spot: 17 Soldiers: 27, Last Spot: 20 Soldiers: 28, Last Spot: 23 Soldiers: 29, Last Spot: 26 Soldiers: 30, Last Spot: 29 Soldiers: 31, Last Spot: 1 Soldiers: 32, Last Spot: 4 Soldiers: 33, Last Spot: 7 Soldiers: 34, Last Spot: 10 Soldiers: 35, Last Spot: 13 Soldiers: 36, Last Spot: 16 Soldiers: 37, Last Spot: 19 Soldiers: 38, Last Spot: 22 Soldiers: 39, Last Spot: 25 Soldiers: 40, Last Spot: 28 Soldiers: 41, Last Spot: 31

The series on the right looks conspicuously susceptible to a shortcut. But I can't find it for the life of me... Anyone ?

round pi('s) will kill you?

2009-07-30 Reply Admin

Here are 4 variations in C#

        private static int Josephus1(int numberOfSoldiers, int soldiersToSkip)
        {
            char livingSoldier = '|';
            string deadSoldier = "_";
            string circleOfSoldiers = string.Empty.PadLeft(numberOfSoldiers, livingSoldier);
            int indexOfAxe = -1;
            while (circleOfSoldiers.IndexOf(livingSoldier) != circleOfSoldiers.LastIndexOf(livingSoldier))
            {
                for (int skippedSoldiers = 0; skippedSoldiers <= soldiersToSkip; skippedSoldiers++)
                {
                    indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier, indexOfAxe + 1);
                    if (indexOfAxe == -1)
                    {
                        indexOfAxe = circleOfSoldiers.IndexOf(livingSoldier);
                    }
                }
                circleOfSoldiers = circleOfSoldiers.Remove(indexOfAxe, 1).Insert(indexOfAxe, deadSoldier);
            }
            return circleOfSoldiers.IndexOf(livingSoldier) + 1;
        }

        private static int Josephus2(int numberOfSoldiers, int soldiersToSkip)
        {
            Queue<int> circleOfSoldiers = new Queue<int>();
            for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
            {
                circleOfSoldiers.Enqueue(soldier);
            }
            while (circleOfSoldiers.Count > 1)
            {
                for (int skip = 1; skip <= soldiersToSkip; skip++)
                {
                    circleOfSoldiers.Enqueue(circleOfSoldiers.Dequeue());
                }
                int deadSoldier = circleOfSoldiers.Dequeue();
            
            }
            return circleOfSoldiers.Dequeue();
        }

        private static int Josephus3(int numberOfSoldiers, int soldiersToSkip)
        {
            List<int> circleOfSoldiers = new List<int>();
            for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
            {
                circleOfSoldiers.Add(soldier);
            }
            int indexOfDeadSoldier = 0;
            while (circleOfSoldiers.Count > 1)
            {
                indexOfDeadSoldier += soldiersToSkip;
                while (indexOfDeadSoldier >= circleOfSoldiers.Count || indexOfDeadSoldier < 0)
                {
                    if (indexOfDeadSoldier >= circleOfSoldiers.Count)
                    {
                        indexOfDeadSoldier -= circleOfSoldiers.Count;
                    }
                    if (indexOfDeadSoldier < 0)
                    {
                        indexOfDeadSoldier += circleOfSoldiers.Count;
                    }
                }
                circleOfSoldiers.RemoveAt(indexOfDeadSoldier);
            }
            return circleOfSoldiers[0];
        }

        private static int Josephus4(int numberOfSoldiers, int soldiersToSkip)
        {
            LinkedList<int> circleOfSoldiers = new LinkedList<int>();

            for (int soldier = 1; soldier <= numberOfSoldiers; soldier++)
            {
                circleOfSoldiers.AddLast(soldier);
            }
            LinkedListNode<int> currentSoldierWithAxe = circleOfSoldiers.First;
            while (circleOfSoldiers.Count > 1)
            {
                for (int passAxe = 0; passAxe < soldiersToSkip; passAxe++)
                {
                    currentSoldierWithAxe = currentSoldierWithAxe.Next;
                    if (currentSoldierWithAxe == null)
                    {
                        currentSoldierWithAxe = circleOfSoldiers.First;
                    } 
                }
                LinkedListNode<int> deadSoldier = currentSoldierWithAxe;
                currentSoldierWithAxe = deadSoldier.Next;
                circleOfSoldiers.Remove(deadSoldier);
                if (currentSoldierWithAxe == null)
                {
                    currentSoldierWithAxe = circleOfSoldiers.First;
                } 
            }
            return currentSoldierWithAxe.Value;
        }

2009-07-30 Reply Admin

Wongo:
1) That's a bit obvious (40 of them are praying, and only Josephus is drawing in the sand, mumbling "...skip Marcus, kill Anthony, skip Aurelius...").

What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")

As I read the problem (again, I might be mistaken), he uses his wits to quickly find a general solution to the problem, which would accommodate for a variable number of soldiers and skip steps.

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

Bear in mind that modern historians regard TJF's credibility as "questionable".

And we only have TJF's account of what actually happened.

As Wongo implies there - during the battle, anything could have happened - there was no way TFJ could know in advance there would be exactly 41 individuals present.

So, the possibilities are:

1: there is a very rapid shortcut, that no subsequent mathematician has been able to rediscover...

2: he has previously calculated and memorised the answer for multiple scenarios...

3: he works it out just once cycle ahead - "1, 2, argh, 1, 2, glurg" - and moves position to stay alive one move cycle - "I'll just check that Aaron is actually dead there..." walks over, stabs the corpse and stays standing in that new location...

4: he was just genuinely lucky that day...

5: he lied about what happened...

6: he lied about what happened...

< Kryten_mode > Now I realise the last two suggestions are actually the same point, but I thought it was such a big one it was worth mentioning twice. < Kryten_mode />

So, in other words, the original documentation is faulty, and everyone here is now coding a solution to something other than the real situation... :)

SteamBoat · 2009-07-30 Reply Admin

The position that Josephus took was as the executioner.

MArk B.

halcyon1234 · 2009-07-30 Reply Admin

Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT

Run pond.bat [NumberofDucks] [skips until kill]

It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

Repeat until the goose lays a golden egg in the pond, and the final position is reported.

======== pond.bat

@ECHO OFF REM usage: pond.bat NumberOfDucks SkipsUntilGoose

SET DUCKS=%1 SET GOOSE=%2

IF %DUCKS%=="" GOTO USAGE IF %GOOSE%=="" GOTO USAGE

REM *** Begin the spot-check loop *** :START REM start the golden goose at position 1 SET GOLDENGOOSE=1

:BREED

REM set the counter at 1 SET DUCKDUCK=1

REM reset the counter SET COUNT=1

:HATCH

copy liveduck.bat duck%COUNT%.bat >nul

SET /A COUNT=%COUNT%+1

IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

GOTO :HATCH

:ENTERPOND

REM set the number of alive ducks SET QUACKERS=%DUCKS%

REM set the first calling duck SET QUACKER=1

:DUCKDUCK

CALL duck%QUACKER%.bat

REM Two ending conditions IF %POND%==crap GOTO BADRESULT IF %POND%==gold GOTO GOODRESULT IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

REM Else the next duck should be called

SET /A QUACKER=%QUACKER%+1

REM loop back to the first duck if needed IF %QUACKER% GTR %DUCKS% SET QUACKER=1

GOTO DUCKDUCK

:SOMETHINGAWFUL echo exception all ducks died but the golden goose never crapped GOTO END

:BADRESULT REM oh no, the golden goose was killed! Let's start again, but move the REM goose one higher

ECHO Golden Goose unsafe at position %GOLDENGOOSE%

SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

REM If we've exhausted positions, than this is unwinnable IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

REM Recreate the ducks GOTO BREED

:GOODRESULT REM the golden goose was safe! What position was he in? ECHO Golden Goose was safe at position %GOLDENGOOSE% GOTO END

:ROASTDUCK REM the golden goose was unsafe at any position ECHO There is no safe spot for the goose. Would you like leg or thigh? GOTO END

:USAGE ECHO Proper usage: ducks.bat NumberOfDucks NumberOfSkips

:END SET COUNT=1

:KILL del duck%COUNT%.bat SET /A COUNT=%COUNT%+1 IF %COUNT% LEQ %DUCKS% GOTO :KILL

============ liveduck.bat

@ECHO OFF

REM DUCKDUCK = the current loop counter REM GOLDENGOOSE = the position of the special goose REM POND = Where to put the return variable REM GOOSE = The max of the skip counter REM QUACKER = The last goose to act REM DUCKS = The number of ducks we started with

REM If the highest counter was hit, this duck dies IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

REM Otherwise quack and move onto the next duck SET POND=quack REM Increase the count by one SET /A DUCKDUCK=%DUCKDUCK%+1

GOTO END

:FUCKTHATDUCK

SET DUCKDUCK=1

REM This duck must die. If this duck is the last duck alive, the golden REM goose is safe

IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

REM Kill self SET POND=dead copy deadduck.bat %0 >nul GOTO :END

:GOLDDIGGER

REM The golden goose is about to die. See if it is the last duck alive, REM it wins. Ohterwise, bad.

SET POND=crap

IF %QUACKERS% EQU 1 SET POND=gold

GOTO END

:END

============ deadduck.bat

@ECHO OFF REM Dead ducks aren't much fun. They don't increase the duckduck counter, REM since they don't count. Just ignore this duck and move on

SET POND=brains

:END

Schneau · 2009-07-30 Reply Admin

Simple in Python with a list that gets shorter:

def josephus(n, k): soldiers = range(0,n) kill = -1 while n > 1: kill = (kill + k) % n soldiers.pop(kill) n -= 1 kill -= 1 return soldiers[0] + 1

Schneau · 2009-07-30 Reply Admin

halcyon1234:
Here's an overly complex and deadly game of Duck Duck Goose, done in DOS. For what it's worth, I wrote it in EDIT
Run pond.bat [NumberofDucks] [skips until kill]

It will create that many duck files. The Golden Goose will be put in the first spot. A duck increases the count, then either quacks (safe), dies (unsafe), craps (golden goose dies) or golds (golden goose last one standing).

If the pond gets crapped in, all the ducks are resurrected, and the golden goose is put into the next spot.

Repeat until the goose lays a golden egg in the pond, and the final position is reported.

======== pond.bat

@ECHO OFF REM usage: pond.bat NumberOfDucks SkipsUntilGoose

SET DUCKS=%1 SET GOOSE=%2

IF %DUCKS%=="" GOTO USAGE IF %GOOSE%=="" GOTO USAGE

REM *** Begin the spot-check loop *** :START REM start the golden goose at position 1 SET GOLDENGOOSE=1

:BREED

REM set the counter at 1 SET DUCKDUCK=1

REM reset the counter SET COUNT=1

:HATCH

copy liveduck.bat duck%COUNT%.bat >nul

SET /A COUNT=%COUNT%+1

IF %COUNT% GTR %DUCKS% GOTO ENTERPOND

GOTO :HATCH

:ENTERPOND

REM set the number of alive ducks SET QUACKERS=%DUCKS%

REM set the first calling duck SET QUACKER=1

:DUCKDUCK

CALL duck%QUACKER%.bat

REM Two ending conditions IF %POND%==crap GOTO BADRESULT IF %POND%==gold GOTO GOODRESULT IF %POND%==dead SET /A QUACKERS=%QUACKERS%-1

IF %QUACKERS% EQU 0 GOTO SOMETHINGAWFUL

REM Else the next duck should be called

SET /A QUACKER=%QUACKER%+1

REM loop back to the first duck if needed IF %QUACKER% GTR %DUCKS% SET QUACKER=1

GOTO DUCKDUCK

:SOMETHINGAWFUL echo exception all ducks died but the golden goose never crapped GOTO END

:BADRESULT REM oh no, the golden goose was killed! Let's start again, but move the REM goose one higher

ECHO Golden Goose unsafe at position %GOLDENGOOSE%

SET /A GOLDENGOOSE=%GOLDENGOOSE%+1

REM If we've exhausted positions, than this is unwinnable IF %GOLDENGOOSE% GTR %DUCKS% GOTO ROASTDUCK

REM Recreate the ducks GOTO BREED

:GOODRESULT REM the golden goose was safe! What position was he in? ECHO Golden Goose was safe at position %GOLDENGOOSE% GOTO END

:ROASTDUCK REM the golden goose was unsafe at any position ECHO There is no safe spot for the goose. Would you like leg or thigh? GOTO END

:USAGE ECHO Proper usage: ducks.bat NumberOfDucks NumberOfSkips

:END SET COUNT=1

:KILL del duck%COUNT%.bat SET /A COUNT=%COUNT%+1 IF %COUNT% LEQ %DUCKS% GOTO :KILL

============ liveduck.bat

@ECHO OFF

REM DUCKDUCK = the current loop counter REM GOLDENGOOSE = the position of the special goose REM POND = Where to put the return variable REM GOOSE = The max of the skip counter REM QUACKER = The last goose to act REM DUCKS = The number of ducks we started with

REM If the highest counter was hit, this duck dies IF %DUCKDUCK% EQU %GOOSE% GOTO FUCKTHATDUCK

REM Otherwise quack and move onto the next duck SET POND=quack REM Increase the count by one SET /A DUCKDUCK=%DUCKDUCK%+1

GOTO END

:FUCKTHATDUCK

SET DUCKDUCK=1

REM This duck must die. If this duck is the last duck alive, the golden REM goose is safe

IF %0==duck%GOLDENGOOSE%.bat GOTO GOLDDIGGER

REM Kill self SET POND=dead copy deadduck.bat %0 >nul GOTO :END

:GOLDDIGGER

REM The golden goose is about to die. See if it is the last duck alive, REM it wins. Ohterwise, bad.

SET POND=crap

IF %QUACKERS% EQU 1 SET POND=gold

GOTO END

:END

============ deadduck.bat

@ECHO OFF REM Dead ducks aren't much fun. They don't increase the duckduck counter, REM since they don't count. Just ignore this duck and move on

SET POND=brains

:END

mad props

Maurits · 2009-07-30 Reply Admin

Still Not Tim:
Wongo:
2) What if they were 400 soldiers? ("Guys, please pray a bit more, I haven't finished calculating my, er... tax returns")
2: he has previously calculated and memorised the answer for multiple scenarios...

then you keep fighting 2: memorizing 40 numbers is doable, especially if your life depends on it

The number 40 had great significance to Hebrews (it rained for 40 days and 40 nights, etc.) so I wouldn't be surprised if it was standard practice to give up if your fighting force dropped below 40 (assuming your cause was hopeless)

2009-07-30 Reply Admin

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

I'd like to see somebody come up with a solution that works on 1st century A.D. technology.

Aha! That's how he figured it out so quickly!

Using his trusty abacus, he put dirt on one side of each bead. With lightning speed, he rolled beads over one-by-one, and found the correct spot. Brute force wins!

mol1111 · 2009-07-30 Reply Admin

He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).

2009-07-30 Reply Admin

mol1111:
He actually had plenty of time. If he knew who will be starting he could easily select position to not be killed in the first round, so he had 13*(time to commit suicide) to find out final solution (and if you are in such situation you think quickly) and create some excuse for changing the spot (they were not expecting cheater so it wasn't that big problem).

And, all in all, maybe he just got lucky? :)

2009-07-30 Reply Admin

In PHP, with a nice visual representation

\n"; $k++; } ?> <?php }else{ ?> <form action="<?php echo $_SERVER['PHP_SELF']; ?>" method="get"> <input type="hidden" name="form_set" value="on"/> <label for="soldiers">soldiers: </label><input name="soldiers" val=""/>
<label for="skip">skip: </label><input name="skip" val=""/>
<input type="submit"/> </form> <?php } ?>

Code Dependent · 2009-07-30 Reply Admin

It's just amazing now many of you dumbasses are willing to spend time working out and arguing over the workings of this puzzle. Are there really that many of you out of work?

Caveat: I work. I read TDWTF while my work is compiling. I make occasional comments unrelated to the topic.

kastein · 2009-07-30 Reply Admin

Josephus:
Last

... best "first" post ever. Code Dependent, eat your heart out! :P

RaspenJho · 2009-07-30 Reply Admin

private static int jcircle(int soldiers, int skip)
{
    Queue<int> q = new Queue<int>(Enumerable.Range(0, soldiers).ToList());
    while (q.Count > 1)
    {
        for (int i = 0; i < skip; i++)
            q.Enqueue(q.Dequeue());
        q.Dequeue();
    }
    return q.Dequeue() + 1;
}

Naturally, a Queue!

If you add a print statement inside the loop you can almost visualize them lining up to get the axe ;)

Soldiers: 2, Last Spot: 2 Soldiers: 3, Last Spot: 2 Soldiers: 4, Last Spot: 1 Soldiers: 5, Last Spot: 4 ... Soldiers: 39, Last Spot: 25 Soldiers: 40, Last Spot: 28 Soldiers: 41, Last Spot: 31

Josephus' Circle

In fact, the question is now rather similar to the one about Fermat's Theorem: at the time, could he or could he not have found a solution that required none of the knowledge we now have?

======== pond.bat

============ liveduck.bat

============ deadduck.bat

======== pond.bat

============ liveduck.bat

============ deadduck.bat

Leave a comment on “Josephus' Circle”