Flavius Josephus

February 19, 2009

Flavius Josephus was a famous Jewish historian of the first century, at the time of the destruction of the Second Temple. According to legend, during the Jewish-Roman war he was trapped in a cave with a group of forty soldiers surrounded by Romans. Preferring death to capture, the Jews decided to form a circle and, proceeding around it, to kill every third person remaining until no one was left. Josephus found the safe spot in the circle and thus stayed alive.

Write a function josephus(n,m) that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list. What is the value of josephus(41,3)? In what position did Josephus survive?

About these ads

Pages: 1 2

14 Responses to “Flavius Josephus”

  1. Sasha B said

    Depending on your interpretation of “every third person”, this question could be done a few different ways.

    def josephus(n, m):
        """Returns a list of n people, numbered from 0 to n - 1,
        in the order in which they are executed (every mth person
        in turn). The sole surviver is the last person in the list.
        >>> josephus(40, 3) # Kill every 3rd person
        """
    
        people = range(n)
        current = m - 1
        executions = []
        while len(people) > 1:
            executions.append(people.pop(current))
            current += m - 1 # Advance m people
            current = current % len(people) # In case we go past the first person
        return executions + [people[0]]
    
  2. [...] For the correct Haskell solution check the first comment on the challenge page. [...]

  3. kawas said

    I’ve tried two clojure versions : one using modulus, filtering “alive” vector and an other using the trick of the front and back queue.
    Both functions have the same size but the second one is clearly an order of magnitude faster.
    Seems like modulus and filtering entire vector are expensive compared to only playing with head, tail and last element of front & back vectors :)

    (defn josephus [n m]
      (loop [idx m front (range n) back [] dead []]
        (cond
          (and (empty? front) (empty? back)) dead
          (empty? front) (recur idx back [] dead)
          (= idx 1) (recur m (next front) back (conj dead (first front)))
          :else (recur (dec idx) (next front) (conj back (first front)) dead))))
    
    (josephus 41 3)
    
  4. Alex said

    My solution using C
    void josephus ( int n, int m)
    {
    int i, j, kill = m – 1;
    int reset = 0;
    int circle[n], killOrder[n];

    for (i = 0; i < n; i++)
    circle[i] = i;

    for ( i = 0; i < n; i++)
    {
    killOrder[i] = kill;
    circle[kill] = -1;
    for ( j = 0; j n – 1)
    {
    kill = 0;
    }
    while (circle[kill] == -1)
    kill++;
    }

    }

    for (i = 0; i < n; i++)
    printf("%d\t%d \n", i, killOrder[i]);

    }

  5. Alex said

    Ok i fail at posting. Not sure how to do the code block thingy. Copy pasting lost some of my code.

  6. Alex said

    OK.. sorry about the triple post… I read the HOWTO post source code section.

    And here is my solution using C:

    http://pastebin.com/T08Jpj7G

  7. My variant using Python lambda’s and list slices:

    http://pastebin.com/pVgE9hF2

  8. Yuri said

    Scheme solution that makes use of circular lists:

    http://pastebin.com/faTX0j6q

  9. j0sejuan said

    golang

    package main
    
    import (
    	"fmt"
    	"container/ring"
    )
    
    func josephus(N, k int) {
    	r := ring.New(N)
    	for n := 0; n < N; n++ {
    		r.Value = n
    		r.Next()
    	}
    	for r.Len() > 1 {
    		fmt.Printf("%d killed\n", r.Value.(int))
    		r.Unlink(1)
    		r.Move(k)
    	}
    }
    
    func main() {
    	josephus(41, 3)
    }
    
  10. kevin galkov said

    in coffeescript:

  11. [...] is another one taken from Programming Praxis #5 – Flavius Josephus, has a historical background which can be found here. For this exercise, write a function that [...]

  12. Eleanore said

    She said thewy often see people at seo keyword research tool the worst point in their careers.
    ”In the UK we already have the tension and pressure seo
    keyword research tool they can collect. The online programs in psychology seo keyword research
    tool to teach it! The parents of teenagers under the age of 80 Baroness Bakewell better
    known as broadcaster Joan Bakewell faces a fight much closer to home.
    Skye is not interested in the issue of same-sex attraction than my male patients.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: