Ships

by Mithrandir

Let’s say we have two ships arranged on a line. Both ships are sailing with the same speed. However, while the first one is always going in a perpendicular direction to the line initially connecting the ships, the second one will always try to go towards the first.

We are asked to determine the distance between the ships after enough time has passed.

First, let’s begin with some imports and type definitions:

import System.Environment(getArgs)

type Speed = Float
type Dir = (Float, Float)
type Point = (Float, Float)
type TimeStamp = Float
type TimeIncrement = Float
type Distance = Float

Basically, our world will have the two ships and one timestamp which will be used later for data plotting. A ship, like any other physical object has a direction, a speed and a position. Later, I will modify this code to include the possibility to change heading in a non-instant way.

data Ship = Ship {
  position :: Point,
  direction :: Dir,
  speed :: Speed
  } deriving (Show)

data World = World {
  firstShip :: Ship,
  secondShip :: Ship,
  timeStamp :: TimeStamp
  } deriving (Show)

Now, we would like to calculate the distance between two points and the direction in which this distance is reduced the most.

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

We will also define some functions to compute the distance between two ships and to advance one ship from one point to the other. In a later article, we’ll try to make the following functions more readable.

distShip :: World -> Distance
distShip w = dist (position . firstShip $ w) (position . secondShip $ w)

getNewPos :: Ship -> TimeIncrement -> Point
getNewPos (Ship (x,y) (z,u) s) t = (x+z*s*t/w, y+u*s/w*t)
  where
    w = sqrt $ z **2+ u ** 2

Now, we can advance the clock of the world, simulating it.

advanceWorld :: World -> TimeIncrement -> World
advanceWorld w@(World s1 s2 t) dt = w { firstShip = s1',
  secondShip = s2', timeStamp = t + dt}
  where
    p2 = getNewPos s2 dt
    p1 = getNewPos s1 dt
    s1' = s1 { position = p1}
    s2' = s2 { position = p2, direction = slope p2 p1}

Of course, someone must create the world for us, or we couldn’t simulate anything.

createWorld :: Distance -> Speed -> World
createWorld initialDistance sp = World (Ship (0, 0) (0,1) sp)
  (Ship (initialDistance, 0) (-1, 0) sp) 0

We would like to iterate advanceWorld until the timestamp will be greater than some value. We could have used until like in previous posts or iterate and takeWhile. However, I decided to use a different version of iterate, one which will cons the new result instead of adding it to the end of the list.

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)

With this in mind, we can now begin evolving our world:

doEvolution :: World -> TimeIncrement -> TimeStamp -> [World]
doEvolution w t tm = iterateUntil (flip advanceWorld t) (\x -> timeStamp x > tm) w

To obtain something, we print some results to specific files and we will use gnuplot afterwards.

printResults w = do
  appendFile "dist" $ show $ timeStamp w
  appendFile "dist" "\t"
  appendFile "dist" $ show $ distShip w
  appendFile "dist" "\n"
  appendFile "trace" $ show $ fst $ position $ firstShip w
  appendFile "trace" "\t"
  appendFile "trace" $ show $ snd $ position $ firstShip w
  appendFile "trace" "\t"
  appendFile "trace" $ show $ fst $ position $ secondShip w
  appendFile "trace" "\t"
  appendFile "trace" $ show $ snd $ position $ secondShip w
  appendFile "trace" "\n"

Our main function just gets some arguments for the user and calls the required functions.

main = do
  args <- getArgs
  let d = read $ args !! 0
  let t = read $ args !! 1
  let s = read $ args !! 2
  let w = createWorld d s
  let maxt = read $ args !! 3
  writeFile "dist" ""
  writeFile "trace" ""
  mapM_ printResults $ doEvolution w t maxt

We compile this code and then we will use a bash script to run it and send data to gnuplot in order to obtain some nice graphics:


mihai@keldon:~/Desktop/hs/ships$ ghc --make ships.hs

[1 of 1] Compiling Main             ( ships.hs, ships.o )

Linking ships ...

mihai@keldon:~/Desktop/hs/ships$ cat test.sh

#!/bin/bash

./ships $1 $2 $3 $4

echo 'set term png; plot "trace" using 1:2 title "First" with lines, "trace" using 3:4 title "Second" with lines' | gnuplot > trace.png

echo 'set term png; plot "dist" title "Distance" with lines' | gnuplot > dist.png

mihai@keldon:~/Desktop/hs/ships$ ./test.sh 100 0.1 1 200

The results are shocking: the trajectory is neither a circle as someone believed when she was introduced to the problem nor a parabola as I believed it to be. Moreover, it is very shocking to see that the final distance is always one half of the initial one, as the following plots sugest:

Initial distance 100. Speed 1. Max timestamp 200. Timestep 0.1

Initial distance 100. Speed 5. Max timestamp 200. Timestep 0.1

Initial distance 500. Speed 5. Max timestamp 200. Timestep 0.1

To add more fun, I’ve changed the direction the first ship is taking and it’s starting point. See the following pictures:

Initial distance 500. Speed 5. Max timestamp 200. Timestep 0.1. Not in origin, not axis-alligned ( (42, 24) (-5.42, -2.34))

I will come back to this problem when I’ll sanitize some functions, I’ll add more reality to the problem (I’m thinking of a steering velocity) and I’ll try to solve xckd’s problem.

About these ads