Haskell

My naive solution was taking ages until I tried matching from right to left instead :3

In the end the cache required for part two solved the problem more effectively.

import Control.Arrow
import Control.Monad.State
import Data.List
import Data.List.Split
import Data.Map (Map)
import Data.Map qualified as Map

arrangements :: [String] -> String -> Int
arrangements atoms = (`evalState` Map.empty) . go
  where
    go "" = return 1
    go molecule =
      let computed = do
            c <- sum <$> mapM (\atom -> maybe (return 0) go $ stripPrefix atom molecule) atoms
            modify (Map.insert molecule c)
            return c
       in gets (Map.!? molecule) >>= maybe computed return

main = do
  (atoms, molecules) <- (lines >>> (splitOn ", " . head &&& drop 2)) <$> readFile "input19"
  let result = map (arrangements atoms) molecules
  print . length $ filter (> 0) result
  print . sum $ result