Last Survivor Coding Question

lastSurvivor.js

'use strict';
/** APPLICANT INFO ***********************************************************
------------------------------------------------------------------------------
 * Name: Alex Hawkins
 * Email: alexhawkins.me@gmail.com
 * GitHub: github.com/alexhawkins
 * LinkedIn: linkedin.com/in/alexhawkinsme/
 ****************************************************************************/


/** THE PROBLEM *************************************************************
-----------------------------------------------------------------------------
 * Take a second to imagine that you are in a room with 100 chairs arranged in
 * a circle. These chairs are numbered sequentially from One to One Hundred.
 * At some point in time, the person in chair #1 will be told to leave the room.
 * The person in chair #2 will be skipped, and the person in chair #3 will be 
 * told to leave. Next to go is person in chair #6. In other words, 1 person 
 * will be skipped initially, and then 2, 3, 4.. and so on. This pattern of 
 * skipping will keep going around the circle until there is only one person 
 * remaining...the survivor.
 *
 * Note that the chair is removed when the person leaves the room.
 ****************************************************************************/


/** THE ANSWER **************************************************************
----------------------------------------------------------------------------*/

// Initiate an array of 100 chairs
var chairs = [];
for (var i = 1; i <= 100; i++)
    chairs.push(i);

/**
 *  A recursive function which checks for the lone survivor in
 *  a circle of 100 chairs, incrementing the number of chairs
 *  that are skipped with each round.
 */

var lastSurvivor = function(skip, count, chairs) {
    //base case checks to see if there is a lone survivor
    if (chairs.length === 1)
        return chairs[0];
    //remove chairs when they are left/become dead
    chairs.splice(skip, 1);
    //increment the skip count so we know which chair
    //to leave next. 
    skip = (skip + 1 + count) % chairs.length;
    count++;
    //recursive call
    return lastSurvivor(skip, count, chairs);
};

/** TESTS *******************************************************************
----------------------------------------------------------------------------*/

var result = lastSurvivor(0, 0, chairs);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31




/** ALTERNATE IMPLEMENTATIONS ***********************************************
-----------------------------------------------------------------------------

/* Implemenation 2 
-----------------*/

var lastSurvivor2 = function(chairs, skip) {
    skip++;
    if (chairs === 1)
        return 1;
    else
        return ((lastSurvivor2(chairs - 1, skip) + skip - 1) % chairs) + 1;
};

/** Tests 2 *******************************************************************/

var result = lastSurvivor2(100, 0);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31



/* Implemenation 3 
------------------*/

var chairs2 = [];
for (var i = 1; i <= 100; i++)
    chairs2.push(i);

var lastSurvivor3 = function(chairs, skip) {
    var count = 0;
    while (chairs.length > 1) {
        chairs.splice(skip, 1);
        skip = (skip + 1 + count) % chairs.length;
        count++;
    }
    return chairs[0];
};

/** Tests 3 *******************************************************************/

var result = lastSurvivor3(chairs2, 0);
console.log('The lone survivor is located in chair #', result);
// The lone survivor is located in chair # 31