Published December 11, 2025
It's day 11 and today's was a pretty easy one. Some simple recursion with memoization got part 1
@functools.cache
def find_out(node: str, node_map: HashableDict) -> int:
next_nodes = node_map[node]
if 'out' not in next_nodes:
return sum(find_out(next_node, node_map, filter, found)
for next_node in next_nodes)
else:
return 1
I created the HashableDict class so I could use dictionaries for memoized functions just like this:
class HashableDict(dict):
def __hash__(self):
return hash(tuple(self.items()))
def __setitem__(self, key, value):
# The key must be hashable because it's a dictionary. We run a hash on the value to make sure that is. since
# that will raise a TypeError if it's not we don't need to do anything else.
hash(value)
super().__setitem__(key, value)
Without that my options would be to not leverage functools.cache or something like a tuple that has the node and it's exits. The problem
with that being that I would have to iterate through it every time to find the node I'm looking for.
When I originally wrote part 1 I assumed that I would need to know the nodes on the path for part 2, so I had the function preserve that.
Since I needed something hashable I chose to use a frozenset and rebuild it every time. For part 1 that wasn't a big deal but with the
different start point for part 2 we get more, longer paths, and I ended up with something that was starting to feel like a heat death
of the universe solution. I realized that I didn't actually need that to do the filtering - all I needed was to keep track of the nodes
that I hit that were in the filter. If I hit all of them, I had a valid path.
@functools.cache
def find_out(node: str, node_map: HashableDict, filter_for: tuple[str], found: tuple[str]) -> int:
if node in filter_for:
found += (node,)
next_nodes = node_map[node]
return (
sum(find_out(next_node, node_map, filter_for, found) for next_node in next_nodes)
if 'out' not in next_nodes
else not filter_for or found == filter_for
)
All told, I'm pretty happy with my solution for today. Part 1 runs in ~3ms and part 2 in ~61ms all with < 20 lines of code.
Full solution is on my GitHub.