Advent of Code 2024 Day 19 (BaseA Style)
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Discussion thread for day 19 of the Advent of Code - https://adventofcode.com/2024/day/19
- Labels:
- Advent of Code
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
I like this kind of puzzle.
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Simple problem if you utilize a critical optimization (otherwise very difficult problem) ((also a remarkably elegant solution)):
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):
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Today's problem was fairly simple once I figured out the approach.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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.
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
I nailed it quickly today!
  
  
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
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!
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Solved!
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!
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Notify Moderator
Day 19. More in spoiler
P2: Had to sum up combo matches cause brute force would take too long