2022-12-16 - Proboscidea Volcanium
(original .ipynb)
from collections import defaultdict
puzzle_input_str = open("./puzzle_input/day16.txt").read()
test_input_str = """Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II"""
def parse_rate(rate_str):
_, rate = rate_str.split("=")
return int(rate.rstrip(";"))
def parse_line(line):
tokens = line.split(" ")
return tokens[1], parse_rate(tokens[4]), [valve.rstrip(",") for valve in tokens[9:]]
def bfs_find(neighbours, v1, v2):
queue = [(v1,0)]
visited = {v1}
while queue:
(v, cost) = queue.pop(0)
visited.add(v)
if v == v2:
return 1 + cost
queue += [(n, cost+1) for n in neighbours[v] if n not in visited]
raise Exception(f"couldn't find {v2}")
def build_distances_lookup(neighbours):
distances = defaultdict(dict)
for v1 in neighbours:
for v2 in neighbours:
distances[v1][v2] = bfs_find(neighbours, v1, v2)
return distances
def part_one(input_str):
valves = [parse_line(line) for line in input_str.splitlines()]
flow_rates = {v[0]:v[1] for v in valves}
neighbours = {v[0]:v[2] for v in valves}
all_valves = {v[0] for v in valves if flow_rates[v[0]] != 0}
time_to = build_distances_lookup(neighbours)
max_pressure = 0
queue = [("AA", 30, set(), 0)]
while queue:
valve, minutes, valves_open, pressure = queue.pop(0)
max_pressure = max(pressure, max_pressure)
for n in all_valves:
if n != valve and n not in valves_open:
t = time_to[valve][n]
next_minutes = minutes - t
if next_minutes > 0:
queue.append((n, next_minutes, valves_open.union({valve}), pressure + (flow_rates[n] * next_minutes)))
return max_pressure
assert 1651 == part_one(test_input_str)
print("part one:", part_one(puzzle_input_str))
part one: 1754
%%time
from itertools import permutations
def solve(me, elephant, valves_open, pressure, all_valves, flow_rates, time_to):
me_v , me_t = me
elephant_v, elephant_t = elephant
combs = permutations([v for v in all_valves if v not in valves_open and v != me_v and v != elephant_v], 2)
solutions = [pressure]
for me_vnext, elephant_vnext in combs:
me_tnext = me_t - time_to[me_v][me_vnext]
elephant_tnext = elephant_t - time_to[elephant_v][elephant_vnext]
me_pnext = flow_rates[me_vnext] * me_tnext
elephant_pnext = flow_rates[elephant_vnext] * elephant_tnext
if me_tnext < 0 and elephant_tnext < 0:
break
if me_tnext < 0:
me_tnext = me_t
me_vnext = me_v
me_pnext = 0
if elephant_tnext < 0:
elephant_tnext = elephant_t
elephant_vnext = elephant_v
elephant_pnext = 0
pressure_next = pressure + me_pnext + elephant_pnext
solutions.append(
solve(
(me_vnext, me_tnext),
(elephant_vnext, elephant_tnext),
valves_open.union({me_vnext, elephant_vnext}),
pressure_next,
all_valves, flow_rates, time_to
)
)
return max(solutions)
def part_two(input_str):
valves = [parse_line(line) for line in input_str.splitlines()]
flow_rates = {v[0]:v[1] for v in valves}
neighbours = {v[0]:v[2] for v in valves}
all_valves = {v[0] for v in valves if flow_rates[v[0]] != 0}
time_to = build_distances_lookup(neighbours)
max_pressure = 0
return solve(("AA",26), ("AA", 26), set(), 0, all_valves, flow_rates, time_to)
assert 1707 == part_two(test_input_str)
print("part_two:", part_two(puzzle_input_str))
part_two: 2474
CPU times: user 9h 32min 1s, sys: 3.17 s, total: 9h 32min 4s
Wall time: 9h 32min 15s
# ABORTED BFS VERSION - this is my first attempt, it eats up all available RAM. 0/10, would not recommend.
# I've leaving this here because I usually *sort of* polish my solutions up, and I figured it might be interesting to see
# not only an unpolished work-in-progress one with debug prints and such, but a completely failed one :)
from itertools import permutations
def part_two(input_str):
valves = [parse_line(line) for line in input_str.splitlines()]
flow_rates = {v[0]:v[1] for v in valves}
neighbours = {v[0]:v[2] for v in valves}
all_valves = {v[0] for v in valves if flow_rates[v[0]] != 0}
time_to = build_distances_lookup(neighbours)
max_pressure = 0
queue = [(("AA", 26), ("AA", 26), set(), 0)]
print(len(all_valves))
n = 0
while queue:
me, elephant, valves_open, pressure = queue.pop(0)
# CAREFUL!!! I may have fucked this up
max_pressure = max(pressure, max_pressure)
me_v , me_t = me
elephant_v, elephant_t = elephant
print(len([v for v in all_valves if v not in valves_open and v != me_v and v != elephant_v]))
combs = list(permutations([v for v in all_valves if v not in valves_open and v != me_v and v != elephant_v], 2))
#print(valves_open, f"({me_v}, {elephant_v})", len(combs), me_t, elephant_t)
for me_vnext, elephant_vnext in combs:
me_tnext = me_t - time_to[me_v][me_vnext]
elephant_tnext = elephant_t - time_to[elephant_v][elephant_vnext]
me_pnext = flow_rates[me_vnext] * me_tnext
elephant_pnext = flow_rates[elephant_vnext] * elephant_tnext
if me_tnext < 0 and elephant_tnext < 0:
continue
if me_tnext < 0:
me_tnext = me_t
me_vnext = me_v
me_pnext = 0
if elephant_tnext < 0:
elephant_tnext = elephant_t
elephant_vnext = elephant_v
elephant_pnext = 0
pressure_next = pressure + me_pnext + elephant_pnext
queue.append((
(me_vnext, me_tnext),
(elephant_vnext, elephant_tnext),
valves_open.union({me_vnext, elephant_vnext}),
pressure_next))
#print(n, len(valves_open), len(queue), max_pressure)
n += 1
# if n == 1:
# from pprint import pprint
# pprint(queue)
# print()
if n == 2:
# from pprint import pprint
# pprint(queue)
# print()
break
# if n == 3:
# from pprint import pprint
# pprint(queue)
# #break
return max_pressure
part_two(test_input_str)
# 1657 too low
#print("part two:", part_two(puzzle_input_str))
6
6
4
792