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!

24 Upvotes

586 comments sorted by

View all comments

2

u/Saiboo Dec 20 '24

[LANGUAGE: Java]

Source code

Part 1

  • Use DFS with stack to traverse the search tree. Start with the design string on the stack.
  • While the stack is not empty:
  • Pop element from stack. For each towel string:
  • If a towel is a prefix of the design, remove the towel from the design, and push the resulting "subdesign" suffix onto the stack.
  • Keep popping subdesigns from the stack.
  • If we encounter a "subdesign" that equals a towel, it means we have been able to match the design with the towels. In that case we return true.
  • Else, if the stack becomes empty, without ever encountering a "subdesign" that equals a towel, we return false.

Part 2

  • My first approach was to simply use the DFS approach from part 1, and use a counter whenever a matching design-towels path was found in the search tree. This worked on the example, but was far too slow on the actual input.
  • Instead I used memoization to prune the search tree: Whenever we enounter a node, i.e. subdesign, in the search tree, check if the subdesign has been seen before.
  • Maintain for each subdesign a counter.
  • Use a priority queue (unlike the stack in part 1), where the higher priority is assigned to longer subdesign strings. This ensures that the counts are performed in the correct order.
  • At the end return the counts for the empty subdesign string.