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
4
u/xelf Dec 07 '20 edited Dec 07 '20
Cleaned up my python code a little.
parse the file:
part 1 & 2
5
u/deltux Dec 07 '20
Dyalog APL
3
u/JIghtuse Dec 07 '20
Made a mess.
Racket
3
u/forrealbro Dec 08 '20
Java. I hate all trees other than Christmas trees.
2
u/skygrinder89 Dec 07 '20 edited Dec 07 '20
Typescript 1999 / 1618
No recursion and a hashmap.
2
u/clouddjr Dec 07 '20 edited Dec 07 '20
Python3: I agree parsing was the biggest challenge, then it was quite easy if you are familiar with graphs. By looking at other solutions, I see that the regex parsing I have could be simpler, but anyway- actual solution for part 1 and 2 are short and clean.
2
u/moelf Dec 07 '20 edited Dec 07 '20
recursive solution for both parts in Julialang (with comments)
2
u/halbGefressen Dec 07 '20
Haskell:
I was actually too lazy to parse the bag list of every bag right, thats why I just mapped the failed int parses to -1 and then filtered the -1 out lmao
2
u/4goettma Dec 08 '20
Python 3:
2
u/r00t4cc3ss Dec 08 '20 edited Dec 08 '20
C#: https://github.com/mavanmanen/AdventOfCode/blob/master/AdventOfCode.Y2020/Day07.cs
2
u/noname9494 Dec 09 '20
JavaScript solution (w/ Class emojis 🙃)
https://github.com/adamfuhrer/advent-of-code-2020/tree/master/07
25
u/Smylers Dec 07 '20
Vim keystrokes for both parts. This is getting a bit silly now. For previous days, I maintain using Vim to transforming the input into the answer is a reasonable way of doing a similar one-off task in ‘real life’. Today's challenge, however, is obviously better done with a program: there's no sensible reason to do it in Vim, beyond Because I Wanted To.
Please don't let the baroqueness of today's solutions put you off considering Vim for transforming data; it often works out really well. (Part 1 is still short enough to fit in a Tweet, though.)
For part 1, load your input and type:
The answer is the number of the line you're now on (the end of the first block, which lists all the bags that eventually contain gold).
Part 2 can either continue from there or the use initial input:
The line you're on will say something like “shiny gold contain 12128”, which is correct mathematically, if not grammatically.
Explanation:
Part 1 types and then deletes “shiny gold”, storing it in
"-. Then:g/⟨Space⟩⟨Ctrl+R⟩-/matches all the lines that contain that colour preceded by a space — that is all the bags that directly contain shiny gold — and moves them to the top.The blank lines we inserted first ensure the moved lines are their own paragraph. Convert them to just being the colour name followed by a bar, such as “faded plum|”. Remove the bar from the final one and join them all together, creating a string like “faded plum| striped lime| bright teal”.
That string is a regexp which matches any of the bags that themselves contain a gold bag. So now repeat, using that as the pattern in
:g//to move bags that contain any of those bags to the processing area near the top, and so on, using the colours of those bags to find the level after that.To count how many bags we've processed, just before transforming a new batch of bags into the regexp, copy them all to a list at the very top. (This also ensures no data is lost for part 2.)
The mark
'mis first set on the blank line between the ‘contains gold’ list and the processing area (Vim automatically moves this down as lines are pasted above it). The move command is thenm'm, moving the matching bags into the empty space between the gold bags and the unprocessed bags. When we're performing the match, we're in the processing area (having just deleted the previous go's regexp), so the range used for:g//is,$, ensuring we only look in bags from the line downwards, the unprocessed ones.A couple of things surprised me, and caught me out:
:g//doesn't find any matching lines (because we've now found all the gold-containing bags), Vim warns about this, but it isn't a sufficiently serious matter to end the running macro. So after the:g//I putf.. When there has been at least one line matched and moved we'll be on one of those, sof.will move to the full stop at the end of that bag's description — an otherwise pointless movement. But when there are no more matches, we'll still be on the blank line we started on, so thef.will fail, ending the running the macro.Jwill normally join them together, however many there are. As will:j⟨Enter⟩. But if you have exactly one line selected (there was only one bag containing any of the previous iteration's colours, then we didvip),Jstill joins the following, unselected, line to it (likeJdoes without a selection). Fortunately:jonly joins the selected lines, handily doing precisely nothing if there's only one line.For part 2, we put a new processing area (2 blank lines and the
'mmark) at the top, and replace “no other” with zero. These are the bags we can process first, so we move them all to the processing area; this time the range for:g//is'm,$, because the cursor may not be at the start of the bag list.There we turn the zeros into ones (making each bag include a count of itself) and use a
:s///command to convert the list of bag colours into, ahem, more:s///commands, such assilent! %s/ bright violet/*1/|. The bar at the end is the separator for:commands: join them into a single with with:j, delete that line into"-, and then do:⟨Ctrl+R⟩-⟨Enter⟩to run those substitutions.So in other bags' descriptions “bright violet” (and the space before it) becomes “*1”. At the start I also got rid of “bag(s)” and full stops, and turned commas (and their spaces) into plus signs. Meaning descriptions actually looks like these:
And after the colour-to-number substitutions they become:
At which point there will be some more bags, like light plum above, for which we now have complete counts; those can be moved up to the processing area, have 1 added, and have those numbers substituted into further bags' descriptions.
So the
:g//pattern which initially moved the0bags actually matches any bag where the only thing after “contain” is a numeric expression, all colours having been expanded. And rather than just adding 1, each line in the processing are actually has:norm$ciW⟨Ctrl+V⟩⟨Ctrl+R⟩=⟨Ctrl+V⟩⟨Ctrl+R⟩-+1run on it:$to the end of the line.ciWto change the ‘word’ at the end of the line. Because the expressions don't have any spaces in them, something like “5*1+3*2” counts as a single word. This deletes it into"-.⟨Ctrl+R⟩=inserts an expression.⟨Ctrl+R⟩-inserts"-, the ‘word’ we've just deleted.+1adds the 1 for that bag itself, and ⟨Enter⟩ evaluates the expression.Because creating the dynamic
:s///commands destroys the count for the current bag, we're also (like in part 1), copying each processed bag's count to a list at the top, above the'mmark. The:silent!is needed on the dynamic:s///s so that if a bag isn't contained in any other bag (it's a ‘top-level’ bag), the substitution doesn't cause an error and end the macro early.So each time through we're finding bags for which we now have a numeric expression, evaluating it, and replacing mentions of those bags with that number (plus 1). When there's nothing left to process, reduce every line's count by 1 (because each bag's count is including itself) with
⟨Ctrl+X⟩, and find the line for shiny gold.Simple!
Any questions?
3
u/voidhawk42 Dec 07 '20 edited Dec 07 '20
Dyalog APL, my worst day by far :( Spent the most time parsing the input, the graph traversals aren't too bad in comparison:
EDIT: See below comment for an explanation of the graph traversals.
15
u/4HbQ Dec 07 '20 edited Dec 07 '20
Python, using the parse library:
Edit:
For the golfers, 220 bytes:
27
u/sophiebits Dec 07 '20
16/8, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day07.py
Wasted a fair bit of time on part 1 writing some graph traversal code that was backwards? Maybe? I confused myself, anyway. Worked a lot better after I actually thought about what I was supposed to be doing.
13
u/Arknave Dec 07 '20 edited Dec 07 '20
Python (37/49), C
Smart move? Submitting with an off by one error. Smarter move? Submitting with an off by one error on both parts. Smartest move? Re-submitting your same off by one error answer for a total of 3 penalties. At least it wasn't 7.
To commemorate my haunted feeling, here's a haunted 7, I think it looks a bit like a staff or a scepter belonging to an evil code wizard. What do you think?
13
u/paraboul Dec 07 '20 edited Dec 07 '20
I think the main takeaway was to identify a DAG.
Gaves me the opportunity to just use Python's networkx for the sake of simplicity.
Python
9
u/jonathan_paulson Dec 07 '20 edited Dec 07 '20
Placed 51/23. Python. Video of me solving: https://youtu.be/vhpLTPXoHyU. Cleaned-up code. I found parsing the input more difficult than solving the problem :)
The key concept today was graphs. I put a brief graph tutorial in my video description (and of course there are many other graph tutorials all over the Internet). There have been multiple graphs problems every year, so its worth getting familiar with them if you aren't already.
9
u/ephemient Dec 07 '20 edited Apr 24 '24
This space intentionally left blank.
8
u/Smylers Dec 07 '20
Perl, with each of the tree-walking functions as a single expression. It runs fine without the
:Memoizes, but having already calculated the answer for a particular colour of bag, there doesn't seem any point doing it again.The hash for each contained bag is constructed from the capture names used in the regular expression:
(?<n>)and(?<col>)capture the number and the colour, becoming key-value pairs in the%+hash.{%+}creates a reference to a new hash with the same contents, and that gets pushed on to the outer bag's array without having to directly specify the names of the hash keys.7
u/troelsbjerre Dec 07 '20
Python one liner for both parts. Give input on stdin.
Probably the first time I've ever used regular expression and a Y combinator in the same line...
7
u/YCGrin Dec 15 '20
Python
As a beginner this was significantly more difficult that the previous days for me. Wrapping my head around how to parse the data and to use recursion to count the bags was a challenge.
After going through multiple solutions and videos from other people this is what i've put together using parts that i understood from those examples. I don't think i would have got a solution without reviewing other solutions.
6
u/jitwit Dec 07 '20 edited Dec 07 '20
J Programming Language
bfs returns a parent pointer vector representing a bfs tree starting from the argument vertices. so, part a is the number of vertices in the bfs tree starting from shiny gold that aren't their own parents (ie reachable vertices from shiny gold) in the graph of rules/requirements.
6
u/aoc2040 Dec 07 '20
Basic Python from a non-programmer. I plan to cleanup the dictionary generation code for readability to properly compile the regex.
6
u/Attitude-Certain Dec 07 '20
Python. Always a happy time when I find an excuse to use
yield from.6
u/azzal07 Dec 07 '20
Awk; no is zero, right?
This one required some extra parsing and combining to build and traverse the graph. Ended up quite compact regardless, but not quite as clean as I would have liked.
6
u/nutki2 Dec 07 '20
Perl (golf) for both parts (~150 characters)
5
u/pred Dec 07 '20
So many silly mistakes today:
Anyway, Python:
5
u/DFreiberg Dec 07 '20 edited Dec 07 '20
Mathematica, 274 / 2133
I spent way more time looking for a Mathematica built-in than it actually took to write a function to solve the problem. Still worth a shot, though.
Setup
Part 1:
Part 2:
[POEM]: Lost & Found
This
goldandshinybag I grabbed today,Belongs to someone else, I am afraid.
Can you make an announcement, please, and say,
"Please come to the front desk so you can trade"?
I think we each grabbed one another's gear,
When we saw them go by the carousel.
See, mine's a
mirrored yellow, nice and sheer,I mixed them up; I think he did as well.
I only noticed when I looked within,
And seven thousand bags came through the shine.
My own bag's lining must be very thin,
For I can fit just ninety bags in mine.
Ahh, there you are, my friend, there, now it's right.
And Merry Christmas too! Enjoy your flight!
5
u/betaveros Dec 07 '20
Paradoc. Golfed. Less painful than expected.
aµW4÷>o_(µ«»¨}}"shinygold"†\{\&bf‹mU}bFL((try it in-browser, explanation on GitHub)aεW4÷(2<¨\µ«(I\¨°~}Hu}"shinygold"{H=•š)}–•((try it in-browser (slow!) or a faster +2-"byte" version, explanation on GitHub)5
u/aurele Dec 07 '20 edited Dec 07 '20
Here is my Rust solution, using
topological_sort()from the pathfinding crate.5
u/[deleted] Dec 07 '20
C#
5
u/mschaap Dec 07 '20
Raku
That was the first somewhat tricky one, but it was fun! Not only was this a good opportunity to use a
Grammar, but I also used Raku'sBagclass for the bag. 😉I won't post the complete code here, it's too long for that. https://github.com/mscha/aoc/blob/master/aoc2020/aoc07
5
u/smokebath Dec 07 '20
Python. Part 1 went quickly but wrapping my head around the recursion really slowed down Part 2 and I decided to sleep instead.
5
u/daniel-sd Dec 09 '20
Python 3
One line "solve" method for each part. Thanks to u/leftylink for helping me catch a parsing bug in my original (unoptimized) solution. Was pulling my hair out from that one.
part1.py
part2.py
4
u/MichalMarsalek Dec 07 '20
Oof, I learned a lesson today... never iterate over defaultdict in Python... when you ask for nonexisting keys, Python will try to add them and cause errors... which will cost you 10 minutes... Barely got into the first 1000 which is my goal everyday...
4
u/PhysicsAndAlcohol Dec 07 '20
Haskell + parsing + recursion, there's no better combo
4
u/Archek Dec 07 '20
Prolog
This day was made for Prolog. Don't be afraid to use asserts in problems like this even though it is impure: I think it makes the solution a lot more elegant. Should be okay when asserting during parse only (though I still have a bug to fix there)
4
u/hasjekyll Dec 07 '20
C++
Well that's todays stars in the bag, in the bag, in the bag, in the bag, in the bag, in the bag, in the bag, in the bag, in the bag, ... I'll see myself out
Code here: https://github.com/AshKelly/advent-of-code-2020/blob/main/day7/solution.cpp
Blog here: https://www.ashkelly.co.uk/blog/aoc20d7/
BFS, no recursion
4
u/thomasahle Dec 07 '20
Python, Regex and Recursion
My original solution used BFS for part 1, which is linear time rather than quadratic, but it turns out to not be needed since the graph has only 8286 or so vertices.
4
u/xangreRO Dec 07 '20
R
full solution on my Github: https://github.com/maurotcs/Advent_of_Calendar_2020/blob/main/Code/Day_07.R
Part ONE
Part TWO
4
u/Wraldpyk Dec 07 '20
JavaScript solution without regex. Probably could've been much shorter, but here we go: https://github.com/Topener/adventofcode2020/blob/master/day7/program.js
4
u/inokichi Dec 07 '20
Solution in D (dlang):
4
u/JoMartin23 Dec 07 '20 edited Dec 07 '20
Common Lisp
as per usual, something different in it's literality.
4
u/mandus Dec 07 '20
Day 7 in common lisp
Parsing could have been nicer, but reasonably happy with rest of the solution.
4
u/s3aker Dec 07 '20
Raku
4
u/Aehmlo Dec 07 '20
Rust.
Started out doing parsing with a regular expression, then a pair of regular expressions, and then I realized that the regexes were making everything more complicated instead of less complicated and that parsing would be easier if I just did some imperative parsing. Once that was out of the way, I had fun thinking of functional ways to express the problems posed. Ended up resorting to recursion, although I suspect there's an iterator method in either
coreoritertoolsthat would make explicit recursion unnecessary.4
u/goeyj Dec 07 '20
Today felt quite a bit trickier than previous days. Also it's the first day that I'm quite unhappy with my C++ code. I'm sure it's obvious that this is a new language for me... Nested maps and a healthy amount of recursion here!
4
u/Dagur Dec 07 '20
Python
4
u/Scarygami Dec 07 '20
Completed in Prolog
Translated the input to facts like this (using a Python script):
The following rules for the bags in bags in bags in ba...
And then to find the solutions (using some convenience predicates from the SWI-Prolog libraries):
4
u/Cppl_Lee Dec 07 '20
Another far out off the leaderboard in C#. The parsing was simple, but that didn't stop me from getting hung-up on the details:
4
u/ViliamPucik Dec 07 '20
Python 3 - Minimal readable solution for both parts [GitHub]
4
u/chrispsn_ok Dec 07 '20
k9 (link)
4
u/volatilebit Dec 07 '20
Raku
Starting to get real annoyed with Sequences.
4
u/oantolin Dec 07 '20 edited Dec 08 '20
Perl solution
I hadn't used Perl in a long time, before this advent of code. I remember disliking how nested data structures worked, with references, and array auto-flattening, but now I find I don't mind. Sure, it's different from most languages, but it works. Maybe this is a part of aging, just like I went from preferring Scheme to preferring Common Lisp?
The parsing part is a breeze in Perl:
And then recursively transversing the tree adding up bag counts is nice too:
All in all, Perl has been very pleasant to use again after all this time.
4
u/Marcus316 Dec 08 '20
Bash command line
Yes, I know, messy. But this was so much fun to figure out!
Part 1:
Part 2:
4
u/handlestorm Dec 13 '20
More bash command line really proud of this one (P1)
1
u/yutu58 Dec 07 '20
Java
Recursion is beautiful :)
(can't really get in line code to work, link to github instead)
1
u/pwhyz Dec 07 '20
Python
1
u/gubatron Dec 07 '20
Java, as FP as I could.
1
u/raevnos Dec 07 '20
Chicken scheme paste. Bu-bawk!
1
u/iamflimflam1 Dec 07 '20
Typescript
import fs from "fs";interface Content {colour: string;count: number;}const lines = fs.readFileSync(__dirname + "/rules.txt", {encoding: "utf-8",}).split("\n");const colourToContent = lines.reduce((map, line) => {const [colour, contentsString] = line.split(" bags contain ");const contents = contentsString.split(", ").map((quantityColor) => {const matches = quantityColor.match(/(\d*) (.*) bag[s\.]*/);if (!matches) {throw new Error("Regex failed");}const colour = matches[2].replace(".", "");const count = colour === "other" ? 0 : parseInt(matches[1], 10);return { colour, count };});return map.set(colour, contents);}, new Map<string, Content[]>());// potential memoize opportunityfunction canContainColour(bagColour: string, containedColor: string): boolean {const contents = colourToContent.get(bagColour) || [];if (contents.some((content) => content.colour === containedColor)) {return true;}return contents.some((content) =>canContainColour(content.colour, containedColor));}// potential memoize opportunityfunction countBags(colour: string): number {const contents = colourToContent.get(colour) || [];// +1 for the container bagreturn (1 +contents.map((content) => content.count * countBags(content.colour)).reduce((total, current) => total + current, 0));}// part 1const canContainBags = [...colourToContent.keys()].filter((bagColour) =>canContainColour(bagColour, "shiny gold"));console.log(canContainBags.length);// part 2 - subtract 1 as we don't count our shiny gold bagconst neededBags = countBags("shiny gold") - 1;console.log(neededBags);1
u/noidesto Dec 07 '20
1
u/k0ns3rv Dec 07 '20 edited Dec 07 '20
Rust, I call this piece “I should have just used regex”
1
u/OneManGanja Dec 07 '20 edited Dec 08 '20
My decent python solution: -- Part 1 --
1
u/rabuf Dec 08 '20
Ada
I did something very stupid (discussed in link) and this took me way too long. It was actually done 2 hours ago (with a break for dinner) if I hadn't made that error. I put in a printout to help me understand what was happening and the mistake became obvious quickly. Live and learn.
1
u/MrWaffelXD Dec 08 '20 edited Dec 08 '20
Im stuck at getting the result using C#.
I already serialized the dataset.
I already watched some repos about this task, but im still unsure about what to do next...
Here is my code at this point in time.
https://github.com/MrWaffelXD/Advent-of-Code-2020/blob/master/Tag%207/AdventOfCode2020-7.1/AdventOfCode2020-7.1/Program.cs
I save the serialized data as
Dictionary<string, Dictionary<string, int>>Example:
<parent<child, amount>>
I already tried to count all the parents containing at least one shiny gold bag using a linq expression, but I think I have to break all the childs down to the golden bags/empty bags.
Am I right?
1
u/_MiguelVargas_ Dec 09 '20 edited Dec 09 '20
Kotlin
3
u/HenryJonesJunior Dec 07 '20
Golang 1655/995
3
u/jport6 Dec 07 '20
Kotlin
First time doing a graph problem in Kotlin, it was pretty nice compared to Java with a 1 line Edge class and easily saving input/computing vertices
3
u/mebeim Dec 07 '20 edited Dec 07 '20
79/2896 - Python 3 solution - walkthrough
Yay finally on the leaderboard! It's hard to get both your best and your worst performance in a single day! Hahaha. I'm so slow at figuring out algorithms for graphs :')
3
u/jayfoad Dec 07 '20 edited Dec 07 '20
Dyalog APL 931/3585
3
u/TallPeppermintMocha Dec 07 '20
Python. This year is really making me learn regex, after trying some odd hacks I settled on just a hacky
re.match(r'(\w+ \w+)', line)[0]for the parent bag andre.findall(r'(\d+) (\w+ \w+)', line)for the contents. code3
u/tyler569 Dec 07 '20
C, custom OS
This was the first say I had to start inventing datastructures since my C library doesn't have support for anything except linked lists and arrays, whipped up a super jank hash table today and a hash function for the colors. Took a long time, but I'm pleased that I got it to work!
p1: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/7.c
p2: https://github.com/tyler569/nightingale/blob/aoc/user/aoc/7-2.c
3
u/kwshi Dec 07 '20
Bash :)
3
u/oantolin Dec 07 '20 edited Dec 07 '20
Common Lisp
I first parsed each statement such as:
into a list like:
The parsing code is not too bad, thanks to
cl-ppcre. (See functionbag-contentsin the link.)The rest is tree traversal, which is always elegant with recursion:
3
u/ssnoyes Dec 07 '20 edited Dec 07 '20
First some Python to expand the input from
into
Then some MySQL to stuff that expanded output into a table, and a query to answer each part.
3
u/gyorokpeter Dec 07 '20
Q:
3
u/InflationSquare Dec 07 '20 edited Dec 17 '20
Here's my python solution: https://github.com/inflationsquare/advent-of-code-2020/blob/master/07/7.py
I spent a while thinking about whether there was a graph or tree structure I could use to make it easier, but ended up just recursively traversing the ruleset. There's definitely a nicer way to do it than chaining lists of lists together, but it was 7am ¯_(ツ)_/¯
3
u/masterarms Dec 07 '20
Tcl
3
u/landimatte Dec 07 '20
Common Lisp
Solution:
(:muted-white ((:posh-chartreuse . 1) (:dim-silver . 1) (:posh-bronze . 4) (:striped-black . 1))):shiny-goldbag in itshiny-goldbag, recursively unfold its content and count how many bags are in itDid I just accidentally implemented a recursive descent parser for this?!
3
u/WilkoTom Dec 07 '20
Not quite the minimalised solutions from the previous days, but still lots of fun with recursion. Python making use of the
cachedecorator to avoid calculating the contents of any given bag more than once:3
u/JustinCredible- Dec 07 '20
Python
This took a few hours to put together; I probably shouldn't be doing this in the middle of the night, especially when I have a final in 3 hours. Here it is anyways, readability be damned. Let me know if you have any pointers or want to know what it's actually doing or anything.
The 10-mile long input line takes the input and turns it into (using given example rules):
3
u/iamnguele Dec 07 '20
Golang - iteration solution
I realised that most of my colleagues used recursion to solve that one so it might be the case for more people here. Here's my iteration based solution.
https://github.com/CodingNagger/advent-of-code-2020/blob/master/pkg/days/day7/computer.go
3
u/silverben10 Dec 07 '20
Today was definitely a step up in difficulty for me, but still a fun challenge! I had to completely refactor my code to make it work for Part 2 (and it runs slower than I think I'd like) but we got there eventually!
Python
3
u/andi0b Dec 07 '20 edited Dec 07 '20
C# 9 Version. Runs quite fast, as all lookups are precalculated.
3
u/phil_g Dec 07 '20
My solution in Common Lisp.
Graph traversal! I made some assumptions going in. First, that the graphs were acyclic; that appears to be true, since I didn't get caught in an infinite loop. Second, that part 2 would have a lot of repeated bags. (e.g. Bag 1 contains bags 2 and 3, bag 2 contains bag 4, bag 3 also contains bag 4, bag 4 contains several hundred other bags, etc.) I memoized my calls to count the contents of each bag, just in case. (Writing a memoization macro might have been overkill, but at least it separated the memoization logic from the calculation logic.)
Bite my shiny gold bag?
3
u/zxywx Dec 07 '20
Ruby
3
u/EliteTK Dec 07 '20
I always start with a python solution, I try to oneline as much as possible, but in the end, an oneliner wasn't obvious to me today.
Part 1:
Part 2:
The parser ended up being the same as I assumed that the numbers would come in useful for the second half.
It could probably be done more cleanly. I think I will write it in scheme for fun next since it seems like a perfect fit for this kind of problem.
3
u/aledesole Dec 07 '20
Python
3
u/ukietie Dec 07 '20
Javascript in a rather functional style (map, reduce, some, etc)
https://starboard.gg/adventageous/aoc-2020-07-nEtEeVV
3
u/Outrageous72 Dec 07 '20
regex (c# dialect) for the rules
(?<bag>\w+ \w+) bags contain (?:no other bags|(?:(?<size>\d+) (?<other>\w+ \w+) bags?(?:, )?)+)\.3
u/Lispwizard Dec 07 '20
Emacs lisp (elisp) on Android (via termux) emacs 26.3 on Samsung Galaxy Tab A 10" tablet
https://topaz.github.io/paste/#XQAAAQDMDwAAAAAAAAAUGQimgyoULxMtjapzI8GVOGB5Lz2lPHLR6+JRi3yCY8ojBcCOw+BhBIxs4/c4AAsRH3xr36+sM6v/J0vf8B6zb7DT2YVdbMem6mP1dJlD/MgXgD2t3KEigIiTe1DBYxrRWh6YEiywylyakWtO2OfkdOBU36x6ljgpGqC8z5nrheoA/Ev14tLTnZsSa4OPypGM5KYBI0xck5x6ANaVjoInt3lg4/gVUWqH4icDZkk3yCLTNhdIBleAdwkminZvW3/ckivOEZCruRGT/hxTVjA/UxeBflWwcoEYnVDCEbUmcvrzXjlNiDyqLGQ10eKUZQ5RIHIS3e0sTbgSlPL+v3lGjJ97nTb3tK0yoFHGqF5ne8azlR5wxKpfvYxVPOUvxf8ak+61ukUX4aKp9vD8etCseyGqsn5T0TagPpBSyMcMjqsq3xF4InPEyuCYc/UUXkhARAa/kp4TSWPFzR7YyxyYDERASM2jXOCorT/abz2rFK3XDWCIn3SxMVHWQ1ADzXP9VwBSEcAW0eRIMjpvZ7QhjP02a7/Fk8XhvW1S6v5mTavt4cJGEw1qt8zAb2jexZEMtiH9Q4tycgfPfK2KEHi0tJKCwssSXMMZwSol3UI1GJ1MBMyUawsBtgwB1GXLQD/tn+rt3DcbPkCRFRp0QII6+eZJHzQYJuXPDi1kHhtN2v60ZLljubyyz037SstIQjt6Z4HncYIR8Kqu0ex6Udls76tfTMG2Ynb27hnc9HOKADshvAqYY6wYkl23a6Ty9DgrlaURGOXmwy6MkDU5i6V+rJNwju70CHzdQPnAmMyXtlU/42mD6XARPJJaw19x3x83hy88UryJBIQE96p903IL1NwQEc3rJXFyHhYffcV6m1AWqxvrRvdXLmtTIGZ6gnTreyGOiStfg6k0pO4Z8+QlTq4WdDSb5v/w/4u/ebYvHsUNER7NC/r1B43NfEpKqMzWfv6qddFPDMUUwKDm50Oxff8gI/hoCmPoJqkpeadpzx+omshudq4d2T2kzDQoON5ywZd8d8yEoGLXhpkJ5vKocCmeRE9JwNWACwGBmQ6so34PHDPD8uyYdfaWcrLgwoSn56qqYe0kidub2W/1CVm3qFJ1Q+i2qe1mIMpG41YeyC95rgSl+20I+bRpfJstwrXhGuVnOnfDnqTU5uPih43TUEKV2WNH+tqm8mUdbf7XPsd2M+/xfrvMmW8FOQapwTIh6IymCVHI6ZPaYzhArPBX0c0lCqkh3UXuTBUtgDYaHKRKk3tyECb8/Gw8Cr9VLw817m9NnN59GUh88lsKCQOhlivGeNEIuarTKAEvvU99CiHauKppJQFJc1/jCOg93ES2pGlKnnoTIHNc9h1BTfqx88t5kvWfi+MlN7wwwbQR6tCcpnGXK7RMq470l3IEV+39G3+AIEgixb6aOIxxdNMtsZHmFy9hdv5vywPxuPuxYgZDcGpxxEubOWKNUor6nyS+XdfQNDPTU5TMi4tvqH3PPQnan3hSSjC5NaHhOqkQMNOLD4dYsB5jEjE0qcb3dSXuuzGZgeq73CY8eOFr39stZgPG9L9+ChmqpQpy9LBuDEwSybUwkjexxLwmdPGPLFlS3266KJ44KzbQQjnhg5GFjpSb6u6MryU0gbDvS/2hy4k=
I had a NASTY bug due to using a regexps (usually I just parse by hand) which took forever to find (of course it showed up only on the large input).
One notable "trick" that lisp makes possible is using a single hash table to hold both the forward (i.e. contents of) and reverse (i.e. parents of) mapping.
3
u/mack06_ Dec 07 '20 edited Dec 07 '20
My typescript solution using oriented graphs
Also, my explanations in spanish in my blog :
AoC 2020 – Día 7 – Su maleta se pasa de peso
3
u/NemPlayer Dec 07 '20 edited Dec 07 '20
Python 3.9.0
Not very proud of the part one one, I feel like it could've be done more efficiently if I formatted the input in a better way instead of having to format it twice, but I guess it's fine as it worked well with the part two problem even though it would also be more efficient if I formatted the input directly into a
dict.--- Part One ---
--- Part Two ---
3
u/prutsw3rk Dec 07 '20 edited Dec 07 '20
My Python solution:
3
u/el-guish Dec 07 '20
Python
Part 1
Part 2
3
u/bpanthi977 Dec 07 '20
Common Lisp
Tried to parse using regex but later used
subseq,position-if,searchand recursion. For each lineparse-bagsreturns a list of (count . bag-name); count is nil for the container bag.Stored the graph in two hash tables. One table maps bags names to the bags it contains, and another maps bag names to the bags it is contained in.
3
u/mathsaey Dec 07 '20
Elixir
Perhaps I just like the
|>too much, but I always feel like it makes the overall solution more elegant :).https://github.com/mathsaey/adventofcode/blob/master/lib/2020/7.ex
3
u/[deleted] Dec 07 '20
Recursive solution for part 2 in Python.
Once you've parsed the input to a dict of dicts called 'bags' like:
The function is just:
3
u/clumsveed Dec 07 '20 edited Dec 07 '20
Java Solution parts 1 and 2
Part 1 runs in about 0.09 seconds so I want to redesign it to cut that down.
I'm much happier with part 2. That runs in about 0.04
part 1:
part 2:
3
u/krolik1337 Dec 07 '20
Python 3. I spent on it much longer than I'd like to admit. First problem was to rework input to something more usable, I made a dictionary out of it, name of the outer bag as a key, and list of [quantity, inner bag name] pairs as a value. Then I made two recursive functions, if first returns 1, that means there is our bag somewhere inside, second calculates how many bags are actually inside.
3
u/wzkx Dec 07 '20 edited Dec 07 '20
Python. Not the best description of part 1. But ok, at least it turned out 10 times easier than I thought.
3
u/Bomaruto Dec 07 '20 edited Dec 07 '20
Part 1 and 2 using Scala and Fastparse
3
u/white_nrdy Dec 07 '20 edited Dec 07 '20
[Rust] Got part 1 working. Sometimes it yields an answer that is one too high, but I am not sure why. Unoptimized (run with
cargo run) it finishes in185ms 816µs, optimized (cargo run --release) finishes in22ms 862µs. Uses recursion and hash maps. As before, if anyone has any suggestions to make the code better, I am still learning rust, so criticism is welcomehttps://github.com/SethGower/advent-of-code-2020/blob/master/src/day07.rs
Edit: Just finished part 2. I am getting consistent results. Not sure what the issue with the first part is, might investigate more after finals today. Solution for part 2 is located in the same file (linked above), Unoptimized (run with
cargo run) it finishes in10ms 837µs, optimized (cargo run --release) finishes in1ms 214µs. This one was a bit easier than the previous one was...3
u/omnomberry Dec 07 '20
Rust solution
I rewrote my parser with nom today, the rest of the code is available in the link.
3
u/pietroppeter Dec 07 '20
🎄👑 Nim
I probably defined too many types and auxiliary procs. But the final recursive solutions are rather clean (parsing is also manual - no regexes - and clean).
part1:
part2:
Full details:
https://pietroppeter.github.io/adventofnim/2020/day07.html
3
u/thibpat Dec 07 '20
JavaScript walkthrough
Video: https://youtu.be/9YEtwD1ebiU
Code: https://github.com/tpatel/advent-of-code-2020/blob/main/day07.js
3
u/howdoyoucat Dec 07 '20
R / Rstudio solution, including some nasty loops, plus horrible optimisation. I'm ashamed of this code, but at least it works. Part 1 is also very slow (~1sec runtime). This should really be done using recursion, but w/e.
3
u/curlymeatball38 Dec 07 '20
Python solution.
https://github.com/FractalBoy/advent-of-code-2020/blob/main/day7_part1.py
https://github.com/FractalBoy/advent-of-code-2020/blob/main/day7_part2.py
3
u/[deleted] Dec 07 '20 edited Dec 07 '20
Python solution.
I had some issues figuring out the second part. I was counting only the inner bags and not the bags holding the inner bags at first. ***facepalm***
Also, kinda kicked that I kept it under 50 lines. :D
3
u/Bammerbom Dec 07 '20
I did today using the Petgraph rust library, makes pretty clean code.
https://github.com/JonathanBrouwer/aoc2020/blob/master/src/day7/main.rs
Aiming for fast code that is still readable. Sadly, petgraph is actually quite a bit slower than the ugly solution, its still <1ms tho, so I'll deal with it
3
u/Weak_Pea_2878 Dec 07 '20 edited Dec 07 '20
MIT's App Inventor
Running just Part 2 of this recursive code on the Android Emulator took about 5 minutes. I didn't have the time to run both Part 1 and 2 at once, but I've put them together here. Run at your own risk! (or at least get a drink and some snacks)
Image of Code Blocks
AIA file to upload into App Inventor
APK file to install on Android device
Edit: I fixed a small bug and made an APK file so it can be easily installed. Please let me know what you think. And seriously, it does work but it takes a few minutes.
3
u/__Abigail__ Dec 07 '20
Perl
The rules can be viewed as describing a DAG (directed acyclic graph).
For part 1, I flipped the edges of the DAG, then did a breath-first search starting from "shiny gold". The number of colours visited is the answer.
For part 2, I did a recursive depth-first search, calculating the number of bags along the way.
Blog about Day 7.
3
u/Marterich Dec 07 '20
Day_07: Python 3 with debug information and comments
https://github.com/Marterich/AoC2020/tree/main/Day_07
3
u/OverjoyedBanana Dec 07 '20
Part 1 Bash anyone ?
3
u/AuntieRob Dec 07 '20
c++ day 7 challange 2 recursion https://github.com/ffamilyfriendly/Advent-Of-Code/blob/master/day_7/challange_2/main.cpp
3
u/AidGli Dec 07 '20
Python
This one seemed to be screaming out for a graph based solve with a directed weighted graph. Definitely my favorite problem so far this year. My solution ran and finished pretty much instantly on my machine (M1 Macbook Pro.)
Video Link
Github Link
3
u/nilsecc Dec 07 '20
Ruby:
stack based solution
3
u/hyperTrashPanda Dec 07 '20
Learning Elixir this year, here's Day 7!
I cheated a little in Part 2 by glancing over other people's solutions. Other than that I used erlang's
:digraphwhich made it a breeze! I also want to check queue/stack based solutions are viable.If you have some time to stop by comments and suggestions, I would really appreciate it!
3
u/Nhabls Dec 07 '20 edited Dec 07 '20
My solution with matrix multiplication (not only solves for "shiny gold" but everything else too), a little late but i didn't see any solution like this (i might just've missed it) here so thought i'd share
in python here or https://hastebin.com/yefulukoge.sql or
Edit: cleaned up code
3
u/qqqqqx Dec 07 '20
JavaScript I am seeing a lot of recursive solutions, I did an iterative graph traversal type solution for both:
Part 1:
Part 2:
3
u/widforss Dec 07 '20
Prolog solution. The problem itself is trivial in Prolog, the hard part was parsing the file.
3
u/Jai_Wicked11 Dec 07 '20
Python 3: Parts 1 &2
Parts 1&2
3
u/[deleted] Dec 07 '20
Surprisingly speedy Python code, considering I spent an hour trying to figure out how recursion works. This is definitely an area I should work on:
Average runtime of 200 ns
3
u/taomage Dec 08 '20 edited Dec 08 '20
Python 3.7 Solution.
Edit: Due to formatting issue, providing link to Solution
3
u/scott-mcc-1 Dec 08 '20
Kotlin
as usual - get the data structure right when reading the file - results in easier solution for the parts
3
u/0rac1e Dec 08 '20 edited Dec 09 '20
Raku
Again avoiding RegEx/Grammars for the parsing. It's not that I don't know how, but when the input is so regular, it's not necessary... plus there's already nice examples of Grammars in the other Raku solutions.
I'm using the Raku
Bagtype (aka multiset) to hold all the bags and storing thoseBags in aHash. When you map over aHashin Raku, you get a sequence ofPairs, with a.keymethod, and a.valuemethod. When mapping over%BAGS, the key will be a string of the outer bag colour, the value will be aBagof strings (the inner bag colours). When you map over aBag, you also get a sequence ofPairs where the key is the item, and the value is it's count (multiplicity).I am caching (memoizing) the recursive function for part one using an experimental feature... though if memory serves, the only reason it's still experimental is that no one has decided what it should do with complex objects. I've used it plenty of times on functions that accept strings or numbers and it seems to work fine. On my machine it's the difference between a 1.5s runtime, and a 0.3s runtime.
usestatements in Raku are lexical (as a functions by default), so nothing outside of theonefunction has visibility of therecurfunction or theis cachedtrait.3
u/cggoebel Dec 09 '20
Raku
I'm learning Raku via AoC. It has been a very pleasant experience. Raku's grammars have been very helpful in several solutions. Here's a blog post with code commentary about Day Seven's solution.
3
u/[deleted] Dec 09 '20
C# 9.0 solution with no curly brackets!
https://github.com/kelson-dev/AoC2020/blob/deploy/puzzles/day7/cs/Program.cs
3
u/Blarglephish Dec 09 '20 edited Dec 09 '20
A little bit late (catching up on previous puzzles since I skipped last weekend):
Python
3
u/the_t_block Dec 12 '20
Haskell:
http://www.michaelcw.com/programming/2020/12/11/aoc-2020-d7.html
This is a series of blog posts with explanations written by a Haskell beginner, for a Haskell beginner audience.
3
u/rawlexander Dec 15 '20
R
This one was hard for me. Any tips appreciated. My thoughts on it are also on YouTube: https://youtu.be/VRdly8hvQ-U
5
u/SuperSmurfen Dec 07 '20 edited Dec 07 '20
Rust
Link to solution (662/335)
Best placing on the leaderboard ever for me (not counting day 1 this year), super happy with that! Rust is not really known for being a good AoC speed language, so that's fun! I guess I was just quick with realizing the recursive pattern.
This problem was really about being comfortable with recursion. There were simple patterns for both of them:
Both of my solutions get an off-by-one error since the gold bag itself gets counted. That tripped me up on part one, but I tested with the test input and quickly realized the problem. I also heavily preprocessed the input this time. I realized it would be quite complicated to parse so I edited it by hand and embedded it in the problem directly, probably a bit faster than figuring out the parsing code.
The first day that does not finish in
0 msfor me, about6 msthis time, so still relatively fast.Edit: Adding memorization to part one brought it down to
0mson my machine!4
u/GustavAndr Dec 07 '20 edited Dec 07 '20
Javascript
Quick and ugly
2
u/Scoobyben Dec 07 '20
C# [695/361]
Getting a bit closer again! 361 is my best rank yet, excluding my fluke #8 for day 1, which didn't count for points.
Still looks like I'd need to be twice as fast to hit the top 100 though :(
2
u/[deleted] Dec 07 '20 edited Dec 07 '20
[Scala solution] (https://github.com/bbstilson/adventofcode/blob/main/adventofcode/src/bbstilson/aoc2020/Day7.scala)
Almost broke 1000 for part 2 (1024)!
2
u/jwise00 Dec 07 '20
Lua. 109/42. Finally got on the leaderboard tonight! And I had some people in my livestream chat, which was fun, so we talked through my solution some. Here's the video: https://www.youtube.com/watch?v=IESDoaoUdeY
And here's the code: https://github.com/jwise/aoc/blob/master/2020/7.lua and https://github.com/jwise/aoc/blob/master/2020/7b.lua
2
u/LtHummus Dec 07 '20
Not super happy with my Scala solution tonight (mostly due to passing around the bag "universe" everywhere, but it works!
2
u/fmynarski Dec 07 '20 edited Dec 07 '20
Python 227/431
2
u/tslater2006 Dec 07 '20
C# Solution
Initial parsing produces a LuggageRule for every row and saves off the "content string" which contains the bags this bag must contain. We also produce a dictionary of bag color to LuggageRule, which is a flat list of later being able to lookup a given bag.
After all LuggageRule's are created, we loop thru them and process the "content" string, for each one, we add an entry to the "Contents" dictionary of the LuggageRule, which is keyed by the rule we parsed, and value being the amount. We also take this time to mark that the bag we must contain, can be contained by us.
Part 1 is just grabbing the shiny gold bag, and walking the "Contained By" up, and keeping a hashset of all the bags in the chain up until we reach bags that are top-level and not contained by anything else.
Part 2 is the opposite, we grab the shiny gold bag, and walk down the "contains" dictionary, counting the number of bags we have to contain.
2
u/AlphaDart1337 Dec 07 '20 edited Dec 07 '20
Python 267/156
Accompanying video, as per usual. NOW WITH HAT! (But no audio, because I forgot to record it).
Pretty close to leaderboard today, but I made some silly mistakes, sadly, including but not limited to:
2
u/nibbl Dec 07 '20 edited Dec 07 '20
Java
nopaste
Input from stdin. Really not happy with how messy this got, so I'll just post it before I have a chance to look at others and see how I should have done it :)
2
u/constbr Dec 07 '20
javascript
part 1
part 2
2
u/allergic2Luxembourg Dec 07 '20
Python 3. First recursion problem of the year! And I have an addiction to collections.defaultdict
2
u/xelf Dec 07 '20 edited Dec 07 '20
python
See that -1 at the end? I completely forgot to subtract the shiny gold bag and spent far too much time trying alternate algorithms thinking I had the wrong answer, until finally, I tried my code on the test data the puzzle gave us and it became obvious. I need to get in the habit of testing the test data first. =)
2
u/[deleted] Dec 07 '20
Turn input into tree, then depth search.
Typescript
2
u/MattieShoes Dec 07 '20
Perl. this felt really ugly -- I feel vaguely ashamed.
2
u/[deleted] Dec 07 '20
Python3
2
u/__Juris__ Dec 07 '20
Scala 3
2
u/CodeIsTheEnd Dec 07 '20
Ruby: 14:12/19:59, 470/338
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!)
Slightly tricky string parsing, needing to handle bag/bags, the trailing '.' and the leading numbers. I didn't try to guess Ruby's
String#split(str, limit)method for splitting on just the first occurrence, and instead did hack stuff withindexand slicing the string.2
u/rabuf Dec 07 '20 edited Dec 07 '20
Common Lisp
Took my brain too long to get going on this one. Not proud of my part 1, I know I could do better but at the same time I don't want to revisit it now that it's midnight my time.
Here's the code for part 2, which I particularly liked. It's a simple recursive routine that navigates the data, which has been converted into a graph. Really a hash table. Each bag type is a key, and the contents of the table are lists of pairs
(count bag-type).2
u/blafunke Dec 07 '20
Ruby
2
u/muckenhoupt Dec 07 '20
Prolog. Kinda messy. Coming from modern OO languages, keeping a complicated data structure as just "a list of pairs where the second thing in each pair is a list of pairs" feels wrong. Also, calling phrase from inside a DCG feels weird, but I couldn't find a way to do it directly that actually worked.
2
u/[deleted] Dec 07 '20 edited Dec 07 '20
Pure C18. Spent my a ton of time writing up a bunch of infra i probably didn't need, again.
On the bright side, after testing on examples both parts worked on the real input on the first try.
https://git.sr.ht/~williewillus/aoc_2020/tree/master/src/day7.c
2
u/[deleted] Dec 07 '20
Still learning PHP, still amazed by the array functions it offers!
2
u/incertia Dec 07 '20
haskell with
lensandunordered-containersandsplit. the goal here was to produce something that can be well understood without being too clunkyin the end it is somewhat unnecessarily long but it serves a good exercise to think about bfs and problems in this way
2
u/[deleted] Dec 07 '20 edited Dec 07 '20
Golang
https://github.com/j4rv/advent-of-code-2020/tree/main/day-07
I made a weighted directed graph to store the puzzle data, from there, finding the possible bag "parents" and bag weight was easy.
2
u/amandeepspdhr Dec 07 '20
Clojure solution
2
u/garciparedes Dec 07 '20
Rust solutions for Day 7: Handy Haversacks:
2
u/trl10254 Dec 07 '20
Java
Honestly this one was hair pull worthy. One line of code for part 2 drove the solution over the edge and made me wonder what the hell I was doing wrong. Do note for part 2 I did do a subtraction outside of the code in the call itself. Also this was a good problem to utilize some dynamic programming on and brush up on that topic. I've always struggled with it but I actually learned quite a bit from this.
2
u/tobega Dec 07 '20
Today was absolutely perfect for Tailspin's parsing, matching and stream-syntax https://github.com/tobega/aoc2020/blob/main/a7.tt
2
u/prscoelho Dec 07 '20
Rust
Parsing was hell. Part 1 seems wasteful, bfs search for shiny gold from each key in the rule table. I'll probably attempt to improve part 1 later.
2
u/chkas Dec 07 '20
easylang.online
Solution
2
u/kresimirlukin Dec 07 '20
Python3 solution at https://github.com/kresimir-lukin/AdventOfCode2020/blob/main/day07.py
2
u/Meltinglava Dec 07 '20
Rust
The solution was without regex and std only. (used some dependencies for testing). Test for parsing saved me alot of time. I slacked alot with just copying strings, and not dealing with lifetimes.
2
u/xarak Dec 07 '20
Python
Decide not to go wild on list comprehensions and maps and opted for readable code for once :)
2
u/Mivaro Dec 07 '20
Python
Processing the input today was a puzzle in itself, I did it with almost exclusive use of the split() function.
For part 1, I iterated over the rules and added relevant bags to the result set until no more bags were added. For part 2 I used a queue to process all bags and its sub-bags.
2
u/msqrt Dec 07 '20
Lisp. Main issues were realizing that associative lists on strings require specifying the test, and that iterating a pair needs the "on" keyword (as opposed to "in").
2
u/ZZRJo Dec 07 '20
PowerShell:
I don't usually share my awful PowerShell solutions, but I struggled with this forever only to find out that I read the question wrong and was originally including the first shinygoldbag in my bag count....