this post was submitted on 19 Dec 2024
8 points (78.6% liked)

Advent Of Code

995 readers
4 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
Ategon
[email protected]
CameronDev
8
๐Ÿ‘ป - 2024 DAY 19 SOLUTIONS -๐Ÿ‘ป (self.advent_of_code)
submitted 2 weeks ago by CameronDev to c/advent_of_code
34 comments fedilink hide all child comments
 

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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 3 points 2 weeks ago (2 children)

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
[โ€“] [email protected] 2 points 2 weeks ago (1 children)

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?

[โ€“] [email protected] 1 points 2 weeks 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.

[โ€“] [email protected] 2 points 2 weeks 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