JavaScript中的约瑟夫斯问题

Question

我完全迷上了CodeEval，其中一个问题引起了我的注意。这里是从这里复制的：

挑战说明：

弗拉维乌斯·约瑟夫斯( Flavius )是第一世纪著名的犹太历史学家，当时第二神庙被毁。根据传说，在犹太罗马战争期间，他被困在一个洞穴里，一群士兵被罗马人包围。犹太人宁愿死也不想抓，于是决定围成一个圆圈，绕着它走下去，杀死剩下的每一个人，直到没有人留下为止。约瑟夫斯在圆圈中找到了安全的位置，因此保留了一个alive.Write程序，该程序返回n个人的列表，编号从0到n-1，按执行顺序排列。输入样本：

您的程序应该接受文件名的路径作为其第一个参数。该文件中的每一行包含两个逗号分隔的正整数n和m，其中n是人数，每m个人都将被执行。例如：

10,3
5,2

输出样本：

按照执行的顺序打印n个人的列表(分隔的空格)。例如：

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

下面是我在JavaScript中的解决方案，它在所有测试用例中都成功了：

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

欢迎所有的评论，但我对效率特别感兴趣。

Answer 1

1. 您可以很容易地找到下一个使用模运算的死亡索引：next = (current + space) % totalStillAlive。不需要花哨的循环(见答案的结尾)。
2. 不要创建数组数组(顺便说一句，不要用new Array创建js数组，使用数组文本[])，只需存储一个原始索引数组，然后从每个数组中拼接，直到没有更多的人。
3. 提取数据的方式很尴尬，特别是spacer定义--为什么不立即将其定义为parseInt(...) - 1呢？
4. 对于这个输入大小，它可能不是很重要，但是同步行读取是不允许的；除非有理由不使用异步版本，否则您应该使用异步版本。
5. if (line != "")可以是if (line)
6. 使用#1，您不需要regroup，但是您的forEach循环是一个实现filter (文档)

(作为第2条的延续：

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

我不明白你当时在想什么，但为什么不只是people[i] = [i, 1]呢?)

因此，您的主要算法可以简化为1 nice循环，而不是3(折扣实例化循环)：

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

Answer 2

function josephus(n, interval) {
    return (n > 1 ? (josephus(n - 1, interval) + interval - 1)%n + 1 : 1)
}

它迭代n次。

Answer 3

编写迭代解决方案比较简单。

每次执行后，需要循环/计算新的位置，但是我们可以使用队列来处理这些位置。

如下所示：

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");