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?
Programming Praxis 
You can find my solution here
http://pastebin.com/f7fd2a526
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]][…] For the correct Haskell solution check the first comment on the challenge page. […]
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)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]);
}
Ok i fail at posting. Not sure how to do the code block thingy. Copy pasting lost some of my code.
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
My variant using Python lambda’s and list slices:
http://pastebin.com/pVgE9hF2
https://github.com/gcapell/ProgrammingPraxis/blob/master/05_ringlist/ring.go
Scheme solution that makes use of circular lists:
http://pastebin.com/faTX0j6q
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) }in coffeescript:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
gistfile1.txt
hosted with ❤ by GitHub
[…] 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 […]
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.
Solution using Clojure. Very slow, but correct.
(defn rotate [n coll] (let [c (count coll)] (take c (drop (mod n c) (cycle coll))))) (defn execute [m ps dead] (if (< (count ps) m) (reverse (concat (reverse ps) dead)) (let [executed (nth ps (dec m)) alive (take (dec m) ps) rest (drop m ps) newalive (rotate (dec m) (concat alive rest)) newdead (cons executed dead)] (execute m newalive newdead (dec limit))))) (defn josephus [n m] (let [people (range 0 n)] (execute m people '())))Rust version
/* Author Bill Wood Order N "killed" people are tracked using a vec, where each entry contains the index of the next "living" person, and is updated to bypass each person who is "killed" */ struct Josephus { people: Vec<usize>, m: usize, current: usize, count: usize, } impl Iterator for Josephus { type Item = usize; fn next(&mut self) -> Option<Self::Item> { if self.count == 0 { return None } let mut prev = self.current; for _i in 0..self.m { prev = self.current; self.current = self.people[self.current]; } self.count -= 1; self.people[prev] = self.people[self.current]; Some(self.current) } } impl Josephus { fn new(size: usize, m: usize) -> Self { let mut j = Josephus{ count: size, m: m, current: size - 1, people: vec!() }; for i in 0..size - 1 { j.people.push(i + 1); } j.people.push(0); j } } fn main() { let mut x = Josephus::new(41, 3).peekable(); while let Some(p) = x.next() { if x.peek().is_none() { println!("\nfinal position = {}", p) } else { print!("{} ", p); } } }Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1cf29532b1f6ff85b5afd189cebb8ec3
If we are doing old problems, here’s a neat recursive solution in Python (not the most efficient being n^2, we can use a similar trick to find the final position in linear time though).
def josephus(m,k): if m == 1: return [0] else: return [k-1] + [(k+i)%m for i in josephus(m-1,k)] print(josephus(41,3)) # [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, # 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, # 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 34, 30]Oops, should have checked that more carefully (note repeated 34 in “solution” there). I hope this is right:
def josephus(m,k): if m == 1: return [0] else: return [(k-1)%m] + [(k+i)%m for i in josephus(m-1,k)]We should be able to define a similar but more complex recurrence that takes a complete trip around the remaining circle at each step.
[…] can read a fuller explanation at my blog, which gives three different solutions. Or you can run the program at […]