### Raptors

#### by Mithrandir

All xkcd‘s fans know the raptor problem: suppose you are standing at the centre of an equilateral triangle with three raptors in the corners, one of them injured (thus going with a slower speed). Knowing the speeds of all entities and the edge of the triangle determine the direction in which you will have to run to maximize your life time.

We are going to reuse parts of the code presented in the Ships article. First, we have the same imports and types.

import System.Environment(getArgs) type Speed = Float type Dir = (Float, Float) type Point = (Float, Float) type TimeStamp = Float type TimeIncrement = Float type Distance = Float

However, we must change the world representation. Instead of ships we have some actors, instead of a world with only two entities, now we have four.

data Actor = Actor { position :: Point, direction :: Dir, speed :: Speed } deriving (Show) data World = World { man :: Actor, injuredRaptor :: Actor, firstRaptor :: Actor, secondRaptor :: Actor, timeStamp :: TimeStamp } deriving (Show)

Some of the functions from the previous article are the same, they need no further explanations:

dist :: Point -> Point -> Distance dist (x,y) (x', y') = sqrt ((x - x') ^ 2 + (y - y') ^ 2) slope :: Point -> Point -> Dir slope p1@(x,y) p2@(x', y') = ((x'- x)/d, (y'-y)/d) where d = dist p1 p2 getNewPos :: Actor -> TimeIncrement -> Point getNewPos (Actor (x,y) (z,u) s) t = (x+z*s*t/w, y+u*s*t/w) where w = sqrt $ z ** 2 + u ** 2

However, the world has changed, thus the history generating functions must change.

advanceWorld :: World -> TimeIncrement -> World advanceWorld w@(World m i f s t) dt = w { man = m', injuredRaptor = i', firstRaptor = f', secondRaptor = s', timeStamp = t + dt} where pm = getNewPos m dt pi = getNewPos i dt pf = getNewPos f dt ps = getNewPos s dt m' = m { position = pm } i' = i { position = pi, direction = slope pi pm } f' = f { position = pf, direction = slope pf pm } s' = s { position = ps, direction = slope ps pm }

When we create the world we must be sure to place the raptors and the man it the right position. For this, we consider the man to be placed in the origin and the raptors accordingly, with the injured raptor just at north from the human.

createWorld :: Dir -> Speed -> Distance -> Speed -> Speed -> World createWorld mandir sm d si sr = World (Actor (0, 0) mandir sm) (Actor (0, d*sq3/3) (0, -1) si) (Actor (-0.5*d, -d*sq3/6) (0.5*sq3, 0.5) sr) (Actor (0.5*d, -d*sq3/6) (-0.5*sq3, 0.5) sr) 0 where sq3 = sqrt 3

We copy the `iterateUntil`

function from the previous article but we will change the `doEvolution`

function because we want to stop the problem when the raptors are too close to us (within a circle of a specified radius). In order to bound the execution time we will also stop when a certain number of steps has been taken.

iterateUntil :: (a -> a) -> (a -> Bool) -> a -> [a] iterateUntil f p e = go [e] where go l@(x:xs) | p x = l | otherwise = go ((f x):l) doEvolution :: World -> TimeIncrement -> Distance -> [World] doEvolution w t dm = iterateUntil (flip advanceWorld t) f w where f world = or [d injuredRaptor, d firstRaptor, d secondRaptor, max] where m = man world d raptor = (dist (position m) (position $ raptor world)) < dm max = timeStamp world > 10000

Now, we only store the positions of the four actors in a file for later ploting.

printResults w = do appendFile "trace" $ show $ fst $ position $ man w appendFile "trace" "\t" appendFile "trace" $ show $ snd $ position $ man w appendFile "trace" "\t" appendFile "trace" $ show $ fst $ position $ injuredRaptor w appendFile "trace" "\t" appendFile "trace" $ show $ snd $ position $ injuredRaptor w appendFile "trace" "\t" appendFile "trace" $ show $ fst $ position $ firstRaptor w appendFile "trace" "\t" appendFile "trace" $ show $ snd $ position $ firstRaptor w appendFile "trace" "\t" appendFile "trace" $ show $ fst $ position $ secondRaptor w appendFile "trace" "\t" appendFile "trace" $ show $ snd $ position $ secondRaptor w appendFile "trace" "\n"

The main function gathers the arguments from the command line and passes them to the needed functions in order to obtain the output.

main = do args <- getArgs let d = read $ args !! 0 let ms = read $ args !! 1 let rs = read $ args !! 2 let is = read $ args !! 3 let angle = (read $ args !! 4) * pi / 180 let maxd = read $ args !! 5 let t = read $ args !! 6 let w = createWorld (cos angle, sin angle) ms d is rs writeFile "trace" "" mapM_ printResults $ doEvolution w t maxd

That’s all the code for the raptor problem. Now, let’s see some results. Let’s see if our intuition saying to go towards the injured raptor is good:

XKCD’s initial problem: edge: 20, man speed 6, raptor speed 25, injured speed 10

It seems we are on the right track. Let’s see what happens when we change the speeds a little:

Changed problem: edge: 20, man speed 8, raptor speed 15, injured speed 1

Hmm, not really. Let’s see what happens when we tweak the edge:

Big edge problem: edge: 200, man speed 8, raptor speed 15, injured speed 1

The shape is the same. Thus, the angle doesn’t depend on the edge of the triangle. (The above plot also show me that I have a bug in the code as the number of iterations is bigger than the limit at some points). Let’s see a live trace of one case :)

Live example (edge 20, man 8, raptor 15, injured 1, angle 89)

Next time I’ll try to generalize the problem and transform the code into something as general as possible.

[...] This post was mentioned on Twitter by Mihai Maruseac, Jason Reich. Jason Reich said: Haskell solution to the xkcd raptor problem http://bit.ly/cIhxBX [...]

=== popurls.com === popular today…yeah! this story has entered the popular today section on popurls.com…

main = do

args <- getArgs

let d = read $ args !! 0

let ms = read $ args !! 1

let rs = read $ args !! 2

let is = read $ args !! 3

let angle = (read $ args !! 4) * pi / 180

let maxd = read $ args !! 5

let t = read $ args !! 6

Ouch, my eyes. I'd suggest rewriting this; a 'map read' might not be bad, and you could name the bindings somewhat like (d:ms:rs:is:angle:maxd:t:_).

printResults could also use some clean up or at least a utility function.

(Running hlint over the whole thing might not be a bad idea either.)

Great! Did you factor in the size of their brains and the probability of the Raptors, attacking the injured Raptor whilst only slightly distracted by say, us running?

[...] full post on Hacker News If you enjoyed this article, please consider sharing it! Tagged with: Problem [...]

[...] Raptors All xkcd‘s fans know the raptor problem: suppose you are standing at the centre of an equilateral triangle with [...] [...]

The pictures at the end of the post all look broken. Please fix them?

@gwern: Yes, I will try to refactor the code soon.

@Ms Rubio: Nop, not yet.

@David Trejo: My external (non wordpress) picture server is down at the moment :(

You mention in the other post that you find it shocking that changing the distance or velocity doesn’t affect the result, and you seem similarly surprised here that changing the size of the triangle (without changing the speeds) doesn’t affect the results.

This is actually not that surprising at all, if you’re familiar with the idea (from physics) of “nondimensionalizing” a problem. The fundamental idea there is that physical units like “meters” and “seconds” are arbitrary and thus physically meaningless.

This is reflected, of course, in the fact that in your program you did not tell the computer that the edge length was 20 meters; you merely gave the length as 20, and implicitly gave the information that that was 20 of the same length measurement as used in the velocity numbers. But the computer program and calculations would have been identical if the length were 20 inches, the velocity numbers were inches per years, and the time numbers on the output were in years rather than seconds. Thus, we prove that the shape of the result does not change if we change the actual input variables, so long as they stay appropriately proportionate (i.e., same units for everything).

Likewise, changing the edge length from 20 to 200 while keeping the velocity numbers the same will give you the same shape of results with the time numbers increased by a factor of ten, because what you are computing is the exact same physical situation but with distances in decimeters, velocities in decimeters per decisecond, and times in deciseconds. The units that you use to measure and report the physical situation cannot possibly change what the raptor actually does, so you have to get the same result.

The principle of nondimensionalization, then, says that instead of using units like “meters” and “seconds” to express the problem, you can simplify things by using some of the parameters of the problem as your measurement units, and then expressing the other parameters in terms of them. This gives you fewer parameters, and thus a simpler problem to solve. For example, in the ship problem, if you do that you see that the only length that shows up in the problem is the initial distance, and the only time is the ship velocity divided by that distance — so, if you change the length or velocity, all you can possibly change is the size or timing of the result, but not its shape.

Hmm, that gives me some ideas :) Thanks for explaining the apparently shocking thing

Found the bug. Will post the new version in a week or so.

Your iterateUntil builds the list from right to left, which seems to be the wrong direction here.

It forces you to build the entire history of worlds in memory, and only then start printing it out.

Haskell’s built in iterate functions would serve you better, I think. It allows

your program just to iterate through the world states and print them, discarding the previous ones

after they are no longer needed.

There are two issues, though. One is that the list will be ordered from

earliest to latest. That actually seems more natural to me. If you insist

on your order of latest to earliest, you could apply reverse to the result,

but that will revert to the behavior of building the whole thing up in memory.

The other issue is that you insist on including one world state *after*

the predicate becomes true. If you don’t mind skipping that very last world

state, you could just use

iterateUntil f p = takeWhile (not p) . iterate f

But if you insist on including that extra world state at the end, you’ll have

to keep track of two world states throughout the iteration, the current

one and the previous one. That way, you can check

whether the predicate had become true on the previous time through:

iterateUntil f p e = (e :) . map snd . takeWhile (not p . fst) $ zip it (tail it)

where it = iterate f e

Thanks. That function was a hack first time and I didn’t have time to change it until now :)

Had good health in your hand

[...] Raptors | Code and Bugs All xkcd‘s fans know the raptor problem: suppose you are standing at the centre of an equilateral triangle with three raptors in the corners, one of them injured (thus going with a slower speed). Knowing the speeds of all entities and the edge of the triangle determine the direction in which you will have to run to maximize your life time. (tags: Coding XKCD) [...]

thanks for information

Picture server still down. Fix it pls? :D

Not my server unfortunately:( Will try to post elsewhere