From a0ad528004525aa4ffc14dd55543bdc7a64db0a2 Mon Sep 17 00:00:00 2001 From: Tom Smeding Date: Wed, 15 Dec 2021 19:42:36 +0100 Subject: Faster 14 --- 2021/14.hs | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/2021/14.hs b/2021/14.hs index b088a8f..5059088 100644 --- a/2021/14.hs +++ b/2021/14.hs @@ -9,8 +9,8 @@ import Input import Util -step :: Eq a => [((a, a), a)] -> [a] -> [a] -step rules (a:b:s) = case lookup (a, b) rules of +step :: Ord a => Map (a, a) a -> [a] -> [a] +step rules (a:b:s) = case Map.lookup (a, b) rules of Nothing -> a : step rules (b:s) Just c -> a : c : step rules (b:s) step _ l = l @@ -27,12 +27,12 @@ maphistogram = foldr (\x -> Map.insertWith (+) x 1) mempty -- table[p][0][q] = if p == q then 1 else 0 -- table[p][n][q] = sum over pairs r: -- table[p][n-1][r] * (number of occurrences of q in step(r)) -dyn :: [((Char, Char), Char)] +dyn :: Map (Char, Char) Char -> Int -> (Map Char Int, Int, A.Array ((Int, Int), Int, (Int, Int)) Int) dyn rules nsteps = (charmap, maxid, table) where - chars = uniq . sort $ concatMap (\((a,b),c) -> [a,b,c]) rules + chars = uniq . sort $ concatMap (\((a,b),c) -> [a,b,c]) (Map.assocs rules) charlist = zip chars [0::Int ..] charmap = Map.fromList charlist maxid = snd (fst (Map.deleteFindMax charmap)) @@ -51,7 +51,7 @@ dyn rules nsteps = (charmap, maxid, table) | otherwise = count (a, b) (y:s) count _ _ = 0 -solve :: [((Char, Char), Char)] -> String -> Int -> Int +solve :: Map (Char, Char) Char -> String -> Int -> Int solve rules template nsteps = let (charmap, maxid, table) = dyn rules nsteps inttemplate = map (charmap Map.!) template @@ -69,7 +69,7 @@ solve rules template nsteps = main :: IO () main = do template : _ : rules' <- getInput 14 - let rules = map (\[a,b,' ','-','>',' ',c] -> ((a, b), c)) rules' + let rules = Map.fromList (map (\[a,b,' ','-','>',' ',c] -> ((a, b), c)) rules') -- let string1 = iterate (step rules) template !! 10 -- hist1 = Map.elems (maphistogram string1) -- print (maximum hist1 - minimum hist1) -- cgit v1.2.3-54-g00ecf