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
BOUNDARY
index, 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
BOUNDARY
indices. 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 theBOUNDARY
indices.
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;
}