{-# Language QuasiQuotes, ImportQualifiedPost #-}
{-|
Module      : Main
Description : Day 9 solution
Copyright   : (c) Eric Mertens, 2015
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2015/day/9>

>>> :{
:main +
  "London to Dublin = 464\n\
  \London to Belfast = 518\n\
  \Dublin to Belfast = 141\n"
:}
605
982

-}
module Main where

import Advent.Format (format)
import Data.List (permutations)
import Data.Map (Map)
import Data.Map qualified as Map
import Data.Set qualified as Set

data Edge = Edge String String    deriving (Edge -> Edge -> Bool
(Edge -> Edge -> Bool) -> (Edge -> Edge -> Bool) -> Eq Edge
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Edge -> Edge -> Bool
== :: Edge -> Edge -> Bool
$c/= :: Edge -> Edge -> Bool
/= :: Edge -> Edge -> Bool
Eq, Eq Edge
Eq Edge =>
(Edge -> Edge -> Ordering)
-> (Edge -> Edge -> Bool)
-> (Edge -> Edge -> Bool)
-> (Edge -> Edge -> Bool)
-> (Edge -> Edge -> Bool)
-> (Edge -> Edge -> Edge)
-> (Edge -> Edge -> Edge)
-> Ord Edge
Edge -> Edge -> Bool
Edge -> Edge -> Ordering
Edge -> Edge -> Edge
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Edge -> Edge -> Ordering
compare :: Edge -> Edge -> Ordering
$c< :: Edge -> Edge -> Bool
< :: Edge -> Edge -> Bool
$c<= :: Edge -> Edge -> Bool
<= :: Edge -> Edge -> Bool
$c> :: Edge -> Edge -> Bool
> :: Edge -> Edge -> Bool
$c>= :: Edge -> Edge -> Bool
>= :: Edge -> Edge -> Bool
$cmax :: Edge -> Edge -> Edge
max :: Edge -> Edge -> Edge
$cmin :: Edge -> Edge -> Edge
min :: Edge -> Edge -> Edge
Ord, Int -> Edge -> ShowS
[Edge] -> ShowS
Edge -> String
(Int -> Edge -> ShowS)
-> (Edge -> String) -> ([Edge] -> ShowS) -> Show Edge
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Edge -> ShowS
showsPrec :: Int -> Edge -> ShowS
$cshow :: Edge -> String
show :: Edge -> String
$cshowList :: [Edge] -> ShowS
showList :: [Edge] -> ShowS
Show, ReadPrec [Edge]
ReadPrec Edge
Int -> ReadS Edge
ReadS [Edge]
(Int -> ReadS Edge)
-> ReadS [Edge] -> ReadPrec Edge -> ReadPrec [Edge] -> Read Edge
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: Int -> ReadS Edge
readsPrec :: Int -> ReadS Edge
$creadList :: ReadS [Edge]
readList :: ReadS [Edge]
$creadPrec :: ReadPrec Edge
readPrec :: ReadPrec Edge
$creadListPrec :: ReadPrec [Edge]
readListPrec :: ReadPrec [Edge]
Read)

edge :: String -> String -> Edge
edge :: String -> String -> Edge
edge String
x String
y
  | String
x String -> String -> Bool
forall a. Ord a => a -> a -> Bool
< String
y     = String -> String -> Edge
Edge String
x String
y
  | Bool
otherwise = String -> String -> Edge
Edge String
y String
x

-- |
-- >>> :main
-- 251
-- 898
main :: IO ()
IO ()
main =
 do [(String, String, Int)]
input <- [format|2015 9 (%s to %s = %u%n)*|]
    let graph :: Map Edge Int
graph = [(Edge, Int)] -> Map Edge Int
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(String -> String -> Edge
edge String
x String
y, Int
d) | (String
x,String
y,Int
d) <- [(String, String, Int)]
input]    
        places :: [String]
places = [String] -> [String]
forall a. Ord a => [a] -> [a]
uniques [String
z | (String
x,String
y,Int
_) <- [(String, String, Int)]
input, String
z <- [String
x,String
y]]
        costs :: [Int]
costs  = Map Edge Int -> [String] -> Int
tripLength Map Edge Int
graph ([String] -> Int) -> [[String]] -> [Int]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [String] -> [[String]]
forall a. [a] -> [[a]]
permutations [String]
places
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Int]
costs)
    Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Int]
costs)

tripLength :: Map Edge Int -> [String] -> Int
tripLength :: Map Edge Int -> [String] -> Int
tripLength Map Edge Int
m [String]
xs = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((String -> String -> Int) -> [String] -> [String] -> [Int]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith String -> String -> Int
edgeLength [String]
xs ([String] -> [String]
forall a. HasCallStack => [a] -> [a]
tail [String]
xs))
  where
    edgeLength :: String -> String -> Int
edgeLength String
x String
y = Map Edge Int
m Map Edge Int -> Edge -> Int
forall k a. Ord k => Map k a -> k -> a
Map.! String -> String -> Edge
edge String
x String
y

uniques :: Ord a => [a] -> [a]
uniques :: forall a. Ord a => [a] -> [a]
uniques = Set a -> [a]
forall a. Set a -> [a]
Set.toList (Set a -> [a]) -> ([a] -> Set a) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Set a
forall a. Ord a => [a] -> Set a
Set.fromList