Day 19 - Linen Layout

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • lwhjp@lemmy.sdf.org
    3·
    9 days ago

    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
    • sjmulder@lemmy.sdf.org
      2·
      8 days ago

      until I tried matching from right to left instead :3

      My intuition nudged me there but I couldn’t reason how that would change things. You still have to test the remaining string, and its remaining string, backtrack, etc right?

      • lwhjp@lemmy.sdf.org
        1·
        8 days ago

        It was just a hunch that the inputs were generated to be difficult to parse using a naive algorithm (ie the towels have a lot of shared prefixes). In general I don’t think there’s any reason to suppose that one direction is better than the other, at least for random inputs.

    • lwhjp@lemmy.sdf.org
      2·
      8 days ago

      A better version of arrangements using laziness:

      arrangements :: [String] -> String -> Int
arrangements atoms molecule = head counts
  where
    counts = zipWith go (tails molecule) (tails counts)
    go [] _ = 1
    go m cs = sum $ map (\a -> if a `isPrefixOf` m then cs !! length a else 0) atoms