9 ms·

Solving xkcd's raptor problem

66 points by dons 16y ago

harpastum 16y ago
Interesting. Haven't had time to fully create my own solution; I'll have to work on it tonight. If anyone wants what I've got so far (ruby): http://codepad.org/qggAcIKy http://codepad.org/qggAcIKy
roschdal 16y ago
What about problem #3 of http://xkcd.com/135/ http://xkcd.com/135/ ? Will xkcd ever publish the floor plan from the next page where you escape from the raptors?
- jpwagner 16y ago
  Remember, they do not know fear
- dutchflyboy 16y ago
  About that, has anyone noticed the test isn't very consistent? In the first exercise the speed of a raptor is 25 m/s, in the second exercise the wounded raptor runs at 10 m/s. So far, so good. But in the third exercise the raptors run at 10 m/s. Why, are they wounded? And of course, can the raptors chew through walls?
  - orangecat 16y ago
    in the third exercise the raptors run at 10 m/s. Why, are they wounded? The third exercise is inside a building, where obstructions and narrow paths slow them down.
    - deleted 16y ago
      [deleted]
adharmad 16y ago
An analytical solution would be nice in addition to the simulation one. Even better if the number of sides of the polygon could be parametrized :)
- merraksh 16y ago
  The optimal solution, i.e. the human's trajectory, is a function and therefore has to be found through variational calculus. Not sure there is an analytical one, but the optimum should be quite easy to find numerically.
- phreeza 16y ago
  My guess would be that there is a relatively simple analytical solution iff the raptors are allowed to accelerate infinitely, but the capped speed probably makes it a bit more difficult.
mitko 16y ago
Apparently, from the plot seems that if you are faster than the slow raptor, your best direction is not straight at it, but nearby. This makes some sense because if you you are close to the slow one and far of the fast ones you can outrun go around the slow one.
andrewljohnson 16y ago
Why use we instead of I? There is just one author and the we convention used for papers with multiple authors is inappropriate and misleading. Just a small quibble... the article was otherwise fine if you like that sort of thing.
- dutchflyboy 16y ago
  I think the we is used so the user takes part in the thinking process.
- jules 16y ago
  We = the author and the reader.
- sundarurfriend 16y ago
  A polite expression of opinion here has been downvoted, and a comment elsewhere that just informs that this question appeared in someone's exam has been upvoted _twice_!
allanmac 16y ago
This looks like a variant of the "Lion and Man" problem which is also described as a "bounded pursuit" problem in the operations research journals: http://www.google.com/search?q=lion+and+man+problem+&ie=utf-8 http://www.google.com/search?q=lion+and+man+problem+&ie=... -and- http://mathworld.wolfram.com/PursuitCurve.html http://mathworld.wolfram.com/PursuitCurve.html -and- http://books.google.com/books?id=HeESjfM2geUC http://books.google.com/books?id=HeESjfM2geUC (good!) This problem may have had relevance in World War II all the way to the present: dogfights between airplanes, battleships trying to sink each other, etc.
- Groxx 16y ago
  Wolfram is frightening in its completeness... I should really look into their setup some time. Anyone have any suggestions for starting it? From what I've gathered, it's a bit different than other math texts / different conceptual basis.
kingkawn 16y ago
i had to take an intro calc class recently, my professor put this problem on the final exam.
KERMIT 16y ago
I wish that somebody would solve the "funny" problem with xkcd. You know, make it so that they're actually funny.
harpastum 16y ago
I've created a quick graph [1] of the survival time running in a single fixed direction. While this doesn't take acceleration into account, the results agree with the article and common sense. No matter which direction you run, one of the 25 m/s raptors will catch you, so your best bet is to run directly toward the weakened one. The code's available here: http://gist.github.com/418783 http://gist.github.com/418783 [1] http://chart.apis.google.com/chart?cht=s&chd=t:0.0,1.11111111111111,2.22222222222222,3.33333333333333,4.44444444444444,5.55555555555556,6.66666666666667,7.77777777777778,8.88888888888889,10.0,11.1111111111111,12.2222222222222,13.3333333333333,14.4444444444444,15.5555555555556,16.6666666666667,17.7777777777778,18.8888888888889,20.0,21.1111111111111,22.2222222222222,23.3333333333333,24.4444444444444,25.5555555555556,26.6666666666667,27.7777777777778,28.8888888888889,30.0,31.1111111111111,32.2222222222222,33.3333333333333,34.4444444444444,35.5555555555556,36.6666666666667,37.7777777777778,38.8888888888889,40.0,41.1111111111111,42.2222222222222,43.3333333333333,44.4444444444444,45.5555555555556,46.6666666666667,47.7777777777778,48.8888888888889,50.0,51.1111111111111,52.2222222222222,53.3333333333333,54.4444444444444,55.5555555555556,56.6666666666667,57.7777777777778,58.8888888888889,60.0,61.1111111111111,62.2222222222222,63.3333333333333,64.4444444444444,65.5555555555556,66.6666666666667,67.7777777777778,68.8888888888889,70.0,71.1111111111111,72.2222222222222,73.3333333333333,74.4444444444444,75.5555555555556,76.6666666666667,77.7777777777778,78.8888888888889,80.0,81.1111111111111,82.2222222222222,83.3333333333333,84.4444444444444,85.5555555555556,86.6666666666667,87.7777777777778,88.8888888888889,90.0,91.1111111111111,92.2222222222222,93.3333333333333,94.4444444444444,95.5555555555556,96.6666666666667,97.7777777777778,98.8888888888889,100.0|70.5,71.5,72.5,73.5,75.0,76.0,77.5,78.5,80.0,81.5,83.0,84.5,85.5,87.0,88.5,90.0,91.5,92.5,94.0,95.0,96.5,97.5,98.5,98.5,97.5,96.5,95.0,94.0,92.5,91.5,90.0,88.5,87.0,85.5,84.5,83.0,81.5,80.0,78.5,77.5,76.0,75.0,73.5,72.5,71.5,70.5,69.5,68.5,67.5,67.0,66.5,66.0,65.5,65.0,64.5,64.5,64.5,64.5,64.5,65.0,65.0,65.5,66.0,66.5,67.5,68.0,69.0,70.0,70.0,69.0,68.0,67.5,66.5,66.0,65.5,65.0,65.0,64.5,64.5,64.5,64.5,64.5,65.0,65.5,66.0,66.5,67.0,67.5,68.5,69.5,70.5|40&chxt=x,y&chs=700x400&chxr=0,0,360,45|1,0,1 http://chart.apis.google.com/chart?cht=s&chd=t:0.0,1.111...
- harpastum 16y ago
  I created an interactive version of the graph, so you can enter values and see how long you would last: http://news.ycombinator.com/item?id=1390136 http://news.ycombinator.com/item?id=1390136

66 points by dons 16y ago

Interesting. Haven't had time to fully create my own solution; I'll have to work on it tonight. If anyone wants what I've got so far (ruby): http://codepad.org/qggAcIKy http://codepad.org/qggAcIKy

roschdal 16y ago

What about problem #3 of http://xkcd.com/135/ http://xkcd.com/135/ ? Will xkcd ever publish the floor plan from the next page where you escape from the raptors?

jpwagner 16y ago
Remember, they do not know fear
dutchflyboy 16y ago
About that, has anyone noticed the test isn't very consistent? In the first exercise the speed of a raptor is 25 m/s, in the second exercise the wounded raptor runs at 10 m/s. So far, so good. But in the third exercise the raptors run at 10 m/s. Why, are they wounded? And of course, can the raptors chew through walls?
- orangecat 16y ago
  in the third exercise the raptors run at 10 m/s. Why, are they wounded? The third exercise is inside a building, where obstructions and narrow paths slow them down.
  - deleted 16y ago
    [deleted]

adharmad 16y ago

An analytical solution would be nice in addition to the simulation one. Even better if the number of sides of the polygon could be parametrized :)

merraksh 16y ago
The optimal solution, i.e. the human's trajectory, is a function and therefore has to be found through variational calculus. Not sure there is an analytical one, but the optimum should be quite easy to find numerically.
phreeza 16y ago
My guess would be that there is a relatively simple analytical solution iff the raptors are allowed to accelerate infinitely, but the capped speed probably makes it a bit more difficult.

mitko 16y ago

Apparently, from the plot seems that if you are faster than the slow raptor, your best direction is not straight at it, but nearby. This makes some sense because if you you are close to the slow one and far of the fast ones you can outrun go around the slow one.

andrewljohnson 16y ago

Why use we instead of I? There is just one author and the we convention used for papers with multiple authors is inappropriate and misleading. Just a small quibble... the article was otherwise fine if you like that sort of thing.

dutchflyboy 16y ago
I think the we is used so the user takes part in the thinking process.
jules 16y ago
We = the author and the reader.
sundarurfriend 16y ago
A polite expression of opinion here has been downvoted, and a comment elsewhere that just informs that this question appeared in someone's exam has been upvoted _twice_!

allanmac 16y ago

This looks like a variant of the "Lion and Man" problem which is also described as a "bounded pursuit" problem in the operations research journals: http://www.google.com/search?q=lion+and+man+problem+&ie=utf-8 http://www.google.com/search?q=lion+and+man+problem+&ie=... -and- http://mathworld.wolfram.com/PursuitCurve.html http://mathworld.wolfram.com/PursuitCurve.html -and- http://books.google.com/books?id=HeESjfM2geUC http://books.google.com/books?id=HeESjfM2geUC (good!) This problem may have had relevance in World War II all the way to the present: dogfights between airplanes, battleships trying to sink each other, etc.

Groxx 16y ago
Wolfram is frightening in its completeness... I should really look into their setup some time. Anyone have any suggestions for starting it? From what I've gathered, it's a bit different than other math texts / different conceptual basis.

kingkawn 16y ago

i had to take an intro calc class recently, my professor put this problem on the final exam.

KERMIT 16y ago

I wish that somebody would solve the "funny" problem with xkcd. You know, make it so that they're actually funny.

harpastum 16y ago

I've created a quick graph [1] of the survival time running in a single fixed direction. While this doesn't take acceleration into account, the results agree with the article and common sense. No matter which direction you run, one of the 25 m/s raptors will catch you, so your best bet is to run directly toward the weakened one. The code's available here: http://gist.github.com/418783 http://gist.github.com/418783 [1] http://chart.apis.google.com/chart?cht=s&chd=t:0.0,1.11111111111111,2.22222222222222,3.33333333333333,4.44444444444444,5.55555555555556,6.66666666666667,7.77777777777778,8.88888888888889,10.0,11.1111111111111,12.2222222222222,13.3333333333333,14.4444444444444,15.5555555555556,16.6666666666667,17.7777777777778,18.8888888888889,20.0,21.1111111111111,22.2222222222222,23.3333333333333,24.4444444444444,25.5555555555556,26.6666666666667,27.7777777777778,28.8888888888889,30.0,31.1111111111111,32.2222222222222,33.3333333333333,34.4444444444444,35.5555555555556,36.6666666666667,37.7777777777778,38.8888888888889,40.0,41.1111111111111,42.2222222222222,43.3333333333333,44.4444444444444,45.5555555555556,46.6666666666667,47.7777777777778,48.8888888888889,50.0,51.1111111111111,52.2222222222222,53.3333333333333,54.4444444444444,55.5555555555556,56.6666666666667,57.7777777777778,58.8888888888889,60.0,61.1111111111111,62.2222222222222,63.3333333333333,64.4444444444444,65.5555555555556,66.6666666666667,67.7777777777778,68.8888888888889,70.0,71.1111111111111,72.2222222222222,73.3333333333333,74.4444444444444,75.5555555555556,76.6666666666667,77.7777777777778,78.8888888888889,80.0,81.1111111111111,82.2222222222222,83.3333333333333,84.4444444444444,85.5555555555556,86.6666666666667,87.7777777777778,88.8888888888889,90.0,91.1111111111111,92.2222222222222,93.3333333333333,94.4444444444444,95.5555555555556,96.6666666666667,97.7777777777778,98.8888888888889,100.0|70.5,71.5,72.5,73.5,75.0,76.0,77.5,78.5,80.0,81.5,83.0,84.5,85.5,87.0,88.5,90.0,91.5,92.5,94.0,95.0,96.5,97.5,98.5,98.5,97.5,96.5,95.0,94.0,92.5,91.5,90.0,88.5,87.0,85.5,84.5,83.0,81.5,80.0,78.5,77.5,76.0,75.0,73.5,72.5,71.5,70.5,69.5,68.5,67.5,67.0,66.5,66.0,65.5,65.0,64.5,64.5,64.5,64.5,64.5,65.0,65.0,65.5,66.0,66.5,67.5,68.0,69.0,70.0,70.0,69.0,68.0,67.5,66.5,66.0,65.5,65.0,65.0,64.5,64.5,64.5,64.5,64.5,65.0,65.5,66.0,66.5,67.0,67.5,68.5,69.5,70.5|40&chxt=x,y&chs=700x400&chxr=0,0,360,45|1,0,1 http://chart.apis.google.com/chart?cht=s&chd=t:0.0,1.111...

harpastum 16y ago
I created an interactive version of the graph, so you can enter values and see how long you would last: http://news.ycombinator.com/item?id=1390136 http://news.ycombinator.com/item?id=1390136