[RESOLVED] Help with math algorithm
Hi,
I recently applied to a job and took a programming test. I didn't hear back, so I'm assuming I didn't get the position. I was able to answer all of the questions except one. I'm trying to find out what the answer is because its been bugging me, but I'm not having any luck. The question is a math calculation.
A man is standing in the middle of a long dry riverbed when he sees a wall of water heading towards him. If the water is moving at 8 times the speed at which the man can run, then he’ll have the best chance of escape by running:
A) Straight toward a river bank
B) Toward a bank, but at a slight angle away from the water
C) Away from the water, but at a slight angle toward the bank
Give a short explanation of your reasoning. Establish your answer mathematically.
Does anybody know what exactly needs to be done to find the optimal path? Is there an exact equation to use?
Thanks for any help you can offer.
regards
Re: Help with math algorithm
Here is a hint...
The shortest distance between 2 points is a straight line...
Re: Help with math algorithm
But aren't all of the options a straight line? I'm assuming you mean answer A) head straight for the river bank? But wouldn't you have a better chance running at a slight angle away from the water so you increase your distance from the encroaching water as you run?
Re: Help with math algorithm
Since the water moves 8 times faster that you can run, running in the same direction as the water, even a small angle, would be wasting time.
Re: Help with math algorithm
They were probably more interested in how you would logically approach the problem than an answer to the problem...
You would need to know 3 variables first....
distance to the water...
distance to the riverbank...
the speed you can run... (can get speed of the water from this)
With these known variables it is just a time/speed calculation.
Re: Help with math algorithm
Quote:
Originally Posted by
Vanaj
Since the water moves 8 times faster that you can run, running in the same direction as the water, even a small angle, would be wasting time.
Running at an angle is not a waste if the extra distance from the water compensates for the extra time it takes you to run a longer stretch.
If x is the shortest distance to the bank and y is the distance along the bank between the point you are running to and the point on the bank closest to you (meaning you are running away from the water y distance), then the distance to reach the bank is sqrt(x^2 + y^2). The time you gain is y/8. So if sqrt(x^2 + y^2) - y/8 <= x, it's better to run at this angle then straight towards the bank. That solves as 0 <= y <= 16*x/63. Since its quadratic, the minimum will be at y = 8*x/63.
Re: [RESOLVED] Help with math algorithm
Thanks guys,
I think I understand it now!
Re: Help with math algorithm
Quote:
Originally Posted by
D_Drmmr
the minimum will be at y = 8*x/63.
It depends on what you're optimizing. I've looked at minimizing w which is the distance between the runner and the approaching water when he starts running. For a given y and x this formula gives the w for which runner and water arrive at y simultaneously,
w = sqrt(x^2 + y^2) * 8 - y
The square root is the distance the runner runs to get to the riverbank a distance y downstream. Runner and water arrive at y at the same time but the water has travelled 8 times longer to get there hence the 8. Finally y is subtracted to give w, the distance between water and runner when he started to run.
In my view it makes most sense for the runner to aim for the y which gives the smallest possible w. W is the point of no return really. If the water gets closer you won't make it regardless of how you run. By running towards the y that puts w the closest to you will give you the best chance of making it regardless of how far away the water actually is when you start.
So what y gives the smallest w? Well according to my calculations it's y = x/sqrt(63). This differs from the y = 8*x/63 that D_Drmmr got so lets set x=1 and calculate w for the two y values.
w (1/sqrt(63)) = 7.937253933
w (8/63) = 7.937257808
Amazingly the results differ only after the fifth decimal. But mine is smaller so it's more optimal :).
Re: [RESOLVED] Help with math algorithm
here is another pov ( IMO a more correct solution ). If w is the riverbed width, v the runner speed, d > 0 the distance of the water front from the runner at time 0 and p the angle giving the runner direction, as measured CCW from the (0,-1) versor, we have
the trajectory of the runner: ( w/2 + v*t*sin(p), v*t*cos(p) )
the trajectory of a water front point: ( 0, 8*v*t - d )
then the runner will escape iff the following equation has no solution
v*t*cos(p) = 8vt-d and w/2 + v*t*sin(p) <= w
that is if
w/d < 2*sin(p)/(8-cos(p))
so the best chance of escaping ( cosidering that he may not be able of estimating w/d with sufficient accuracy ) si attained by maximizing the rhs: this gives p = arccos(1/8) ~ 83°. Hence the correct answer is B.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
this gives p = arccos(1/8)
Adapting my solution to that I get this,
p = arctan(sqrt(63))
which doesn't look at all what you have but I consulted an old math handbook and,
arctan(sqrt(63)) = arccos(1/sqrt(1 + sqrt(63)^2)) = arccos(1/8)
so our solutions are in fact identical! (although our approaches differ a lot)
Quote:
Hence the correct answer is B.
I wouldn't be at all surprised if we're actually genetically programmed to make the right choise here. It feels so natural to run straight for shore but slightly away from the roaring white water front. I wonder how many poor apemen it took to firmy established those genes in our genome :).
Re: Help with math algorithm
Quote:
Originally Posted by
nuzzle
So what y gives the smallest w? Well according to my calculations it's y = x/sqrt(63). This differs from the y = 8*x/63 that D_Drmmr got so lets set x=1 and calculate w for the two y values.
I redid the math and my first answer was wrong. It should be y = x/sqrt(63) indeed. :thumb:
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
nuzzle
so our solutions are in fact identical! (although our approaches differ a lot)
yes, but it's not obvious why one should minimize the no return point to maximize the escape chance ... indeed, note that if the runner can exactly estimate the <riverbed width>/<water front distance> ratio then any angle satisfying the disequation in post #9 will maximize the escape probability ( = 1 ). Moreover, a correlation between the estimation errors of that ratio and the angle ( for example, due to parallax effects ) could render the optimal expected angle different from our calculations; in any case, the relevant equation to solve would be that in post #9, at least for the straight motion case.
Quote:
Originally Posted by
nuzzle
I wouldn't be at all surprised if we're actually genetically programmed to make the right choise here. It feels so natural to run straight for shore but slightly away from the roaring white water front. I wonder how many poor apemen it took to firmy established those genes in our genome :).
note that if the <water speed>/<runner speed> ratio is less then sqrt(2) then the C answer becomes the right one, with no optimal angle for the ratio = 1 limit case ( unless we consider being trapped forever in the riverbed an "escape" ). So, for slow moving water ( like a tide ) or fast moving trasnport ( like a car ) the correct behavior would be reversed.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
superbonzo
yes, but it's not obvious why one should minimize the no return point to maximize the escape chance ... indeed, note that if the runner can exactly estimate the <riverbed width>/<water front distance> ratio then any angle satisfying the disequation in post #9 will maximize the escape probability ( = 1 ).
I don't quite follow your argumentation here. How does the riverbed width enter the picture? As I have it the optimal escape strategy is independent on both riverbed width and waterfront distance. At least if you assume the water front is advancing as a straight line, and you always aim for the closest riverbank, and the water is faster than you. Under these circumstances you want the point of no return to be as late as possible.
Quote:
note that if the <water speed>/<runner speed> ratio is less then sqrt(2) then the C answer becomes the right one, with no optimal angle for the ratio = 1 limit case ( unless we consider being trapped forever in the riverbed an "escape" ). So, for slow moving water ( like a tide ) or fast moving trasnport ( like a car ) the correct behavior would be reversed.
I don't understand this either. If the waterfront hasn't reached the point of no return when you start running, the optimal single y splits into an interval of opportunity with two endpoints y1 and y2. And sure, y1 can be upstream from where you stand. These endpoints could be called dare-devil points. If you aim for them you'll arrive at shore exactly when the water just misses you. If you aim for somewhere in-between you'll arrive safely before the water.
Re: [RESOLVED] Help with math algorithm
You don't need alot of complicated trigonometry to answer this. Since the question is how to maximize the PROBABILITY of the man escaping, it is obvious that running away from the water wall at a slight angle to the bank will afford the maximum probability of escape. This is a general solution of what is essentially a problem in differential calculus, but a specific solution is not possible because we don't have the actual speed of the water, the width of the river bed, and how close the water is to the man to start with (initial conditions). So no matter what those conditions are, running at an angle away from the water gives him the best chance, but does not guarantee that he will escape.
Re: [RESOLVED] Help with math algorithm
Quote:
Originally Posted by
Mike Pliam
You don't need ........
You're wrong.
I agree that the instinctive response is what you indicate namely to head straight for shore slightly downstream but that doesn't make it obvious. The question asks for an informed explanation backed up by math, not mere guessing and handwaving. This is perfectly possible and the math is not complicated.
You're claiming that the problem is under-determined but it isn't. With the information given it's possible to establish how to optimally run to have the best chances of escaping the water. It's been shown in this thread already.
And the optimal angle is arctan(1/sqrt(63)) radians. That's approximately 7.2 degrees (downstream from running straight to shore). And it's regardless of the width of the river and where you stand on the riverbed and where the waterfront is when you start running. The only thing you need to know is how much faster the river is than you and in this case it's 8 times. This angle gives you the best chance of survival because it lets you make it dry to shore with the advancing river front the closest to you.