AdventOfCode/2022/day19.py

82 lines
3.5 KiB
Python
Raw Permalink Normal View History

2022-12-19 23:15:42 +10:30
from helpers import *
from multiprocessing import Pool
lines = read_day(19).split('\n')
sample_lines = '''
Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.
'''.strip().split('\n')
2022-12-20 00:16:03 +10:30
maximum_potential = np.arange(33, dtype=np.int8).cumsum()
2022-12-19 23:15:42 +10:30
def bp_quality(line, t_max=24):
bp, cost_orebot_ore, cost_claybot_ore, cost_obsbot_ore, cost_obsbot_clay, cost_geodebot_ore, cost_geodebot_obs = line_to_numbers(line)
2022-12-20 02:09:03 +10:30
# print(line)
2022-12-19 23:15:42 +10:30
# Ore, Clay, Obsidian, Geode
orebot_cost = np.array([cost_orebot_ore, 0, 0], dtype=np.int8)
claybot_cost = np.array([cost_claybot_ore, 0, 0], dtype=np.int8)
obsbot_cost = np.array([cost_obsbot_ore, cost_obsbot_clay, 0], dtype=np.int8)
geodebot_cost = np.array([cost_geodebot_ore, 0, cost_geodebot_obs], dtype=np.int8)
robot_orders = ( # Special ordering to try and hit best case earliest
2022-12-20 02:09:03 +10:30
(1, claybot_cost),
(0, orebot_cost),
(2, obsbot_cost),
2022-12-19 23:15:42 +10:30
(None, geodebot_cost),
)
2022-12-20 00:16:03 +10:30
max_robots = np.array([max(cost_orebot_ore, cost_claybot_ore, cost_obsbot_ore, cost_geodebot_ore), cost_obsbot_clay, cost_geodebot_obs], dtype=np.int8)
2022-12-19 23:15:42 +10:30
search_stack = []
2022-12-20 02:09:03 +10:30
seen = set()
2022-12-19 23:15:42 +10:30
def add_state(t, robot_counts, res_counts, geodes_total):
state = (t, tuple(robot_counts), tuple(res_counts), geodes_total)
2022-12-20 02:09:03 +10:30
if state not in seen:
2022-12-19 23:15:42 +10:30
search_stack.append((t, robot_counts, res_counts, geodes_total))
2022-12-20 02:09:03 +10:30
seen.add(state)
2022-12-19 23:15:42 +10:30
add_state(0, np.array((1,0,0), dtype=np.int8), np.array((0,0,0), dtype=np.int8), 0)
geodes_best = 0
2022-12-20 02:39:53 +10:30
while search_stack:
2022-12-19 23:15:42 +10:30
t, robot_counts, res_counts, geodes_total = search_stack.pop()
if t < t_max:
2022-12-20 00:16:03 +10:30
if (geodes_total + maximum_potential[t_max-t]) < geodes_best:
continue
2022-12-20 02:09:03 +10:30
for idx, cost in robot_orders:
if idx is not None:
if robot_counts[idx] >= max_robots[idx]:
2022-12-20 00:16:03 +10:30
continue
2022-12-20 02:09:03 +10:30
next_robots = robot_counts.copy()
next_robots[idx] += 1
2022-12-19 23:15:42 +10:30
mask = cost > 0 # Only look at resources within the cost
if np.any(robot_counts[mask] == 0): # no robot no income, we can't just wait to build it
continue
time_to_resources = max(-(-(cost[mask] - res_counts[mask]) // robot_counts[mask]))
dt = max(0, time_to_resources) + 1 # Always need one minute to build something after having the resources ready
nt = t + dt
if nt < t_max: # Nothing interesting can happen on the very last minute
new_res = res_counts + (dt * robot_counts) - cost
2022-12-20 02:09:03 +10:30
if idx is None: # Special case for Geodebots
2022-12-19 23:15:42 +10:30
add_state(nt, robot_counts, new_res, geodes_total+(t_max-nt))
else:
2022-12-20 00:16:03 +10:30
add_state(nt, next_robots, new_res, geodes_total)
2022-12-19 23:15:42 +10:30
geodes_best = max(geodes_best, geodes_total)
quality = bp * geodes_best
2022-12-20 02:09:03 +10:30
print(f'Blueprint {bp}: at {t_max} minutes: max geodes {geodes_best}, quality number = {quality}')
2022-12-19 23:15:42 +10:30
return bp, geodes_best, quality
2022-12-20 02:09:03 +10:30
def bp_quality32(line):
2022-12-20 00:16:03 +10:30
return bp_quality(line, 32)
2022-12-19 23:15:42 +10:30
if __name__ == '__main__':
2022-12-20 00:16:03 +10:30
with Pool(8) as p:
2022-12-20 02:09:03 +10:30
depth32 = p.map_async(bp_quality32, lines[:3])
depth24 = p.map_async(bp_quality, lines)
qual_tally = sum((quality for bp, max_geodes, quality in depth24.get()))
2022-12-20 00:16:03 +10:30
print(f'Part 1: {qual_tally}')
2022-12-20 02:09:03 +10:30
max_prod = prod((max_geodes for bp, max_geodes, quality in depth32.get()))
2022-12-20 00:16:03 +10:30
print(f'Part 2: {max_prod}')
# qual_tally = sum((bp_quality(line)[-1] for line in lines))
# print(f'Part 1: {qual_tally}')
2022-12-20 02:09:03 +10:30
# max_prod = prod((max_geodes for bp, max_geodes, quality in map(bp_quality32, lines[:3])))
# print(f'Part 2: {max_prod}')