
October 15th, 2012, 11:40 PM
#1
[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

October 15th, 2012, 11:48 PM
#2
Re: Help with math algorithm
Here is a hint...
The shortest distance between 2 points is a straight line...
Jim
ATP BE400 CE500 (C550BSPW) CE560XL MU300 CFI CFII
"The speed of non working code is irrelevant"... Of course that is just my opinion, I could be wrong.
"Nothing in the world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and determination are omnipotent. The slogan 'press on' has solved and always will solve the problems of the human race."...Calvin Coolidge 30th President of the USA.

October 15th, 2012, 11:56 PM
#3
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?

October 16th, 2012, 12:06 AM
#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.
Jim
ATP BE400 CE500 (C550BSPW) CE560XL MU300 CFI CFII
"The speed of non working code is irrelevant"... Of course that is just my opinion, I could be wrong.
"Nothing in the world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and determination are omnipotent. The slogan 'press on' has solved and always will solve the problems of the human race."...Calvin Coolidge 30th President of the USA.

October 16th, 2012, 12:23 AM
#5
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.
Jim
ATP BE400 CE500 (C550BSPW) CE560XL MU300 CFI CFII
"The speed of non working code is irrelevant"... Of course that is just my opinion, I could be wrong.
"Nothing in the world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and determination are omnipotent. The slogan 'press on' has solved and always will solve the problems of the human race."...Calvin Coolidge 30th President of the USA.

October 16th, 2012, 04:53 AM
#6
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 05:01 AM.
Reason: fixed calculus error
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

October 16th, 2012, 10:21 AM
#7
Re: [RESOLVED] Help with math algorithm
Thanks guys,
I think I understand it now!

October 18th, 2012, 12:37 PM
#8
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 04:39 AM.

October 19th, 2012, 04:10 AM
#9
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) = 8vtd and w/2 + v*t*sin(p) <= w
that is if
w/d < 2*sin(p)/(8cos(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.

October 19th, 2012, 05:58 AM
#10
Re: [RESOLVED] Help with math algorithm
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)
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 .
Last edited by nuzzle; October 19th, 2012 at 06:09 AM.

October 19th, 2012, 07:01 AM
#11
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.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky

October 19th, 2012, 12:21 PM
#12
Re: [RESOLVED] Help with math algorithm
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.
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.

October 19th, 2012, 04:21 PM
#13
Re: [RESOLVED] Help with math algorithm
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.
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 daredevil points. If you aim for them you'll arrive at shore exactly when the water just misses you. If you aim for somewhere inbetween you'll arrive safely before the water.
Last edited by nuzzle; October 19th, 2012 at 04:41 PM.

October 19th, 2012, 09:27 PM
#14
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.
mpliam

October 20th, 2012, 12:39 AM
#15
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 underdetermined 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 02:08 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

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
OnDemand Webinars (sponsored)
