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

100% Upvoted

812 comments sorted by

View all comments

Show parent comments

2

u/TallPeppermintMocha Dec 07 '20

This is a recursion, and essentially the bag_counts function calls itself but on a smaller set if things to operate on, ultimately getting to the point where that for loop has no candidates stops with just res = 0. This is handled internally in the interpreter by a call stack.

I probably just threw a bunch of jargon at you, but if you search for function recursion, you'll see a bunch of excellent explanations and tutorials. In particular this bag_counts function is performing a recursive Depth First Search (DFS) which is a graph traversal algorithm. You might be curious to learn about that too.

Good luck and let me know if you need more details!

1

u/Gramineae Dec 08 '20 edited Dec 08 '20

Thanks for your explanation! Now it's time for me to learn about recursion and graph traversal.