Skip to content

Instantly share code, notes, and snippets.

@ebaizel
Last active August 29, 2015 14:01
Show Gist options
  • Save ebaizel/4fc9ebaf69dc8f08be52 to your computer and use it in GitHub Desktop.
Save ebaizel/4fc9ebaf69dc8f08be52 to your computer and use it in GitHub Desktop.
Given 100 chairs, keep one and skip the next. Repeat till only one chair remains.
var Seat = function(number) {
this.occupied = true;
this.number = number;
}
var seats = [];
(function setup() {
for (var i=0; i < 100; i++) {
seats[i] = new Seat(i+1);
}
})();
// Including the starting seat (start), what is the next occupied seat?
function findNextOccupiedSeat(seats, start) {
if (start >= seats.length) {
start = 0;
}
if (seats[start].occupied == true) {
return start;
}
var found = false;
var currSeat = start + 1;
while (!found && currSeat !=start) {
if (currSeat >= seats.length) {
currSeat = 0;
}
if (seats[currSeat].occupied) {
found = true;
} else {
currSeat++;
}
}
return currSeat;
}
// Given a seat, dismiss it if it is not the last occupied seat
function dismissSeat(seats, seatNumber) {
// find next occupied seat
var nextOccSeat = findNextOccupiedSeat(seats, seatNumber + 1);
// if it's not the same as current seat, then dismiss current seat
if (seatNumber != nextOccSeat) {
console.log('dismissing seat ' + seatNumber);
seats[seatNumber].occupied = false;
} else { // final answer
return seatNumber;
}
// continue the search, skipping past that next occupied seat we found
nextOccSeat++;
if (nextOccSeat >= seats.length) {
nextOccSeat = 0;
}
return dismissSeat(seats, findNextOccupiedSeat(seats, nextOccSeat));
}
var lastSeat = dismissSeat(seats, 0);
console.log('Last seat is ' + seats[lastSeat].number);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment