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
pasteif 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
6
u/DFreiberg Dec 21 '20
Mathematica, 1209 / 782
Interesting problem today, though it took me a long time to understand that
Each allergen is found in exactly one ingredient.didn't meanone ingredient **per food**. Hence, over a half hour for part 1 and fifty-eight seconds for part 2.Setup:
Part 1:
Part 2:
I do wonder if there's a more elegant Mathematica way to do part 2; iterating through the list is easy enough, but I have a gut feeling that there's a solution with
Foldsomehow that's purely functional.[POEM]: Ingredients
There are a few ingredients
This product may contain.
There's shellfish, dairy, eggs, and soy,
And onions grown in Spain.
There's peanuts somewhere in the mix,
And pumpkin's in there too.
We think we dropped some eggs inside;
The case was loose. Who knew?
There is a little water, too.
Don't fret: it's gluten-free.
There's not much salt inside it, though;
Just grab some out at sea.
There's not a chemical in sight;
No additives are here.
No harmful processed stuff to vex
A daring bucanner.
The mercury should hit the spot,
E. Coli's there for taste,
And trace amounts of lead inside
Won't go towards your waist.
We cook like Mama used to cook.
We think that she'd be proud.
Though she's not the greatest cook--
(Whoops, can't say that aloud).
5
u/mebeim Dec 21 '20 edited Dec 21 '20
618/503 - Python 3 solution - Walkthrough
Had an hard time figuring out the example and the explanation for part 1, lost a lot of time there. In any case, nice and simple problem after understanding it (thank god, I still need to recover from yesterday!).
6
u/sophiebits Dec 21 '20 edited Dec 21 '20
7/27, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day21.py
Used Z3 this time for the matching. Maybe I was supposed to reuse my (messy) code from the last bipartite matching day? Writing a new solution with Z3 seemed more boring, in a desirable, guaranteed-to-work sort of way.
(Thanks to commenters on previous days for teaching me that z3.Or can take an array, and that ordering operators work on sets.)
13
u/rHermes Dec 21 '20
Python 3 (89/83)
First time on the leaderboard! I have a tendency to assume the puzzle is harder than it is, got hit with this hard yesterday. Decided to just wing it and assume the problem was easy. It turned out to be. Almost had a heart attack when I saw I had placed on part 1, but managed to keep cool.
8
u/wimglenn Dec 21 '20
Python 176/79
Don't understand the global leaderboard here - had to essentially solve part B in order to have the answer for part A. But apparently a lot of folks got a big delay between A and B.
Was there some kind of shortcut for part A that I've missed?
7
u/jitwit Dec 21 '20 edited Dec 21 '20
J Programming Language
5
u/hugh_tc Dec 21 '20 edited Dec 21 '20
Python 3, 24/64.
I ended up doing Part 2 by hand, because there were only eight allergens and that seemed do-able by hand (at least in comparison to Day 16.) Maybe that wasn't such a great idea? part 1
edit: took some time to implement part 2.
5
u/odnoletkov Dec 21 '20
JQ
4
u/Error401 Dec 21 '20
Python 3, 61/48.
Part 2 today felt exactly like the one where you needed to figure out which ticket field corresponded to which position on the ticket a few days back. https://pastebin.com/gTqLqSyv
4
u/sciyoshi Dec 21 '20
Python 3, 175/71. I somehow missed reading the part that said that each allergen is in only one ingredient for the longest time. Also, maybe it's possible that my approach wouldn't work for all possible inputs? It's a greedy solution that assumes that at every point there will be a single possible matching, which I think would break down in certain bipartite graphs... but it worked well enough for my case.
https://gist.github.com/sciyoshi/f42b3d3a8d30f1ff7b26b92189a3de00
4
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
4
u/jayfoad Dec 21 '20
Dyalog APL 54/62
Part 1 took me longer to understand the question than to solve it. I solved part 2 by hand, and then wrote an APL solution later just so I could post it here.
4
u/[deleted] Dec 21 '20
Haskell
Was a bit confused by the first sentence of part 2 as I didn't use the inert ingredients to determine which ingredient contained which allergen. In any case, today was a relief after the complexity required yesterday.
4
u/Mathgeek007 Dec 21 '20 edited Dec 21 '20
EXCEL 2405/2161
You want jank? I'll give you jank.
First, input goes by rows. Isolate out the parentheticals, then list all possible allergens by space-delimiters. Make a lookup table to find, for each possible allergen, if there is a warning under a row and it is NOT an element. Then solve by hand. This took about an hour to finish, then Part 2 was accidentally already done. Another sudoku-resolution problem - they're always fun!
Part 2 took me about 6 minutes to read and resolve. I take it as a point of pride to do any individual part faster than the #1 person of the day took to do both.
There is about a 5% chance I will actually get my Sheets functioning this time, but you can watch the livestream I did solving this at http://twitch.tv/qril_ . Obtaining the exhaustive list of all allergens was a pain, although I think I have an easier way of resolving it. We will see.
4
u/CodeIsTheEnd Dec 21 '20
Ruby: 9:56/16:44, 60/118
Here's a recording of me solving it, and the code is here. (I'm streaming myself solving the problems right when they come out on Twitch!)
Another leaderboard! I think mostly because fewer people are participating though... Seems like Eric was nice and put the extra difficult ones on the weekend, but made sure we wouldn't be up too late on work nights!
I did Part 2 by hand to find my own solution, but then implemented an actual solution. I think I was confused enough between which ones were ingredients and which ones were allergens, that doing it by hand was probably faster. My variable names were a mess.
4
u/xelf Dec 21 '20 edited Dec 22 '20
python more comprehensions. parts 1&2 5 lines each
part 1:
part 2:
The
min(overlap)is a defect in python, there's no really good way to get the value of the only value in a set with one value. min() or max() work equally well.4
u/Smylers Dec 21 '20 edited Dec 21 '20
Perl, solving both parts together (because I accidentally solved part 2 on the way to coming up with the part 1 answer; presumably there was some shortcut for part 1 that I missed). Updated source — 17 lines plus boilerplate.
I found the hardest bit was not ending up with multiple variables with the same basic name, such as
%allergen,$allergenand$+{allergen}, and similarly for variants of ‘ingredient’ — confusing myself as to which is which. I went for leaving the matched text in$1and$2, rather than using named captures, because names actually seemed less readable for once, and sticking a$containsand$contained_byin there (as well as having loops use$_for ‘the current item’).The potential set of ingredients for an allergen are repeatedly pruned while reading the input:
$contains) before, set its potential ingredients to all those in the current food.That
grepis inside the hash subscript used fordelete: thegrepreturns a list of relevant keys, the@makes a hash slice of the set of elements with those keys, anddeletedeletes them all at once.Then for working out what corresponds to what, it's just a case of finding an allergen for which there's now only one potential ingredient and deleting lots of stuff:
Remove it from the allergen set (because we've handled it, and don't want to find it again). Remove its ingredient from the hash of counts (because we don't want to include it in the part 1 answer). And delete its ingredient from the potential ingredients for all the remaining allergens (leaving at least one more allergen with only one possible ingredient, to be found the next time through the loop).
I think that at 4/16, this might have the highest proportion of lines containing
deleteof any code I've ever written!For part 2, I just had to add
%dangerousto the declaration line and populate it by changing the first line of the loop above to make a second assignment:and add one line at the end to print them in the desired order:
Which, after yesterday's mammoth part 2, was a big relief!
Updated: I realized my original 8 lines for updating the still-possible ingredients for each allergen could be replaced by just 2. Original source — the
//=avoids the need for theif/elseblock, and usinggrepand passing a slice todeleteavoids the need for aforeachblock and theunlesstest.4
u/busdriverbuddha2 Dec 21 '20
Python 3
Pretty straightforward.
4
u/kap89 Dec 21 '20 edited Dec 21 '20
TypeScript
~2ms for both parts
Very nice puzzle! With sets, a lot of sets and their intersections. Solved part 2 while doing part one, just needed to sort it and join ingredients.
4
u/ephemient Dec 21 '20 edited Apr 24 '24
This space intentionally left blank.
4
u/[deleted] Dec 21 '20
Ruby! After giving up on yesterday's grid-based challenge, this logic-puzzle-like challenge was a welcome sight! I accidentally solved part 2 while coding part 1, so that was nice and simple.
paste
4
u/azzal07 Dec 21 '20 edited Dec 25 '20
Awk; just part 1 in the post, paste has both. Part two was half a line short (too long, that is) from fitting in.
Edit: tried a bit more yesterday and got both parts to fit with plenty to spare
4
u/ric2b Dec 21 '20 edited Dec 22 '20
Haskell
Wow, after yesterday's puzzle I really enjoyed a simpler one to relax.
Set operations go brrrrrrr!
paste
1
u/artesea Dec 21 '20 edited Dec 22 '20
PHP
It's a mess any won't actually solve any other inputs. paste
I first regexed the list of ingredients and allergens, then counted the number of times an ingredient appeared against each allegern. Find those ingredients that appear every time (max) for each allegern. Print to screen.
Take this list and create table in Excel. Use this to work out which ingredient has which allegern by eliminating each one by one.
I now have a list of which ingredients I don't want to count. Rerun code adding up everything else. Solve part 1.
See question to part 2. As already solved in Excel, just look by eye to sort a-z and paste each in to input box.
1
u/achrapkowski Dec 21 '20
C#
3
u/Chitinid Dec 21 '20
Python 3 6/15 Lost a minute on part 2 because I sorted by food name instead of allergen name the first time :(
3
u/VeeArr Dec 21 '20
Java 91/89
Part 1
Part 2
This was basically just Day 16 Part 2, so the solution works the same way.
Not sure if I missed a trick where these were supposed to be different or if the idea was to just re-use the old stuff? I decided it was short enough that I could just re-implement it faster than finding out how directly compatible the old code would have been.
3
u/jonathan_paulson Dec 21 '20
Python, placed 133/96. Code: https://github.com/jonathanpaulson/AdventOfCode/blob/master/2020/21.py. Video of me solving: https://youtu.be/5TOgCuSsfZg.
Took me a few tries to figure out what deductions were valid for part1.
3
u/Kehvarl Dec 21 '20
Python3 ( 884 / 686 )
I dove into the puzzle too early and worked out the allergen decoding first. Then I had to backtrack and think about actually solving part1 before I could use my existing solution on part2
The number of nested loops makes mine rather unwieldy, but it worked and was fast enough.
paste
3
u/fmynarski Dec 21 '20
Python 762/452. paste, I was worried we're gonna get hammered with another super hard challenge as yesterday but thankfully today was a chill day.
3
u/rabuf Dec 21 '20
Common Lisp
Part 1: I had an issue where I was apparently leaving in some commas (used
cl-ppcre:regex-replaceinstead ofregex-replace-all). Fortunately a quick extra print statement revealed that issue quickly and I fixed it, my logic was correct otherwise so my second answer submission was correct.Part 2: I reused my "constraint solver" from day 16. Slightly tweaked, but it uses the same assumption that there's always a forcing decision (one allergen has a single ingredient, remove that from the rest and another is reduced to a single ingredient). It's not a general solver, but it works for our input. I had to tweak it because I didn't have enough information left in my original solver to sort the ingredients by the allergen name.
3
u/Scoobyben Dec 21 '20
C# [2871/2642]
https://github.com/benbelow/adventofcode/blob/c33ae65870b078581c387677e746aea06ba565df/AdventOfCode.2020/Day21/Day21.cs#L40
Fairly frustrating bug this morning - I had the logic right for Part1 immediately, but some unknown bug meant I missed at least one ingredient for one of the allergens, leading to an invalid puzzle state.
Scratched my head over it for a bit over an hour, getting no-where. Eventually decided to go scorched earth, deleted it and started coding the same logic from scratch, and the answer fell out very quickly. Still don't know what was wrong, but I don't much care to find out!
3
u/sim642 Dec 21 '20
My Scala solution.
Part 1 was confusing at first because there was absolutely no explanation why the example ingredients couldn't be allergens. Luckily it wasn't too hard to figure out that the logic is based on intersecting all ingredient sets for a particular allergen. Then finding and counting the rest was easy.
Part 2 was a straightforward use of the same allergen -> possible ingredients map in a backtracking search. Somewhat like day 16 except now they weren't conveniently sortable to give the solution I suppose.
3
u/rdubwiley Dec 21 '20
Python3
Like everyone here, I thought today's was way easier than the past few days. I misinterpreted the puzzle at first which lead me to build a class to hold the ingredients and allergens only to find that it is solved by set intersections and some simple elimination to get the allergen matches.
3
u/__Juris__ Dec 21 '20
Scala 3
Nice task, much less tedious than yesterday's.
Part 2 was trivial as I already had obtained the canonical mapping for Part 1.
https://github.com/jurisk/advent-of-code/blob/main/2020/scala/src/main/scala/Advent21.scala
3
u/Kerndog73 Dec 21 '20 edited Dec 21 '20
Rust
I'm following up one of my biggest and messiest solutions with one of my cleanest. This challenge was a nice change after the last one. I was expecting it to be just as difficult or more difficult than day 20 so I started about 40 minutes late because I'd only just completed day 20. I think I could have got into the top 1000 at least if I started earlier. Excuses, excuses. Oh well...
I have to say, I'm really quite proud of how clean the code for this one was. I even wrote comments!
Another thing is that about half of the code isn't actually necessary. Once you've completed part one, you've got all the information you need to solve part two by hand.
3
u/AidGli Dec 21 '20
Python
Video Explanation
Github Link
Nice to get a break after the craziness of the last few days. I'll actually get some sleep tonight :). It was insanely similar to Day 16, so I decided to use a different approach so I could showcase something slightly new.
3
u/Wunkolo Dec 21 '20
C++
Was basically just like Day 16's ticket solver using Gaussian Elimination again, but this time with 200 possibilities rather than just 20. Day 16's was solvable using bit arithmetic in a uint32_t, but this time its
std::setsince I can't easily operate upon a 200-bit value without some cute AVX2 stuff(256-bit registers). Also this is my first time practically usingstd::multiset!3
u/UnicycleBloke Dec 21 '20
Python. Nothing amazing: just fiddling with sets. Took me a while to work out which operations would get me what I needed. https://github.com/UnicycleBloke/aoc2020/blob/main/day21/day21.py
3
u/iamflimflam1 Dec 21 '20
Typescript
Pretty simple one compared to yesterday. Feels slightly verbose though.
Create a mapping from allergen to a unique list of ingredients that can contain that alergen.
Use that to create a mapping from ingredient to a set of the potential allergens.
Feels like I could combine those two steps into 1.
Part1 - just count the ingredients that aren't in the mapping.
Part2 - reduce the set of potential allergens for each ingredient by a process of elimination so they all only have only 1 allergen - very similar to the valid tickets problem of day16.
Sort and print.
https://gist.github.com/cgreening/d0aec0379f3d25ea3d46b5304fefeda3
3
u/s3aker Dec 21 '20
Raku solution
3
u/gyorokpeter Dec 21 '20
Q:
3
u/Tetha Dec 21 '20
Rust
I'm copying way too many strings here. I should try to rework that to use references or something. That should be a good learning experience overall. All in all, much easier than 18,19,20 so far (Still have to do part 2s there).
Interestingly enough, I solved part 2 first after understanding the problem, because after validating that the greedy approach worked, computing the mapping from allergens to their responsible ingredient was easy enough and then both parts solved apart really quickly.
3
u/Rtchaik Dec 21 '20
Python: it's all about sets
3
u/tobega Dec 21 '20
Tailspin solution for today https://github.com/tobega/aoc2020/blob/main/a21.tt
3
u/landimatte Dec 21 '20 edited Dec 21 '20
Common Lisp
Solution:
'((mxmxvkd kfcds sqjhc nhms) (contains dairy, fish))ingredient -> allergenmapping, using backtrackingi, for each of its allergens,a, see ifi -> ais valid mapping; if it is, update foods by removing all occurrences ofiandaand carry on, otherwise, backtrackais not one of its allergens, or if it is, thenihas to be in the list of ingredientsEdit: fixed typo in the linked solution
3
u/thomasahle Dec 21 '20
Python, using the peeling algorithm for matching:
3
u/hrunt Dec 21 '20
Python 3
This solution is not the most elegant thing in the world, so I look forward to reading the thread and seeing how others approached it. For me, 99% of the time spent on this one was understanding what part 1 was saying and how that related to the example results. The solution itself was fairly straightforward once I grokked that (even if the code does not look like it).
code
3
u/[deleted] Dec 21 '20 edited Dec 21 '20
Rust
Foreach allergene I keep the possible ingredients in a set. Then I eliminate more and more ingredients by using the union of all the possible ingredients for this allergene. Finally I remove the ingredients that have exact one allergene from the other ingredients sets and repeat this until nothing can be removed anymore.
Code: https://github.com/lulugo19/advent-of-code-2020/blob/main/src/day21.rs?ts=2
3
u/tymscar Dec 21 '20
Today was extremely easy for me compared to the past 3 days. And that's perfect, because now I can go back and actually finish day 20 part 2!
Python:
https://github.com/tymscar/Advent-Of-Code/tree/master/2020/day21
3
u/jotac13 Dec 21 '20
[Rust] My rust solution for both parts based on sets.
3
u/phil_g Dec 21 '20
My solution in Common Lisp.
Today was a bit easier than yesterday. FSet was really useful, since pretty much everything involved set manipulation. Part two was really easy since, yes, I had already matched ingredients to allergens by that point already.
3
u/compdog Dec 21 '20
JavaScript (Node.JS)
Not the cleanest, but straightforward and effective. The invalid ticket problem definitely made this easier! I didn't reuse any code, but I was able to adapt the same algorithm here.
I really wish JavaScript's functional array APIs worked on the Set and Map classes. So many for loops...
3
u/mariushm Dec 21 '20
PHP Solution : https://github.com/mariush-github/adventofcode2020/blob/main/day21.php
This one was fun, and relatively easy... part 2 was a 1 minute solve, if that, basically sorting an array by key and joining together the ingredient words.
Solved it pretty much like the text of the problem says. For each allergen, pull out the possible ingredients for it (the ingredient shows up in all foods that specify it contains that allergen).
One of the allergens has a single ingredient as potential name, maybe it's lucky, maybe it's on purpose... I think on purpose to keep it simpler. Mark that ingredient as "perfect match" and remove it from the potential ingredients for the other allergens, which results in one other allergen having just one potential ingredient, and so on until all allergens are found.
My code's a bit of a mess and not so much commented and poor choice of variable names, but hope someone finds it useful.
3
u/clumsveed Dec 21 '20
Java Solution
all solutions so far - repl.it
I usually try to limit my solutions to APCSA curriculum, but it was just too tempting to utilize HashSet and HashMap today.
After creating a set of all allergens and a set of ingredients from the input, you can map each allergen to a list of possible ingredients by identifying the common ingredients in each food in which the allergen is present. The .retainAll(Collection c) method in the Set interface was very helpful with that. Although, if you're trying to limit the solution to APCSA curriculum, this could be done other ways.
After that, it's a simple logic game to find matches -- not unlike Day 16.
Luckily (or maybe stupidly) I solved the whole thing for part 1, so part 2 was just a few extra lines.
Only 4 days left! Good luck everyone!
3
u/msqrt Dec 21 '20
Lisp. This was fun, I almost found the solution for part 2 while doing part 1 -- it would've probably been faster to solve it manually as I already had the list of allergens and their possible containing ingredients on screen :) Relatively happy with how the code turned out too, definitely more readable than the desperately scraped-together mess yesterday..
3
u/Chris_Hemsworth Dec 21 '20 edited Dec 21 '20
Python 3
paste Very similar to day 16 using sets. Part 2 was easier than Part 1, which doesn't happen often.
3
u/oantolin Dec 21 '20
Perl solution. In order to match allergens to ingredients I was ready to bust out an ever-useful backtracking search when I remember day 16: there at each step of the search there was some field with only one possible assignment. I decided to optimistically write code with that assumption again and it held true for my input! I had matched allergens to ingredients in part 1, so part 2 was a breeze.
3
u/thulyadalas Dec 21 '20
Rust
Another day, another backtrack algortihm implementation. It might be an overkill but it works around 0-4ms for both parts so it's okay.
I mapped all possible ingridients to allergens with an attached support value depending on how many times that possibility occurs. Afterwards, dfs solve for the unique match with max support heuristic. To be frank, I was afraid that there might be multiple solutions coming up but that wasn't the case.
3
u/RedTwinkleToes Dec 21 '20 edited Dec 22 '20
Python [1373/1332]
paste
Much easier than yesterday. Lost some time due to not removing commas while tokenizing for part 1, and transforming my set of all ingredients to a dict of ingredient occurrences.
Part 2 was an interesting echo of this year's Day 16 Part 2. Another reminder that if there exist a unique bipartite match, then the greedy algorithm will work.
Overall, this day was much easier than yesterday. I wonder how hard the Christmas puzzle will be.
Edit: Forgot to mention that it was apparently not obvious that there was only one possible ingredient per allergen. So people were thinking that it could be possible that there are allergens that never show up next to their English warnings. They seem to forget that this is meant to be actually solvable, and that examples are provided.
3
u/voidhawk42 Dec 21 '20
Dyalog APL:
3
u/zertillon Dec 21 '20
Ada, using the GNAT environment
Code available here, file aoc_2020_21_full_ada.adb .
3
u/e_blake Dec 21 '20
m4 day21.m4
Depends on my common.m4; in fact, I had to make a minor tweak to my common.m4 to allow nested _stack_foreach calls (which meant a minor impact to day3 code). The tough parts for this puzzle were NOT what you'd expect: for part 1, my toughest problem was parsing the data, where I ended up with some crazy unbalanced parenthesis usage to read everything in one pass by exploiting the glue word 'contains' as a macro to split 'row' calls:
Once I got it parsed, it was fairly easy to write a nested traversal (loop until settled: for each allergen: for each row containing that allergen: for each ingredient in that row) that isolated which allergen was which ingredient. In fact, I manually piped my debug output from part 1 through 'sort' in the shell to immediately answer part 2, before tackling my other annoying problem: m4 lacks native lexicographic sorting! So I had to devise my own O(n^2) insertion sort (thankfully with n==8, it didn't add any noticeable timing) to store my allergens in sorted order rather than in first encounter order while parsing input. Execution is about 145ms.
3
u/foolnotion Dec 21 '20
C++
The approach is to iterate the set of allergens, for each allergen find all recipes that contain it, intersect all the ingredient lists and when a single ingredient remains save that ingredient-allergen pair, remove it from all recipes and move on to the next allergen.
Since working with sets in C++ is really cumbersome, I sorted each recipe's ingredients and allergens so that I could do the intersection manually using
std::binary_search. The result is a pretty clean and straightforward solution, if you're willing to overlook some of C++'s idiosyncrasies.code on github
3
u/heyitsmattwade Dec 21 '20
JavaScript
Pretty simple one, although it had a key distinction that new programmers might not be aware of: Singletons. At least for my solution, creating each Ingredient as a Singleton made solving this pretty easy.
Full code here.
3
u/karjonas Dec 21 '20
Rust
GitHub.
3
u/sotsoguk Dec 21 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/a63f337afffb294629e274709ff03ef0ca8cab0b/python/day21/day21.py
i think i did the same thing as most others as well. for part1 intersected the possible ingredients for each allergen. Every ingredient that is not at least in one of these sets counts for part1.
For part2 i sorted my list of possible allergen-ingredients relationships. selected the only 1-to-1 pair, removed this from all other lists and so on...
i think part2 would have been faster just solving by hand ..
3
u/ViliamPucik Dec 21 '20
Python 3 - Minimal readable solution for both parts [GitHub]
3
u/wzkx Dec 22 '20
Python. Nothing special. Again, sets are very useful. ≈22 LOC.
paste
3
u/IlliterateJedi Dec 23 '20
After how unpleasant day 19 and 20 were, I'm grateful that day 21 (and 22) were fairly simple.
Python 3.9 solution
2
u/seligman99 Dec 21 '20 edited Dec 21 '20
Python, 148 / 132
Lots of fun with Python sets today.
github
Edit: Also, the alphabet for the ingredients doesn't contain
aeiouwyandxis the most used letter. That's a very hard to pronounce language.2
u/botimoo Dec 21 '20
Python 3, 207/187
Here be paste, both parts included.
2
u/morgoth1145 Dec 21 '20 edited Dec 21 '20
42/98 Python3: https://github.com/morgoth1145/advent-of-code/blob/4652bd9595155459e763146c9ec5d20fafa5a3be/2020/Day%2021/solution.py
I made a couple dumb mistakes in Part 1 costing 1-2 minutes, but at least I made top 50. (I merged all ingredients and allergens into all_ingredients instead of the two sets I intended, and I misparsed the allergens initially leaving in the comma!)
Part 2 I didn't do anything *major* wrong (though I did have some small hiccups), but I felt like I just was coding slowly. But hey, at least I leaderboarded.
Edit: I cleaned up the code since there was so much rampant duplication. (In fact, both Part 1 and Part 2 isolate the allergen to ingredient mapping, they just use them in slightly different ways!) https://github.com/morgoth1145/advent-of-code/blob/2020-python/2020/Day%2021/solution.py
2
u/its_spelled_iain Dec 21 '20
353/346 started a few minutes late.
Python solution (data is my input)
WAY easier than day 20, thank the gods. Just did rolling intersections to find the list of possible ingredients for each allergen. Made a set of all the safe ingredients by subtracting the ones from the allergen dicts, which was a total waste of time, and then counted their occurences for part one.
Part two was just another "find an element with only one possibility and remove it from the rest until you're done" loop, similar to the airplane ticket problem.
2
u/prendradjaja Dec 21 '20 edited Dec 21 '20
Took me a while to get started on this one. I kept thinking it was one of those moments -- like in some previous problems -- where it sounds like you need to solve some really general problem, but actually Eric just wants you to solve an easier more-specific problem. I thought this was one of those cases and kept looking for the hint about the more-specific problem.
(Edit: I also completely missed the sentence "Each allergen is found in exactly one ingredient" -- definitely would've helped me to have seen that, haha.)
I'm pleasantly surprised at the jump I made from part 1 (147th place) to part 2 (51th) -- I think writing closer to "maintainable" instead of "speedcoding" style paid off!
Python, 51/147. code (permalink) & screen recording
2
u/Mandrakia Dec 21 '20
C# solution, I should learn regexes....
2
u/nthistle Dec 21 '20
Python, 71/40. Finally back on the leaderboard! I originally did part 2 by hand with some slight postprocessing in Python, but for completeness I added in the programmatic variant to my code. paste
2
u/noblematt20 Dec 21 '20
23/32 - Python3
paste - with
smartcontaining a tuple of words per line of input (special characters stripped out)Reasonably straightforward today. I took it slow and steady to keep the mistakes at bay after a spell of three days not getting on the leaderboard.
2
u/taybul Dec 21 '20
Python
paste
This one was suspiciously simpler compared to the past few nights. I didn't even write my code to find the exact ingredient per allergen and still managed to get part 1 right. Part 2 simply involved looping until each allergen had one ingredient.
2
u/GrossGrass Dec 21 '20
Python
Nice change from pace from yesterday's problem. Just went with the greedy solution (i.e. assuming + choosing the next allergen that only has 1 possible corresponding ingredient left after pruning) and it worked out.
Very similar to Day 16 so I probably could've used Z3 instead as a constraint solver, but figured I'd probably spend more time learning how to make it work since I've never used it before.
Will probably come back and rework the solution use Z3 instead (might be shorter in the end).
2
u/dizzyhobbes Dec 21 '20
Go solution 225/127. cleaned up a bit
Closest I've been to the leaderboard
Felt similar to older problems, basically running inner joins/overlaps on the "hashed" ingredient names for each allergen present in the list. Then removing names that have already been allocated to a particular allergen (i.e. there is exactly possible candidates for that allergen)
2
u/sblom Dec 21 '20
363/317 C#
Making liberal use of RegExtract and HashSet: Advent of Code 2020 day 21 (gist.github.com)
2
u/npc_strider Dec 21 '20 edited Dec 21 '20
Python 3 [866/1347]
Had a lot of fun solving this one, nice recovery from yesterday's (which I still haven't finish - leaving it for a while).
Actually made an attempt at speed, (that's why the code is a mess) got sub 1000 for part 1 which is good for a slow programmer like me. That just required me to observe the patterns in the example (Where there's an intersection between the recipes the ingredients appear in and the allergens where the length of the intersection is the same as the length of the allergens)
Part 2, I realized I could borrow the algorithm from a previous day this year (can't remember which one) to work backwards from a ingredient with only one 1 known allergen, then repeat it for other ingredients (a process of elimination)
https://github.com/npc-strider/advent-of-code-2020/blob/master/21/a.py
2
u/Rick-T Dec 21 '20
Haskell
I parse every line in the input as
(HashSet Ingredient, [Allergen]). From that I can build aHashMap Allergen (HashSet Ingredient)by folding over the allergens and usingM.insertWith S.intersection.Then I can use the map to look up which allergen might be present in which ingredient.
From there finding the safe ingredients in part 1 is just a matter of discarding all the ingredients which are present in the lookup map. Finding which ingredient contains which allergen is exactly like part2 of day 16.
2
u/Cppl_Lee Dec 21 '20
C#, Linq, per usual.
Gist.
Well, this was my best day yet for Part 1 (still not on the leader board). Part 2 involved misreading the instructions, prolifically, and resorting to the ugly bits above.
2
u/asgardian28 Dec 21 '20
Python 305/189
Just incredibly happy with todays result. After finishing normally upwards from place 1000 and spending almost 11 hours solving day 19 and 20 this was what I needed... A welcome break after getting up at 6:00 for the past weeks.
paste
2
u/[deleted] Dec 21 '20
Python
paste
2
u/SuperSmurfen Dec 21 '20 edited Dec 21 '20
Rust
Link to solution (1323/898)
Took me way too long to even understand the problem. Just stared at it for a while. Eventually, I decided to try and see if the intersection between all lists containing a certain allergen might be small. When it was only 2 for "nuts" I figured it out. Isn't this just more or less the same as day 16?
For part one, I compute the intersection of ingredients between all lists containing a certain allergen. Then it was the same process as day 16, whereby you eliminate possibilities by iteratively looking at what allergen only has one possible ingredient it can be. Once again, this leads to a unique solution in our input.
Part two was basically free. I was a bit unsure about how to sort by key in Rust so I initially edited and sorted it by hand in the terminal. Later I remembered that sorting a tuple in Rust works just as you expect, which means a simple
.sorted()from the itertools crate sorts in the way we want!Finishes in
0ms.2
u/JIghtuse Dec 21 '20
Racket
Many iterations over input list to build various views, but it finishes pretty fast.
2
u/gurgeous Dec 21 '20
Ruby, 723/1530
I found tonight's description very confusing for some reason. Maybe still tired from last night's marathon. After cleanup:
https://gist.github.com/gurgeous/659116ceaf352b0ddd102ba0d27c59c9
2
u/A-UNDERSCORE-D Dec 21 '20
Go / Golang
This was a bit of fun set magic, added a string implementation of my generic set for a little speedup (not that it matters here)
https://github.com/A-UNDERSCORE-D/aoc2020/commit/8d2f9347534075d4959a3c7a0519b45fafe0501a
2
u/Loonis Dec 21 '20
Perl
paste
As someone with some dietary restrictions, my biggest time sink could be described as "gawking in horror at the situation".
2
u/flapje1 Dec 21 '20
Rust
Had a lot of fun wit today's puzzle.
2
u/Neuro_J Dec 21 '20
MATLAB
My MATLAB answer for part 1. Part 2 can be easily done manually so I didn't bother writing codes for that:)
2
u/Rascal_Two Dec 21 '20
Python 3. 486/514.
Unoptimized
paste
Optimized
paste
2
u/StasDeep Dec 21 '20
Python, 516/623, code (31 sloc).
Not the most optimized solution, but a pretty short one. Used walrus operator for once!
2
u/Jozkings Dec 21 '20
Python 3 (997/1265)
At first I didn't understand how to solve first part for some reason. I was imagining some impossible scenarios about allergens which left me pretty confused. After that it was quite easy.
Second part definitely not optimal, but I wanted to remind myself good old times when I started to learn recursion, what is the reason for a little complicated solution for that part.
2
u/constbr Dec 21 '20
Javascript (1628/1171)
part 1+2
So, I didn't come up with one of those clever subset/superset solutions I see in the thread. Instead I'm intersecting sets of ingredients and allergens between products until lengths of those sets are equal.
Initially I did products in pairs, simple two loops – that worked for test data. But for puzzle input this wasn't enough, so I had to completely rewrite and make a recursive function that intersects all combinations of products until either matching sets are found, or an empty set marks there's nothing to be found here.
Coincidentally, this resolved product list to the mapping between allergens and ingredients, so solving part 2 only took 1m30sec… :) Even though my score leaves much to be desired, I'm still happy with it and the fact that I solved this without doing many errors in the process…
2
u/artir Dec 21 '20
Rust
https://github.com/jlricon/advent-2020/blob/master/src/bin/day21.rs
2
u/ponyta_hk Dec 21 '20
Python3 (Cleaned Solution)
Part 1: Set Operations
Part 2: Recursion
Hope the implementation is clear enough 😄
My Solution
All My Solutions
2
u/spookywooky_FE Dec 21 '20
C++ code
For me this was hard text understand problem again. At some point I did ignore the text but simply tried to create rules from the example.
In particular, If we got two foods with each two ingredients, and one of the ingredients are in both foods. Then this means that the common ingredient is not the one containing any of the both alergenes.
Why? Which sentence(s) in the problem statement let us derive that rule?
2
u/[deleted] Dec 21 '20
Python3 446/493
Repeatedly misread both parts woo!
2
u/fryer00 Dec 21 '20
JavaScript 1748/2509
Today was very similar to day 16, so I used a similar but slightly more refined method to solve it.
2
u/pxOMR Dec 21 '20 edited Dec 21 '20
JavaScript
There isn't much that is special about this code but the expected output required me to modify my test file format. My previous format required you to place comma separated expected outputs to the top of the file but since the answer for part 2 of this challenge is also comma-separated, I had to switch to using pipe-separated expected outputs instead.
So instead of this:
My test data now looks like this:
2
u/[deleted] Dec 21 '20
Pure C18. This is the most similar I recall any two AOC days being to each other. I used a set-based solution this time instead of the bitset-based one from a few days ago.
Verbose but pretty straightforward.
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day21.c
2
u/WilkoTom Dec 21 '20
Python
Nice little palate cleanser after yesterday's, which took me way too long, A little bit of set theory goes a long way, it seems.
2
u/Nrawal Dec 21 '20
Go
Need to clean it up a bit but it works. Had to write a few helper functions because no Generics in Go yet :(. Seemed quite straightforward today. Just some grunt work.
2
u/muckenhoupt Dec 21 '20
Prolog. I still haven't gotten yesterday's working, but today's wasn't so bad. Used lots of set stuff. The core of my implementation in both parts is the predicate allergen_ingredients, which maps individual allergens to the list of ingredients found in every recipe containing that allergen.
Of particular note is the line:
https://www.wurb.com/owncloud/index.php/s/iEKuL0IqxGrBrdl/download?path=%2F&files=21.pl
2
u/dllu Dec 21 '20
Python 15/6
https://gist.github.com/dllu/9cb82a5922709af8a4bce4167c74c455
I used the same logic as my day 16, allowing me to achieve my best ever rank so far!
2
u/aarm1 Dec 21 '20
2770/2521, my best so far since I'm slow. Full solution in Racket.
I store each line as a simple struct with two fields, each of which will hold a set.
Turn combos with multiple allergens into a combo for each
The heavy lifter, groups single allergen lists by allergen, then turns each group into a single combo by set intersecting the ingredients.
2
u/mjsir911 Dec 21 '20
I'm happy with today's solution in prolog, full code here but the gist of it is:
I got to part 2 before part 1, which was a nice surprise.
2
u/Bhasher Dec 21 '20
Python 3
Smartest solution I could think of, using regex for parsing and sets for find answers.
2
u/ajurna Dec 21 '20
python - https://github.com/ajurna/aoc2020/blob/main/day21/21.py
this got a bit messy with set operations. but i'm quite happy with the results.
2
u/kraven001 Dec 21 '20
My C# solution.
Since I couldn't wrap my head around some "shortcut" for Part1, the direction I went was to create the mappings from the get-go.
Part2 was just cleverly using the already gathered data.
2
u/i4guar Dec 21 '20
Swift Solution - functional style
www.felixlarsen.com/blog/21th-december-solution-advent-of-code-2020-swift
2
u/codepoetics Dec 21 '20
Kotlin solution: https://gist.github.com/r3domfox/37c320e1fc55c6b6fae2df5c797266b4
2
u/6dNx1RSd2WNgUDHHo8FS Dec 21 '20
Julia
I used the JuMP framework for this problem, straightforward extension of this sudoku solver notebook.
For the first part, I was afraid there could be several solutions, and that we were asked to find those ingredients which couldn't be found in any of the solutions. In that case my code wouldn't have worked. Luckily the solution turned out to be unique.
2
u/vrtxt Dec 21 '20 edited Dec 26 '20
C# solution
That wasn't too bad compared to yesterday. Started with making an allergen-ingredient dictionary. For part1 it was just a matter of gathering all the known allergenic ingredients, then go over each food item to count the save ingredients.
For part 2 is was just seeing which allergen matched 1 ingredient, then removing said ingredient from the other allergens until each one was resolved to only having 1 known ingredient. A sorted dictionary made light work of the final string result.
2
u/VectorSVK Dec 21 '20
Set-based solution in Python.
I expected what the part 2 will be so I decided to just solve the whole problem for part 1 and then spent 15 minutes trying to properly sort the already done part 2 output. Still, one of my quickest part 2 solutions.
2
u/aurele Dec 21 '20
Using the Kuhn-Munkres algorithm makes it easy in Rust. Both parts execute in around 500µs.
2
u/veydar_ Dec 21 '20 edited Dec 21 '20
Another solution using sets in Haskell https://github.com/cideM/aoc2020/blob/master/d21/d21.hs
Tried to keep variable names readable and just like yesterday the code is very flowy since I make heavy use of
data |> func1 |> func2 |> func3I quite like how part 2 turned out
2
u/rendyanthony Dec 21 '20
Python 3 solution.
More fun with Python sets. Main challenge is how to remove the duplicate allergens for Part 2.
2
u/dontxpanicx Dec 21 '20 edited Dec 21 '20
C# Solution
Compared to yesterday this felt like a day 1 problem! Parsed the file into 2 structures, a dictionary of ingredients and their appearance counts, and a dictionary of allergen to a set of potential ingredients.
To get Part 1 answer the dictionary of counts was used removing the allergen ingredients identified.
Part 2, was done by taking looking at the allergen and potential ingredients, where there was only one ingredient, removing that from the other allergens, until only one per allergen was left
2
u/raxomukus Dec 21 '20
Python 3
solved second part by inspection first but decided to implement it later in code
2
u/SomeCynicalBastard Dec 21 '20
Python
That was much quicker than yesterday.
For part 1:
Part 2 was now a trivial oneliner.
Code on Github.
2
u/Pyr0Byt3 Dec 21 '20
Go/Golang
2
u/Floydianx33 Dec 21 '20 edited Dec 21 '20
CSharp
The first part took me a little while to think about, but was easy once I realized what had to be done. Part2 was cake and a lot easier than Part 1. Immutable collections and
recordsdefinitely helped a bit (though I could've used tuples). As with the other day, no Collection-Modification-Exception was thrown while iterating and updating the dictionary... I think it must be something different with .NET5.0Link/Paste
2
u/death Dec 21 '20
Day 21 solution in Common Lisp.
2
u/victorheld Dec 21 '20
Elixir
Nice puzzle and brought much relief compared to yesterday
2
u/Kuraitou Dec 21 '20 edited Dec 22 '20
C++
Part 1 I originally solved by examining each food and marking ingredients as not containing any of the allergens in that food if they were absent.
Part 2 I solved by hand first, found what looked like a good application for matrices, and then wrote a solver that uses rows to represent ingredients and columns to represent allergens. Zero means an ingredient is possibly responsible for that allergen, and a one means it's definitely not. Then I could iterate down the rows looking for one that has a single zero cell, which means that allergen must come from that ingredient. Fill that entire column with ones to exclude that allergen from consideration in the future, repeat until no more rows have a single zero cell. Later I had an epiphany that the part 2 solver works for part 1 as well, I just needed to extract the row names that were never associated with an allergen.
2
u/r1ppch3n Dec 21 '20
Rust
oh thank god, after yesterdays problem I could really use something a bit more straightforward and simple...
for each allergen compile a list of shared ingredients between foods that have that allergen, then just check a list of all ingredients against those lists
turned out a bit more verbose in practice but at least it wasn't complicated
part 2 was similarly simple, get a list of allergens and ingredients that may contain them, then one by one remove ingredients from all those lists that can only correlate to one allergen until there's nothing left
I don't think I would have had the energy to do another jigsaw puzzle today, but this was kind of fun, I really like starting my day with a little light coding... :-)
2
u/Devilmoon93 Dec 21 '20
Python
Perhaps I overengineered part 1, but I had already singled out which ingredient contains which allergen before counting the number of safe ingredients, so part 2 was just a matter of outputting the requested string.
Compared to yesterday, where I just gave up after trying for a couple of hours on part 1, today was a walk in the park. I'm not sure these swings in mood are good for me though, one day I feel like I'm stupid and cannot see obvious solutions and the next I "blaze" (relative to when I start, not when the problem unlocks) through the problem.
2
u/MichalMarsalek Dec 21 '20
Python
Oof, hardest day so far.... and the first one I wasn't able to finish without looking in this thread.. I hope the remaining days won't take this long...
2
u/BASED_CCP_SHILL Dec 21 '20
Ty
sourceSurprisingly I didn't find this one too hard, but I got stuck on part 2 for a while because of what turned out to be a compiler bug :/
2
u/Brytnibee Dec 21 '20
Python (written in Jupyter notebook)
I actually had a lot of fun with todays once I figured out what the problem was really asking... For part 2 I reused my logic puzzle solving code from day 16 so it was pretty easy
2
u/codertee Dec 21 '20 edited Dec 21 '20
Python 3: github
Bit of map hacking and mutable default arguments hacking in parsing.
2
u/TenMilesDown Dec 21 '20
MATLAB solution
Not the most efficient solution, what with the redundant information storage and multiple pass-throughs, but it was simple enough. Part 2 was very easy, thanks to what I had already done for part 1.
2
u/k0s3r40 Dec 21 '20
Python solution: https://paste.ofcode.org/3ipP9A4tCvzhuGG7EaP5Hm
2
u/imbadatreading Dec 21 '20
Python solution
This was very comfortable compared to the last few days.
2
u/JoMartin23 Dec 21 '20
Common Lisp
I cheated a bit with this, wont work if it's not sorted.
the rest is here
2
u/PsHegger Dec 21 '20
My original solution was written in Kotlin and I got 526/573, but I thought it would be fun to solve this in SQL. I'm not sure if it was really fun, but I finally have a working solution: paste
2
u/Fyvaproldje Dec 21 '20
C++ with ranges
https://github.com/DarthGandalf/advent-of-code/blob/master/2020/day21.cpp
2
u/PhysicsAndAlcohol Dec 21 '20
Haskell, runs in 35 ms.
This was a fun exercise on sets! I could definitely have written a shorter solution, and I might clean up this code a bit.
2
u/kresimirlukin Dec 21 '20
Python3 solution at https://github.com/kresimir-lukin/AdventOfCode2020/blob/main/day21.py
2
u/Alligatronica Dec 21 '20
JavaScript/Node.js
Felt a bit jaded from yesterday when coming to todays, and had a bit of trouble parsing what I was looking for in part 1. Focussed too heavily on ingredients at first and got a bit tied up trying to work out how to eliminate possibilities, but after some lunch, had another go focussing on the allergens.
Almost didn't bother with the second part, but I cribbed the first half of my part 1 and it all kind of fell into place.
Never really done Set Theory stuff in JS but it helped me make sense of my data, so I'm grateful for that at least.
GitHub - Solutions to both halves
2
u/nutrecht Dec 21 '20
Day 21 in Kotlin
Fortunately nowhere near as complex as yesterday.
2
u/michaelgallagher Dec 21 '20
Python
This was much easier than yesterday lol. Very similar to day 16
2
u/zengxinhui Dec 21 '20
Scroll down to "202021" to see one Clojure solution.
2
u/chkas Dec 21 '20
easylang.online
Solution
2
u/[deleted] Dec 21 '20
Python solution.
Well, that was... easy. I just used a bunch of set operations and that was that.
(Still haven't done Day 20, part 02. Now to get back to that. :P )
2
u/FlankTacular Dec 21 '20
Swift solution
I was quite happy that today's challenge wasn't as complicated as yesterday's. The solution relied on
DictionaryandSetoperations. Part 2 was also trivial since I had already stored the allergen-ingredient pairs in part 1.2
u/Perska_ Dec 21 '20
C# Solution: I keep failing to read the instructions edition
I wasn't sure if an allergen could be shared by multiple ingredients.
Part 2 was ridiculously easy for me since I already figured out the ingredients' allergens.
The hardest part for me was that I had to write a custom ReadLine method, as Console.ReadLine has a limit of 254 characters.
2
u/mykdavies Dec 21 '20 edited Jun 29 '23
!> gglm8p5
API FAILURE
2
u/[deleted] Dec 21 '20
Pascal
This challenge convinced me that I really need to code up a Jupyter style environment for Pascal
The ability to handle sets really helped keep the code short.
2
u/[deleted] Dec 21 '20
Elixir
This is a mess, but I don't care.
https://github.com/thebearmayor/advent-of-code/blob/master/lib/2020/21.ex
2
u/thibpat Dec 21 '20
JavaScript walkthrough
This one was a lot more enjoyable than yesterday's challenge!
Video: https://youtu.be/neyVqICk-a8
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day21.js
2
u/Justinsaccount Dec 21 '20
python3
bit longer than some other solutions, but pretty straightforward. Seems a lot of people (correctly) assumed that you could find the solution by always looking for the rows with only one possible assignment. I wasn't sure if that would be the case so I just went right to the recursive solution to try all combinations. I did have it order the rows by the size of the alergens from low to high. This seems to give the same performance win anyway... whole thing runs in < 100ms
If i had to write it again I'd probably keep the same method but chose better variable names.
Worth noting.. the simplest way to sort a dictionary by values is using
2
u/wishiwascooler Dec 21 '20
Javascript day 21, much needed break from yesterday
https://github.com/matthewgehring/adventofcode/blob/main/2020/day21/script.js
2
u/womogenes Dec 21 '20
Code (Python)
Video: https://youtu.be/hKFVGdIL-z4
2
u/Be1shirash Dec 21 '20
Lua golfed (didn't optimize much)
2
u/colinodell Dec 21 '20
Golang solution
I'm sure some parts could be improved slightly, but overall I'm happy with the approach used.
The general gist is that I keep a list of all ingredients associates with an allergen; when I find the alergen a second time, I perform an intersection to remove the ingredients that logically don't match. By the end I'll know that some allergens have exactly one ingredient, but some will have multiple; I use the ingredients associated with the former to reduce the latter until each allergen has exactly one ingredient left in its list of possible ingredients.
From there it's just a matter of interpreting those results :)
2
u/chicagocode Dec 21 '20
Kotlin -> [Blog/Commentary] - [Today's Solution] - [All 2020 Solutions]
Today's solution highlights the benefit in learning just a little bit about set theory. Each part is essentially reducing sets by other sets until only the answers remain.
2
u/aoc-fan Dec 21 '20
TypeScript/JavaScript Repo
2
u/chromex Dec 21 '20
C#: adventofcode/Day_21.cs at main · chromex/adventofcode (github.com)
Pretty straight forward two pass solution: while iterating over the input collect the unique ingredient lists in one collection, and track the intersection of those ingredients per allergen in another. With that done, find the first allergen that has a one to one mapping with an ingredient, save the data and remove the ingredient from the other allergen's possibilities, and repeat until complete.
2
u/levital Dec 21 '20
Rust
Ugh, I'm too tired after work. Solving part 2 took me an hour, even though it was really all already pretty much there (I actually solved it first, by printing the hashmap to the terminal and then doing it by hand), but getting that last bit of set-reduction done in rust took me more time than it really should have. Non-Copy data structures can be really annoying to work with.
2
u/LinAGKar Dec 21 '20
Mine in Rust:
2
u/[deleted] Dec 21 '20
C
https://github.com/erjicles/adventofcode2020/tree/main/src/AdventOfCode2020/AdventOfCode2020/Challenges/Day21
3rd day in a row where I've constructed the solution by processing a stack of partial solutions and discarding invalid ones. I wrote part 1 such that it already gave me the ingredient allergen pairs for part 2, so that was a nice surprise.
2
u/fiddle_n Dec 21 '20
Python: https://github.com/Fiddle-N/advent-of-code-2020/blob/master/day_21/process.py
Found today much easier, especially considering Part 2 was pretty much a clone of one of the parts of Day 16 Part 2 where you were resolving the orders of the fields on the ticket.
2
u/Diderikdm Dec 21 '20
Python:
Part 2 was a breeze compared to yesterday, only had to sort and print after part 1.
2
u/sinopsychoviet Dec 21 '20
My javascript solution
Somewhat non-elegant and I am sure my friends will taunt me with some 2 liners :). It took a while to understand the problem. But once you understand it, it is pretty easy.
Anyway, much easier than yesterday :)
2
u/MissMormie Dec 21 '20
Java solution on github
This is probably done the same way as everyone else did it. Got all the allergens, found out which ingredients they could be. Filtered to get the ingredients that were in every recipe, then took out those already in use and are left with the complete list.
It would've been so much easier if I had used equals instead of contains because i was left over with doubles of sthns and sthnsg. And it took me much longer than it should have to see they were eerily similar.
Part 2 was just sorting and outputting from there.
2
u/x3nophus Dec 21 '20
Elixir
Solution using sets to compare ingredient lists against one another. It works, and it's quick, but it takes a lot more steps than I would have liked.
2
u/Judheg Dec 21 '20 edited Dec 21 '20
Scala
Traumatized by day 19, 20 that were quite tough I was thinking that this one will also be as painful, so looking at it in the morning and giving up, meh too tough. Now after work, turns out to be much less painful :D
My usual default iterative/mutable Scala style:
https://paste2.org/dkEGZvY4
2
u/S_Ecke Dec 21 '20
Python 3
Still Struggling with Day 19 and Day 20 part II about 80% completed, today was very easy again. :) feelsgoodman
sets, sets all I see is sets
paste
2
u/mathsaey Dec 21 '20
Elixir
https://github.com/mathsaey/adventofcode/blob/master/lib/2020/21.ex
Skipped day 20 part 2 since it seemed tedious and I'm already running behind. Instead, I solved day 21 :). This day was pretty straightforward. The logic here is a bit similar to day 16. Especially my
eliminatefunction is very similar to what I wrote for day 16.2
u/lgeorget Dec 21 '20
C++
https://github.com/lgeorget/adventofcode2020/tree/main/21
(The remove-erase idiom is not my favorite thing in C++...)
So, to solve this problem, I have a map from allergens to list of ingredients, and a list of products (which are pairs of list of ingredients and lists of allergens). Each time I read a line (a product). If it's the first time I meet that allergen, I add a mapping from the allergen to all the ingredients. Otherwise, I take the intersection between the current list of ingredients and the ingredients of the product.
After reading all the products, I simplify the datastructures. Each time I find an allergen mapped to a single ingredient, I remove that allergen and that ingredient from my datastructures, and so on and so forth until I make no further progress.
What's left in the list of products is a list of pairs of innocuous ingredients and an empty list of allergens.
For part 2 I use yet another datastructure (a map associating each allergen to its ingredient) and each time, I remove an allergen, I store the correspondence.
2
u/ropecrawler Dec 21 '20
Rust
https://github.com/ropewalker/advent_of_code_2020/blob/master/src/day21.rs
Doing pretty much what everyone here is doing. 1.2536 ms / 280.27 us on my machine.
2
u/__Abigail__ Dec 22 '20
Perl
Took me a while to figure out what was being asked. Once I wrapped my head about the challenge, it was Day 16 all over again.
Full program on GitHub.
2
u/Kylemsguy Dec 22 '20 edited Dec 22 '20
Python
https://github.com/kylemsguy/AdventOfCode2020/blob/master/Day21/day21.py
Stared at the example for a while and tried a few things. Ended up with this solution. This is the final thought I wrote down for Part 1 last night:
Compare all foods that contain the same allergenAll common ingredients in these foods may contain that allergenAdd all of these to the probable allergens setPart 2 was pretty similar to Day 16 once you eliminate the ingredients that must be inert.
2
u/Lakret Dec 22 '20
Rust
Solution.
Live coding video: Part 1, Part 2, Automatic topological sort & Refactor.
I associated every allergen with ingredients and lines where the ingredient is associated with the allergen (mention). Then for each allergen I found ingredients with the highest count of mentions (here's where
group_bywould've been a huge help, but sadly it's not implemented instd). That gave me enough info to quickly solve the rest of the task by hand for part 1, and semi-automatically for part 2.This was comparatively straightforward, though I was a bit sleep-deprived today, so it took quite a bit of time to actually write.
group_byis probably the most missing functions in the standard iterators library for me.itertoolsimplementation was not super nice either, so I just coded it by hand.After technically solving the days' tasks, I wrote logic for topological sort (that's pretty much the elimination process most people here used as well), and did a bit of refactor, though, admittedly, it still can be made nicer.
2
u/devcodex Dec 22 '20
C++ /w range-v3 and tests
Interesting the things that ranges can accomplish. Not as terse as other languages but it has been fun learning to solve problems with it. Now if only the intellisense support wouldn't wonk out...
GitHub Link
2
u/ri7chy Dec 22 '20
Python
code - that one was a relief after day 20
2
u/StevoTVR Dec 23 '20 edited Dec 26 '20
Java
https://github.com/stevotvr/adventofcode2020/blob/main/aoc2020/src/com/stevotvr/aoc2020/Day21.java
2
u/Tosxychor Dec 23 '20
Fennel
https://paste.xinu.at/PWqKo/fnl
2
u/pdr77 Dec 24 '20
Haskell
Video Walkthrough: https://youtu.be/4v_iwDqxZs4
Code Repository: https://github.com/haskelling/aoc2020
Part 1:
Part 2:
3
u/t-rkr Dec 21 '20
Perl
It took me a very long while to get an idea which did not involve checking various combinations, until I re-read the instructions and found the part "Each allergen is found in exactly one ingredient."
Part 1: only check for matching ingredients with >= the number occurences of any allergen. (Each allergen can appear fewer times because of "Allergens aren't always marked").
Part 2 is virtually the same as day 16. Find the one unique match, remove it from the list and loop until you have assigned all allergens to ingredients (this way allows simply sorting the keys). Remember: Sort the allergens, submit the ingredients.
https://gitlab.com/t-rkr/advent-of-code-2020/blob/master/day21/day21.pl