4
\$\begingroup\$

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.head = new Node("head");
    this.head.next = this.head;
    this.find = find;
    this.insert = insert;
    this.display = display;
    this.findPrevious = findPrevious;
    this.remove = remove;
    this.advance = advance;
    this.count = count;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == this.head)) {
        prevNode.next = prevNode.next.next;
    }
}
function findPrevious(item) {
    var currNode = this.head;
    while (!(currNode.next == this.head) &&
        (currNode.next.element != item)) {
        currNode = currNode.next;
    }
    return currNode;
}
function display() {
    var currNode = this.head;
    while (!(currNode.next == this.head)) {
        print(currNode.next.element);
        currNode = currNode.next;
    }
}
function count() {
    var currNode = this.head;
    var count = 0;
    while (!(currNode.next == this.head)) {
        count++
        currNode = currNode.next;
    }
    return count;
}
function find(item) {
    var currNode = this.head;
    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;
}

function advance(item, n) {
    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();
    var currNode = compatroits.head;

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

    //kill every mth person in the circle
    //start from head
    var currItem = compatroits.head.element;
    while (compatroits.count() > 2) {
        //advance mth person
        var killNode = compatroits.advance(currItem, position);

        //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?

\$\endgroup\$
1
\$\begingroup\$

The Ouroboros

Your code is way too complex for the task

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() {
    this.head = new Node("head");
    this.head.next = this.head;    
}
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 => {
        const link = {pos};
        if (current) {                 // check if not first item
            link.next = current.next;  // insert link to tail
            current.next = link;
        } else { link.next = link }    // first link points to self
        current = link;                // Hold current as head
    }
    const stepOverAndRemove = (link, n) => {
        while (--n) { link = link.next }   // do this n-1 times
        return link.next = link.next.next; // remove next link and return link after that
    }

    while (i < number) { add(i++) }  // create list
    current = current.next;          // move to the start

    // remove every `step` item until only two remain
    while (number-- > 2) { current = stepOverAndRemove(current, step) }

    // return the position of the remaining two        
    return [current.pos, current.next.pos];
}
\$\endgroup\$
  • \$\begingroup\$ Thanks very much for your answer and advice. I really do appreciate you taking out time to help me out \$\endgroup\$ – KKay Jul 8 '18 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.