CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 44

Hybrid View

  1. #1
    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

    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

  2. #2
    Join Date
    May 2004
    Location
    45,000FT Above Nevada
    Posts
    1,539

    Re: Help with math algorithm

    Here is a hint...

    The shortest distance between 2 points is a straight line...
    Jim
    ATP BE400 CE500 (C550B-SPW) 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.

  3. #3
    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. #4
    Join Date
    May 2004
    Location
    45,000FT Above Nevada
    Posts
    1,539

    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 (C550B-SPW) 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.

  5. #5
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Help with math algorithm

    Quote Originally Posted by Vanaj View Post
    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
    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

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: Help with math algorithm

    Quote Originally Posted by D_Drmmr View Post
    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. #7
    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. #8
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Help with math algorithm

    Quote Originally Posted by nuzzle View Post
    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

  9. #9
    Join Date
    May 2004
    Location
    45,000FT Above Nevada
    Posts
    1,539

    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 (C550B-SPW) 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.

  10. #10
    Join Date
    Sep 2012
    Posts
    5

    Re: [RESOLVED] Help with math algorithm

    Thanks guys,

    I think I understand it now!

  11. #11
    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.
    mpliam

  12. #12
    Join Date
    May 2009
    Posts
    2,413

    Re: [RESOLVED] Help with math algorithm

    Quote Originally Posted by Mike Pliam View Post
    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. #13
    Join Date
    May 2004
    Location
    45,000FT Above Nevada
    Posts
    1,539

    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.
    Jim
    ATP BE400 CE500 (C550B-SPW) 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.

  14. #14
    Join Date
    Oct 2008
    Posts
    1,456

    Re: [RESOLVED] Help with math algorithm

    Quote Originally Posted by Vanaj View Post
    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.

    Quote Originally Posted by Vanaj View Post
    .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 ).

    Quote Originally Posted by Vanaj View Post
    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. #15
    Join Date
    May 2009
    Posts
    2,413

    Re: [RESOLVED] Help with math algorithm

    Quote Originally Posted by Vanaj View Post
    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.

Page 1 of 3 123 LastLast

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured