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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 
3 points
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
2 points
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?
1 point
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.
2 points
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
