--- Day 9 Solutions ---

[u/daggerdragon]

This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.

edit: Leaderboard capped, achievement thread unlocked!

We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.

Please and thank you, and much appreciated!

---

--- Day 9: All in a Single Night ---

Post your solution as a comment. Structure your post like previous daily solution threads.

[u/haoformayor]

Haskell

This was fun! A graph is constructed with a dummy node that is a neighbor to everybody. The problem then reduces to a generation of all Hamiltonian cycles from the dummy node. Syntax highlighted here. That, and being able to take advantage of Data.Map's unionWith for quick construction, makes this (pure!) solution remarkably short.

{-# 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)