4
\$\begingroup\$

I'm totally hooked on CodeEval, and one of the problems on there caught my attention. Here it is, copied from here:

Challenge Description:

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 soldiers surrounded by Romans. Preferring death to capture, the Jews decided to form a circle and, proceeding around it, to kill every j'th person remaining until no one was left. Josephus found the safe spot in the circle and thus stayed alive.Write a program that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed. Input sample:

Your program should accept as its first argument a path to a filename. Each line in this file contains two comma separated positive integers n and m , where n is the number of people and every m'th person will be executed. e.g.

10,3
5,2

Output sample:

Print out the list of n people(space delimited) in the order in which they will be executed. e.g.

2 5 8 1 6 0 7 4 9 3
1 3 0 4 2

Here's my solution in JavaScript, which succeeded in all test cases:

var fs  = require("fs"); //object for reading in a file
fs.readFileSync(process.argv[2]).toString().split('\n').forEach(function (line) {
    if (line != "") {
        var lineSplit = line.split(",");
        var maxNum = parseInt(lineSplit[0], 10); //the number of people in the circle (n)
        var spacer = parseInt(lineSplit[1], 10); //Every m'th person is executed
        var counter = spacer - 1; //We're working with a zero-based array, so decrement accordingly
        var people = [];
        var deadPeople = [];
        for (var i = 0; i < maxNum; i++) {
            var person = [];
            person = new Array(i.toString(), 1);
            people[i] = person; //a new person is added with a status of 1 (alive)
        }

        while(deadPeople.length < maxNum){
            people[counter][1] = 0; //sadness
            deadPeople.push(people[counter][0]);
            counter += spacer;
            while(people.length > 0 && counter >= people.length){
                counter = counter - people.length;
                regroup(people);
            }
        }

        console.log(deadPeople.join(" "));
    }
});

function regroup(arr) {
    arr.forEach(function(element, index, array) {
        if (element[1] === 0) {
            array.splice(index, 1);
        }
    });
}

All comments are welcome, but I'm especially interested in efficiency.

\$\endgroup\$

3 Answers 3

Reset to default
9
\$\begingroup\$

  1. You can easily find the next death-index with the modulus operation: next = (current + space) % totalStillAlive . No need for fancy loops (see end of answer).

  2. Instead of making an array of arrays (btw, don't create js arrays with new Array, use the array literal []), simply store an array of original indexes, and splice from that on each around until there are no more people left.

  3. The way you're extracting the data is awkward, specifically the spacer definition - why not define it right off the bat as parseInt(...) - 1 ?

  4. It's probably not very important with this input size, but the synchronous line reading is frowned upon; you should use the asynchronous versions unless there's a reason not to.

  5. if (line != "") can just be if (line)

  6. With #1 you don't need regroup, but your forEach loop is an implementation filter (docs)

(as a continuation of #2:

var person = [];
person = new Array(i.toString(), 1);

I don't get what went through your mind at the time, but why not just people[i] = [i, 1] ?)

So, your main algorithm can be simplified to 1 nice loop instead of 3 (discounting the instantiation loop):

function josephus (n, interval) {
    var people = [],
        deaths = [];
    for (var i = 0; i < n; i += 1) {
        people[i] = i;
    }

    var idx = 0,
        len = people.length;
    while (len = people.length) {
        idx = (idx + interval) % len;
        deaths.push(people[idx]);
        people.splice(idx, 1);
    }

    return deaths;
}
\$\endgroup\$
0
3
\$\begingroup\$ 
function josephus(n, interval) {
    return (n > 1 ? (josephus(n - 1, interval) + interval - 1)%n + 1 : 1)
}

It iterates n times.

\$\endgroup\$
1
  • \$\begingroup\$ The problem with this is that you can easily run into recursion limits with fairly low numbers (mid thousands). It may be better to switch to an iterative approach. var f=1; for(let i=1;i<=n;i++) f= (f+k-1)%i+1;return f; \$\endgroup\$ Commented Oct 30, 2016 at 4:21
1
\$\begingroup\$

It's simpler to write an iterative solution.

A recurrence relation is required to rotate/calculate new positions after each execution, but we can use a queue to take care of the positions.

Like this:

function josIterative(n, k) {
let queue = [];
for (let i = 1; i <= n; i++) queue.push(i);

let deathOrder = [];

while (queue.length !== 1) {
    for (let skip = 1; skip < k; skip++) queue.push(queue.shift());
    deathOrder.push(queue.shift());
}

console.log("Death order is " + deathOrder.join(" "));
return queue[0]; //survivor
}

console.log(josIterative(7, 3) + " is survivor");
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your answer should provide a more in-depth explanation. \$\endgroup\$ Commented Feb 20, 2020 at 13:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.