{-# Language QuasiQuotes, BangPatterns, TransformListComp, BlockArguments #-}
module Main (main) where
import Advent (format, ordNub)
import Advent.MinCut (minCutApprox)
import Advent.Tokenize (autoTokenize)
import Data.Graph.Inductive (UGr, size, labNodes, nmap, mkUGraph)
import System.Random (newStdGen)
import Data.Semigroup (Sum(Sum))
main :: IO ()
IO ()
main =
do input <- [format|2023 25 (%s:( %s)*%n)*|]
let g = (() -> Sum Node) -> Gr () () -> Gr (Sum Node) ()
forall (gr :: * -> * -> *) a c b.
DynGraph gr =>
(a -> c) -> gr a b -> gr c b
nmap (Sum Node -> () -> Sum Node
forall a b. a -> b -> a
const Sum Node
1) ([(Node, [Node])] -> Gr () ()
simpleGraph ([([Char], [[Char]])] -> [(Node, [Node])]
forall a b. AutoToken a b => a -> b
autoTokenize [([Char], [[Char]])]
input))
gs <- minCutApprox g <$> newStdGen
print (product [sz :: Int | g' <- gs, 3 == size g', then take 1, (_, Sum sz) <- labNodes g'])
simpleGraph :: [(Int, [Int])] -> UGr
simpleGraph :: [(Node, [Node])] -> Gr () ()
simpleGraph [(Node, [Node])]
input =
[Node] -> [Edge] -> Gr () ()
forall (gr :: * -> * -> *).
Graph gr =>
[Node] -> [Edge] -> gr () ()
mkUGraph
([Node] -> [Node]
forall a. Ord a => [a] -> [a]
ordNub [Node
n | (Node
k, [Node]
vs) <- [(Node, [Node])]
input, Node
n <- Node
k Node -> [Node] -> [Node]
forall a. a -> [a] -> [a]
: [Node]
vs])
[(Node
k, Node
v) | (Node
k, [Node]
vs) <- [(Node, [Node])]
input, Node
v <- [Node]
vs]