patternjavascriptMinor
The Josephus problem in JavaScript
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.
Output sample:
Print out the list of n people(space delimited) in the order in which they will be executed. e.g.
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
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,2Output 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 2Here'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:
-
Instead of making an array of arrays (btw, don't create js arrays with
-
The way you're extracting the data is awkward, specifically the
-
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.
-
-
With #1 you don't need
(as a continuation of #2:
I don't get what went through your mind at the time, but why not just
So, your main algorithm can be simplified to 1 nice loop instead of 3 (discounting the instantiation loop):
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.