How to escape a monster (using calculus)(datagenetics.com)
datagenetics.com
How to escape a monster (using calculus)
http://www.datagenetics.com/blog/october12013/index.html
13 comments
I think the "perfect J" comes from the fact that we are solving the instance with the critical value K = 4.60333... If K were any greater than this, we couldn't escape.
If K were less though, an "open J" path (like Path #2) would also work.
If K were less though, an "open J" path (like Path #2) would also work.
You can recover the "perfect J" by phrasing the problem as "find the path that results in the monster having been waiting for you at the shore for the least time, or if he's too slow, that results in the maximum distance from the monster when you exit the lake". The best path is always the best path.
What really bothers me about the solution presented is that the (optimum) angle of escape is clearly exactly pi / 2, computed as the arcsine of 1. That's going to be exactly 1, but it's computed here as 4.603339 cos 1.351817, which is only approximate. There must be a solution that gives you the exact value; that's the one I want to see.
What really bothers me about the solution presented is that the (optimum) angle of escape is clearly exactly pi / 2, computed as the arcsine of 1. That's going to be exactly 1, but it's computed here as 4.603339 cos 1.351817, which is only approximate. There must be a solution that gives you the exact value; that's the one I want to see.
The 'exact' answer for the angle you need to row (alpha) is Sin(alpha)=KCos(Phi).
Yes, the 'exact' answer is the tangent. If you want the relationship between K and Phi, then:
K = Cos(Phi) + SQR( (pi+phi)^2 - sin^2(phi))
The derivation of both of these is contained in the article.
Yes, the 'exact' answer is the tangent. If you want the relationship between K and Phi, then:
K = Cos(Phi) + SQR( (pi+phi)^2 - sin^2(phi))
The derivation of both of these is contained in the article.
continuous time games are very messy. Defining the correct notion of Nash equilibrium can be very hard since a player might "respond" to another player's strategy epsilon time after that player "moves". Of course when there is a Nash equilibrium that makes sense, it's all the more interesting.
I first saw this puzzle when it was the monthly "Ponder This" challenge from IBM Research. If you like it, you might enjoy looking through their archives: http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/pages/in...
In the middle section, what prevents the monster from running clockwise, and thus making paths 2 and 3 suboptimal?
It's not clear, but the assumption is that the monster is already running. Once the monster picks a direction (assuming instantaneous acceleration and whatnot), Path 3 is the limit for which turning around makes sense for the monster. So you row the boat in tight circles getting the monster going until you get to the circle of safety, then you can choose from anywhere between Path 1 to Path 3 to get to the shore before the monster can make it to you, with our without running in the opposite direction.
Yeah, so the solution to the problem ignore the rule mentioned on the 1st paragraph of the page about it always going the shortest route or doing the most clever thing or something.
The determinant factor is not the direction, but the current angle of both entities.
The monster will always have to run towards the direction where the angle between itself and the boat is smaller, otherwise it'd be choosing a longer path.
In facts, if at some point the monster decides to go clockwise, the boat could simply choose the symmetrical direction compared to the relative position of the monster.
This being sad, I'm not sure I am convinced that no other trajectory can be faster, since many of the arguments seem to be a little too wavy.
The monster will always have to run towards the direction where the angle between itself and the boat is smaller, otherwise it'd be choosing a longer path.
In facts, if at some point the monster decides to go clockwise, the boat could simply choose the symmetrical direction compared to the relative position of the monster.
This being sad, I'm not sure I am convinced that no other trajectory can be faster, since many of the arguments seem to be a little too wavy.
How can I help convince you?
- I hope you agree that, until you breach the circle of safety, it does not matter what the strategy, as you have control to adjust relative positions to anywhere? So, it's all about how to get from the edge of the circle of safety to the shore.
- I hope you can agree that the path from the circle of safety to the shore is a straight one? After all, if you elected for a curved path you would be wasting time. (Any curved path you took between point A and B is inefficient as it would be longer than the straight line connecting the two points. If it is longer, it would take more time. This is bad!)
- So now, we know we need to connect a line from the circle to the shore. We are starting with the monster as far away from us as possible, and we then select where we draw the line.
- In the article I show that the line can be anywhere in a 90 degree sector (it's pretty obvious that outside of these 90 degrees is not too).
- With these constraints, I use trigonometry and calculus to find the maximum.
I'll be happy to re-clarify things in more detail if you let me know which of these arguments is "a little too wavy".
- I hope you agree that, until you breach the circle of safety, it does not matter what the strategy, as you have control to adjust relative positions to anywhere? So, it's all about how to get from the edge of the circle of safety to the shore.
- I hope you can agree that the path from the circle of safety to the shore is a straight one? After all, if you elected for a curved path you would be wasting time. (Any curved path you took between point A and B is inefficient as it would be longer than the straight line connecting the two points. If it is longer, it would take more time. This is bad!)
- So now, we know we need to connect a line from the circle to the shore. We are starting with the monster as far away from us as possible, and we then select where we draw the line.
- In the article I show that the line can be anywhere in a 90 degree sector (it's pretty obvious that outside of these 90 degrees is not too).
- With these constraints, I use trigonometry and calculus to find the maximum.
I'll be happy to re-clarify things in more detail if you let me know which of these arguments is "a little too wavy".
I liked the website and the idea. I didn't mean 'wavy' as offensive, but just that this above may be correct assumptions, but I fail to see whether or not are mathematically rigorous.
For example. I agree that within the circle of safety you can readjust your position however you want, given enough time for you to readjust.
What I don't necessarily see, is that one straight line is the best way to maximize the escape. For example, I could consider going at pi/2 for a bit, having the monster trying to catch up counter clock wise, and then slightly bend toward pi/2 + alpha.
This may be wrong, and maybe it's easy to see, but I failed at understanding whether or not that is possible from the explanation. After all, it's a similar strategy to the pi/2 one. I.e., the monster will have to get there covering more space. This would be very different from aiming at that point when you are at the edge of the safety circle, since now the monster is at a different relative position. So it depends on whether or not there is no solution that gives you some extra time.
For example, why is a spiral (that keeps being a spiral after leaving the safety circle) worse than a J shape? (same point as above but with a curve instead of two straight lines at an angle).
Another point is the optimal strategy for the monster. If the monster waits for a second waiting for you to move, would pi/2 still be the best strategy?
To be honest I think that the solution sounds perfectly reasonable. I just thought I wasn't mathematically 100% convinced.
And I liked the website and the other puzzles (I'm still thinking about the Ace of Spade, on which I have a question).
For example. I agree that within the circle of safety you can readjust your position however you want, given enough time for you to readjust.
What I don't necessarily see, is that one straight line is the best way to maximize the escape. For example, I could consider going at pi/2 for a bit, having the monster trying to catch up counter clock wise, and then slightly bend toward pi/2 + alpha.
This may be wrong, and maybe it's easy to see, but I failed at understanding whether or not that is possible from the explanation. After all, it's a similar strategy to the pi/2 one. I.e., the monster will have to get there covering more space. This would be very different from aiming at that point when you are at the edge of the safety circle, since now the monster is at a different relative position. So it depends on whether or not there is no solution that gives you some extra time.
For example, why is a spiral (that keeps being a spiral after leaving the safety circle) worse than a J shape? (same point as above but with a curve instead of two straight lines at an angle).
Another point is the optimal strategy for the monster. If the monster waits for a second waiting for you to move, would pi/2 still be the best strategy?
To be honest I think that the solution sounds perfectly reasonable. I just thought I wasn't mathematically 100% convinced.
And I liked the website and the other puzzles (I'm still thinking about the Ace of Spade, on which I have a question).
Any path that is not straight could have been reached sooner by going on the straight line connecting: The shortest distance between two opposite corners on a rectangle is the diagonal line between them. Any curve you draw connecting them is longer. Any curved path you run gets you to the same point later than you could have got to it at if you went directly there. Outside of the circle of safety, it has to be a straight path.
A spiral is also not going to work outside the circle of safety, as the monster has a higher angular velocity; he moves around the shore faster than your projection to the shore.
A spiral is also not going to work outside the circle of safety, as the monster has a higher angular velocity; he moves around the shore faster than your projection to the shore.
Nice! I worked out something much more basic for how to outrun a crashing spaceship: http://www.win-vector.com/blog/2012/06/how-to-outrun-a-crash...
I feel like a zigzag pattern would work here as well. Keep the monster switching directions. Essentially, the monster is balanced perfectly on the opposite side of the lake from the one you are headed towards.
The monster is a smart monster. He knows that, once you leave the safe circle, he has a higher angular velocity. So, as soon as you pass that threshold, he will start to run around the lake. It does not matter which direction he initially takes, but once moving is committed to that direction (if he were to reverse direction, he would end up, in the future at the same point he was once at, but at a later time, and you would be nearer your goal; he's too smart to let that happen). Once you are outside the safety circle, he will run, and not stop running in that direction.
This problem is similar to the one OP had to solve in his interview:
https://news.ycombinator.com/item?id=6583580
DAMN..
DAMN..
Did anyone else figure it out without any calculus?
How? You mean you intuitively understood, or you can prove it your solution without calculus?
Just intuitively. Geometrically... Maybe it's from playing online games. I would kite it one direction, then escape in the other. The natural way to do that is a J shape.
I just thought in a spiral at first and then run, not exactly a J but something close.
An animation of the solved path would be awesome.
umm another naive solution for this would be to go from the center to any arbitrary end, do not cross on to the lake just wait around 2-3 meters from the bank and wait for the monster.
Once the monster reaches the bank just in a straight line to the other side.
This way you will have to cover 2r distance where as the monster will cover 3.14r (pi*r ) distance .
You will be able to out run a monster around 1.57 times your speed. Sure it is not that good enough but if your calculus isn't that good (To be honest calculus is the last thing on your mind when a monster is chasing you) and the monster is slow then you will be able to out run him.
This way you will have to cover 2r distance where as the monster will cover 3.14r (pi*r ) distance .
You will be able to out run a monster around 1.57 times your speed. Sure it is not that good enough but if your calculus isn't that good (To be honest calculus is the last thing on your mind when a monster is chasing you) and the monster is slow then you will be able to out run him.
[deleted]
Amazing that the optimal path to land creates a perfect "J". It's solutions like this that leave me in awe-- another felt connection to mathematical truth through an emotional reaction to simplicity. It's empowering to understand a piece of it, but humbling to know it's only part of a larger system that I can't fathom. I think that's the loop that beckons mathematicians.