• (cs)

    Interesting pattern when you line up the plotted points of the "safe spot" in varying numbers of soldiers...

                1
               12
               123
                1234
             12345
                123456
             1234567
          12345678
                123456789
             1234567890
          12345678901
       123456789012
    1234567890123
               12345678901234
            123456789012345
         1234567890123456
    
  • Justin Drury (unregistered)

    Here is my C# 3.5 solution. I kept looking for a nice easy few liner for it but ran out of time.

    static int Josephus(int numSoldiers, int skipCount)
    {
        List<int> soldiers = Enumerable.Range(1, numSoldiers).ToList();
        var deadMen = new List<int>();
        var stillAlive = new List<int>();
        int currentCount = 0;
        while(true)
        {
            stillAlive = soldiers.Where(s => !deadMen.Contains(s)).ToList();
            if(stillAlive.Count() == 1)
            {
                break;
            }
            foreach(var guy in stillAlive)
            {
                currentCount++;
                if(currentCount == skipCount)
                {
                    deadMen.Add(guy);
                    currentCount = 0;
                }
            }
        }
        return soldiers.SkipWhile(s => deadMen.Contains(s)).First();
    }
    
  • Steve Vance (unregistered)

    $ cat saveJos.c

    #include <stArmyFunctions.h>

    int main (int argc, const char **argv) { if(argc > 0) { DefectFromArmy(); //from stArmyFunctions fprintf ("Josephus successfully defects from the army and survives!"); } else fprintf ("Josephus has nothing to worry about as they are killing nobody"); return 0; }

  • (cs)

    Here's a XSLT solution - with graphics! Needs XSLT 2.0 and uses EXSLT for the graphics (which aren't really necessary), so it probably will not run on your browser. Here's a sample Saxon output.

    Takes three parameters - the number of soldiers, the number of people to skip between two victims and the radius of the graphical circles in pixels.

    Since the output is done with pixel positioning, your mileage might vary on different operating systems and browsers. And I know that the "copyright" text might be under the circles.

    Example XML:

    <?xml version="1.0" encoding="UTF-8"?>
    <!-- XSLT Josephus' Circle ~ (C) Shadikka 2009 -->
    <?xml-stylesheet type="text/xsl" href="josephus.xsl"?>
    
    <circle>
        <soldiers>29</soldiers>
        <skip>2</skip>
        <radius>90</radius>
    </circle>

    And here's the XSLT:

    <?xml version="1.0" encoding="UTF-8"?>
    <xsl:stylesheet version="2.0"
      xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
      xmlns:math="http://exslt.org/math"
      xmlns="http://www.w3.org/1999/xhtml">
    
    <!-- XSLT Josephus' Circle ~ (C) Shadikka 2009 -->
    
    <xsl:output method="html" indent="no" version="4.0" />
    
    <xsl:variable name="pi" select="3.141592653589793" />
    
    <xsl:template match="/circle">
        <html>
            <head>
                <title>XSLT Josephus' Circle</title>
                <style type="text/css">
    BODY { background-color: white; }
    DIV { border: 1px dashed black; }
    H1 { font: bold 1.2em sans-serif; color: black; text-align: center; }
    H2 { font: bold 1em sans-serif; color: black; text-align: center; }
    P { font: bold 1em monospace; text-align: center; }
    .d { color: red; }
    .a { color: green; }
    .copy { font: 0.7em sans-serif; text-align: center; }
                </style>
    
        </head>
        
        <body>
            <h1>Josephus' Circle</h1>
            <h2>
                <xsl:value-of select="soldiers" /> soldiers, skipping
                <xsl:value-of select="skip" /> at a time.
            </h2>
                        
            <xsl:choose>
                <xsl:when test="soldiers &lt; 2 or skip &lt; 1">
                    <p>More than one soldier and skip of more than zero, please.</p>
                </xsl:when>
                <xsl:otherwise>
                    <xsl:call-template name="josephus-circle-init">
                        <xsl:with-param name="string" select="'aa'" />
                    </xsl:call-template>
                </xsl:otherwise>
            </xsl:choose>
            
            <p class="copy">
                XSLT Josephus' Circle by Shadikka 2009<br />
                Coded for The Daily WTF Programming Praxis just for the sake of it.
            </p>
        </body>
    </html>
    

    </xsl:template>

    <xsl:template name="josephus-circle-init"> <xsl:param name="string" />

    <xsl:choose>
        <xsl:when test="string-length($string) = soldiers">
            <xsl:call-template name="josephus-circle">
                <xsl:with-param name="alive" select="$string" />
                <xsl:with-param name="pos" select="1" />
            </xsl:call-template>
        </xsl:when>
        <xsl:otherwise>
            <xsl:call-template name="josephus-circle-init">
                <xsl:with-param name="string" select="concat($string, 'a')" />
            </xsl:call-template>
        </xsl:otherwise>
    </xsl:choose>
    

    </xsl:template>

    <xsl:template name="josephus-circle"> <xsl:param name="alive" /> <xsl:param name="pos" />

    <xsl:choose>
        <xsl:when test="count(index-of(string-to-codepoints($alive), 97)) = 1">
            <p>The survivor is soldier #<xsl:value-of select="index-of(string-to-codepoints($alive), 97)" />.</p>
        </xsl:when>
        <xsl:otherwise>
            <xsl:call-template name="josephus-step">
                <xsl:with-param name="alive" select="$alive" />
                <xsl:with-param name="pos" select="$pos" />
                <xsl:with-param name="past" select="0" />
            </xsl:call-template>
        </xsl:otherwise>
    </xsl:choose>
    

    </xsl:template>

    <xsl:template name="josephus-step"> <xsl:param name="alive" /> <xsl:param name="pos" /> <xsl:param name="past" />

    <xsl:choose>
        <xsl:when test="$pos > soldiers">
            <xsl:call-template name="josephus-step">
                <xsl:with-param name="alive" select="$alive" />
                <xsl:with-param name="pos" select="1" />
                <xsl:with-param name="past" select="$past" />
            </xsl:call-template>
        </xsl:when>
        
        <xsl:when test="substring($alive, $pos, 1) = 'd'">
            <xsl:call-template name="josephus-step">
                <xsl:with-param name="alive" select="$alive" />
                <xsl:with-param name="pos" select="$pos+1" />
                <xsl:with-param name="past" select="$past" />
            </xsl:call-template>
        </xsl:when>
        
        <xsl:when test="$past = skip">
            <xsl:variable name="new_alive" select="concat(substring($alive, 1, $pos - 1), 'd', substring($alive, $pos + 1, string-length($alive)-$pos))" />
            <xsl:call-template name="josephus-draw">
                <xsl:with-param name="alive" select="$new_alive" />
                <xsl:with-param name="y" select="count(index-of(string-to-codepoints($alive), 100))" />
            </xsl:call-template>
            <xsl:call-template name="josephus-circle">
                <xsl:with-param name="alive" select="$new_alive" />
                <xsl:with-param name="pos" select="$pos" />
            </xsl:call-template>
        </xsl:when>
        
        <xsl:otherwise>
            <xsl:call-template name="josephus-step">
                <xsl:with-param name="alive" select="$alive" />
                <xsl:with-param name="pos" select="$pos + 1" />
                <xsl:with-param name="past" select="$past + 1" />
            </xsl:call-template>
        </xsl:otherwise>
    </xsl:choose>
    

    </xsl:template>

    <xsl:template name="josephus-draw"> <xsl:param name="alive" /> <xsl:param name="y" />

    <xsl:variable name="xpos" select="105 + (3*radius) * ($y mod 3)" />
    <xsl:variable name="ypos" select="floor($y div 3) * (3*radius) + radius + 100" />
    <xsl:element name="p">
        <xsl:attribute name="style">position:absolute;left:<xsl:value-of select="$xpos - 5" />px;top:<xsl:value-of select="$ypos" />px;</xsl:attribute>
        #<xsl:value-of select="$y + 1" />
    </xsl:element>
    <xsl:call-template name="josephus-draw-soldier">
        <xsl:with-param name="alive" select="$alive" />
        <xsl:with-param name="pos" select="1" />
        <xsl:with-param name="ypos" select="$ypos" />
        <xsl:with-param name="xpos" select="$xpos" />
        <xsl:with-param name="step" select="(2 * $pi) div string-length($alive)" />
    </xsl:call-template>
    

    </xsl:template>

    <xsl:template name="josephus-draw-soldier"> <xsl:param name="alive" /> <xsl:param name="pos" /> <xsl:param name="ypos" /> <xsl:param name="xpos" /> <xsl:param name="step" />

    <xsl:variable name="angle" select="($pos - 1) * $step" />
    <xsl:variable name="ypos2" select="round($ypos + math:sin($angle) * radius)" />
    <xsl:variable name="xpos2" select="round($xpos + math:cos($angle) * radius)" />
    <xsl:variable name="class" select="substring($alive, $pos, 1)" />
    
    <xsl:element name="p">
        <xsl:attribute name="class">
            <xsl:value-of select="$class" />
        </xsl:attribute>
        <xsl:attribute name="style">position:absolute;top:<xsl:value-of select="$ypos2" />px;left:<xsl:value-of select="$xpos2" />px;</xsl:attribute>
        <xsl:choose>
            <xsl:when test="$class = 'a'">
                <xsl:value-of select="$pos" />
            </xsl:when>
            <xsl:otherwise>X</xsl:otherwise>
        </xsl:choose>
    </xsl:element>
    
    <xsl:if test="$pos &lt; string-length($alive)">
        <xsl:call-template name="josephus-draw-soldier">
            <xsl:with-param name="alive" select="$alive" />
            <xsl:with-param name="pos" select="$pos + 1" />
            <xsl:with-param name="ypos" select="$ypos" />
            <xsl:with-param name="xpos" select="$xpos" />
            <xsl:with-param name="step" select="$step" />
        </xsl:call-template>
    </xsl:if>
    

    </xsl:template>

    </xsl:stylesheet>

    Addendum (2009-07-31 02:21): In light of the other XSLT solution, I might add that this is the brute-force solution. :)

  • John Stracke (unregistered) in reply to Scarlet Manuka
    <?xml version="1.0" encoding="UTF-8" standalone="no"?>
    <xsl:stylesheet version="1.0"
                    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                    xmlns="http://www.w3.org/2000/html">
    
      <xsl:template match="/many/j">
    
        <html>
          <head>
            <title>Josephus</title>
          </head>
          <body>
            

    Josephus

    <xsl:variable name="n"><xsl:value-of select="./@n"/></xsl:variable> <xsl:variable name="k"><xsl:value-of select="./@k"/></xsl:variable> <xsl:function name="j"> <xsl:param name="n"/> <xsl:param name="k"/> <xsl:choose> <xsl:when test="$n=1"> <xsl:sequence select="0"/> </xsl:when> <xsl:otherwise> <xsl:sequence select="(j($n-1,$k)+$k) mod $n"/> </xsl:otherwise> </xsl:choose> </xsl:function>

    <xsl:value-of select="$n"/>

    <xsl:value-of select="$k"/>

    <xsl:value-of select="j($n,$k)"/> </body> </html> </xsl:template> </xsl:stylesheet>
  • (cs)

    Brute Force C#

            static int JosephusFunc(int numOfSoldiers, int numToSkip)
            {
                ArrayList soldierCircle = new ArrayList();
    
                for (int i = 0; i < numOfSoldiers; i++)
                {
                    //Instanitates the ArrayList with index number
                    soldierCircle.Add(i);
                }
    
                //Since we're zero indexed start with this
                int soldierToDie = numToSkip-1;
    
                while (soldierCircle.Count > 1)
                {
                    //Since we'll be making multiple loops, we'll need to reset the death index
                    while (soldierToDie >= soldierCircle.Count)
                        soldierToDie -= soldierCircle.Count;
    
                    //Kills the soldier
                    soldierCircle.RemoveAt(soldierToDie);
    
                    //Subtracts one, since all soldiers move over a place
                    soldierToDie += numToSkip-1;
                }
    
                return (int) soldierCircle.ToArray()[0]+1;
            }
    
  • (cs)

    I haven't read through all the comments, but a search for Brainfuck on each page of comments didn't return anything, so I decided to give it a go.

    I haven't optimised the final code - I took Alex Mont's Python code, expanded the recursivity to a simple for-loop and proceeded to hack my way through in BF.

    Original Python:

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

    Port to C without recursivity:

    for (int i = 2; i <= n; ++i) {
      result += k;
      result %= i;
    }
    

    Finally, in Brainfuck: (result in memory cell 0, input in cells 1 and 2 (no. of men, kill-every)).

    >++++++++++     10 men
    >+++            kill every 3 places
    <[>>+>+<<<-]
    >>>[<<<+>>>-]
    <-[-
            <[<<+>>>>+<<-]
            >>[<<+>>-]
            <<<[>>>>+>+<<<<<-]
            >>>>>[<<<<<+>>>>>-]
            <<<[>+>>+<<<-]
            >>>[<<<+>>>-]
            <<[>-<-]
            <<<<[>>>>+<<<<-]
            >>>>[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
            [-]>[-]>>[-]
            <[<<<<<<+>>>>>>-]
            <<<
    ]
    The following is for output and can be ignored if running in a debugger
    <<[-]<
    ++++++++
    ++++++++
    ++++++++
    ++++++++
    ++++++++
    ++++++++
    .
    

    I couldn't find an atoi in Brainfuck, so I added the ordinal of ascii zero (48) and output, so it'll break if the result is >9. (for the reader's convenience, the sequence is 0123456789:;<=>?@ABC...)

  • Unknown Entity (unregistered)

    The trick to staying alive isn't knowing the safe spot... it's being the man with the axe.

  • Still Not Tim (unregistered) in reply to Unknown Entity
    Unknown Entity:
    The trick to staying alive isn't knowing the safe spot... it's being the man with the axe.
    and the way to do that in Python...

    is to be A LUMBERJACK

  • (cs)

    A somewhat juvenile Perl solution.

    #!/usr/bin/perl
    sub josephus {
                  ($m, $s) =  @_;
             @l=                    1..
         $m;                          $c=0;
      $n=$m;                            $k=1;
     while                                ($n>
     1){                                   do{
    $c=                                     ($c
    +1)%                                    $m}
    until                                    $l 
    [$c];                                 $k++;
    if                                      ($k
     ==                                    $s)
     {$k                                   =0;
      $l                                 [$c]
        =0;                              $n
          --;                          }}
              $c                    ++
                  until $l[$c];$c
    }
    $r = &josephus ( (@ARGV)[0,1] );
    print "$r\n";

    Addendum (2009-07-31 00:51): I should note. The program takes two arguments on the commandline - the first is the number of men, and the second is the number to skip each time. There's no checking on those, so if you give zero men, you'll get a divide by zero error (don't ask) and if you give zero skip size you'll get an infinite loop.

    It prints out a zero-indexed solution.

  • Roberto M (unregistered)

    A really random solution in Java.

    import java.util.*;
    
    public class Josephus {
    
      public static void main(String[] args) {
        System.out.println("The zero-based safe spot index is " + joephus(Integer.parseInt(args[0]), Integer.parseInt(args[1])));
      }
    
      public static int joephus(int numberOfSoldiers, int soldiersToSkip) {
        // prepare data
        Vector<String> soldiers = new Vector<String>(numberOfSoldiers);
        soldiers.setSize(numberOfSoldiers);
        Collections.fill(soldiers, "Soldier");
        soldiers.set(0, "Joephus");
        --soldiersToSkip;
    
        // random loop
        int position = 0;
        String last = null;
        do {
          Vector<String> testset = (Vector<String>) soldiers.clone();
          shuffle(testset);
          position = testset.indexOf("Joephus");
    
          // kill loop
          int soldierToKill = 0;
          while (testset.size() > 1) {
            soldierToKill += soldiersToSkip;
            while (soldierToKill >= testset.size()) {
              soldierToKill -= testset.size();
            }
            testset.remove(soldierToKill);
          }
          last = testset.get(0);
        }
        while(!last.equals("Joephus"));
    
        return position;
      }
    
      public static void shuffle(Vector<String> array) {
        Random rng = new Random();
        for (int n = array.size()-1; n > 0; n--) {
          int k = rng.nextInt(n + 1);
          String tmp = array.get(k);
          array.set(k, array.get(n));
          array.set(n, tmp);
        }
      }
    }
    
  • HV (unregistered)

    Haskell

    spot l n = red [1..l] n 
    red l n = if (length l) /=1 then red (del l n) n else l !! 0
    del l n = if (length l) >= n then drop n l ++ take (n-1) l else drop (length l) (del (l ++ l) n)
    
  • StinoFasto (unregistered)

    C# implementation:

    private int DoTheJosephusCircle(int numberOfSoldiers, int soldiersToSkip)
    {
        var theCircleOfDeath = new List<bool>();
        for (int i = 0; i < numberOfSoldiers; i++ ) theCircleOfDeath.Add(false);
    
        Shoot(theCircleOfDeath, 0, soldiersToSkip);
        return theCircleOfDeath.IndexOf(false);
    }
    
    private void Shoot(IList<bool> theCircleOfDeath, int startIndex, int soldiersToSkip)
    {
        int counter = 0;
        while (counter < soldiersToSkip)
        {
            if (!theCircleOfDeath[startIndex] && (++counter == soldiersToSkip))
            {
                theCircleOfDeath[startIndex] = true;
                break;
            }
            startIndex = (startIndex >= theCircleOfDeath.Count - 1) ? 0 : ++startIndex;
        }
        if (theCircleOfDeath.Count(soldier => !soldier) == 1) return;
        Shoot(theCircleOfDeath, startIndex, soldiersToSkip);
    }
    
  • (cs) in reply to ponky
    ponky:
    piet [image]

    First input is the number of soldiers. Second input is the number to skip. Output is the (zero based) index of the survivor.

    This is officially awesome. I thought of making a solution in Piet, but thought it'd be too tricky. It's good to be proven wrong, though.

  • gvainfo (unregistered)

    Bah, the rules are dizzy! Count of three means that I start to count at 1 and number 3 gets killed. In some examples you kill number 2 because you start to count at zero. Don't forget that in those times they did not have arrays yet and people started to count at 1. What I found particularly difficult was the "hop over the edge", alas what do you do when 10 are in the array and you need to count to 11?

    #!/usr/bin/perl -w strict my $group=$ARGV[0]; my $count=$ARGV[1]; print "$group people count to $count\n";

    Create an array

    my @circle; my $array_length; for ($i = 1 ; $i < $group+1 ; $i++) { $array_length=push (@circle,$i); } print "Starting circle: @circle\n"; my $victim=0; while (@circle > 1) { my $loop=0; my $nextvictim=($victim)+$count-1; while ($nextvictim >= @circle) {$nextvictim=$nextvictim-@circle;$loop++;} $victim=$nextvictim; print "Remove $victim ($circle[$victim]) from @circle "; if ($loop > 0) {print" (looped $loop times)"}; print "\n"; splice(@circle,$victim,1); } print "Number @circle survives\n";

    for 10/3 that gives me ./titus.pl 10 3 10 people count to 3 Starting circle: 1 2 3 4 5 6 7 8 9 10 Remove 2 (3) from 1 2 3 4 5 6 7 8 9 10 Remove 4 (6) from 1 2 4 5 6 7 8 9 10 Remove 6 (9) from 1 2 4 5 7 8 9 10 Remove 1 (2) from 1 2 4 5 7 8 10 (looped 1 times) Remove 3 (7) from 1 4 5 7 8 10 Remove 0 (1) from 1 4 5 8 10 (looped 1 times) Remove 2 (8) from 4 5 8 10 Remove 1 (5) from 4 5 10 (looped 1 times) Remove 1 (10) from 4 10 (looped 1 times) Number 4 survives

    and for 40/3 40 people count to 3 Starting circle: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Remove 2 (3) from 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 .. Remove 2 (32) from 13 28 32 Remove 0 (13) from 13 28 (looped 2 times) Number 28 survives

    I really don't know if that's correct as I only checked manually for small numbers. I tested though what happens if you put high numbers (40 people kill every 1.000.000 person: Stand in position 36)

    And now I will read the wikipedia article ;-)

  • Gerben (unregistered)

    public static int Josephus(int number, int skip) { return number == 1 ? 0 : (Josephus(number - 1, skip) + skip) % number; }

  • (cs) in reply to kastein
    kastein:
    Josephus:
    Last
    ... best "first" post ever. Code Dependent, eat your heart out! :P
    Dang!
  • Stéphane (unregistered)

    If you want to be REALLY FAST (in your head), here's an algorithm

    When you know a last spot for a given number if soldiers, Add 3 to the spot if you add one soldier. If your number is above the number of soldiers, just reduce it (ie: remove by the amount of people in the circle)

    ie: For 20 soldiers, the spot is 20 (easy to remember) Add 3, For 21 soldiers it should be 23, so you are over, substract 21 and you get 2 as the spot. Add 3, For 22 soldiers the spot is 5 Add 3, For 23 soldiers the spot is 8 ... Add 3, For Soldiers: 30 the spot is 29 Add 3, For 31 soldiers it should be 32, so you are over, substract 31 and you get 1 as the spot. ...

  • Louis (unregistered)

    Here's dc code implementing the 'obvious' algorithm (fill a stack with soldiers and delete them one by one:

    dc -e '12 3 1-s$ddsls#[dS~1-d0<s]dssxs.[l#dsll{xs.]sr[LtS~1-d0<{]s{[ll1-dslL~St0=r]sz[lzx1-d0<}]s}[l$l}xs.L~s.l#1-ds#ll1-dsl0=r1<m]dsmxL~p'</pre>
    

    and unobfuscated (well, as unobfuscated as dc can be):

    12 # number of soldiers
    3  # number to skip each round
    
    1-s$
    ddsls#
    
    [
      dS~
      1-
      d0
    

    And Alex Mont's J function (except de-recursion-ized):

    dc -e '12 3 sksm2sn0[lk+ln%ln1+dsnlm!<J]dsJx1+p'</pre>
    

    I adjusted it to output one-based instead of 0-based with the 3rd- and 2nd-to-last letters, the '1+'. You can save two characters by deleting those.

  • causa (unregistered)
    
    all_dead = [];
    
    class soldier:
        def __init__(self, previous,number,first):
    
            self.previous_soldier = previous;
            self.number = number;
            if first == 0 :
                first = self;
            
            if number == 0 :
                self.next_soldier = first;
                first.previous_soldier = self;
            else:
                self.next_soldier = soldier(self, number -1, first);
            
        def step(self, step, countdown):
            if self.next_soldier == self:
                print 'Suiciders, in order:', all_dead;
                print 'I can haz LIFE!', self.number;
                return;
            if countdown == 0 :
                self.previous_soldier.next_soldier = self.next_soldier;
                self.next_soldier.previous_soldier = self.previous_soldier;
                all_dead.append(self.number);
                self.next_soldier.step(step, step);
            else:
                self.next_soldier.step(step, countdown - 1);
                
    first_soldier = soldier(0,40,0);
    first_soldier.step(2, 2);
    

    Well, here's my try. I'm late to join the party, I know. But its friday night, and I had to do something while getting drunk for the pub. ;) And I figured that making a program in python for the first time would be a good way to spend the time.

    If someone feels like it, point out the bad stuff. Heh.

  • dbkk (unregistered) in reply to Dave

    God.getInstance().sortOut(soldiers);

    I disagree with using a singleton pattern here... after all, the story is set in Roman times.

    God.get("Mars").sortOut(soldiers);

    There, I corrected it for you.

  • quibus (unregistered) in reply to Wongo
    Wongo:
    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.
    bobtherriault@mac.com:
    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:

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

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

    When I was a kid, I could actually pick the last spot in circles to be singled out in these games. I cant remember how I did it, but it wasnt overly complicated. I think I counted the size of the circle up backwards from two, two numbers each step and then fixing at the end if it was an odd number of people.

  • (cs) in reply to causa

    Never; saw; so; many; semicolons; in; a; Python; program; :-) But if it's your first Python program that's OK.

  • causa (unregistered) in reply to mol1111
    mol1111:
    Never; saw; so; many; semicolons; in; a; Python; program; :-) But if it's your first Python program that's OK.

    Haha, being tipsy prolly didnt help me much either. >.<

  • John Stracke (unregistered) in reply to John Stracke
    John Stracke:
    <?xml version="1.0" encoding="UTF-8" standalone="no"?>

    ...no, that gives the wrong answer.

  • Dean Mitchell (unregistered)
    <?php if(empty($_GET)) { $body = '<html><head><title>Smarty Pants Josephus</title></heade>'; $body .= '<body><form method="GET" action="josephus.php" name="smarty">'; $body .= 'Number of Soldiers:<input name="number1" type="text" length="5">
    Soldiers to Skip:<input name="number2" type="text" length="5">
    '; $body .= '<input type="submit" action="submit" value="Calculate"></form></body></html>'; echo $body; } else { $amount = $_GET['number1']; $skip = $_GET['number2']; $soldiers = array_flip(range(1, $amount)); for($deathblow = 1; $soldiers[$deathblow] != end($soldiers); $deathblow++) { if((($deathblow + $skip) % $skip) != 0) array_push($soldiers, $soldiers[$deathblow]); } echo "Stand in spot ".(end($soldiers) + 1)." if you want to live!"; } ?>
  • Wongo (unregistered) in reply to Stéphane
    Stéphane:
    If you want to be REALLY FAST (in your head), here's an algorithm

    When you know a last spot for a given number if soldiers, Add 3 to the spot if you add one soldier. If your number is above the number of soldiers, just reduce it (ie: remove by the amount of people in the circle)

    ie: For 20 soldiers, the spot is 20 (easy to remember) Add 3, For 21 soldiers it should be 23, so you are over, substract 21 and you get 2 as the spot. Add 3, For 22 soldiers the spot is 5 Add 3, For 23 soldiers the spot is 8 ... Add 3, For Soldiers: 30 the spot is 29 Add 3, For 31 soldiers it should be 32, so you are over, substract 31 and you get 1 as the spot. ...

    Ok, I think you nailed it... Takes a few seconds, doesn't require any knowledge other than adding and subtracting, it's a great solution! Kudos, Stéphane! You win! :)

  • Andrew (unregistered)

    The goal of this is not to be clever, but to provide a solution in Perl that won't be recognized as being Perl. Here goes:

    #!/usr/bin/perl
    use MooseX::Declare;
    use Moose::Autobox;
    
    class Josephus {
      has size => (isa => 'Int', is => 'ro', required => 1);
      has stride => (isa => 'Int', is => 'ro', required => 1);
      has position => (isa => 'Int', is => 'rw', default => -1);
      has soldiers => (is => 'ro', isa => 'ArrayRef[Int]', lazy => 1,
        default => sub { [ (0 .. shift->size - 1) ] }
      );
    
      method move (Int $spaces) {
        $self->position(
          ($self->position + $spaces) % $self->soldiers->length
        );
      }
    
      method kill {
        splice @{ $self->soldiers }, $self->position, 1, ();
        # Killing that guy moved the cursor to the guy after him, but we want
        # $self->move(1) to land on the guy after him, so move back one.
        $self->move(-1);
      }
    
      method josephus {
        while ($self->soldiers->length > 1) {
          $self->move( $self->stride );
          $self->kill;
        }
        return $self->soldiers->[0];
      }
    }
    

    Invoke as

    $safe_pos = Josephus->new(size => 12, stride => 3)->josephus

  • (cs)

    Man,where is the Haskell love? Here's a quick hack.

    praxis :: Int -> Int -> Int praxis 1 k = 0 praxis n k = mod ((praxis (n-1) k)+k) n

    coward:: Int-> Int -> IO () coward n k = do c <- return (show ((praxis n k)+1)) putStrLn ("With "++show n++" soldiers and "++show k++"soldiers to skip, stay at position "++c)

    Addendum (2009-08-02 15:23): This is based on the previous Python solution.

    Addendum (2009-08-02 15:24): by Alex Mont.

  • naren (unregistered)

    javascript.

    function life_spot(circle_size, skip_by) {
     circle = new Array();
    
     for(i=1; i <= circle_size; i++)
      circle.push(i);
    
     while(circle.length > 1) {
       value = circle.shift();
       if(counter == skip_by)
         counter = 1;
       else {
         counter++;
         circle.push(value);
       }
     }
     alert(circle.shift());
    }
    
  • MF (unregistered) in reply to Dave
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    You're assuming God is a singleton ;)
  • (cs)

    Minski register machine: [image] Basic model of computation: you have named random-access registers and an FSM. An (x++) node increments register x and moves to its single successor. An (x--) node first checks whether register x is 0: if so, it moves to the double-arrow successor; otherwise it decrements register x and moves to the single-arrow successor.

    This machine takes input in n (number of soldiers) and k (advance) and gives output in r (zero-indexed). It is assumed that r, i, and t are all 0 before computation begins.

    The first two HALT nodes are error conditions (respectively k=0 and n=0).

    Addendum (2009-08-01 07:35): s/Minski/Minsky/ My apologies.

  • plaga (unregistered) in reply to MF
    MF:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    You're assuming God is a singleton ;)

    When, in fact, god is a simpleton. ;)

  • Josephus (unregistered) in reply to Dave
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    

    Assuming you only believe in one God... unfortunately this problem has been outsourced to India so this code is no good.

  • Chris Judge (unregistered) in reply to Observer
    Observer:
    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.

    1. It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

    2. I don't think this is an indication of the need for a "more unique problem to solve." I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

  • (cs)

    Several people were talking about how you could work this out in your head. Well I was thinking about this last night in bed and here is what I was able to come up with:

    In your mind split the 41 people up into rows containing 9 soldiers each. This will give you 4 rows of 9 and one row at the end with 5.

    One the first round of killing you will lose columns 3, 6 and 9. Two soldiers remain after the last killing (columns 4 and 5) so on the second run through columns 1 and 5 will be taken out. This leaves you with columns 2478 (remember this number!) and 18 soldiers still alive.

    Again divide these soliders into 9 columns (which gives you exactly two rows). On the previous run we killed off column 5 last so we will lose columns 3, 6 and 9 again, followed by 4 and 8. This leaves columns 1257 (remember this number) and 8 soldiers still alive.

    It is trivial at this stage to work out that the safe spot out of these 8 is position 7 (you may be able to do this visually in your mind, or if you have to, resort to using fingers. Remember the first to die is the 3rd one as we killed off the last guy in the previous round).

    We know that the safe position is number 7, but this is from the final 8 soldiers. We need to move back up the grids and work out what the real position is. Thankfully this is easy. The number of surviving columns each time was 4, so see how many 4s you can get into 7, this tells you how many rows to skip, then the remainder is the index of the safe column (from the numbers you remembered).

    So:

    7 = 4 + 3 Down one row, 3rd safe column (from 1257) so column 5.

    9 soldiers per row so safe position is (9 * 1) + 5 = 14

    14 = 4 + 4 + 4 + 2 Down three rows, 2nd safe column (from 2478) so column 4 9 soldiers per row so safe position is (9 * 3) + 4 = 31

    So there is your final answer, you need to be standing in position 31. And all you had to remember was two four digit numbers and who was first to die between stages.

  • (cs) in reply to Chris Judge
    Chris Judge:
    I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.
    Copy-pasting code from Wikipedia is sad, but when you talk about "solving the problem" I find myself disagreeing with you about the point. Programming Praxis was launched as an opportunity "to sharpen your programming skills", not your problem-solving skills. More power to the people who transform it into a tail-recursive solution.

    (It's also being used for language one-upmanship, but that's just the TDWTF crowd for you.)

  • (cs) in reply to MF
    MF:
    Dave:
    foreach(soldier:soldiers){
     soldier.kill();
    }
    God.getInstance().sortOut(soldiers);
    
    You're assuming God is a singleton ;)

    This is what the singleton is meant for.

    If you have code all over your program like this:

    god = God.getInstance(); god.sortOut(theDead); god.createHeavens(); // etc.

    Then you only have to update 1 line of code rather than all of them, like you would with a static class.

    God.sortOut(theDead); God.createHeavens(); // etc.

  • Brian Hartvigsen (unregistered)

    I always remember being told that you would feel more connected with things if you named them, so I made sure each soldier had a name (I have both Jewish and Roman name lists now, number 31 is Josephus in both.)

    import sys
    
    names = []
    with open("names2.lst") as f:
        names = f.readlines()
    
    class Soldier(object):
        def __init__(self, idx, name, next_soldier = None, prev_soldier = None):
            self.__next = next_soldier
            self.__prev = prev_soldier
            self.__idx = idx
            self.__name = name
    
        def __str__(self): return self.__name
    
        def get_next(self): return self.__next
        def set_next(self, next_soldier): self.__next = next_soldier
        next = property(get_next, set_next)
    
        def get_prev(self): return self.__prev
        def set_prev(self, prev_soldier): self.__prev = prev_soldier
        prev = property(get_prev, set_prev)
    
        @property
        def index(self): return self.__idx
    
        def die(self):
            self.prev.next = self.next
            self.next.prev = self.prev
            return self.next
    
        
    def Josephus(number_of_soldiers=12, soldiers_to_skip=3, deaths=False):
        root_soldier = None
        node_soldier = None
        
        for i in range(number_of_soldiers):
            next_soldier = Soldier(i, names[i].strip())
            if root_soldier == None:
                root_soldier = next_soldier
            else:
                node_soldier.next = next_soldier
                next_soldier.prev = node_soldier
                
            node_soldier = next_soldier
            
        root_soldier.prev = node_soldier
        node_soldier.next = root_soldier
        node_soldier = None
    
        sformat = "[#%%0%dd] %%s %%s" % len((str)(number_of_soldiers))
        while root_soldier.next != root_soldier:
            for i in range(soldiers_to_skip-1):
                root_soldier = root_soldier.next
                
            root_soldier.die()
    
            if deaths: print sformat % (root_soldier.index + 1, 'DIES', root_soldier)
            root_soldier = root_soldier.next
    
        if deaths: print sformat % (root_soldier.index + 1, 'LIVES', root_soldier)
        else:
            print "With %d soldiers skipping %d, stand in position %d" % (number_of_soldiers, soldiers_to_skip, root_soldier.index + 1)
    
    
    if __name__ == "__main__":
        argc = len(sys.argv)
        if argc == 3:
            Josephus((int)(sys.argv[1]), (int)(sys.argv[2]))
        elif argc == 2:
            Josephus((int)(sys.argv[1]))
        else:
            Josephus()
    

    Example output:

    >>> Josephus(41, 3, True)
    [#03] DIES Mordechai
    [#06] DIES Liron
    [#09] DIES Yosef
    [#12] DIES Sheraga
    [#15] DIES Eliezer
    [#18] DIES Gideon
    [#21] DIES Itamar
    [#24] DIES Efraim
    [#27] DIES Yaakov
    [#30] DIES Yitzhak
    [#33] DIES Avram
    [#36] DIES Hevel
    [#39] DIES Hayyim
    [#01] DIES Lev
    [#05] DIES Ron
    [#10] DIES Rotem
    [#14] DIES Elkan
    [#19] DIES Yochanan
    [#23] DIES Ofra
    [#28] DIES Aryeh
    [#32] DIES Yishai
    [#37] DIES Moss
    [#41] DIES Akiba
    [#07] DIES Adi
    [#13] DIES Nir
    [#20] DIES Tovia
    [#26] DIES Lior
    [#34] DIES Eyal
    [#40] DIES Amir
    [#08] DIES Lavi
    [#17] DIES Roi
    [#29] DIES Avi
    [#38] DIES Immanuel
    [#11] DIES Gil
    [#25] DIES Noach
    [#02] DIES Solly
    [#22] DIES Aharon
    [#04] DIES Abraham
    [#35] DIES Asher
    [#16] DIES Itzhak
    [#31] LIVES Josephus
    
    >>> Josephus(41,3)
    With 41 soldiers skipping 3, stand in position 31
    
  • amet (unregistered) in reply to Chris Judge
    Chris Judge:
    Observer:
    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.

    1. It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

    2. I don't think this is an indication of the need for a "more unique problem to solve." I think it's just a sign that there are many, many losers who value posting the "right" solution first over actually solving the problem on their own.

    Part of being a good programmer is to know that you are not the best at everything and finding solutions done by someone better at it than you. And then implementing it in code.

    The only thing wrong I see with digging the solution up on wikipedia is that there were no credits. I think you should always credit the guy or place you got the solution from.

  • Indrora (unregistered)
    static int ohgod(int notme/*obfustications*/,int pleasenotme/*they make me happy*/){/*but only when and */if/*its*/(notme/*reading them*/==1){return(0)/*,*/;}else{/*things go bad,*/return/*ing*/((/*to*/ohgod(/*,*/notme--/*, oh,*/,pleasenotme)/*dear programmer,*/+pleasenotme)/*let anyone read this but please,*/%notme);}/*. :)*/}

    My C# implementation, with the aformentioned recursion, but with as much /obfustication/ that if you read it right is a little poem to the reader.

    and no, there are no unnecesary spaces within this.

    I'm a little rusty on my lisp but I think the LISP version would be:

    (defun j(n,s) (if(= n 1) 0 ( % ( + j( ( - n 1 ) , s) n )s)))
    

    ... Just my two cents

  • Kogle (unregistered)

    Brute C# solution

    static int Josephus(int soldiers, int index)
            {
                //status of the soldiers, true means dead.
                bool[] soldierStatus = new bool[soldiers];
                int last = 0, deadSoldiers = 0;
                //iterate while more than one is alive
                for (int i = 0, counter = 0; deadSoldiers + 1 < soldiers; i = (i + 1) % soldiers)
                {
                    if (soldierStatus[i]) /* If this soldier is dead, skip loop */
                        continue;
                    if (counter == 2) /* If this soldier is the third, kill him */
                    {
                        soldierStatus[i] = true;
                        deadSoldiers++;
                    }
                    else /* If we don't kill him, he might be the last man standing */
                        last = i;
                    counter = (counter + 1) % 3;
                }
                return last + index;
            }
    
  • greyfade (unregistered) in reply to HypocriteWorld
    HypocriteWorld:
    Ha, now we have a way to stop people from posting "Frist!!1". Anyways, random solution here
    josepheus total skip =
      head $ head $ dropWhile notDone $ iterate go (cycle [1..total])
        where go xs = let y:ys = drop (skip - 1) xs in filter (/=y) ys
              notDone (x1:x2:_) = x1 /= x2
    
    A shorter version:
    josephus num sk = let gr = [1..num]
                          iter _ (x:[]) = [x]
                          iter n (x:xs) = if n == sk
                                          then iter 1 xs
                                          else iter (n+1) $ xs ++ [x]
                      in head iter 1 gr
    
    Do I get a cookie? :)
  • (cs) in reply to Code Dependent
    Code Dependent:
    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...

    Your socks and shirts are ful of God?

  • Paul Zaczkiewicz (unregistered)

    Some perl:

    #!/bin/perl
    
    use strict;
    use integer;
    
    if (@ARGV < 2) {
        print "Usage: $0 [number of soldiers] [soldiers to skip]\n";
        return 1;
    }
    
    if ($ARGV[0] <2) {
        print "You must have more than 1 soldier!\n";
        return 1;
    }
    
    print circle($ARGV[0], $ARGV[1], 0), "\n";
    
    sub circle
    {
        my ($size, $mod, $offset) = @_;
        if ($size <= 2) {
    	return ($mod+$offset)%2+1;
        }
        my $kills = ($size+$offset)/$mod;
        my $safe = circle($size-$kills, $mod, ($size+$offset)%$mod);
        return $safe + ($safe+$offset-1)/($mod-1);
    }
    
  • Manu (unregistered)

    If someone hasn't figured it out, yet, there is a simple pattern to it, if you read the list at http://thedailywtf.com/Comments/Programming-Praxis-Josephus-Circle.aspx#280029

    you can see that with each increasing number of soldiers, the safe spot rises once by the kill factor. if the number is bigger than the current amount of people, simply continue from the bottom, again.

    quick C# Implementation:

    public static uint Josephus(uint n, uint k) { uint safespot = 1;

    for (int numbers = 1; numbers <= n; numbers++)
    {
        safespot += 3;
        while (safespot > numbers)
        {
            safespot -= numbers;
        }
    }
    
    return safespot;
    

    }

    Also, this will still need a bit of brainpower to do in the head, but better than any modulo or recursive calls out there.

  • Manu (unregistered) in reply to Manu

    Damn. Forgot BBCodes, also forgot to set 3 to k. fix:

    public static uint Josephus(uint n, uint k)
    {
        uint safespot = 1;
    
        for (int numbers = 1; numbers <= n; numbers++)
        {
            safespot += k;
            while (safespot > numbers)
            {
                safespot -= numbers;
            }
        }
    
        return safespot;
    }
  • 14mWtF (unregistered)

    most of the solutions are wtfs...

    josephus needs to be the 40th man

  • inky (unregistered)

    Quick Python solution:

    def josephus(count=40, skip=3):
        assert count > 1
        soldiers = [i and str(i+1) or 'top' for i in range(count)]
        alive, index = count, 0
        while soldiers[1:]:
            print(', '.join(soldiers))
            i = (index + skip - 1) % len(soldiers)
            soldiers.pop(i)
            index = i
        return soldiers[0]
    >>> print(josephus())
    top, 2, 3, 4, 5, ..., 37, 38, 39, 40
    top, 2, 4, 5, ..., 37, 38, 39, 40
    ...
    top, 13, 19, 28, 32
    top, 13, 28, 32
    13, 28, 32
    13, 28
    28
  • Paul N (unregistered) in reply to dbkk
    dbkk:
    > God.getInstance().sortOut(soldiers);

    I disagree with using a singleton pattern here... after all, the story is set in Roman times.

    God.get("Mars").sortOut(soldiers);

    There, I corrected it for you.

    Your modification throws the error: "Object reference not set to an instance of an object."

    The story is about the Jews who do not follow the Roman gods, but do follow a Singleton God.

Leave a comment on “Josephus' Circle”

Log In or post as a guest

Replying to comment #:

« Return to Article