Advent of Code 2024 Day 19 (BaseA Style)

[AlteryxCommunityTeam]

Discussion thread for day 19 of the Advent of Code - https://adventofcode.com/2024/day/19

[gawa]

I like this kind of puzzle.

Spoiler

For both part1 & 2, try to prune the duplicated records so calculation volume gets huge. 


My logic was:
1) Append all patterns at first (cross join)
2) Filter the records by StartsWith([Design],[Pattern])
3) Remove the match pattern by RegexReplace
4) Get out of loop for record having empty string

[CoG]

Simple problem if you utilize a critical optimization (otherwise very difficult problem) ((also a remarkably elegant solution)):

Spoiler

This problem is very close to a brute force solution, with one critical exception: Case Consolidation.

Take one of the provided examples - assume you want to create the following pattern "rgrgr" and you have the following designs "r" & "gr" & "rg". You can build the target pattern in several different ways (but let's look at two):
1. r - gr - gr
2. rg - r - gr

You can build all possible strings iteration by iteration adding one design pattern at a time and checking if the pattern still matches the target (although the number of cases being considered will quickly explode), but notice that on iteration 2 we have a redundancy as both cases will now try to match patterns to rgr. Whether this is ultimately an achievable target pattern or not is only relevant once (or for part 2, only the number of ways to generate the pattern is relevant) so we can Summarize the data to only those cases that are unique, using Group By (and Sum for Part 2). This one optimization takes a problem that will never run to completion on your machine and converts it to one that runs in a matter of seconds!

Main Workflow:


Match Stripes (Iterative Macro w/ Case Consolidation):

[DaisukeTsuchiya]

Today's problem was fairly simple once I figured out the approach.

Spoiler

The task is to remove characters one by one from the beginning, and it's complete when all characters have been removed.

Since the number of records increases over time, I grouped them within the Iteration Macro.

[ScottLewis]

That was a good one, with an excellent data science lesson tucked in.

No workflow because it was basically scratch paper.

I really appreciate how this type of advent problem reminds you that problems exist that can't be solved with compute cycles alone.

Spoiler

The iterative macro is just generate rows equal to the number of towels, check left (pattern, length of towel) keep the matches, reduce pattern by towel and repeat. 

For part 1 I missed the key optimization for a bit, so I was focused on using the macro to remove redundant towels. That worked for part 1 but forced me to throw out the whole solution for part 2 because the condition was literally "don't do that thing you did."

The key optimization is that for part 1 you only need to keep one copy of each point you have reached on each pattern. That (mostly) removes the exponential term from the number of combinations you have to consider. For part 2, the optimization is similar, just that instead of keeping only one copy, you count the number of copies (or really, sum the number of copies each copy represents) and keep that summarized copy. 

---

[Hub119]

Once I got my head out of thinking I needed to go down crazy nested macro paths I realized this actually wasn't too bad at all... and the added bonus of really only needing to add a count field to then sum in my existing part 1 macro to get to the part 2 solution was a nice cherry on top.

Spoiler

Workflow

Spoiler

Macro

[ntakeda]

I nailed it quickly today!

Spoiler

  

  

[DataNath]

Day 19 done! At the point of only tackling 'quicker' days now so was pleased to see this one when I logged on. Did get stuck on p2 a bit as I'd took a different approach with my macro originally, using a join/union to remove towels that already had a valid solution. After making some changes, a quick peek at @Hub119's macro made me realise I was over-grouping in the final Summarize between iterations!

Spoiler

[AkimasaKajitani]

Solved!

Spoiler

Part 1 macro


Part 2 macro

I was so caught up in the thoughts in Part 1 that I had a hard time coming up with an answer for Part 2.

And I used the ReplaceFirst! I love simple function!

[mmontgomery]

Day 19. More in spoiler

Spoiler

P1: Actually took me longer to land on approach. I ended up doing substring matches on each combos then filtering a dataset to matches only
P2: Had to sum up combo matches cause brute force would take too long