Jack Bauer: (sitting at his computer) “Ok, I’ve got the data from the sensors. It looks like there’s a network of pipes and pressure-release valves here. If we open these valves and follow the tunnels, we might be able to stop the terrorist threat.”
(starts typing on his computer) “First, I need to import some libraries to help me process this data.”
(types quickly)
(pauses, then speaks into his headset) “Chloe, I’m going to need you to send me the data file for the network of pipes and pressure-release valves. I need to create a class for the nodes in this network.”
(waits for Chloe to send the file)
(types)
“Ok, got it. Now I’m creating a class for the nodes in the network.”
(types)
“Now I’m reading in the input and creating the nodes for the network.”
(types)
“Now I need to create a function to traverse the network and find the most pressure we can release.”
(types)
“And now I can use this function to find the most pressure we can release in 30 minutes, or in 26 minutes if we take into account the time it will take us to get the elephants out.”
(types)
“Alright, running the function now. Chloe, I’m going to need you to keep an eye on the timer. We’ve only got 30 minutes before the terrorists launch their attack.”
(stares intently at the computer as it processes the data)
(exhales deeply) “Ok, got it. The most pressure we can release in 30 minutes is X. And if we factor in the time it will take us to get the elephants out, the most pressure we can release in 26 minutes is Y.”
(pauses) “Chloe, send this data to the field team. They need to follow these routes and open these valves to release the most pressure possible. We’ve got to stop this attack before it’s too late.”
Python 3.11
There were algorithms to simplify the puzzle space; I rolled my own because I didn’t know about the others. Part 1 worked. Part 2, where you had to share tasks with an elephant that showed an interest, worked for me. I chose the best route for the human and the best route through what remained for the elephant.
Apparently that is the incorrect strategy. I played around with some other algorithms but stuff was just not working, so… put it aside. Always a new puzzle. I have my two golden stars for the day.
from time import time_ns
import re
from collections import defaultdict
class Node:
def __init__(self, data):
self.name = data[0]
self.flow = int(data[1])
self.neighbor_map = defaultdict(int)
for neighbor in data[2:]:
self.neighbor_map[neighbor] = 1
def __repr__(self):
return f"Node({self.name}, {self.flow}, {self.neighbor_map})\n"
def read_input():
nodes = []
with open(r"2022\puzzle16.txt") as f:
for l in f.read().splitlines():
nodes.append(Node(re.findall(r"[A-Z][A-Z]|\d+", l)))
for node in nodes:
for a_node in nodes:
if node != a_node and node.name in a_node.neighbor_map:
current_distance = a_node.neighbor_map[node.name]
for my_neighbor in node.neighbor_map:
if my_neighbor == a_node.name:
continue
if my_neighbor not in a_node.neighbor_map:
a_node.neighbor_map[my_neighbor] = current_distance + \
node.neighbor_map[my_neighbor]
else:
a_node.neighbor_map[my_neighbor] = min(
a_node.neighbor_map[my_neighbor], current_distance + node.neighbor_map[my_neighbor])
if not node.flow:
del a_node.neighbor_map[node.name]
return {node.name: node for node in nodes if node.name == starting_node or node.flow}
def traverse(node_map, current_node, visited=[], time=0, max_time=30):
if time >= max_time:
return 0, visited
node = node_map[current_node]
score = node.flow * (max_time - time)
new_visited = visited + [current_node]
child_scores = max([traverse(node_map, neighbor, new_visited, time + node.neighbor_map[neighbor] + 1, max_time)
for neighbor in node.neighbor_map if neighbor not in visited])
return (score + child_scores[0], [current_node] + child_scores[1])
def part1():
score, _ = traverse(node_map, starting_node)
return score
def part2():
score, path = traverse(node_map, starting_node, max_time=26)
# remove the nodes in 'path' from the neighbor_map of all nodes
for node in node_map.values():
for p in path[1:]:
if p in node.neighbor_map:
del node.neighbor_map[p]
elephant_score, _ = traverse(node_map, starting_node, max_time=26)
return elephant_score+score
starting_node = 'AA'
node_map = read_input()
start = time_ns()
print(f"Part 1: {part1()} in {(time_ns()-start)/1e6}ms")
start = time_ns()
print(f"Part 2: {part2()} in {(time_ns()-start)/1e6}ms")
