# JavaScript circular linked list compatriot game

I found this question in O'Reilly Data Structure and Algorithm in Javascript:

According to legend, the first-century Jewish historian Flavius Josephus was about to be captured along with a band of 40 compatriots by Roman soldiers during the Jewish-Roman War. The Jewish soldiers decided that they preferred suicide to being captured and devised a plan for their demise. They were to form a circle and kill every third soldier until they were all dead. Josephus and one other decided they wanted no part of this and quickly calculated where they needed to place themselves so they would be the last survivors.

Write a program that allows you to place n people in a circle and specify that every mth person will be killed. The program should determine the number of the last two people left in the circle. Use a circularly linked list to solve the problem.

This is my solution:

function Node(element) {
this.element = element;
this.next = null;
}

function LList() {
this.find = find;
this.insert = insert;
this.display = display;
this.findPrevious = findPrevious;
this.remove = remove;
this.count = count;
}

function remove(item) {
var prevNode = this.findPrevious(item);
prevNode.next = prevNode.next.next;
}
}
function findPrevious(item) {
(currNode.next.element != item)) {
currNode = currNode.next;
}
return currNode;
}
function display() {
print(currNode.next.element);
currNode = currNode.next;
}
}
function count() {
var count = 0;
count++
currNode = currNode.next;
}
return count;
}
function find(item) {
while (currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}

var currNode = this.find(item);
for (let i = n; i > 0; i--) {
currNode = currNode.next;
}
return currNode;
}

function survivor(number, position) {
//40 compatriots
//kill every third soldier. advance by 3
//last two survivors

//place n people in a circle
var compatroits = new LList();

for (let i = 1; i <= number; i++) {
compatroits.insert(i, currNode.element);
currNode = currNode.next;
}

//kill every mth person in the circle
while (compatroits.count() > 2) {

//set new start point to m.next node
currItem = killNode.next.element;

//remove mth person
compatroits.remove(killNode.element);
}

//determine the last two people in the circle
return compatroits.display();
}


Does anyone have a more efficient way to solve this problem?

# The Ouroboros

The most obvious improvement is to remove the functions find, findPreviouse, and count

## Why

• Rather than hold the data each list item has, hold the current link. This means you dont need to find the item each time you move along the list
• You can know the remaining number of links by counting each link removed so there is no need for the function count.
• If you remove the next link in the sequence rather than the current you don't need to find the previous link as you already have that, thus you dont need findPreviouse.

## Some more points

• When doing a simple countdown use a while loop. eg while (n--) { is much simpler than for (let i = n; i > 0; i--) {
• Don't test for conditions if there is no need. In remove you have if (!(prevNode.next == this.head)) { which I can not work out why you have it there. Also it should have been written as if (prevNode.next !== this.head) {
• You should use const when ever possible, only if the variable has to change should you use var or let
• Always use === or !== never use == or !=
• If you are defining a object use the prototype or define the properties as an object. Creating a list of unrelated function names and then adding them to the object at creation is a mess, a source of bugs from the inevitable naming conflicts.

eg

function LList() {
}
LList.prototype = {
remove(item) {
// function body
},
findPrevious(item) {
// function body
},
display() {
// function body
},
count() {
// function body
},
// and so on...
};


## Rewrite

I think that the LList and Node objects are overkill for this problem. A simple ad-hock object can hold the item position and link to the next. You only need to hold the current node, and to determine when you have two left just count off each item as they are removed.

function survivor(number, step) {
var i = 0, current;
const add = pos => {
if (current) {                 // check if not first item
}
const stepOverAndRemove = (link, n) => {
while (--n) { link = link.next }   // do this n-1 times
// remove every step item until only two remain