rabbithole.js

/**
 * 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`)