AoC: Day 07


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!

, ,

Leave a Reply

Your email address will not be published.