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'...
For further actions, you may consider blocking this person and/or reporting abuse
moar rust. My brain ran into so many fence post errors on this one. I should have drank more coffee before attempting.
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
Vec
of 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 aHashMap
where the key is the start of each edge and the value is theVec
of 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.
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.
Python
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
Part2
Node
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.
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.
Here's Ruby:
Today's puzzle was a little bit more complicated. However, like every other day before, I've created a step-by-step tutorial for my fellow TypeScript and JavaScript developers:
[Advent of Code 2020] Day 7 Step-by-Step Tutorial (TypeScript)
Kai ・ Dec 7 ・ 8 min read
Thanks for reading! :)
F#:
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
ancestors
for 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.
My JavaScript walkthrough:
I'm not happy with this javascript solution. Part 1 is very slow, and part 2 is not regexy enough. I'll hide it behind this gist.