Advent of Code 2024 day 19

It was pretty obvious that a naïve, brute-force approach wouldn't work for part 2 of the day 19 puzzle. But I thought it might work for part 1. In the end, solving part 1 gave me part 2 for basically free.

Naïve approach: parsing

The puzzle is to take an input string (the design) and find a way to split it into its constituent elements (the towels). If you look at this from a slight angle, this is a lot like parsing: splitting the input into the tokens you define.

That prompted this parser, for splitting designs into towels, using attoparsec.

buildPattern towels design = parseOnly ((designP towelsT) <* endOfInput) (pack design)
  where towelsT = fmap pack (reverse $ sortOn length towels)

designP :: [Text] -> Parser [Text]
designP towels = many1 (towelChoiceP towels)

towelChoiceP :: [Text] -> Parser Text
towelChoiceP towels = (try . choice) $ ( string <$> towels )

That worked for the sample input, but (unsurprisingly) didn't find all the solutions. This is because of how attoparsec makes commitments to partial parses: if it can find a parse for the first part of the input string, it won't backtrack to find alternatives if that approach doesn't work.

Haskell has a standard alternative parser library, ReadP, that does much more backtracking. This will find all possible solutions for a parse. The problem is, there can be many such solutions. This version again worked on the test input, but ran out of memory on the full input.

A different approach as needed.

Careful approach: dynamic programming

Let's consider an example. Using the examples in the puzzle text, consider the design gbbr. Can I make this design with the towels specified?

The towels that could be on the right-hand end of the design are r and br. I could use r to complete this design to if I can somehow make gbb, or I could use br if I can somehow make gb. How do I know if I can make those shorter designs? I have a table of possible designs that shows all the ones I can make with these towels. All I need to do now is build that table.

I do that by walking along the design, left to right. At each point, I work out which towels match the suffix of the design so far. For each one, I work out the remaining prefix of the pattern. If that prefix is in the table, it means the design-so-far is possible by making that prefix then adding this towel; in that case, the design is added to the table.

Each step is implemented as addTowel.

addTowel :: [String] -> S.Set String -> String -> S.Set String
addTowel towels acc design 
  | any (\p -> p `S.member` acc) prefixes = S.insert design acc
  | otherwise = acc
  where allPS = zip (inits design) (tails design)
        prefixes = [p | (p, s) <- allPS, s `elem` towels]

Analysing the whole design is a foldl across the design, seeding the table with the notion I can always make the empty design. A design is possible if, after building it, the design itself is in the table.

isPossibleDesign :: [String] -> String -> Bool
isPossibleDesign towels design = design `S.member` (buildDesign towels design)

buildDesign :: [String] -> String -> S.Set String
buildDesign towels design = foldl' (addTowel towels) (S.singleton "") $ inits design

Part 2 is a small extension of this idea. Rather than just recording if a design is possible, I use a multiset to count how many ways I can make that design.

countDesigns :: [String] -> String -> Int
countDesigns towels design = MS.occur design $ buildDesignCount towels design

buildDesignCount :: [String] -> String -> MS.MultiSet String
buildDesignCount towels design = foldl' (addTowelCount towels) (MS.singleton "") $ inits design

addTowelCount :: [String] -> MS.MultiSet String -> String -> MS.MultiSet String
addTowelCount towels acc design = MS.insertMany design prefixWays acc
  where allPS = zip (inits design) (tails design)
        prefixWays = sum  [ p `MS.occur` acc 
                          | (p, s) <- allPS
                          , s `elem` towels ]

I read the input data and count the designs. That makes the solutions almost trivial.

The possible designs are those where countDesigns returns more than zero; the number of possible alternative designs is the sum of countDesigns.

part1 = length . filter (> 0)
part2 = sum

Code

You can get the code from my locally-hosted Git repo, or from Codeberg.