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.

Advertisement