Seemingly IMPOSSIBLE Fox Puzzle || Fox in a Hole || Asked in Google Interview
HTML-код
- Опубликовано: 26 авг 2024
- There are five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?
The video has complete explanation of the logic behind the solution.
Please comment below your answers and suggestions. Also LIKE the video and SUBSCRIBE to my channel if you are new.
Also, please give a try to difficult puzzles and Interview Questions Answers specific to Puzzles and Riddles.
Gold bar break Puzzle : • Gold Bar Puzzle || Bre...
Pirates of the Caribbean Puzzle [100 Gold Coins & 5 Pirates] : • 5 Pirates PUZZLE || 10...
![Tee Grizzley - Detroit (Feat. 42 Dugg) [Official Video]](http://i.ytimg.com/vi/aeKfTtt0x14/mqdefault.jpg)
Stay awake for one night and catch it, when it tries to move one hole. Done.
Exactly this is the optimal strategy
Find out the fox's name and write it in the deathnote
@@two697 lol
@@two697 you have to see also 🤣🤣
@EruYagami You are selected ..
just simply watch fox footprints on mud around hole lol..hahaha
Damn, I thought the same😂
THER IS A HARD COURT.
Fill the hole with concrete every day .......that's it
I was going to say sand, but concrete works.
The aim is to find the fox , not to kill it.
@@Shubham-np6od
No the aim was to find out what does the fox say?
How would filling an empty hole kill it?
@@mbearlover how would you know whether the hole is empty or there is fox in it.
Smooth out the dirt around all five holes, come back the next day and look for tracks.
I'm glad the people at Google understand the old art of tracking 😂😂
They are good at tracking. Not just this kind of tracking.
Dig a trench between the holes.
I thought similar. Honestly, I would fill all the holes with mud and see which one he pops out of and say... there he was ...in that hole. or put different color paint at the bottom of each hole and then follow the tracks
@@phDST1913 Hell bring 4 friends to checkj the other holes -- if you're only permitted to check 1 hole per day.
@@uberfu lmao
I solved it differently by visualizing where the fox can be each day.
1. Starting with hole 2 => the fox can be in any other hole (1, 3, 4 ,5).
2. Moving to hole 3 => the fox can be in three other holes (2, 4, 5).
3. Moving to hole 4 => the fox can be in three other holes (1, 3, 5).
4. Staying on hole 4 => the fox *has* to be in hole 2. (We could go grab it right now)
5. Moving to hole 3 => the fox *has* to be in hole 1. (What are you waiting for? Go grab it!)
6. Moving to hole 2 => It is caught. (Finally...)
My sequence is 2, 3, 4, 4, 3, 2; reversing the first half. But it's basically the same solution.
I liked my approach because I didn't have to assume anything.
However it is much simpler to generalize with the approach shown in the video.
Just start with the second slot and increment until n-1, then do that sequence again or in reverse and you are done in O(2(n-2))
I used to be a fox. Always staying ahead of the neighbouring husbands.
First we should inspect the first hole and fill it with cement
Second day you should inspect the second hole and fill it with cement
And do the same process😂
Saved one day of inspection
I tried that, but I never found the fox. However, there was a fox foot sticking out of the cement.
QI 300! You are a CyberPunk living in 2070 XD
Actually saves two days of inspection 😂
Or save cement. And check same hole every day... 20 pct chance to catch
2, 2, 3 ,4, 4, 3 ,2 this sequence will work very well. If the fox in 1st hole first day, it will catch in 2nd day. if the fox in 2nd hole it will be caught in the 1st day. if the fox in 3rd hole in first day, there are three ways to move: move to 2nd hole in the 2nd day(it will be caught in 2nd day), move to 4 in the 2nd day then 5 then 4 holes in 3 and 4 days (it will be caught in the 4 th day based on my sequence ), move to 4 in the 2nd day then 3 then (it will be caught in the 3 rd day) . if the fox in the 4 hole in the first day, so there are 11 scenarios can be happened; move to 5 then 4 then 5 then 4 (it will be catch in 5th day ), move to 5 then 4 then 3 then 4 (it will be catch in 5th day), move to 5 then 4 then 3 then 2 then 3 (it will be catch in the 6 days), move to 5 then 4 then 3 then 2 then 1 then 2 (it will be catch in 7 days), move to 3 then 4 then 5 then 4 (it will be catch in 5 days), move to 3 then 4 then 3 then 4 (it will be catch in 5 days), move to 3 then 2 then 3 then 4 (it will be catch in 5 days), move 3 then 2 then 3 then 2 then 3 (it will be catch in 6 day), move 3 then 2 then 3 then 2 then 1 then 2 (it will be catch in 7 days), move 3 then 2 then 1 then 2 then 1 then 2 (it will be catch in 7 days), move 3 then 2 then 1 then 2 then 3 (it will be catch in 6 days). If the fox in 5th hole, there are two scenarios for moving: move to 4 then 5 then 4 (catch in 4 th days). Move to 4 to 3 (it will be caught in three days).
solve by Ala Zayed
Of course, your solution is better than mine due to the fact the maximum number of days that I need is 7, but you need only 6 and your method also is easier than my method.
Mind blowing Zayed... that's truly interesting solution. You really solved it in a natural way. Although it took an extra day but it's a beautiful approach. (I checked for all the possibilities and all of them seem to be solved with your approach)
Nice work, but sorry for the spoiler. The sequence u mentioned 2, 2, 3, 4, 4, 3, 2 will definitely work as it has a subset sequence 2, 3, 4 ,4 ,3, 2 which is optimal.
So even the sequence 5, 2, 3, 4, ,3, 2 will work and also 4, 2,3,4, 2, 3, 4 as the have the subset optimal sequence of 2, 3, 4,2, 3, 4 or 2, 3, 4, 4, 3, 2
Thanks, and and nice effort. appreciate it, as I think u tried it before you learned about the optimal solution sequence.
Great approach. This is optimal if the fox starts on hole 1.
Two possible ans from my side-
2,4,3,2 2,3,4
2,4,3,2 4,3,2
There can be many possible answers
I solved it too in a similar way, but ans by channel is the most elegant as it takes 6 days instead of 7
You can actually generalize this to any number of "holes" (memory addresses, etc.) with a guaranteed worse case of 2(N-2).
Bro where did you learn your algorithm and data structure?
I want to improve in those.
Please help me
Bro tell me also
I can probably see everything in the holes from the window of my 3 story house.
That's more logical
Then yu broke first rule.
The easiest way would be to go and select a hole in the morning, if you are lucky enough you catch the fox and if not fill up that hole and come next morning and keep doing until you catch the fox 😃
It would make more sense to present this as a friend offers you the riddle as a party game that he will move an object from one cup to another while you cooperate and do not look, there is no looking through the cups and no other forms of bypassing your choice to guess blindly or optimize probability and ensure you guess right.
People won't cover a cup if they are told it is cheating but if you say there is a fox you want to stop it just check all the holes in one day or cover the holes when you know it has this strange compulsion to move around that foxes usually do not have.
PARTY GAME, PLEASE.
Keep the food outside with strong aroma....and sit back relaxed
Mission accomplished in 10 second 😋
Only problem is: I smell the food, come over, and eat it not knowing why it is there.
I would check all the hole at once cause I like to work smarter not harder lol
You contradict your own statement about you by checking all holes at once (which is equivalent to working harder) 😆
@@cool-aquarian no, thats a lot easier than checking 6 holes on 6 different days
@@william7yifans great.. your boss would be happy to know. He would like you to wrap up whole of week's work tomorrow.
@@cool-aquarian you are seriously telling me youd rather walk to work every day for a week to sign one paper and go home than to sign 5 papers at once? cuz that's what this is comparable to
@@william7yifans yes because once you sign 5 papers together, your boss will expect you to sign 5 papers everyday from then onwards for same pay. 😷
Awesome thanks, caught the fox in my yard and it bit me!
My solution was 1-2-3-4-5-5-4-3-2-1 (every hole is inspected twice, once on an even-numbered day and once on an odd-numbered day, and you're inspecting them in systematical order, so that if the fox is in an odd-numbered hole on the first day then you'll find it in the first five days; otherwise you'll find it in the last five days).
I hadn't realized that we can ignore hole 1 and hole 5 because if the fox is there then it is forced to a certain hole the next day anyway.
So the optimal solution is 2-3-4-4-3-2, or 4-3-2-2-3-4, or 2-3-4-2-3-4, or 4-3-2-4-3-2.
Anyway, excellent puzzle, and excellent solution!
Hi Yuri... Your first approach shows that you are a real puzzle solver.... although you missed to optimize it as you explained later... but still the first part of your comment shows the simplest way to solve this puzzle. I will certainly use your explanation when we will have some theoretical videos on 'Art of solving puzzle'.
Thanks for the contribution Yuri... :)
@Logically Yours, thanks for your kind reply. Several of your puzzles seem to contain a certain twist that I can't just solve with only mathematics; it really requires puzzle-solving skills. The one about crossing the bridge in 17 minutes on a dark knight really fooled me! (Very fun puzzle, once I heard the answer it seems so simple!) I would be interested in theoretical videos on "The Art of Puzzle Solving". Keep up the good work! :)
You mention 1-2-3-4-5-5-4-3-2-1 as a non-optimal solution. With the same reasoning, another non-optimal solution would be 1-2-3-4-5-1-2-3-4-5. Am I correct?
Dimitrios Kalemis,
Yes, I think that's correct. I don't know why I hadn't thought of that order before.
A strategy can be checked visually by drawing an N-by-5 "chessboard" (with black and white squares), where N is the number of days in the strategy. So the columns correspond with the five holes, and the rows correspond with the days. In each row, we put a mark (X) in the column that corresponds to the hole that we're checking that day. The strategy 1-2-3-4-5-1-2-3-4-5 would then look like this:
Holes:
1 2 3 4 5
||X|| ::: ||||| ::: |||||| day 1
| ::: |X|| ::: ||||| ::: | day 2
|||||| ::: |X|| ::: |||||| day 3
| ::: ||||| ::: |X|| ::: | day 4
|||||| ::: ||||| ::: |X||| day 5
| X ||||| ::: ||||| :::: | day 6
|||||| X ||||| ::: |||||| day 7
| ::: ||||| X ||||| :::: | day 8
|||||| ::: ||||| X |||||| day 9
| ::: ||||| ::: ||||| X | day 10
The fox would start in one of the five holes on day 1, and move to a diagonally neighbouring square on the next day (like a Bishop in chess, but only one diagonal step at a time). It would then have the task to find a way to make it to day 10 without hitting on a square with a mark.
If the fox starts on day 1 on a "black" square ( "||||" ), it's easy to see that it's either discovered on the first day, or it would not manage to move past the diagonal of X's before day 5. If the fox starts on day 1 on a "white" square ( " ::: " ), then it manages to pass the diagonal of the first five days, but it won't manage to go past the second diagonal on days 6-10; on one of those days, it's forced to move to a square with an X, which means it will be found on that day. So this strategy of X's is successful.
We can draw a similar diagram for a shorter strategy, 2-3-4-2-3-4:
Holes:
1 2 3 4 5
|||||| X ||||| ::: |||||| day 1
| ::: ||||| X ||||| ::: | day 2
|||||| ::: ||||| X |||||| day 3
| ::: |X|| ::: ||||| ::: | day 4
|||||| ::: |X|| ::: |||||| day 5
| ::: ||||| ::: |X|| ::: | day 6
Again we can see that if the fox starts on a "white" square, there's no path to to make it past day 3; and if the fox starts on a "black" square, the fox makes it through day 3, but it will not manage to avoid a marked square in days 4, 5 and 6. So this is also a successful strategy.
1234554321 and 1234512345 wont work man, wew
If it's that hard to look into 5 holes in one day, then use a camera over night, capture it on day 2 for sure.
Check hole 3 every day until it’s in there. Maybe the fox just goes back-and-forth from 1 to 2 or 4 to 5 and never comes to 3, but there’s already nothing logical about a fox changing holes every day, so I’ll add my own assumptions and can’t be wrong.
No, you can be (and definitely are) wrong. If you refuse to comprehend that a logic puzzle serves as a catalyst for critical and logical thought then you're simply stagnating your own mental growth by being obstinate. This has nothing to do with a fox.
@@shivafatalis4368 Thanks for your opinion.
@@shivafatalis4368 Imagine checking the hole requires a camera. Perhaps setting it up at hole 3 is the best idea because it’s far more expensive to have multiple cameras. Fuck it!
Staying at 3 until it happens require the least amount of effort and resources (and has a small chance of never happening but ‘probably’ will eventually) and may be a more ideal solution. It just depends on what the business’s priorities are.
Bill Gates once said something along the lines of ‘ask a lazy man to perform a task and he’ll show you the easiest way to do it’…. Which may be a boon for whatever project. Ya know, something like that.
It may be an advantage to find the highly probably solution in less time as well, when an absolute answer may have wasted a day to develop.
@@shivafatalis4368 this also brings up the idea of cheap-fast-good: pick two.
If it’s cheap and good, it’s not fast.
If it’s fast and cheap, it’s not good.
If it’s good and fast, it’s not cheap.
What’s the goal, given a situation? Is one of these objectively better than the others?
@@drummyt7166 I'm really not sure why you're suggesting these various trivialities to me. Maybe you misread my response or completely missed the point, because you took this a completely different direction.
How would the problem change if the holes were arranged in a ring, where the Fox may move from Hole 1 to Hole 5 or vice-versa?
Hi Jason, I can roughly say it would not be possible to catch the fox at all as there is no corner hole to avoid the escape.
I had the same thought long back... glad to see your comment... now I can look into this type of circular arrangement with some additional constraints/arrangements.
@@LOGICALLYYOURS
Simply check 2 holes each day. Start at any pair of neighbouring holes, A, number N, and B, number N +1. Check the pair twice, move the pairing to A1, number of hole A -1, and B1, number of hole B + 1. Repeat until all the holes have been checked twice. The space between each pairing will allows be fox free assuming the fox never moves more than 1 square.
Never knew what he wanted in solution. He didn't mention he was looking for minimum number of days to find the fox.
Yeah. Just said make sure he's eventually caught. That problem solves itself. Eventually.
@@jeffreywilliamson4863 I mean if you're not doing it the right way you aren't guarantee to catch the fox ever.
We can easily solve this as:-
We can cover each hole with air exchange cloth and fox would always remove cloth when want to move to specific hole and now we can easily track fox movement.
Damn... Even I wish I would get to enter a different hole every day ( if you know what I mean ).
Do you want a job of call boy 🍌
Wow 2 years old comment but got only 5 likes ....lol
what do you mean?
Better strategy for more general problems is apply Dynamic programing. It was not intuitive how we arrive at even/odd guess. We start from the last day and go back. Say All possible ways the fox can move are caught in say day T (terminal state). Lets pick 4 as terminal state (4/2 will work but not 5/3/1) as for say 1 fox could have been in hole 2 earlier and could move to 3 to avoid getting caught. If 4 was the last possibility then fox was in 5 previous day. So previous day better to look at 3, to make sure fox can move only from 2 -4 and not 2-3, and so on. Sorry difficult to explain in words, pic would have been easier. You will see you will get the same answer pointing to even/odd intuition
Can't we just wait in any one hole🐾!
no because it can jump from left to right indefinitely
In that case there will be another man the next day searching for fox as well as you ..But he wont be able to find you somehow
If you fill it with mud every other day you'll catch the 🦊 in 3 days
This was close to my solution to just cover each hole, one per day, until you catch the fox.
Hmm I got the exact same answer, although my thought process wasn't the same. Instead of focusing on determining whether the fox started on an even or odd hole, I had made a chart of sorts of all possible fox locations and checked spots with the intention of lowering the possible locations he could be in while keeping in mind that if the fox is at the edge he's forced to move to only 1 possible location the next day. Interesting how different outlooks still converge to the same solution.
Yea in the chart I noticed the foxes superposition was like a checkerboard where he lived on all black squares or all white squares. The fox was either black or white so I did two sweeps one going left then repeating that square so that I would switch from black to white then sweep right. Boom.
My thought was far simpler, start at hole 2, and repeat hole 2. If the fox is not caught you know the fox is not in holes 1 or 2.. Try hole 3 if not caught the fox is in hole 4,5 or 6. Repeat hole 3, to catch any fox moving from 4 to 3. If not caught repeat hole 4. The last hole to repeat is 5. The holes for repetition is 2, 3, 4 and 5, a total of 8 moves.
@@michaeledwards2251 Hey bro, your solution is wrong. when you will cheak hole 3, then you said that the fox will be in hole 4 or 5. But the fox can be in hole 2 also. as on day 2 if the fox is in hole 3, then the fox can go inhole 2 or hole 4 on day 3. so your assumption is wrong here. Please think again :)
@@Sanket_Jagtap
Did you not wonder why I started at hole 2, and repeated. If the fox was in hole 1, it will move 1 hole, putting it in hole 2. This means checking each hole N twice in 2 to N -1, ascending by 1 hole each time, all holes prior to the hole being checked are empty of a fox.
The problem is the use of a fox as an image. A real fox would be unpredictable and could move any number of holes with an awareness you are trying to catch it. I prefer my solution as it assumes the fox behaves in a more cautious manner the closer you are to it, and does not assume the fox always moves 1 hole when it would be more difficult to observe.
You’re not getting it. On day two when you check hole 2 the second time, If the fox was in hole 3 then on day 3 he could have moved to hole 2.
Feeling bad for Hole 1
Hole 1 be like....
Oo bhai maaro mujhe maaro...
Ni ye majak ho raha h
This didn't seem impossible but took long time to solve for me lol
Thanks for sharing..very interesting puzzle..
I made it in a paper and got to this other answer:
2-2-4-4-3-2, the logic being you discard the fox being in one corner, then the other, and finally... you catch it
2,2,3,4 then if you haven’t caught him go 4,3,2. I think that should work but I haven’t written anything down.
Please reply if I am wrong
Balzsack... it's really nice to see your approach. It works perfectly.
I think you can improve on this because you dont need to search hole 2 twice at the beginning. 2,3,4,4,3,2 works just the same and so does 4,3,2,2,3,4.
@@AA-100 and so 4,3,2,4,3,2 I assume
The other challenge is to understand him
Yeah,try your luck in understanding a fox while you are being watched by human foxes
He means understand lector :D
He's quite easy to understand if you have a basic grasp of the english language.
@@dallan7740 dude I forgot about that,you think people watching an English video does not have a basic grasp of English
Yeah, the guy talking is definitely not a native English language speaker. However, I can still understand him, but with lots more intuitive attention to what he is trying to pronounce. You must have your ears out and process quickly all he is trying to say...this would not happen if a native English speaker would be presenting the video...👂👂👂
If fox had a google account, they'll track the fox for you ;)
Super answer
If you label the holes 1 2 3 4 5 then the sequence of holes you should check to grab the fox should go 3 4 3 2 2 3 4, or the reverse (3 2 3 4 4 3 2). 3 4 3 2 4 3 2 and 3 2 3 4 2 3 4 should both also work.
EDIT: After watching the video I realized that going with the latter sequence first (234 or 432) gets the first sequence (3432 or 3234) cut a day short by starting with an even rather than an odd. Although I do wonder if you averaged the catch rate of both approaches if they would equal out; the 6 day approach is more likely to catch the fox later while the 7 day approach is more likely to catch the fox earlier.
Actually, why not do the math here?
The chance the 7 day sequence catches the fox on day 1 is 1/5. The chance it catches the fox on day 2 is also 1/5. Day 3 is 1/10. Day 4 is also 1/10. Day 5 is 1/5. Day 6 is 1/10. Day 7 is 1/10.
Ok, so the chance you catch the fox by day 1 is 1/5, by day 2 is 2/5, by day 3 is 1/2, by day 4 is 3/5, by day 5 is 4/5, by day 6 is 9/10, and by day 7 is 5/5
The chance the 6 day sequence catches the fox on day 1 is 1/5. On day 2 it is 1/10. On day 3 it is 1/10. On day 4 it is 1/5. On day 5 it is 1/5. On day 6 it is 1/5.
So the chance you catch the fix by day 1 is 1/5, by day 2 is 3/10, by day 3 is 2/5, by day 4 is 3/5, by day 5 is 4/5, and by day 6 is 5/5.
On average the 7 day approach will get you the fox on day 3.6 while the 6 day approach will get you the fox on day 3.7. That means my hypothesis is correct, the 7 day approach will, on average, give you the fox sooner than the 6 day approach. Which is really weird to think about.
Hi... I have noted down your comment and I will analyze it carefully. I am really glad to see that you have analyzed it so deeply. Let me summarize your comment.
Which one is a better appraoch :
1 - An approach with least number of attempts/iterations.
2 - An approach with least average value of number of attempts (based on probability)
It's a challenging question and needs great analysis. I will try my level best to analyze it.. but I request all the comment readers to share their thoughts.
LOGICALLY YOURS I screwed up. Day 4 on the 6 day strategy should have a 3/10 chance of nabbing the Fox, with days 5 and 6 having a 3/20 chance each. This results in an average catch rate on day 3.55, making it still the optimum strategy.
@@LOGICALLYYOURS So after more thought, there might be a way to, on average, get the days down from the 6 day approach. To start, I want to try 2234432, although I think 224422442244... repeating might be the optimum solution for netting you the fox the earliest on average.
So let's do the math and see if I'm wrong or right. We'll start on the 2234432; I'm not sure if I want to do the 22442244... on this comment.
Ok, so on day 1 (2) you have a 1/5 chance of catching the fox. On day 2 (2) you have a 3/10 chance of catching the fox. Day 3 (3) is a 3/20, day 4 (4) is also a 3/20. Day 5 (4) has a 1/8 chance, while days 6 (3) and 7 (2) each have a 3/80 chance.
Averaging these results out, we get an average of 2.9625 days to catch the fox on average, with a guaranteed catch by day 7. Yeah, that is way shorter than the average method.
What is going on here is you are starting with an even to try to catch the fox whether it starts on an even or odd (which is more efficient than starting on an odd and trying to catch the fox that way), but instead of focusing down the fox starting on an even first you focus down the fox starting on an odd first, which is more likely. But you first take your chance at an even fox. You get your 2 best chances to catch the fox at the start and from there-on out the chances decrease.
The 22442244... method, although never guaranteeing you the fox, should mean you always pick the highest chance you catch the fox (or picking for having the highest chance to catch the fox on the next pick). By placing the higher chances of you picking the fox sooner and the lower chances later, you might be able to get the average down as low as it can go even if you can theoretically never catch the fox.
This is an interesting question, but remember to consider conjunction. The probability of any strategy succeeding on day 1 is 1/5. If you picked 2 or 4 on day 2, then day 2's probability of success is 1/4 because 1 or 5 is impossible given day 1's guess, but you still have to multiply .25 by .8 because you only get to day 2 if day 1 did NOT succeed. And then you have to multiply day 3's success probability by .75 and by .8 because you only get to day 3 if you did NOT succeed day 1 and did NOT succeed day 2. And so on. By day 6, using the deductive strategy, you are multiplying everything times 1, so the conjunctions stop meaning anything.
Maybe some strategies have a steeper probability curve early on, but getting to 100% sooner probably helps the average...
I paused this approx a week ago. finally got the answer this morning, I hope I am right - 234234 will ensure the fox get caught eventually
Explain question clearly 😅😅😅
Indeed
I look in every hole each day because I'm not bound by your rules and I'm trying to find a dang fox.
I was thinking about always looking at hole 3, which will always have a 33% chance on having the fox after night 1. I'll explain: If the fox isn't in hole 3, then it's, obviously, on holes 1, 2, 4 or 5. If it's on holes 1 or 5, it will have only one movement, which is to move to holes 2 or 4 respectively. If it's on holes 2 or 4, it will have a 50% chance on moving to holes 1-5 and a 50% to move to hole 3. That's 2 movements out of 6 possible ones, which will lead the fox to the hole 3.
But this approach doesn't GUARANTEE catching the fox in 6 days or less.
Some quick math, it gives me a rough 70% chance by the 6th night. This is by having 20% on the first night, and 33% on the next nights. Anyone who could confirm, plz comment below.
what if the fox decides to *never* enter hole 3? how many days would it take to catch it? :)
Yes, and that's why my approach is not the best approach, but it gives a fair chance of success. But if you bring it to the example given, there's two times it actually coincides that the fox should be in there. As you said, no 100% guarantee, but that's what I thought before looking st the answer. Like, the first 20 seconds.
Holy shit, I actually solved it with the method in the video.
Congratulations you have been selected in google
Holy shit
Very nicely explained. Thanks!
This test is strangely written.. if I have to "eventually" catch it, I'd just check the same hole every day. Given an infinite amount of days then my chance of catching it is so close to 100% so as to not make a difference.
Incorrect, as you have no idea where the fox is when it starts, it could be bouncing between two holes that you never check.
I heard a similiar riddle, but there was 100 holes and fox could just jump between the same 2 holes all the time
Update the question as follows: the fox knows your future actions and she will do everything (within the rules) to protect herself.
Kejriwal is the best person to solve this puzzle
😂😂😂😂😂
He is a Kharagpuria IITian, mind it. Never underestimate an "AAM AADMI".
He's an IITian after all
Why would i do these things !!
(Go out of box) keep piece of meat .
And see from which hole he is coming from 😄
Your strategy is taking six days mine just 2 min 😄😂
I thought this: name the consecutive holes A B C D E. Check B - C - D - B - C - D. In the word case you find the fox at sixth check in D.
that's perfect :)
LOGICALLY YOURS that's exactly same as ur method, just manipulated it into alphabets
Or sooner. And to quote the narrator, "then, it's fine."
Put some food near there the fox will come out itself. 🤣
I liked your approach to this one.
I have my own approach ->
5,4,3,2,1,1,2,3,4,5
Or 1,2,3,4,5,5,4,3,2,1
Anywhere the fox goes it will get eventually caught while u implement this system
Prove ->
Suppose
Fox choose 3rd hole
Start from side (hole 5th or hole 1st)
Next day check hole 4th if u took side 5th
Or hole 2nd if u took side 1st.
Continue in this sequence.
If fox jumped twice towards your last observed hole then on your third day it is caught.
If it ran away from u then don't worry
Just keep on doing it eventually u will find out fox is getting trapped after it makes escape jump.
*Logic goes that if u have observed 1st hole but fox was at odd no. now, then it would be eventually caught and if it was at even then we simply made it to jump at odd no.*
Another valid sequence is 2, 2, 4, 4, 3, 2. (Why? Left to the reader as an exercise)
I'm assuming that's a typo for 2,3,4,4,3,2.
This solution has the advantage of generalising better than the solution in the video, specifically to even numbers of holes. E.g. 2,3,4,5,5,4,3,2 would catch a fox from 6 holes, but 2,3,4,5,2,3,4,5 would not, to use an ascending sequence for both parities you would have to waste a day: 2,3,4,5,*,2,3,4,5.
@@Smithers888 if the fox starts in hole one, you'll never catch the fox.
@@treytavares1727 where is your fox going on subsequent days and which of my sequences are you looking at? If the fox alternated between 1 and 2 it gets caught by the 2 in the second half of the sequence.
Think outside the hole??
The riddle is easier to solve by visualizing each day's status
?X???
0?X??
?0?X?
0?0X0
?0X00
0F000
where:
X is the hole we check today
? is possible current location of the fox
0 is 100% empty hole
F is the fox caught by it's tail
A Very smart visualization; what is your background? Programming? Math?
@@Asdfgfdmn thanks, i do programming
Smart one!
To be honest, since it wasn't specified other than "What strategy would ensure that the fox is eventually caught?", I would start at the far left hole and if he's there' great, and if not then I FILL THE HOLE. I would continue moving to the right-most hole repeating my filling of a hole he wasn't in until he was eventually found as he would run out of left/right decisions quick enough. The best part is, if I saw that a previously filled hole was now open again, that's the first hole I would check when it's time and BOOM...fox.
Remember, they just asked what strategy would ensure capture, and didn't mention that I couldn't think outside the box. So that would be my strategy.
2,2,3,4,4,3,2,2,3,4,4,3... until you find him. He won't be able to avoid you.
Guys, why not just bring a couple of friends to help? Forget the cement, and checking hole 3 everyday. Bring 4 friends and have it done and dusted by dinner time : )
Easier logic to catch the fox: Tie a piece of meat to a trap and wait till the fox takes the bait. Sometimes common sense works better than mathematics😂
yup
That's not useful to a programming logic tho. This is a software company interview.
Your common sense has no value here
Great one! I thought the puzzle didn't have an answer.
Whilst this method is the quickest surefire way of finding the fox, there is another method which has a smaller expected value for the number of days it takes to find the fox, but has a maximum number of days of 8:
day 1: try hole 2 (if not found, it could be in 1, 3, 4 or 5) - success rate 20%
day 2: try hole 2 (if not found, it could be in 3, 4 or 5) - cumulative success rate 50%
day 3: try hole 4 (if not found, it could be in 2, 3, or 5) - cumulative success rate 75%
day 4: try hole 3 (if not found, it could be in 1, 2, or 4) - cumulative success rate 77.5%
day 5: try hole 2 (if not found, it could be in 1, 3, or 5) - cumulative success rate 80%
day 6: try hole 2 (if not found, it could be in 4 only) - cumulative success rate 87.5%
day 7: try hole 3 (if not found, it could be in 5 only) - cumulative success rate 93.75%
day 8: try hole 4 where you will find it - cumulative success rate 100%
The expected days needed to find the fox is 3.1625 which is lower than the 3.55 days described in the video.
Fox puzzle was easy. The more challanging puzzle was to decrypt your accent
His accent is similar to 84% of google employees
Decrypt?
The bigger challenge is to improve your English. Idiot. Wannabe Einstein
How many languages do YOU speak?
"encrypt your accent"
Several logical options include;
1. Learn about the natural predators of the fox species involved, then buy 4. Or
2. Obtain 5 baited traps. Havahart (tm) live traps will not kill the fox. Or
3. Hire a Hunter looking for fox fur.
According to your strategy it takes atmost 6 days
But if u start from day 1 from hole 1 and next day hole 2 and next day hole 3 and next day hole 4 and at last however it must caught at 5 th hole
atmost it must caught within 5 days (atmost 5)
Rip logic..what happen it was in hole 2 on day 1 and hole 1 all other days
Wow!!! I paused the video after question.. and solved it in couple of minutes.. Then ask my friend the same question and explained the answer to her when she couldn't solve. Then watched the video further, and my explanation was line by line same as the video.. She even asaked if I watched the . video before :P :P
I found the answer in a different way. It took me more days than the optimal solution though.
Label the 5 holes, A, B, C, D, E.
1. Check B. If the fox is not found in B, then the fox moved from B->A, B->C, C->D, D->E, or E->D.
2. Check B again. If the fox is not found in B, then the fox moved from C->D, D->E, D->C, or E->D.
3. Check B again. Now you have two possibilities. 1) The fox moved from initial position D to a different position (D->C or D->E). or 2) The fox moved from a different position to D (C->D or E->D).
4. Check C. For possibility 1, the fox would have moved from C->B or E->D. For possibility 2, the fox would have moved from D->E, and that's the only possibility if the fox is not found in step 4.
5. Check D. If the fox is not found in position D, then possibility 2 is no longer valid. Therefore, we can conclude one of two possibilities - Possibility 1: the fox moved from C->B just before step 4 Possibility 2: the fox moved from D->C just before step 5. If possibility 1 is true, then the current position of the fox would either be A or C.
6. Check D again. If the fox is not found in this step, we can conclude two possibilities. For initial possibility 1, the fox would have to move from A->C or C->B. For initial possibility 2, the fox would have to move from C->B.
7. Check C. If the fox is not found in this step, then the fox must have moved from B->A.
8. Check B. The fox is found.
You can omit step 3. With the step 2 you can come to the same conclusion as step 3.
What about foot prints of fox, we could easily find out where the fox is by just inspecting where the footprint goes......
I will mimic the sound of a hen.Suddenly fox will come out of the hole to catch that hen...😇
The only strategy that I came up with was to check either 2 or 4 but stick to the same option, 2 or 4. I don't think you can add anything to a strategy by stating initial condition of odd or even, because this is not known and there is no stipulation that the starting state would ever change or reset, so that can be totally removed from a strategy.
Same here. 2, 2, 3, 4, 4.
@@nmklpkjlftmch That was exactly my solution as well. Except I needed one more 3 at the end.
@@nickmatveev2670 I think I've just seen a flaw in my plan. If the Fox is in 3 after the second day, then he can jump to 2 when I look in 3.
Solution in the video is the fastest method to be certain to catch the fox in 6 days. Checking a box twice in the beginning does nothing, as the fox can just jump back and forth somewhere else.
@@ne5o2 ahhhh.. I see.
Love these questions... Looking forward to more :)
Took me about an hour of thinking, but yeah. I was correct.
Good luck! You're gonna get job in Google
I think 2, 2, 3, 4, 4 should catch him no matter what. Nice puzzle
If fox goes 4->3->2->1->2, you won't have caught him.
My solution, check holes 2, 2, 2, 3, 4
On the last day - if the fox isn't in hole 4, then it's in hole 5.
Night 1 waite for the fox to move holes and shoot it. How hard was that?
Laughing. like hard to get a job. no offence.
As hard as it is for you to read and follow directions.
@@drewpierpont3361 I try to leave "following directions" for people that cant think for themselves.
lol dude. You wont even get hired for 'thinking outside the box' since the solution you came up with is not only avoiding the spirit of the puzzle, but also inconvienient. Why stay awake all night if you could just inspect all 5 holes one by one on the same morning?
@@ullrichbrand7994 That's ok i have a great job. Lately iv bin saving them a whole lot of money thinking outside of the box.
The correct strategy is to check all of the holes in the first morning.
Is this how Google picks which neighborhoods to gentrify?
while not the most optimal solution it would be fairly easy to code
the sequence 1-5 will catch the fox if he starts on any odd hole
if 1-5 misses, do sequence 5-1. if the fox is in an even hole on your 5th check at hole 5 then if you check hole 5 on your 6th check the parity of the fox reverses meaning you'll find it within 10 moves
even though the example in the video can solve it in 6, I think my solution for code is slightly better since it's far more extendable.
if there were 7 holes you'd have to add extra logic for the optimal solution, but if compute time isn't an issue hitting all the holes in forward then reverse order works for any number of holes with no need for any updates to the algorithm.
(I'm sure an optimal algorithm that handles any number of holes is possible, but that would require more time to implement. if would take about 5 minutes to implement my proposed solution, which would be enough to use until a better more efficient algorithm could be implemented)
Checking the outer holes is unnecessary. So an algorithm that always works (with N holes) is "from hole 2 to hole (N-1), and then from hole (N-1) back to hole 2", which will take 4 days less than your solution.
So for example, with seven holes, an optimal solution would be 2-3-4-5-6-6-5-4-3-2 , which takes (at most) 10 days.
Pick a random one, if you don't find it , block that hole... it will take 5 days..
idiot read the question properly
The question didn't give any limitations. Why do we only block one hole per day? Just look at every whole on the first day. Gg
Can't the rule is 1 hole a day.
I can tell two of you tried to pull this shit on board games when you were little. "You don't HAVE any money because I'm stealing it and I'm bigger than you!!" How's that working out in life outside of youtube riddles?
Logic says look at all the holes on the same day, this has nothing to do with logic lol
Exactly! logically correct
This works with 2, 2, 4, 4, 3, 2
In the first 2 , 2 you know fox is on 3, 4 or 5. Then you pick 4 and again 4 so you know the fox was not in 4 and 5 so when you picked the second day, the fox was in box 3. So from box 3 she can be either in box 1 or 3 since she moved 2 times when you picked the 4 and 4 so you pick box 3 so if she is not there, you pick box 2 since she is at 1 and she will move to 2
+1
I couldn't answer correctly. But I understood ur explaination
Actually your solution is correct but it is not an optimal one in all cases. Your solution has the lowest max days to find the fox.
Optimally though, one could consider the best solution to be the one that has the lowest average number of days to find the fox OR even the lowest average number of holes that need to be searched (how much effort you have to do). Its pretty amazing. All of them have different solutions!!
Your solution: { 2, 3, 4, 2, 3, 4 } :
Max days to find fox = 6, Average days to find fox = 3.55, Average effort needed = 3.55 hole searches
Alternate optimal solution #1:
{
2, 2, 4, 4, /* this search pattern is repeated forever */
3, 2, 2, 3, 4 /* will never be reached, but can truncate forever loop early and execute this to get arbitrarily close to values */
} :
Max days to find fox = INFINITE, Average days to find fox = 2.93333..., Average effort needed = 2.93333... hole searches
Alternate optimal solution #2:
{
X /* skip searching this day */,
2, 2, 4, 4, /* this search pattern is repeated forever */
3, 2, 2, 3, 4 /* will never be reached, but can truncate forever loop early and execute this to get arbitrarily close to values */
};
Max days to find fox = INFINITE, Average days to find fox = 3.73333..., Average effort needed = 2.73333.... hole searches
HERE IS THE CODE: (You can run it on any online C++ compiler and engine)
#include
using namespace std;
// This is the probability that the fox is in particular hole
float prob[5] = { 0.2, 0.2, 0.2, 0.2, 0.2 };
// These are various choices of hole indices (zero-based) to search (uncomment exactly one of them to try it out)
//int choices[] = { 1, 2, 3, 1, 2, 3 }; // 3.55, 3.55 (Worst case is 6 days)
//int choices[] = { 1, 2, 3, 1, 2, 3 }; // 3.55, 3.55 (Worst case is 6 days)
/*
int choices[] = { 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3,
1, 1, 3, 3, // this is repeated forever
2, 1, 1, 2, 3 }; // 2.93333...., 2.93333.... (Worst case is you find the fox after an unbounded number of searches)
*/
int choices[] = { -1, // Negative number indicates skip searching on that day
1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3, 1, 1, 3, 3,
1, 1, 3, 3, // this is repeated forever
2, 1, 1, 2, 3 }; // 3.73333..., 2.73333... (Worst case is you find the fox after an unbounded number of searches)
int main()
{
int effort = 0;
float totalEffort = 0.0;
float totalDays = 0.0;
for (int day = 0; day < sizeof(choices)/sizeof(choices[0]); ++day) {
cout
The problem clearly states: "what strategy would ensure that the fox is *eventually* caught". Any option which has max-time=infinite is not a solution to the given requirements. :)
Most of the time, a well done requirement analysis can save you months of coding ;)
And you should read the code before commenting. It clearly does not go on forever. You can terminate the infinite loop at whatever time and find the fox. You can get arbitrarily close to those numbers by terminating early. In fact the solutions in the code do terminate early. In fact it does not really take too many iterations to be very close indeed and have much better results on average than the proposed solution.
P.S. That's not months of coding (just takes about 20 minutes or so)
Ameya Limaye how did you get the average number of days as 3.55?
I'll Just look at one hole everyday
I solve it like this: F denotes the possibility of the fox being there and N: the absence.
On the first morning, the fox can exist anywhere so FFFFF denotes it. In the next morning a hole can have fox only if there's at least one fox in its neighborhood. So it goes like this:
FFFFF: FNFFF(checking hole 2):NFFFF(next morning):NFNFF(checking hole 3):FNFFF:FNFNF(hole 4): NFNFN:NNNFN(hole 2): NNFNF:NNNNF(hole 3):NNNFN
And finally checking hole 4
So in short check like this and surely you'll find the fox: holes 2 3 4 2 3 4
I like this notation
im sure he would monitoring other holes during night, lol
Start with hole 2 then hole 2 again
If you didn't catch it you now sure hole1&2 are empty
Then go to hole 4 if it is empty you now sure hole 1& 4 are empty
Then go again to hole 4
If you didn't catch it now you sure that hole 4 & 5 & 2 are empty
Now the Fox in hole 1 or 3
So go to hole 2 if you didn't catch it now you sure that the Fox in hole 4
Then go to hole 3 if you didn't catch it now you sure that the Fox in hole 5 now you can catch in next day in hole 4 because no choice for him .
Ali Shaker same here, just need 4 days
after second time checking 4th hole you know 4&5&3 are empty, but it could be in 2...
IF: Fox start in 3, you check 2. Fox jumps to 4, you check 2. Fox jumps to 3 you check 4. Fox jumps to 2!! and you check 4 second time.
U r wrong bro. The second reply answers perfectly for your statement
Check the centre hole repeatedly as statistically it's the one he'll spend the most time in. Eventually he will land in it and you will catch the fox.
Assuming his motion is random that is
@@richardhp77 suppose the fox only shifts between 1 and 2 or 4 and 5 and never jumps to the center hole. The movement will be allowed coz it is alternate right & left movement. So, always looking at the center doesn't count for all cases.
@@kruz2919 it will eventually. Every other day, you’ll have a 50/50 of it being in 3, if it wasn’t there the first day.
@@richardhp77 yeah totally, I agree. If you hang out at 3 and it never comes to 3 because it’s afraid you will be there, then yeah this doesn’t work. Like you said, we are assuming his movement is random.
@@drummyt7166 if motion is random then ofc....that's why I stated not in all cases but in these puzzles u gotta cover the edge cases as well since u have to consider all possible cases and if ur solution checks for every single one of them with the smallest possible sequence then that's the optimized one.
Here’s how to simulate the fox movement in Google Sheets. Put this formula into cell A1:
=RANDBETWEEN(1,5)
Put this formula into A2:
= if(A1=1, 2, if(A1=5, 4, if (RANDBETWEEN(1,2)=2, A1+1, A1-1)))
Copy cell A2 into cells A3 through at A6. The cell references will update automatically. You will get the random movements of the fox.
This will allow you to see how a pattern that you try out against the fox will work. You should be able to test which solutions will work consistently against the fox. (If you want to test patterns of more than 6 movements then copy the A2 cell down through at least cell A20 or so.)
What is the strategy if the five holes arranged in a circle?
You made the puzzle more beautiful. I will certainly capture your comment and will let you know if I can make a video on this.
Much appreciated.
If holes are in circle , it is logically impossible with every variation because it will alwayas have two holes to move
1-2-3-4-__ which is next.
Hint: it is not 5.
-5
@@manasp8456 😵😵😵😵😵😵😵😵😵😵😵
5-
Yash Bansal u replied from different id
@@AyushGupta-yj8jz no bro ye vala yash Bansal koi or hai. Mai answer apni hi Id Se dunga thode time baad
Do some investment and put a camera with tripod in front of hole.... Very next morning fox will be caught... Change with technology dude 🤖
maybe i'm wrong but you can catch the fox in *max 5 days with the sequence of checks - 2,2,3,4,4.*
1 day: check 2 hole. if not there, then either in 1 or 3,4,5 holes.
2 day: check 2 hole. if it was in 1 hole, it must be in 2 in the morning ( also in case if it went to the left from 3 hole). if not we know for sure that the fox is hiding in one of 3,4,5 holes.
3 day: check 3 hole. if not found, then the fox must be in 4 or 5 hole. because the left holes were empty during all previous checks,so it cant come from the left.
4 day: check 4 hole. if not found we already know that is is hiding inside 5 hole, from which it can only move to the left 4 hole.
5 day: check 4 hole and catch it.
there is an issue... if the fox follows the seqence 4,5,4,3,2 then you will miss it. :)
LOGICALLY YOURS yup. totally missed that point.
I don't understand why people are coming with loopholes, just solve it.
We teach our next generation addition not give them calculator directly.
Just check the same hole every morning....
All you need to do is "ensure the fox is eventually caught."
yup
Why cant he just smoke all the holes and wait till the fox come out. ? 🤪🤪🤪🤪🤪
Just check same hole every day maximum 5days needed
Solved in 3 minutes:) maybe I should apply to Google:)
So close.. I solved it on 8 days with a different strategy... but this one is 2 days faster
So did I.. out of curiosity did you start at the end and go 5,5,4,4,3,3,2,2?
@@matthewfinis6723 falsified by fox: [2, 3, 2, 3, 4, 5, 4, 3, 4]
You can catch it by just inspecting each hole twice and then moving to the next. Lets say you do 1, 1, 2, 2, 3, 3, 4, 4, 5, eventually you will catch it but its not best case. Your algorithm is better for the best case
this will not work
@@karunesh26march why would it not work? You go from one side to the other thus youndont give him a chance to dodge it
For example, say day one you inspect hole 1 but the fox is in hole 4.
Day 2 you inspect hole 1 again, the fox moves to hole 3.
Day 3, you inspect hole 2, fox goes to hole 4.
Day 4, you inspect hole 2 again, fox moves to hole 3.
Day 5, you inspect hole 3, fox moves to hole 2.
From here on the fox goes between hole 1 and 2 every day and you wont catch it.
+1up, Your proposed strategy is flawed. Even _two_ independent foxes that are restricted to not occupy the same hole at the same time, could still both escape from being caught. For example:
Day : 1 2 3 4 5 6 7 8 9 10
Fox 1: 2 3 4 3 2 1 2 1 2 1
Fox 2: 5 4 5 4 5 4 3 2 3 2
You : *1 1 2 2 3 3 4 4 5 5*
The solutions given by the video will catch _all_ foxes (even if there are two or more foxes that are also not prohibited from sharing a hole at the same day).
Yes - but there is no need to visit hole 1. Since the fox always has to move each night, visiting hole 2 twice will catch the fox if it started in hole 1.
4 3 2 2 3 4 will work i guess in 6 days too
I have a strategy in 8 days: 2-2-4-4-2-2-3-4.
You start with 2-2: No catch? You know the fox is not in 1 or in 2.
Then you continue with 4-4: you know the fox is not in 4 or in 5. So it means it was in 3. But it has moved two times. So now the fox is in 1 or 3.
You continue with 2. Still no fox? It means it was not in 1 and it was in 3. Now you have to catch him.
2 again. Still not? The fox must have moved to the right in 4.
3. We're all most finished. If there's no fox in 3, he must be in 5
4. The fox was in 5 and has to move the left and here you catch him!
Here you go, it's not the best solution but it works :)
If fox goes 4-3-2-3-4-3-2-1 your solution fails
Too much work. Just inspect the same whole each day preferably hole 3
but then theoretically the fox can do either "1,2,1,2,1,2,1..." or "2,1,2,1,2,1,2,...." or "4,5,4,5,4,5,4,5,..." or "5,4,5,4,5,4,5,4,..."
SImly choose the same hole every day 2,3 or 4. Eventually the fox will be there.
thats what i thought too..it's easier this way
VeiNpl the Fox can keep switching back and forth between the same two holes and you’ll never catch it that way
Pile up mud around all the holes. The fox wen it moves during night it will scatter the mud. U will find it the next morn.
Keep a delicate thread like trap between hole 2 and hole 3 on first day, if it is damaged, it is in hole 2,else hole 4.