HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMinor

The Josephus problem in JavaScript

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
josephusproblemthejavascript

Problem

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 0 && counter >= people.length){
counter = counter - people.length;
regroup(people);
}
}

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

function regroup(arr) {
arr.forEach(function(e

Solution

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

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

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

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

-
if (line != "") can just be if (line)

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

Code Snippets

var person = [];
person = new Array(i.toString(), 1);
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;
}

Context

StackExchange Code Review Q#25230, answer score: 9

Revisions (0)

No revisions yet.