I'm on the computer a little later than usual, so I thought I'd get the post for tomorrow up now so I don't have to do it in the morning, since it's past midnight on the East coast anyway.
Oh my gosh, today’s puzzle is a parsing, dependency graph nightmare. Maybe I'm just tired and overcomplicating things in my head, but I'm thinking that's the case. Our input is a series of lines describing how certain colors of bag (e.g. "vivid plum") can contain certain quantities of other bags (e.g. "shiny gold"). We are to decide which bags can contain our bag, the shiny gold one. Yoy.
As always, this is the spot where I’ll plug any leaderboard codes shared from the community.
Ryan's Leaderboard: 224198-25048a19
If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.
Updated 03:08PM 12/12/2020 PST.
Top comments (19)
moar rust. My brain ran into so many fence post errors on this one. I should have drank more coffee before attempting.
I went way overboard with my Rust solution.
I found a graph library to model the actual structure of the nested bags. Spent more time trying to reason out the graph structure and figure out what I was doing, than I did actually getting the problem solved.
A fun exercise, to be sure, but not the fastest way to row the boat.
As always, available on Github.
Solution for C# (part 2).
Just wanted to finish it, so don't expect any beauty :) :
I start to like parsing these kind of rules in Haskell, it's very intuitive to me.
The association list was a nice fit for this problem; had I done it in Java, I would have used a Map with Lists as a value. Even though it's not the most time efficient approach, it was allright for this size problem.
My cleanest solution! Wrote more about it, even tested networkx in my blogpost.
Ruby, part 1. Kinda ugly, but effective:
Struggled on this one more than I probably should have. I started with a recursion bug that was right in front of my eyes, then went on to part2 to realize that I would need to re-think my model (can't say I didn't see that one coming).
Part 1 is a reachability problem, Part 2 is a Depth first search. But instead of building a graph, I was lazy and kept a Map of edges.
Oh dear, I didn't look at the input and assumed there were just the nine colours in the example. Modelled them in an enum and wrote parsers for them all, which failed on the first line of input text. Lesson: look at the real data!
The problem is a directed acyclic graph one. I modelled the graph as a
Vecof edges with the start and end nodes, which meant quite expensive searching. It only took 10 or 20 seconds to run but I knew it was a mistake. Reworked to a
HashMapwhere the key is the start of each edge and the value is the
Vecof possible end nodes.
The actual graph traversals are the bread and butter of my day job. Those were easy. I wasted a lot of time today on parsing and bad modelling.
Urgh this was horrible. I should have taken the opportunity to learn some kind of graph library to do this, but I've spent way enough time looking at it now.
[Advent of Code 2020] Day 7 Step-by-Step Tutorial (TypeScript)
Kai ・ Dec 7 ・ 8 min read
Thanks for reading! :)
Sweet mother of everything, I've walked a graph in COBOL.
I pull out that PEG parser again to handle my input, I feel it's more readable than a full regex solution, since you define the entire syntax of the input file up-front for everyone to see. But it's not as compact as a pure regex solution, and there's a lot of extra nodes (could probably golf it, but it would be less readable). One benefit is the NodeVisitor is already doing a depth-first visit of the generated AST, so you can piggy back the graph generation in there to save a loop or two.
I used the NetworkX graph library in Python to get the
ancestorsfor free, but unfortunately still had to write a recursive traversal of the DAG to get the sums for Part 2.
Made some nice graphs while I was at it too, more on my post
Ruby, part 2. Oddly much easier than part 1. Parsing modified to suit the problem better:
I caved, I'm sorry. I fought with the parsing in C for long enough and I didn't want to get bogged down and behind a day, so I knocked it out in Python.