Harder Interview Question

[slickpoppa]

I thought the Russian Roulette question was pretty easy. But here is a question that I thought was pretty tough and some of you might enjoy:

You are in a boat in the exact center of a perfectly circular lake. There is a goblin on the shore of the lake. The goblin wants to kill you. The goblin can't swim and doesn't have a boat. Provided that you can make it to shore and the goblin isn't there to grab you, you can always outrun him on land and get away. The problem is this: The goblin can run four times as fast as the maximum speed of your boat. He has perfect eyesight and is completely logical. he will do anything in his power to catch you. How can you make it to land and escape the goblin?

[peachy]

swim for it??

[slickpoppa]

[ QUOTE ]
swim for it??

[/ QUOTE ]
no, you have to stay in the boat. assume that you can't swim

[RocketManJames]

Ok, I'll give this a try... and I'm gonna do a lot of handwaving, because I did not work out the math.

There doesn't exist any spot in the circle where you are 1/4 the distance to a point on the shore as compared to the goblin's distance to that same point. So, I think that if you spiral out from the center, constantly changing your direction, that'd be your only chance.

Now... if you spiraled out in a systematic way and the goblin was completely logical, he'd probably figure you out. So, you'd need to have some randomizer in there to determine just how tight/loose the spiral. And so that's a lot of handwaving, I just can't think of any other way. You essentially need to fake the goblin out, and by constantly varying your trajectory (by spiraling), you might eventually end up where you tricked the goblin into a spot where you are less than 1/4 the distance to a point on shore as compared to the goblin.

I do not mean that you'd change the direction of your spiral, you'd randomize how tight the spiral was and keep on going with that.

How'd I do?

-RMJ

[slickpoppa]

think about it some more. there is an answer that is much less hand wavy

[Duke]

[ QUOTE ]
think about it some more. there is an answer that is much less hand wavy

[/ QUOTE ]

Yeah, just travel in the complex plane and he won't see you until you're already on shore, opposite him.

~D

[RocketManJames]

Ok, so if you always have your heading towards the opposite shore as the goblin... you essentially are doing a spiral. However, I am unable to really convince myself that the guy makes it safely.

Maybe I'm really missing something here.

I tried to break it down into smaller time-steps, and hand calculating out the positions of both goblin and the boat, but it's getting really tedious. However, it does seem that even with the step sizes I was using, the distance you are from the 'opposite goblin' point is closer than before, and so the goblin always has to go the full distance, and since you're closing in, you should beat him. I dunno, still sounds like a lot of handwaving.

-RMJ

[RocketManJames]

Never mind my gibberish... Duke got it. I'm posting his solution on his behalf, and because I am too dumb to get this one myself.

His solution in white:

<font color="white">
Without loss of generality, assume radius = 1.

1) Take boat just a shade under 0.25 towards shore, it doesn't matter which heading. So, let's say 0.24.

2) Now, you can circle along this inner circle (radius = 0.24) faster than the goblin can circle the big circle (in terms of angular movement), since your circumference is less than 1/4 the big circle. You can actually choose any inner radius that is in the range (R/pi, R/4), but I chose 0.24 for simplicity of explanation.

3) Since you can do this, you can keep circling until you are exactly opposite the goblin. You have full control due to your ability to lap him in this circular movement game.

4) Now that you are exactly opposite him, go to shore. Goblin has to go about 3.14 distance. You have to go 0.76. 3.14 &gt; 4 * 0.76, so you make it.

</font>

-RMJ

[Duke]

That basically requires you to have GPS on you and the goblin. In actuality, I'd probably head right for him and take my chances with the oar as my weapon.

I hate goblins.

~D

[dansalmo]

If you head straight for shore opposite of where the goblin is standing, you he will get there first since he only has go ~3.14 (pi) times as far but can do it 4X as fast. His problem is that once he commits to a direction, you can stear away from him at an angle that will make him have to go greater than 4x the distance you must row. This has to be done gradually at first to keep him committed to his direction. If this is a real problem that could be worked out while rowing, then my guess is to row keeping your back to the goblin until you reach about half way to shore then head stright to shore. You would want to hit shore at about a 60 degree angle from your original heading such that the goblin has to run more than 4x your rowing distance. The path would look like a gradual arc that straightens out as you get closer to shore.

[Duke]

That won't work because the relation of chord lengths along the circle to your curved path isn't great enough to make the goblin lose to you in the race. You can make him run farther than halfway around the pond, but work it out and you'll see that you're traveling so far to screw him over that he beats you anyhow. He's 4x as fast as you for a reason. You only gain time within that inner radius of R/4.

~D

[jimdmcevoy]

I think this is it:

You travel in a circle around the centre of the lake, and the radius of the circle you travel is .24 of the radius of the whole lake.

Doing this will eventually result in a situation where you are .24 radius's from the centre of the lake, and the goblin will be on the opposite side of the lake, 1.24 radius's away.

As soon as you are in the situation you change course 90 degrees picking the quickest route to the shore. The goblin has to run Pi radius's to catch you, but you only have to sail .76 radius's, and since .76*4&lt;Pi you'll make it.

[gaming_mouse]

[ QUOTE ]
That won't work because the relation of chord lengths along the circle to your curved path isn't great enough to make the goblin lose to you in the race. You can make him run farther than halfway around the pond, but work it out and you'll see that you're traveling so far to screw him over that he beats you anyhow. He's 4x as fast as you for a reason. You only gain time within that inner radius of R/4.

[/ QUOTE ]

Duke,

Your answer is the only rigorous one I can think of. At the same time, it is not clear to me that the above solution DOESN'T work. I cannot see a way to make it rigorous, but that doesn't mean it can't work. Can you rigorously show that the above CANNOT work? I don't follow your statement about the relation of chord lengths...

[Duke]

Nice work. I'm not quite sure what I mean by that.

~D

[Duke]

[ QUOTE ]
Duke,

Your answer is the only rigorous one I can think of. At the same time, it is not clear to me that the above solution DOESN'T work. I cannot see a way to make it rigorous, but that doesn't mean it can't work. Can you rigorously show that the above CANNOT work? I don't follow your statement about the relation of chord lengths...

[/ QUOTE ]

The way I convinced myself that a spiral path would backfire was by reducing a spiral to going half-way, making a sharp left, or right, and then heading to shore like that. I compared the distance that the goblin would have to travel with the original distance and found that the ratio of the length of his path to the length of my path actually lessened.

I had to do this, because the "spiral" approach was in my head.

That proved to me that you only cost yourself time at some point by moving in that spiral pattern, so I moved on to when/how/why you actually gained any time (or distance) over the goblin.

And the closer you get to the edge, the closer your path and the goblins path will be in terms of distance, because you're spiraling. This is horrible because he moves 4x as quickly as you. The spiral will actually work to start, if at R/4 out you immediately head for shore in a straight line and stop spiraling.

So... it doesn't work because the longer your path is outside of that inner R/4 radius, the closer your path approximates his as far as length goes. If you chop it up into smaller slices (turn every time you travel some smaller distance) you'll find that the length of your eventual path is even more closely related to that of the goblin. It's far easier to fall back to a discrete approximation than to define some smooth curves, but you'll see that the smaller step size doesn't help you nearly enough (his ability to get there rises far too quickly).

I hope that makes sense as to why the spiral will fail. And by spiral, I mean turning at all (his motion defines your spiral in some sense).

~D

[gaming_mouse]

Yes, makes perfect sense. Nice explanation.

gm

[TomCollins]

Make a line from the goblin to yourself. Continue that line to the opposite shore. Always steer the boat following that line.

This appears to not neccisarily work after further thought.

[Duke]

[ QUOTE ]
You can actually choose any inner radius that is in the range (R/pi, R/4)

[/ QUOTE ]

I messed this up the first time. It's really between (4-pi)R/4 and R/4.

~D

[jimdmcevoy]

For extreme nerds I propose the following question...

What is the quickest way to get to the shore and escape?

Assuming the boat travels with speed 1 radius per second, the best I can come up with is a time of:

[Pi-ln(Pi-3)]/(4) seconds

actually, it has to be a hair longer, as you would perfectly meet the Goblin at the shore.

This solution is done by traveling directly opposite the goblin and keeping the centre of the circle directly between you and the goblin, until you are a distance 1-Pi/4 radius's from the centre of the circle, and then you just head straight for the shore.

The equations of motion are:

r(t)=[1-exp(-4t)]/4 when t&lt;=-ln(Pi-3)/4
r(t)=1-Pi/4+t when t&gt;-ln(Pi-3)/4

where r(t) is in units of radius's

and

Theta(t)=4*t when t&lt;=-ln(Pi-3)/4
Theta(t)= -ln(Pi-3) when t&gt;-ln(Pi-3)/4

Where Theta(t) is in units of radians

This would intuitivly seem the quickest way, but I am not sure, so can anyone out there prove this is the quickest or find the quickest way?

[JayDeeBlackOut]

someone draw the solution out so my tilting, fatigue-addled brain can comprehend it!

[pzhon]

[ QUOTE ]
the longer your path is outside of that inner R/4 radius, the closer your path approximates his as far as length goes.

[/ QUOTE ]
It is not optimal to minimize the length of your path outside the R/4 inner circle. Moving directly toward the shore works, but it does not maximize the distance between you and the goblin when you reach the shore.

Moving perpendicular to the shore is inefficient. Suppose the lake is very large so that the shore is almost straight, and represented by the points (x,0). If you are 10m from the shore at (0,10), and the goblin is at (-39,0), you will be caught if you head directly for the shore. You can evade the goblin by going to (2,0), which is 10.198m away. When you reach (2,0), the goblin would move 40.792m to (1.792,0).

The most efficient path is a straight line at an angle of arccos(1/4) ~ 75.52 degrees with the shore. (Aim for (10/Sqrt(15),0) = (2.58,0) in the above example.) Stategies involving such lines (at appropriate angles) allow you to escape if you speed up the goblin to the point when following a radius fails.

Sequel 1: What is the maximum distance you can ensure between yourself and the goblin when you reach the shore, in radians? <font color="white">.586725 radians</font>

Sequel 2: What is the minimum speed of the goblin (as a multiple of yours) that allows the goblin to catch you? <font color="white">4.60334 times your speed</font>

[gaming_mouse]

[ QUOTE ]
The most efficient path is a straight line at an angle of arccos(1/4) ~ 75.52 degrees with the shore.

[/ QUOTE ]

Can you explain this?

[reubenf]

I row the boat sideways to the shore so that the bow and stern hit the shore at the same time. If I can outrun him on land, I can outrun him on the boat.

[pzhon]

[ QUOTE ]
[ QUOTE ]
The most efficient path is a straight line at an angle of arccos(1/4) ~ 75.52 degrees with the shore.

[/ QUOTE ]

Can you explain this?

[/ QUOTE ]
Imagine your luggage is on a conveyor belt moving 4 times as fast as you do. You spot your luggage. Which path toward the conveyor belt gives you the most time to elbow people out of the way before your luggage arrives?

Suppose you are 1 unit away from the conveyor belt. Instead of heading directly toward the closest point, aim for x units away from the closest point. This point is sqrt(1+x^2) units away from you. It takes you sqrt(1+x^2)-1 ~x^2/2 units more time to give your luggage x/4 more units of time to arrive. When x is small, x^2 is much smaller than x, so this is an improvement over going directly toward the the conveyor belt. When x is large, x^2 is large in comparison with x, so your luggage has advanced more than you have in the extra time. Between the two is an optimum. This can be found by setting the derivative of sqrt(1+x^2) equal to 1/4: x=1/sqrt(15)=.2582, so the path you travel has length 4/sqrt(15). That produces an angle not of 90 degrees, but 75.52 degrees.

[gaming_mouse]

nice.

[Duke]

[ QUOTE ]
The most efficient path is a straight line at an angle of arccos(1/4) ~ 75.52 degrees with the shore. (Aim for (10/Sqrt(15),0) = (2.58,0) in the above example.) Stategies involving such lines (at appropriate angles) allow you to escape if you speed up the goblin to the point when following a radius fails.

[/ QUOTE ]

I immediately discounted this thinking that the goblin would run the other way around and get you if you started on an indirect path. I'm now trying to figure out at which point you -can- turn and buy yourself some time. It's obviously not at R/4. I don't yet see it.

~D

[slickpoppa]

[ QUOTE ]
[ QUOTE ]
the longer your path is outside of that inner R/4 radius, the closer your path approximates his as far as length goes.

[/ QUOTE ]
It is not optimal to minimize the length of your path outside the R/4 inner circle. Moving directly toward the shore works, but it does not maximize the distance between you and the goblin when you reach the shore.

Moving perpendicular to the shore is inefficient. Suppose the lake is very large so that the shore is almost straight, and represented by the points (x,0). If you are 10m from the shore at (0,10), and the goblin is at (-39,0), you will be caught if you head directly for the shore. You can evade the goblin by going to (2,0), which is 10.198m away. When you reach (2,0), the goblin would move 40.792m to (1.792,0).

The most efficient path is a straight line at an angle of arccos(1/4) ~ 75.52 degrees with the shore. (Aim for (10/Sqrt(15),0) = (2.58,0) in the above example.) Stategies involving such lines (at appropriate angles) allow you to escape if you speed up the goblin to the point when following a radius fails.

Sequel 1: What is the maximum distance you can ensure between yourself and the goblin when you reach the shore, in radians? <font color="white">.586725 radians</font>

Sequel 2: What is the minimum speed of the goblin (as a multiple of yours) that allows the goblin to catch you? <font color="white">4.60334 times your speed</font>

[/ QUOTE ]
Sorry, but I have no idea what you are saying

[Duke]

[ QUOTE ]
Sorry, but I have no idea what you are saying

[/ QUOTE ]

What he's saying, correctly, is that it's more efficient to go at an angle than directly at the target, because the increased travel path for you isn't as much as the path that you're creating by your angular movement for the opponent.

Think horse racing. They all start in a line, but it's only like 6" or something farther to take a beeline for the inside corner from the outside than it is to go straight on the inside at that same inside corner. You traveled 6" further, and "gained" the width of the track on a pursuer taking the goblin's route.

~D

[Paul2432]

Or you could think football. Ball carrier and defender are both on the 50 yard line, but 10 yards apart. If the ball carrier runs at an angle towards the endzone away from the defender, he can score a touchdown versus a faster defender than he could running directly towards the endzone.

Paul

[reubenf]

Nobody likes my solution? /images/graemlins/frown.gif It requires much less paddling.

[tylerdurden]

Always head for the point on the opposite side of the circle from the goblin (i.e. at the other end of the diameter from the goblin through the center of the circle).

(You have to constantly update your course as the goblin moves for this to work.)

[pzhon]

Imagine the goblin starts at (-1,0) and moves counterclockwise. Imagine you start at (1/4,0) and move straight up to (1/4,sqrt(15/16)). Although it is shorter for the goblin to go clockwise to your destination, the goblin is always within 180 degrees of you in the counterclockwise direction, so the goblin is always heading in the best direction. If the goblin ever turns around, you can move radially outward until the goblin is trying to decrease the angle he makes with your current position.

[reubenf]

[ QUOTE ]
Always head for the point on the opposite side of the circle from the goblin (i.e. at the other end of the diameter from the goblin through the center of the circle).

(You have to constantly update your course as the goblin moves for this to work.)

[/ QUOTE ]

It has been pointed out in this thread that this does not work. Only while you are close to the center (with 1/4 the radius of the pond) are you able to spiral faster than he is. If you constantly paddle away from him, he will end up pushing you back toward the center and you'll never make it to shore.

[tylerdurden]

Ah, yeah, I see what you're saying. I haven't read all the replies yet, as I'm still trying to figure this one out.

[Stork]

Haven't read the other replies yet, but I'm thinking you start going towards him until you are right next to the shore where he is waiting, then right before you hit shore, you do a complete 180 and sail directly away from him and then you should make it to the opposite side going in a straight line before he can get there running half the circumfrence of the lake.

Edit: If this works at all, it only will work when D&lt;pi.