Ninth day of Advent of Code 2015

SingleNight.hs

{-# LANGUAGE TupleSections #-}
module Main where
import BasePrelude hiding (insert)
import Data.Map (Map)
import Data.Set (Set, member, insert)
import qualified Data.Map as Map
import qualified Data.Set as Set

type Graph = Map String [(Int, String)]
graphIO = (lines >>> connect) <$> readFile "<snip>"
main = output minimumBy >> output maximumBy

connect lines = foldl' (Map.unionWith (++)) Map.empty (parse <$> lines)
  where e s t w    = (s, [(read w, t)])
        parse line = case words line of [s, "to", t, "=", w] -> Map.fromList [e s t w, e t s w]

paths graph l = Map.keys graph >>= walk Set.empty 0 . (0,)
  where neighbors s = fromMaybe [] (Map.lookup s graph) ++ [(0, "")]
        walk seen n (w, s)
          | "" == s   = if n == l then [[(w, s)]] else []
          | otherwise = [(w, s):next | not (member s seen), next <- neighbors s >>= walk (insert s seen) (n + 1)]

output f = do
  graph <- graphIO
  let cost xs = sum (fst <$> xs)
  let path = f (compare `on` cost) (paths graph 8)
  print (cost path, path)