CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: [RESOLVED] Help with math algorithm

Hybrid View

1. Junior Member
Join Date
Sep 2012
Posts
5

[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

Does anybody know what exactly needs to be done to find the optimal path? Is there an exact equation to use?

regards

2. Re: Help with math algorithm

Here is a hint...

The shortest distance between 2 points is a straight line...

3. Junior Member
Join Date
Sep 2012
Posts
5

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?

4. 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.

5. Re: Help with math algorithm

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.
Last edited by D_Drmmr; October 16th, 2012 at 04:01 AM. Reason: fixed calculus error

6. Elite Member
Join Date
May 2009
Posts
2,413

Re: Help with math algorithm

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 .
Last edited by nuzzle; October 19th, 2012 at 03:39 AM.

7. Senior Member
Join Date
Oct 2008
Posts
1,456

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.

8. Re: Help with math algorithm

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.

9. 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.

10. Junior Member
Join Date
Sep 2012
Posts
5

Re: [RESOLVED] Help with math algorithm

Thanks guys,

I think I understand it now!

11. Senior Member
Join Date
May 2002
Posts
1,798

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.

12. Elite Member
Join Date
May 2009
Posts
2,413

Re: [RESOLVED] Help with math algorithm

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.
Last edited by nuzzle; October 20th, 2012 at 01:08 AM.

13. Re: [RESOLVED] Help with math algorithm

actually you all are assuming variables not known...so I will do the same

if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.

14. Senior Member
Join Date
Oct 2008
Posts
1,456

Re: [RESOLVED] Help with math algorithm

Originally Posted by Vanaj
actually you all are assuming variables not known...so I will do the same
yes, and we can perfectly manage those "unknowns" using statistical methods, there's nothing to assume or guess.
Again, using a simplified model does not mean obtaining wrong results. On the contrary, most successful physical models work ( both theoretically and practically ) by approaching a problem via successive approximations, the reason being that the very idea of "true model" is (nearly always) meaningless theoretically , and often useless or counterproductive in practice. This is especially true when many unknowns of different nature are present and hence the qualitative structure of the solution, rather than the actual numerical values, are important.

Originally Posted by Vanaj
.as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.
nowhere the problem statement states that the decision ( including the logic behind it ) must be taken by the runner while waiting the water, that would be a totally different problem ( and heavily underspecified, being dependent on non trivial previous knowledge of the runner ... ).
If that was the real intent of the examiner then it would be a bad posed problem ( and I wouldn't work for him ).

Originally Posted by Vanaj
if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....
again, all this can be proven false, and so what ?
Last edited by superbonzo; October 21st, 2012 at 10:51 AM. Reason: typos

15. Elite Member
Join Date
May 2009
Posts
2,413

Re: [RESOLVED] Help with math algorithm

Originally Posted by Vanaj
actually you all are assuming variables not known...so I will do the same

if the water is 5 miles up stream then you can walk directly to the riverbank...else go directly to the riverbank as the delta for running away from the water, you would have to run the delta faster than the water is flowing which is 8 times what you can run...not possible....as an examiner I'm more interested in the logic used to solve the problem than trying to do trig in my head with killer water flowing at me at 8 times the speed I can run.
As I've mentioned you don't have to do trigonometry in your head because evolution has hardwired the optimal strategy into our genes. At least that's what I think. You run straight to shore slightly downstream away from the approaching water without even thinking.

But even if the water is 5 miles upstream you still may not make it. It's because the water front may have passed the point of no return for you even if you run for shore at the optimal angle.

If the water hasn't yet passed the point of no return you'll have an interval of opportunity. It will be defined by two end-points on shore. The end-points will be dare-devil points, one upstream and one downstream. If you aim for one of them you'll arrive exactly when the water does. If you aim for a point in-between you'll arrive on shore with a margin before the water.

There will be a distance to the water at which your interval of opportunity shrinks to just one point. That's the optimal point to always aim for because it allows the water to come as close to you as possible and you'll still make it. If the water comes closer it passes the point of no return, the interval of opportunity shuts down and turns imaginary, and you can no longer get in safely.

If I were the reviewer that's the insight I would be looking for together with some quite straightforward high-school math & physics reasoning and calculations.
Last edited by nuzzle; October 22nd, 2012 at 07:06 AM.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•