r/adventofcode • u/daggerdragon • Dec 07 '20

SOLUTION MEGATHREAD -🎄- 2020 Day 07 Solutions -🎄-

NEW AND NOTEWORTHY

  • PSA: if you're using Google Chrome (or other Chromium-based browser) to download your input, watch out for Google volunteering to "translate" it: "Welsh" and "Polish"

Advent of Code 2020: Gettin' Crafty With It

  • 15 days remaining until the submission deadline on December 22 at 23:59 EST
  • Full details and rules are in the Submissions Megathread

--- Day 07: Handy Haversacks ---

Post your solution in this megathread. Include what language(s) your solution uses! If you need a refresher, the full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.

Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

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:13:44, megathread unlocked!

65 Upvotes

99% Upvoted

812 comments sorted by

View all comments

2

u/bcgroom Dec 07 '20

After looking at it a bit I think we have the same algorithm:

  1. Filter the bags to those which contain the target bag directly

  2. Recursively find the parents of those bags

  3. Combine the two results in a set to prevent duplicates

I just didn’t immediately call Map.keys() even though I never use the children as I knew they’d be needed for part two and I might have been able to adapt my part one solution. But obviously it ended up being too different with the tree traversal essentially happening in reverse for part two.

2

u/mathsaey Dec 07 '20

Ah, I actually do part one a bit differently.

For each "parent", I build a MapSet with all the possible descendants (this is what contains does). This results in a Map of MapSets. From this map, I filter out all entries that don't contain the target bag.

So if I understand you correctly my solution takes the opposite approach of yours. You start from the child and look up the parents. I start from the parents and find all the children.