For Day 11 part 1, the task is to find all paths from the server closest to us—marked by "you"—to an output server, marked by "out". This description is a thinly veiled graph problem: we must enumerate all paths from a start node to an end node in a directed graph. The problem is not immediately clear whether cycles exist, so we need to test for that just in case.
I initially approached this problem using a depth-first search (DFS), later adding memoization to improve efficiency.
with open("11.input") as f:
data = f.read().splitlines()
adj_map=dict()
for line in data:
key = line.split(": ")[0]
nei = line.split(": ")[1].split(" ")
adj_map[key]=nei
One notable implementation choice was how to represent and store paths during traversal. I wanted to record the results of each partial path while searching, primarily for troubleshooting and debugging purposes. Although Python lists have an amortized time complexity of $O(1)$ for appends, they are relatively heavy in terms of memory usage and less efficient than linked structures for this use case. The Node class below provides a more memory-efficient data structure for representing paths incrementally.
class Node:
__slots__ = ("value", "next")
def __init__(self, value=None, next_node=None):
self.value = value
self.next = next_node
def __len__(self):
if self.next == None:
return 1
else:
return 1+self.next.__len__()
def __repr__(self, skip=False):
if self.next == None:
return "Node("+str(self.value)+")-|"
elif skip:
return self.next.__repr__(skip=True)
else:
return "Node("+str(self.value)+ " -> "+self.next.__repr__(skip=True)+")"
def __iter__(self):
current = self
while current:
yield current
current = current.next
def __contains__(self, key):
if self.next == None:
if self.value == key: return True
else: return False
if self.value == key:
return True
else:
return self.next.__contains__(key)
def prepend(self, val):
if self.value == None:
return Node(val)
else:
return Node(val, self)
Note: This solution went through several iterations of the base algorithm before settling on the final approach.
p_map = dict()
def dfs(start, visited, path: Node = Node(), goal = 'out',amap=adj_map) -> (int,(list[Node])):
if (start,goal) in p_map:
ans = p_map[(start,goal)]
return len(ans), ans
elif start == goal:
p_map[(start,goal)] = [path.prepend(start)]
return (1,[path.prepend(start)])
elif start == "out": return (0,[])
else:
ans=0
a_paths = []
for nei in sorted(amap[start], key = lambda x: len(amap[x]) if x in amap else 0):
if nei not in visited:
c_ans, c_path=dfs(nei, visited.union([start]), path.prepend(start),goal, amap)
for p in c_path:
a_paths.append(p)
ans+=c_ans
p_map[(start,goal)] = a_paths
return ans, a_paths
NOTE: the use of frozenset which are immutable. This enables us to maintain DFS recursion without prematurally pruning sub-branches.
ans, ans_paths = dfs( "you", frozenset())
print(f"The answer for part 1 is {ans}")
The answer for part 1 is 758
For Part 2, it quickly becomes clear that the naïve approach will not scale. Even with dynamic programming, the Part 1 solution suffers from both excessive runtime and rapidly growing memory consumption. After several unsuccessful attempts to adapt the original approach, I shifted focus to better understanding the underlying structure of the graph.
My second approach was to analyze partial walks, such as paths from fft to dac or from dac to out. One of my goals was to also identifying subpaths that could be reused to construct a memoization table without visiting the entire search space. Through experimentation, a crucial insight emerged: while paths exist from fft to dac, no paths exist from dac back to fft.
As a result, the overall solution can be decomposed into independent segments:
svr → fft → dac → out
To compute the total number of valid paths, we simply multiply the number of paths in each segment.
dac_out = dfs( "dac", frozenset(), goal = "out")[0]
print(f"The answer for dac to out helper is {dac_out}")
fft_dac=dfs( "fft", frozenset(), goal = "dac")[0]
print(f"the answer for fft to dac helper is {fft_dac}")
svr_to_fft = dfs( "svr", frozenset(), goal = "fft")[0]
print(f"The answer for svr to fft helper is {svr_to_fft}")
print(f"The answer for part 2 is {svr_to_fft*fft_dac*dac_out}")
The answer for dac to out helper is 4800 the answer for fft to dac helper is 5678405 The answer for svr to fft helper is 18003 The answer for part 2 is 490695961032000
Please comment!