The Problem
Given a set of ‘rules’, figure out which bags could contain a given bag, and in part 2, how many bags could be contained in the given bag.
My Solution
In the prior year, the difficulty level ratcheted up fairly quickly, and I was beginning to get worried this year! Not to worry, this one was pretty hairy!
The rules specified very clearly describe a graph, and we need to essentially do a backward traversal for part 1 and a forward traversal (accumulating values as we go) for part 2. I’m happy to say I resisted the lure of actually creating a graph, and instead just used dictionaries instead of nodes and edges.
The format of the input was fairly intricrate, so I just parsed each line directly, rather than putting together a regular expression to do so. Different dictionaries for each part and recursion to wrap it all up!
Implementation
- There is actually a library called
parse
that makes it pretty easy to, well, parse input like this - Most solutions just split the input line into two, and then searched for contained bags. I like my approach better
- Some solutions used either dictionaries or lists but iterated over them multiple times. Very inefficient!
- A few actually used
networkx
to build a graph and then process it - Most solutions were essentially unreadable (as I’m sure mine is). This is a function of the problem that we’re trying to solve, I suppose. Or maybe I’m just tired…
- There was one succint, readable solution that used set comprehensions and a pretty neat recursion within it
Things are beginning to get exciting!