day7.hs

module Day7 where

import Data.Bifunctor
import Data.List
import Data.Set qualified as Set

main :: IO ()
main = do
  input <- readFile "day7.txt"
  let equations = fmap (bimap (read @Int) (fmap (read @Int) . split ' ' . drop 2) . break (== ':')) $ lines input
  print $ sum $ fmap fst $ filter (uncurry isValid) equations
  where
    split :: Eq a => a -> [a] -> [[a]]
    split _ [] = []
    split sep str = 
        let (left, right) = break (== sep) str
        in left : split sep (drop 1 right)
    isValid total = isValid' total . reverse
      where
        isValid' total [x] = total == x
        isValid' total (x:xs) =
          let (q, r) = total `quotRem` x
              s = total - x
              c = take (length (show total) - length (show x)) (show total)
           in s > 0 && isValid' s xs ||
              r == 0 && isValid' q xs ||
              show x `isSuffixOf` show total && not (null c) && isValid' (read @Int c) xs
        isValid' 0 [] = True
        isValid' _ [] = False