Problem
About a week ago (maybe less), I posted this and I didn’t really have a 100% full-proof working implementation, but I think I have got it now.
First of all, here is the coding / algorithm challenge question:
Assume there is a thief hiding in a line of caves. Every day the thief will move either left or right one and only one cave. You are allowed to check any cave, once a day. Given that there is k caves and m days to find the thief, find a solution that will work for any k and m.
This is a bit tricky so I offer an alternative question: Given an infinite amount of days, could you come up with a way to find the thief given there are 5 caves.
Here is an example start of this scenario: [0, 0, 1, 0, 0] given 1 = the thief.
I encourage you to try and solve for 5 caves and look for a pattern in your algorithm that can be applied to the rest of the situations. Then, try and find the lower and upper bounds for the days you need in relation to k caves. If you are interested in the answer or need help, feel free to dm me on slack.
To clarify: Your algorithm for finding the thief for 5 caves and infinite days must work no matter the path the thief takes. This was an interview question received from one of the top 5 companies in tech so really try and think this one out.
Just a few note(s) to help you understand the question more:
The thief cannot move circularly, in other words, when the thief reaches an edge index (i.e.
[1,0,0,0,0]), they MUST go back the other direction[0,1,0,0,0].Also, the thief CAN “jump” you, in other words, if you and the thief are right next to each other, the thief can move past you if you don’t check the same cave twice. (i.e.
[0,X,1,0,0]given this, if you move one to the right, the thief can move one to the left without you catching ‘him’,[0,1,X,0,0]).
And here is the algorithm that I came up with (as a set of rules):
Rule #1: Start one index off from the edges, so for example given a set of 5 caves
[0,1,2,3,4], start always at either index[1]or[3]. These are your (BOUNDARY) indices.Rule #2: When you reach a
BOUNDARYindex, you must wait there one extra day. So, on the first day since you start at aBOUNDARY, you wait one extra day.Rule #3: Do not go beyond the
BOUNDARYindices. In other words, do not touch the edges. So again, given 5 caves[0,1,2,3,4], do not EVER go to index[0]or[4].Rule #4: Move linearly back and forth between index
[1]to[length - 2]or in our case[3], only stopping to wait at theBOUNDARYindices.
A visualization of these rules (given the thief knows your location, WORST CASE):
1 = Thief
X = Person Searching for Thief (You or Me)
C = THIEF CAUGHT
[0,X,0,1,0]
[0,X,0,0,1]
[0,0,X,1,0]
[0,0,1,X,0]
[0,1,0,X,0]
[1,0,X,0,0]
[0,C,0,0,0]
I believe that I’ve successfully implemented this solution, and I’m hoping to get some critique on my implementation (could it be done better), as well as my JavaScript (it’s not my most known language), and finally critique the algorithm itself.
FindThief.js:
/**
* FindThief.js - Coding Challenge
* @author Thomas Yamakaitis
* @version 1.0
* @description Assume there is a thief hiding in a line of caves. Every day the thief will move either left or right one and only one cave. You are allowed to check any cave, once a day. Given that there is k caves and m days to find the thief, find a solution that will work for any k and m.
*
* This is a bit tricky so I offer an alternative question: Given an infinite amount of days, could you come up with a way to find the thief given there are 5 caves.
* Here is an example start of this scenerio: [0, 0, 1, 0, 0] given 1 = the thief.
*
* I encourage you to try and solve for 5 caves and look for a pattern in your algorithm that can be applied to the rest of the situations. Then, try and find the lower and upper bounds for the days you need in relation to k caves. If you are interested in the answer or need help, feel free to dm me on slack.
* To clarify: Your algorithm for finding the thief for 5 caves and infinite days must work no matter the path the thief takes. This was an interview question received from one of the top 5 companies in tech so really try and think this one out.
*/
var caves = new Array();
var foundThief = false;
var length = prompt("How many caves?", 6);
for (var i = 0; i < length; i++) {
caves[i] = 0;
}
var thief = Math.floor(Math.random() * length);
caves[thief] = 1;
var start = 1;
if(length == 1) {
start = 0;
}
var count = 0;
var direction = 0; // -1 = left; 0 = wait; 1 = right;
while(!foundThief) {
count++;
caves[start] += 2;
// window.alert(caves); // Uncomment this line to visualize thief and yourself moving...
if(caves[start] == 3) {
foundThief = true;
window.alert("[" + caves + "]nTries: " + count + "n" + "YOU FOUND THE THIEF!");
console.log("# of Caves: " + length + "nSetup: [" + caves + "]nTries: " + count);
} else {
caves[start] -= 2;
switch(direction) {
case -1:
start--;
if(start == 1) {
direction++;
}
break;
case 0:
switch(start) {
case 1:
direction++;
break;
case (length - 2):
direction--;
break;
}
break;
case 1:
start++;
if(start == length -2) {
direction--
}
break;
}
thief = moveThief(thief);
if(count > 10000) {
foundThief = true;
window.alert("This took 10000+ tries; try something else.");
}
}
}
function moveThief(thief) {
caves[thief]--;
var leftRight = Math.floor(Math.random() * 2);
if(thief == 0) {
thief++;
} else if(thief == (length - 1)) {
thief--;
} else {
if(leftRight == 1) {
thief++;
} else {
thief--;
}
}
caves[thief]++;
return thief;
}
Solution
I would have done this i little different. I would make a basic program to move the thief around and look in a cave, and build the algorithm on top afterwards.
Initialize
var length = 6;
var thief = Math.floor(Math.random() * length);
var days = 0;
You don’t need an array to store the thief’s position, just an integer. Besides that, the only information needed is the number of caves and (optionally) the number of days. Note that the thief’s position is 0-based, like an array, so a length of 6 mean a position between 0 and 5.
I skipped it here, but if you take a user input, make sure it’s usable (a positive integer in this case), since it could be anything. Also, prompt actually returns a string.
Look in a cave
function lookInCave(n) {
days++;
var result = (thief === n);
moveThief();
return result;
}
This function does 3 things. Increment the number of days, move the thief, and returns true if you found the thief, or false otherwise.
Move the thief
function moveThief() {
if(thief === 0) {
thief++;
}
else if(thief === length-1) {
thief--;
}
else if(Math.random() < 0.5) {
thief++;
}
else {
thief--;
}
}
I decided to put this in a separate function, but it’s straight forward. If the thief is at the end, the move is forces. Otherwise choose a random side.
That’s it for the base program.
Algorithm
Your method is correct, but can be improved slightly, because you don’t have to look in the initial cave twice. Also, once you are back to the initial cave, you are guaranteed to have found the thief.
function findThief() {
var guess;
do {
if(days < length-2) {
guess = days + 1;
}
else {
guess = 2 * (length-2) - days;
}
} while(!lookInCave(guess))
console.log('You found the thief in ' + days + ' days!')
}
I use a while loop to make guesses until it return true and the thief is found. For the first length-2 days I start from cave number 1 and move upwards from there. After that I move back again. This is one of the few cases where a do…while loop fit perfectly, since I need to make my initial guess before I can look in a cave.
The final program
var length = 6;
var thief = Math.floor(Math.random() * length);
var days = 0;
findThief();
function lookInCave(n) {
days++;
var result = (thief === n);
moveThief();
return result;
}
function moveThief() {
if(thief === 0) {
thief++;
}
else if(thief === length-1) {
thief--;
}
else if(Math.random() < 0.5) {
thief++;
}
else {
thief--;
}
}
function findThief() {
var guess;
do {
if(days < length-2) {
guess = days + 1;
}
else {
guess = 2 * (length-2) - days;
}
} while(!lookInCave(guess))
console.log('You found the thief in ' + days + ' days!')
}Why do you do window.alert? You don’t write window.console or window.theif. Be consistent, just do alert() without window. It’s easier to read.
Fix your indentation, especially where you have nested switches, that is really difficult to read.
Organize better. Do all your variable definitions at the top.
In javascript you can use an array literal ([]) instead of new Array(). I believe literals are slightly faster.