Josephus

RaspenJho · 2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

Shadikka · 2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

JettingSpike · 2009-07-30 Reply Admin

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

Mathias Rav · 2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

2009-07-30 Reply Admin

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

curtmack · 2009-07-31 Reply Admin

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.

2009-07-31 Reply Admin

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

2009-07-31 Reply Admin

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)

2009-07-31 Reply Admin

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

Shadikka · 2009-07-31 Reply Admin

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.

2009-07-31 Reply Admin

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

2009-07-31 Reply Admin

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

Code Dependent · 2009-07-31 Reply Admin

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

Dang!

2009-07-31 Reply Admin

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

2009-07-31 Reply Admin

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.

2009-07-31 Reply Admin


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.

2009-07-31 Reply Admin

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.

2009-07-31 Reply Admin

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.

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

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.

mol1111 · 2009-07-31 Reply Admin

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

2009-07-31 Reply Admin

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

2009-07-31 Reply Admin

John Stracke:

<?xml version="1.0" encoding="UTF-8" standalone="no"?>

...no, that gives the wrong answer.

2009-07-31 Reply Admin

<?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!"; } ?>

2009-07-31 Reply Admin

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

2009-08-01 Reply Admin

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

the_duke · 2009-08-01 Reply Admin

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.

2009-08-01 Reply Admin

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

2009-08-01 Reply Admin

Dave:

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

You're assuming God is a singleton ;)

pjt33 · 2009-08-01 Reply Admin

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.

2009-08-01 Reply Admin

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

2009-08-01 Reply Admin

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.

2009-08-01 Reply Admin

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.

It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.
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.

Mithious · 2009-08-01 Reply Admin

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.

pjt33 · 2009-08-01 Reply Admin

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

savar · 2009-08-02 Reply Admin

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.

2009-08-02 Reply Admin

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

2009-08-02 Reply Admin

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.
It's sad, the people who simply looked it up on Wikipedia or elsewhere didn't even bother to change the variable names.

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.

2009-08-02 Reply Admin

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

2009-08-02 Reply Admin

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

2009-08-02 Reply Admin

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

death · 2009-08-03 Reply Admin

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?

2009-08-03 Reply Admin

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

2009-08-03 Reply Admin

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.

2009-08-03 Reply Admin

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

2009-08-03 Reply Admin

most of the solutions are wtfs...

josephus needs to be the 40th man

2009-08-03 Reply Admin

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

2009-08-03 Reply Admin

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.

Josephus' Circle

Josephus

Create an array

Leave a comment on “Josephus' Circle”