Skip to content

Instantly share code, notes, and snippets.

@shigemk2
Created June 10, 2015 12:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save shigemk2/6ca68798bcbb8980c1f9 to your computer and use it in GitHub Desktop.
Save shigemk2/6ca68798bcbb8980c1f9 to your computer and use it in GitHub Desktop.
data Section = Section { getA :: Int, getB :: Int, getC :: Int }
deriving (Show)
type RoadSystem = [Section]
heathrowToLondon :: RoadSystem
heathrowToLondon = [ Section 50 10 30
, Section 5 90 20
, Section 40 2 25
, Section 10 8 0
]
data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]
roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
let timeA = sum (map snd pathA)
timeB = sum (map snd pathB)
forwardTimeToA = timeA + a
crossTimeToA = timeB + b + c
forwardTimeToB = timeB + b
crossTimeToB = timeA + a + c
newPathToA = if forwardTimeToA <= crossTimeToA
then (A, a):pathA
else (C, c):(B, b):pathB
newPathToB = if forwardTimeToB <= crossTimeToB
then (B, b):pathB
else (C, c):(A, a):pathA
in (newPathToA, newPathToB)
optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
let (bestAPath, bestBPath) = foldl roadStep ([], []) roadSystem
in if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath
main = do
print $ roadStep ([], []) (head heathrowToLondon)
print $ optimalPath heathrowToLondon
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment