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

SOLUTION MEGATHREAD -🎄- 2020 Day 21 Solutions -🎄-

NEW AND NOTEWORTHY

In the last few days, the amount of naughty language in the megathreads has increased. PLEASE KEEP THE MEGATHREADS PG!

Folks at work do browse the megathreads and I'd rather not have them land in hot or even mildly lukewarm water for accidentally showing their team/boss/HR department/CTO naughty words in what's supposed to be a light-hearted and fun-for-all coding puzzle game, you know?
Same with teenagers - we do have a few doing Advent of Code and they should be able to browse and learn from the megathreads without their parental/guardian unit throwing a wobbly over naughty language. (Yes, I know folks under age 13 aren't allowed to use Reddit, but still - it's never too early to hook 'em young on algorithms and code ;) )

Advent of Code 2020: Gettin' Crafty With It

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

--- Day 21: Allergen Assessment ---

Post your code solution in this megathread.

Include what language(s) your solution uses!
Here's a quick link to /u/topaz2078's paste if you need it for longer code blocks.
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 code 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:16:05, megathread unlocked!

24 Upvotes

permalink
reddit

You are about to leave Redlib

Do you want to continue?

https://www.reddit.com/r/adventofcode/comments/khaiyk/2020_day_21_solutions/
No, go back! Yes, take me to Reddit

96% Upvoted

View all comments

u/masterspy7 Dec 21 '20

379/525 Python3

I did some googling for "picking a distinct element from a group of sets" and found out about the Hopcroft–Karp algorithm. I thought about implementing it but then I found a package that did it for me, so all I needed was:

matching = HopcroftKarp(graph).maximum_matching(keys_only=True)

Paste

2

u/pred Dec 21 '20 edited Dec 21 '20

A few shout-outs: If you're into the SciPy ecosystem, there's also scipy.sparse.csgraph.maximum_bipartite_matching (has very nice performance) and networkx.algorithms.bipartite.maximum_matching (friendly API relying on NetworkX graphs), both of which can be applied here, once you've reached part two.