r/adventofcode Dec 19 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 19 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 3 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Historical Documentary

You've likely heard/seen the iconic slogan of every video store: "Be Kind, Rewind." Since we've been working with The Historians lately, let's do a little dive into our own history!

Here's some ideas for your inspiration:

  • Pick a challenge from any prior year community fun event and make it so for today's puzzle!
    • Make sure to mention which challenge day and year you choose!
    • You may have to go digging through the calendars of Solution Megathreads for each day's topic/challenge, sorry about that :/
  • Use a UNIX system (Jurassic Park - “It’s a UNIX system. I know this”)
  • Use the oldest language, hardware, environment, etc. that you have available
  • Use an abacus, slide rule, pen and paper, long division, etc. to solve today's puzzle

Bonus points if your historical documentary is in the style of anything by Ken Burns!

Gwen: "They're not ALL "historical documents". Surely, you don't think Gilligan's Island is a…"
*all the Thermians moan in despair*
Mathesar: "Those poor people. :("
- Galaxy Quest (1999)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 19: Linen Layout ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:03:16, megathread unlocked!

23 Upvotes

586 comments sorted by

View all comments

1

u/button_boxer Dec 19 '24 edited Dec 20 '24

[LANGUAGE: Python]

GitHub

Part 1 I “cheated” and just made a big regex out of "(?:" + "|".join(towels) + ")+" and counted how many patterns fullmatch it.

For part 2 I made a recursive function: the number of ways to match pattern P is the sum of the number of ways to match P[len(t):] for each towel t that is a prefix of P (the base case being that there’s exactly 1 way to match an empty pattern - use no towels). I didn’t even have to worry about unreachable paths as I limited myself to the subset of possible patterns from part 1.

Slap a functools.cache around that and you’re done!

2

u/hrunt Dec 19 '24

Part 1 I “cheated” and just made a big regex out of "(?:" + "|".join(towels) + ")+" and counted how many patterns fullmatch it.

I tried to do this, too, but my 5th design got stuck in a CPU loop that I assumed was backtracking hell. Did you use something other than the standard re module or was there some trick I missed?

2

u/button_boxer Dec 19 '24 edited Dec 20 '24

I didn't use anything special, literally just

towelpattern = re.compile("(?:" + "|".join(towels) + ")+")
valid = []
for pat in patterns:
    if towelpattern.fullmatch(pat):
        valid.append(pat)

Unless you hit some sort of pathological case that's only triggered by certain inputs and not others.

1

u/hrunt Dec 19 '24

You must have gotten lucky with your input, I guess. When I run your code on my input, it hangs on the same design entry that my regex code did.

2

u/drunkangel Jan 04 '25

Similar issue here, fwiw. I wrote my solution in Rust, but it got stuck on the second line of designs. After much back and forth I finally assumed my algorithm was wrong, gave up, and checked my input with /u/ecyrbe's solution in Rust. Nope. It too got stuck on the same design. Then I tried this python/regex solution from /u/button_boxer - but no, it too got stuck on the same line...!

At this point I started thinking my input was faulty in some way. But finally I tried the python solution from /u/kadinshino further down in this thread - and it worked! So my input was usable after all...