so viel spaß

2 files changed, 103 insertions, 0 deletions

diff --git a/2022/16/input b/2022/16/input
new file mode 100644
index 0000000..4c9f683
--- /dev/null
+++ b/2022/16/input
@@ -0,0 +1,57 @@
+ralve ZN has flow rate=0; tunnels lead to valves SD, ZV
+Valve HO has flow rate=17; tunnel leads to valve LT
+Valve FT has flow rate=6; tunnels lead to valves DW, BV, JA, FB, TV
+Valve AD has flow rate=0; tunnels lead to valves AA, JG
+Valve GE has flow rate=0; tunnels lead to valves JG, RD
+Valve GI has flow rate=0; tunnels lead to valves WJ, RD
+Valve RM has flow rate=0; tunnels lead to valves BU, WJ
+Valve GV has flow rate=0; tunnels lead to valves WB, HS
+Valve VA has flow rate=0; tunnels lead to valves AA, HS
+Valve TJ has flow rate=21; tunnel leads to valve CK
+Valve WB has flow rate=0; tunnels lead to valves GV, EV
+Valve DV has flow rate=19; tunnels lead to valves OI, NK
+Valve EL has flow rate=0; tunnels lead to valves HS, YC
+Valve KU has flow rate=0; tunnels lead to valves WJ, OI
+Valve WI has flow rate=16; tunnels lead to valves SD, AN, GS, JV
+Valve JG has flow rate=3; tunnels lead to valves SV, BU, GC, GE, AD
+Valve TC has flow rate=0; tunnels lead to valves TV, WJ
+Valve GC has flow rate=0; tunnels lead to valves JG, JA
+Valve LS has flow rate=0; tunnels lead to valves JH, YP
+Valve OI has flow rate=0; tunnels lead to valves KU, DV
+Valve ZH has flow rate=0; tunnels lead to valves YZ, RD
+Valve YZ has flow rate=0; tunnels lead to valves ZH, AA
+Valve YP has flow rate=0; tunnels lead to valves KS, LS
+Valve CK has flow rate=0; tunnels lead to valves EG, TJ
+Valve NY has flow rate=0; tunnels lead to valves HS, UU
+Valve IQ has flow rate=18; tunnel leads to valve YC
+Valve HI has flow rate=0; tunnels lead to valves SS, RD
+Valve DW has flow rate=0; tunnels lead to valves FT, JH
+Valve EV has flow rate=7; tunnels lead to valves SV, WB, SS, GS
+Valve SV has flow rate=0; tunnels lead to valves JG, EV
+Valve BU has flow rate=0; tunnels lead to valves JG, RM
+Valve GS has flow rate=0; tunnels lead to valves EV, WI
+Valve UY has flow rate=0; tunnels lead to valves WJ, FE
+Valve AA has flow rate=0; tunnels lead to valves VA, YZ, AD, FB
+Valve SD has flow rate=0; tunnels lead to valves WI, ZN
+Valve KS has flow rate=23; tunnel leads to valve YP
+Valve RD has flow rate=4; tunnels lead to valves GI, HI, BV, ZH, GE
+Valve ZV has flow rate=15; tunnel leads to valve ZN
+Valve HB has flow rate=0; tunnels lead to valves HS, AN
+Valve UU has flow rate=0; tunnels lead to valves EG, NY
+Valve SS has flow rate=0; tunnels lead to valves HI, EV
+Valve HS has flow rate=12; tunnels lead to valves HB, EL, VA, GV, NY
+Valve LT has flow rate=0; tunnels lead to valves DS, HO
+Valve JH has flow rate=5; tunnels lead to valves LS, FE, QU, NK, DW
+Valve AN has flow rate=0; tunnels lead to valves HB, WI
+Valve NK has flow rate=0; tunnels lead to valves DV, JH
+Valve JA has flow rate=0; tunnels lead to valves GC, FT
+Valve EG has flow rate=14; tunnels lead to valves CK, UU, DS
+Valve JV has flow rate=0; tunnels lead to valves QU, WI
+Valve WJ has flow rate=8; tunnels lead to valves GI, RM, KU, UY, TC
+Valve FE has flow rate=0; tunnels lead to valves JH, UY
+Valve TV has flow rate=0; tunnels lead to valves FT, TC
+Valve YC has flow rate=0; tunnels lead to valves IQ, EL
+Valve QU has flow rate=0; tunnels lead to valves JV, JH
+Valve DS has flow rate=0; tunnels lead to valves LT, EG
+Valve BV has flow rate=0; tunnels lead to valves FT, RD
+Valve FB has flow rate=0; tunnels lead to valves AA, FT
diff --git a/2022/16/solve.hs b/2022/16/solve.hs
new file mode 100644
index 0000000..b7744c2
--- /dev/null
+++ b/2022/16/solve.hs
@@ -0,0 +1,46 @@
+{-# LANGUAGE TupleSections #-}
+
+import           Control.Monad
+import qualified Data.HashMap                  as Map
+import           Data.HashMap                   ( Map )
+import           Data.List
+import           Data.MemoTrie
+import           Text.Regex.TDFA
+
+m !!! k = Map.findWithDefault 9999999 k m
+
+parse input = (valves, Map.fromList rates, Map.fromList dists)
+ where
+  match :: String -> [String]
+  match s = getAllTextMatches $ s =~ "([A-Z]{2}|[0-9]+)"
+  matches = map match input
+  valves  = map head matches
+  rates = [ (valve, read rate :: Int) | (valve : rate : _) <- matches, rate /= "0" ]
+  dists = [ ((valve, pipe), 1) | (valve : _ : pipes) <- matches, pipe <- pipes ]
+
+precompute valves distances = updated distances prod
+ where
+  prod = sequence $ replicate 3 valves
+  dist (x : y : z : _) m = min (m !!! (y, z)) ((m !!! (y, x)) + (m !!! (x, z)))
+  updated = foldr (\c@(_ : y : z : _) m -> Map.insert (y, z) (dist c m) m)
+
+solve' :: Int -> Int -> String -> [String] -> Map String Int -> Map (String, String) Int -> Int
+solve' p time current valves rates dists = maximum $ single ++ case p of
+  1 -> [0]
+  2 -> [solve 1 26 "AA" valves rates dists]
+ where
+  single = [ each valve | valve <- valves, (dists !!! (current, valve)) < time ]
+  new_rate = (rates Map.!)
+  new_time = (+ (-1)) . (-) time . (dists !!!) . (current, ) -- troll
+  next valve = solve p (new_time valve) valve (delete valve valves) rates dists
+  each = ap ((+) . liftM2 (*) new_rate new_time) next -- lol
+
+solve = memo solve'
+
+main :: IO ()
+main = do
+  input <- lines <$> readFile "input"
+  let (valves, rates, dists) = parse input
+      dists'                 = precompute valves dists
+  putStrLn $ show $ solve 1 30 "AA" (Map.keys rates) rates dists'
+  putStrLn $ show $ solve 2 26 "AA" (Map.keys rates) rates dists'