summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2021/12.hs52
-rw-r--r--2021/12.in24
2 files changed, 76 insertions, 0 deletions
diff --git a/2021/12.hs b/2021/12.hs
new file mode 100644
index 0000000..03b2d77
--- /dev/null
+++ b/2021/12.hs
@@ -0,0 +1,52 @@
+module Main where
+
+import qualified Data.Array as A
+import Data.Bifunctor (bimap)
+import Data.Char
+import Data.List
+import qualified Data.Map.Strict as Map
+import qualified Data.Set as Set
+import Data.Tuple (swap)
+
+import Input
+import Util
+
+
+uniq :: Eq a => [a] -> [a]
+uniq (x : y : xs) | x == y = uniq (y : xs)
+ | otherwise = x : uniq (y : xs)
+uniq l = l
+
+main :: IO ()
+main = do
+ inp <- getInput 12
+ let listpairs = map (toList . splitOn (== '-')) inp
+ pairs = map (\[a,b] -> (a, b)) listpairs
+ nodes = uniq (sort (concat listpairs))
+ nodeids = Map.fromList (zip nodes [0::Int ..])
+ idpairs = map (bimap (nodeids Map.!) (nodeids Map.!)) pairs
+ startid = nodeids Map.! "start"
+ endid = nodeids Map.! "end"
+ collect l = A.listArray (0, length l - 1) l
+ graph = collect
+ [collect [b | (a, b) <- idpairs ++ map swap idpairs
+ , a == node]
+ | node <- [0 .. length nodes - 1]]
+ issmall = collect (map (all isLower) nodes)
+ npathsfrom :: Int -> Set.Set Int -> Bool -> [[Int]]
+ npathsfrom node seen permissive
+ | node == endid = [[endid]]
+ | otherwise =
+ let nexts = A.elems (graph A.! node)
+ allowed n = not (issmall A.! n) || n `Set.notMember` seen
+ doubling n = n /= startid && n /= endid && not (allowed n)
+ nexts_allowed = filter allowed nexts
+ nexts_doubling = filter doubling nexts
+ seen' | issmall A.! node = Set.insert node seen
+ | otherwise = seen
+ in concatMap (\n -> map (node :) (npathsfrom n seen' permissive)) nexts_allowed
+ ++ (if permissive
+ then concatMap (\n -> map (node :) (npathsfrom n seen' False)) nexts_doubling
+ else [])
+ print (length $ npathsfrom startid mempty False)
+ print (length $ npathsfrom startid mempty True)
diff --git a/2021/12.in b/2021/12.in
new file mode 100644
index 0000000..e1a2275
--- /dev/null
+++ b/2021/12.in
@@ -0,0 +1,24 @@
+pf-pk
+ZQ-iz
+iz-NY
+ZQ-end
+pf-gx
+pk-ZQ
+ZQ-dc
+NY-start
+NY-pf
+NY-gx
+ag-ZQ
+pf-start
+start-gx
+BN-ag
+iz-pf
+ag-FD
+pk-NY
+gx-pk
+end-BN
+ag-pf
+iz-pk
+pk-ag
+iz-end
+iz-BN