wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Minimum number of shots to kill the rat
        
(Message started by: davkrs on Aug 27^th, 2013, 5:57pm)

Title: Minimum number of shots to kill the rat
Post by davkrs on Aug 27^th, 2013, 5:57pm

I came across this problem, and thought would share here for a good discussion

You have an array of size n. And there is rat in one of the positions in the array.

You have a laser gun which lets you shoot at any index in the array at a given instant. You can move to any index in the array to shoot. However, you can shoot only at one index at any given time

Rat gets to move either left or right (randomly, but if there is only one option available, e.g if rat is in right most index of array, it will move to left) by one position in the array, after you shoot the laser gun. It also moves when you move the laser gun.

How many shots are required to make sure that rat is killed.

Title: Re: Minimum number of shots to kill the rat
Post by allonhadaya on Sep 3^rd, 2013, 12:48am

Nice puzzle! ;D
I worked out n 1 .. 4 by hand along with alternate solutions for n = 2 and n = 4. They demonstrate some symmetry.
n 1 = 1 0 n 2 = 2 0,0 1,1 n 3 = 2 1,1 n 4 = 5 1,1,2,2,1 2,2,1,1,2
???
1, 2, 2, 5
I'll sleep on it, but my intuition says something about recursive trees and parity perhaps.

Title: Re: Minimum number of shots to kill the rat
Post by jamez on Sep 3^rd, 2013, 12:56am

Assuming the rat can change direction at will - there is no solution for n>3.

if n==3 you can just hit the middle index twice to catch if the rat is on the side.

if n==4 you can no longer corner the rat.

Assuming the direction can't change, you can continually hit the second index in from either end, so that catches the rat in that spot and the one on that end in 2 moves.

every other rat after that adds another 2 steps because there could be a rat starting right next to where you are firing, moving in the opposite direction, having to get to the other wall before coming back.

formula for n>3
2(n-2)

formula for n=<3
n

Title: Re: Minimum number of shots to kill the rat
Post by allonhadaya on Sep 3^rd, 2013, 1:31am

I beg to differ...

for the case of n = 3:
[ r . . ] - 1 [ . r . ] - 1 [ . r . ] - 1 [ . . r ] - 1 [ . r . ] - 1
2 guesses are sufficient: 2 /= 3

and for 4:
[ r . . . ] - 1 [ . r . . ] - 1 [ . r . . ] - 1 [ . . r . ] - 1 [ . r . . ] - 1 [ . . r . ] - 1 [ . . . r ] - 1 [ . . r . ] - 2 [ . . . r ] - 1 [ . . r . ] - 1 [ . . . r ] - 2 [ . . r . ] - 2 [ . . . r ] - 1 [ . . r . ] - 1 [ . r . . ] - 2 [ . . r . ] - 2 [ . . . r ] - 1 [ . . r . ] - 1 [ . r . . ] - 2 [ r . . . ] - 2 [ . r . . ] - 1
5 guesses are needed: 5 /= 2(4 - 2)

It's a tough problem! :P

Title: Re: Minimum number of shots to kill the rat
Post by towr on Sep 3^rd, 2013, 9:14am

4 is enough for 4.
Shoot at 2, then 3 (the rat is now dead if it started at an even position), then 3, and 2

[e]missed the part where aiming elsewhere lets the rat make an extra move[/e]

Title: Re: Minimum number of shots to kill the rat
Post by allonhadaya on Sep 3^rd, 2013, 9:30am

Nice, you're right. I'll have to think about it some more.

Title: Re: Minimum number of shots to kill the rat
Post by Fellius on Sep 3^rd, 2013, 2:11pm

How does 2-3-3-2 work?
If we have
O@OOR where the O after the @ is where the cursor is then:
1. After firing at 2 (assuming you start there):
O@ORO
2. After moving to 3:
OR@OO
3. After firing at 3 for the first time:
RO@OO
4. After firing at 3 for the second time:
OR@OO
5. After moving to 2:
O@ORO
6. After firing at two for the second time:
O@OOR

Unless I made a mistake somewhere it seems that strategy wouldn't work for catching a very lucky rat.
If we formalize the system a bit, where O represents somewhere the rat could be, X where the rat cannot be, and @ before the square where the cursor is then it would seem this problem is impossible.
We can start with:
@OOOO
Or:
O@OOO
(The two cases on the other end will be symmetric)
Firing an unlimited amount of times from @OOOO will produce @XOOO. If you move to the second square, then you will have O@OOO (the other starting position), since the rat could've been on square 2 and moved to the left as you moved to the right. From here, you can fire >=2 times to achieve X@XOO.
Clearly, you must move. Moving to the 1st square again produces @XOOO, which we have already seen. Moving to the end will create XOO@O, and firing at the end will simply produce OOO@X (symmetric to @XOOO)
If we attempt to move to the third square from X@XOO, we end up with XO@OO. Firing at the third square produces OO@XO, which is symmetric to O@XOO. Since all reachable states have been enumerated and none of them contain XXXX (which means the rat cannot be anywhere and must have been shot), n=4 is not possible.
Since an array of n=4 is embedded in any n>4, and the rat can simply choose to act as if it must walk on an array of size 4 by sheer random luck, you need an infinite number of shots for n>=4.
n=1 is obviously 1, n=2 is 2, n=3 is 2, and n>=4 is infinite.

Title: Re: Minimum number of shots to kill the rat
Post by pmc on Sep 3^rd, 2013, 8:44pm

So I might be misunderstanding some part of the problem, but I think many people may be over thinking the solution.

The rat can only move left or right. It cannot stay in the same position. Also, we know the location of the rat in the array.

So let's set up the first n cases (I picked n=5).

n = 1, s (shots) = 1. Obviously. (The rat can't move.)

n = 2, s = 1. Obviously. (The rat can only move to the one open space.)

n = 3, s = 2. [ ][x][ ] is the only case where s > 1. (Edge cases are always = 1, because we know where the rat will move.) It can go left or right, if we miss then we know that the rat will have to move back to the center.

n = 4, s = 2. [ ][x][ ][ ] and the mirror [ ][ ][x][ ] are also s = 2. We know that the rat can move left or right, so we would want to guess on the side of the longer side so that in the chance that we would miss, we can ensure that we make less guesses as we approach the rat one index at a time.
e.g. [ ][x][ ][ ] -> [x][ ][o][ ] -> [ ][xo][ ][ ], x = rat, o = laser

n = 5, s = 3. If the rat is on the ends of the array, s = 1. If the rat is on the second to last index of the array (like the example shown above), we know that s = 2. The next case to consider is if the rat is in the middle of the array. To guarantee that we kill the rat, we have to consider the worst possible case scenario, meaning that all of our intelligent guesses are by chance wrong. It should then be clear to see why s = 3.
i.e. [ ][ ][x][ ][ ] -> [ ][x][ ][o][ ] -> [x][ ][o][ ][ ] -> [ ][xo][ ][ ][ ]

So a quick look at the numbers shows that s = (n+1)/2 with integer division. Let's analyze if the answer makes sense. Obviously it is possible for us to hit the rat on the first guess, but because the problem asks us the 'guaranteed' number of guesses until the rat is killed, we have to assume that the rat the luckiest of all rats. Because we are only guaranteed predictable movement from the rat when it reaches the end (because it can only move in one direction from that point), we have to slowly drive it to the end of the array. That is why we have to make (n+1)/2 guesses, because we start from the middle (considering arrays also with an even number of indices) and slowly move towards the end.

I hope that makes sense, but moreover is right.

Title: Re: Minimum number of shots to kill the rat
Post by towr on Sep 3^rd, 2013, 10:26pm

on 09/03/13 at 14:11:45, Fellius wrote:

Sorry, it seems I have misread the question and didn't notice that re-aiming the laser also counts as a move. (There's a very similar puzzle floating around without that additional constraint.)

on 09/03/13 at 20:44:29, pmc wrote:

The rat can only move left or right. It cannot stay in the same position. Also, we know the location of the rat in the array.

I don't think we should assume to know the position of the rat. That makes it rather too easy.

Title: Re: Minimum number of shots to kill the rat
Post by davkrs on Sep 5^th, 2013, 2:41pm

on 09/03/13 at 22:26:45, towr wrote:

I don't think we should assume to know the position of the rat. That makes it rather too easy.

Exactly, we should not assume to know the position of the rate.

If we knew the position, we can kill the rat in constant steps

Title: Re: Minimum number of shots to kill the rat
Post by davkrs on Sep 5^th, 2013, 2:42pm

on 09/03/13 at 22:26:45, towr wrote:

(There's a very similar puzzle floating around without that additional constraint.)

Can you post the link to that other puzzle.

Title: Re: Minimum number of shots to kill the rat
Post by Grimbal on Sep 7^th, 2013, 4:01pm

Here are some related problems
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1132524701
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1131519823
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1218583902

Title: Re: Minimum number of shots to kill the rat
Post by davkrs on Sep 10^th, 2013, 2:34pm

Ok, to make things easier, what is the solution when the additional constraint is removed.

Additional constraint being removed: Rat will not move when laser gun is repositioned, it moves only after you shoot the gun.