Last active
August 29, 2015 14:01
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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