## Competitive programming in Haskell: vectors and 2D geometry

In my previous post (apologies it has been so long!) I challenged you to solve Vacuumba, which asks us to figure out where a robot ends up after following a sequence of instructions. Mathematically, this corresponds to adding up a bunch of vectors, but the interesting point is that the instructions are always relative to the robot’s current state, so robot programs are imperative programs.

## Vector basics

The first order of business is to code up some primitives for dealing with (2D) vectors. I have accumulated a lot of library code for doing geometric stuff, but it’s kind of a mess; I’m using this as an opportunity to clean it up bit by bit. So there won’t be much code at first, but the library will grow as we do more geometry problems. The code so far (explained below) can be found in the comprog-hs repository.

First, a basic representation for 2D vectors, the zero vector, and addition and subtraction of vectors.

``````{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Geom where

------------------------------------------------------------
-- 2D points and vectors

data V2 s = V2 !s !s deriving (Eq, Ord, Show)
type V2D  = V2 Double

instance Foldable V2 where
foldMap f (V2 x y) = f x <> f y

zero :: Num s => V2 s
zero = V2 0 0

(^+^), (^-^) :: Num s => V2 s -> V2 s -> V2 s
V2 x1 y1 ^+^ V2 x2 y2 = V2 (x1+x2) (y1+y2)
V2 x1 y1 ^-^ V2 x2 y2 = V2 (x1-x2) (y1-y2)``````

A few things to point out:

• The `V2` type is parameterized over the type of scalars, but we define `V2D` as a synonym for `V2 Double`, which is very common. The reason for making `V2` polymorphic in the first place, though, is that some problems require the use of exact integer arithmetic. It’s nice to be able to share code where we can, and have the type system enforce what we can and can’t do with vectors over various scalar types.

• For a long time I just represented vectors as lists, `type V2 s = [s]`. This makes implementing addition and subtraction very convenient: for example, `(^+^) = zipWith (+)`. Although this has worked just fine for solving many geometry problems, I have recently been reminded that having lots of small lists can be bad for performance. As long as we’re making a library anyway we might as well use a proper data type for vectors!

• Elsewhere I have made a big deal out of the fact that vectors and points ought to be represented as separate types. But in a competitive programming context I have always just used a single type for both and it hasn’t bit me (yet!).

• The `Foldable` instance for `V2` gets us `toList`. It also gets us things like `sum` and `maximum` which could occasionally come in handy.

## Angles and rotation

The other thing we are going to need for this problem is angles.

``````------------------------------------------------------------
-- Angles

newtype Angle = A Double  -- angle (radians)
deriving (Show, Eq, Ord, Num, Fractional, Floating)

fromDeg :: Double -> Angle
fromDeg d = A (d * pi / 180)

toDeg :: Angle -> Double
toDeg (A r) = r * 180 / pi

-- Construct a vector in polar coordinates.
fromPolar :: Double -> Angle -> V2D
fromPolar r θ = rot θ (V2 r 0)

-- Rotate a vector counterclockwise by a given angle.
rot :: Angle -> V2D -> V2D
rot (A θ) (V2 x y) = V2 (cos θ * x - sin θ * y) (sin θ * x + cos θ * y)
``````

Nothing too complicated going on here: we have a type to represent angles, conversions to and from degrees and radians, and then two uses for angles: a function to construct a vector in polar coordinates, and a function to perform rotation.

Incidentally, one could of course define `type Angle = Double`, which would be simpler in some ways, but after getting bitten several times by forgetting to convert from degrees to radians, I decided it was much better to use a `newtype` and entirely prevent that class of error.

## Solving Vacuumba

Now we just put the pieces together to solve the problem. First, some imports:

``````{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RecordWildCards  #-}

import           Control.Arrow
import qualified Data.Foldable       as F
import           Text.Printf

import           Geom
import           Scanner``````

We make a data type for representing robot instructions, and a corresponding `Scanner`. Notice how we are forced to use `fromDeg` to convert the raw input into an appropriate type.

``````data Instr = I { turn :: Angle, dist :: Double }

instr :: Scanner Instr
instr = I <\$> (fromDeg <\$> double) <*> double``````

The high-level solution then reads the input via a `Scanner`, solves each scenario, and formats the output. The output is a `V2D`, so we just convert it to a list with `F.toList` and use `printf` to format each coordinate.

``````main = interact \$
runScanner (numberOf (numberOf instr)) >>>
map (solve >>> F.toList >>> map (printf "%.6f") >>> unwords) >>> unlines``````

Our `solve` function needs to take a list of instructions, and output the final location of the robot. Since the instructions can be seen as an imperative program for updating the state of the robot, it’s entirely appropriate to use a localized `State` computation.

First, a data type to represent the robot’s current state, consisting of a 2D vector recording the position, and an angle to record the current heading. `initRS` records the robot’s initial state (noting that it starts out facing north, corresponding to an angle of $90^\circ$ as measured clockwise from the positive $x$-axis).

``````data RobotState = RS { pos :: V2D, heading :: Angle }
initRS = RS zero (fromDeg 90)``````

Finally, the `solve` function itself executes each instruction in sequence as a `State RobotState` computation, uses `execState` to run the resulting overall computation and extract the final state, and then projects out the robot’s final position. Executing a single instruction is where the geometry happens: we look up the current robot state, calculate its new heading by adding the turn angle to the current heading, construct a movement vector in the direction of the new heading using polar coordinates, and add the movement to the current position.

``````solve :: [Instr] -> V2D
solve = mapM_ exec >>> flip execState initRS >>> pos
where
exec :: Instr -> State RobotState ()
exec (I θ d) = do
RS{..} <- get
put \$ RS (pos ^+^ move) heading'``````

## For next time

We’ll definitely be doing more geometry, but for the next post I feel like doing something different. I invite you to solve Checking Break.