Skip to content

Instantly share code, notes, and snippets.

@fijiaaron
Last active Feb 25, 2022
Embed
What would you like to do?
/**
* rabbithole.js
*
* There are 100 holes, all in a row, and a long tunnel connecting them.
* A rabbit lives down there, and you're trying to catch him.
* The rabbit starts down 1 one of the holes, but you don't know which.
* Every time you look down into a hole the rabbit moves.
* But he only moves one hole -- either left or right.
* How can you find the rabbit? And how long will it take?
*
* Here is my solution to the problem.
* It takes at most 200 tries, or 2 * O(n)
**/
function random (n) { return Math.floor(n * Math.random()) } // generate a random number between 0 and n-1
function left_or_right() { return random(2) ? -1 : +1 } // (randomly) return -1 or +1
// rabbit's initial position
let rabbit = random(100)
function move() {
rabbit += left_or_right()
// rabbit can't go left from first hole
if (rabbit < 0) { rabbit = 1 }
// rabbit can't go right from last hole
if (rabbit > 99) { rabbit = 98 }
console.log(`The rabbit moved to ${rabbit}`)
return rabbit
}
function look(hole) {
if (rabbit != hole) {
console.log(`wrong! The rabbit was in ${rabbit}`)
move() // the rabbit moves whenever you look
return false;
}
else {
console.log(`right! You found the rabbit in ${rabbit}`)
return true;
}
}
let hole = 0
let found = false
let guesses = []
while (! found)
{
guesses.push(hole)
found = look(hole)
// finish if we found the rabbit
if (found) { break }
// test each hole twice to make sure the rabbit doesn't pass us ( 0, 0, 1, 1, ...)
guesses.push(hole)
found = look(hole)
// check the next hole
hole += 1
}
console.log(guesses)
console.log(`It took ${guesses.length} guesses to find the rabbit`)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment