import re from collections import namedtuple STEPS = 32 from multiprocessing import Process, Queue def qual(env, ore_rbt, clay_rbt, obs_rbt, geo_rbt, ore_cnt, clay_cnt, obs_cnt, geo_cnt, t): assert max(ore_rbt, clay_rbt, obs_rbt, geo_rbt) < 32 assert max(ore_cnt, clay_cnt, obs_cnt) < 512 assert geo_cnt < 128 code = (t | ore_rbt <<6 | (clay_rbt <<11)| (obs_rbt <<16) | (geo_rbt << 21) | (ore_cnt <<26) | (clay_cnt <<35) | (obs_cnt <<44) | (geo_cnt << 53)) if code in env.cache: return env.cache[code] if t == STEPS: return geo_cnt # if fewer geodes than 80% of best solution so far -> discard if geo_cnt < env.t_max[t]*8//10: return -1 env.t_max[t] = max(env.t_max[t], geo_cnt) n_ore_cnt = ore_cnt + ore_rbt n_clay_cnt = clay_cnt + clay_rbt n_obs_cnt = obs_cnt + obs_rbt n_geo_cnt = geo_cnt + geo_rbt maxg = 0 if ore_cnt >= env.ore_cost and ore_rbt < env.max_ore_needed: maxg = max(maxg, qual(env, ore_rbt+1, clay_rbt, obs_rbt, geo_rbt, n_ore_cnt - env.ore_cost, n_clay_cnt, n_obs_cnt, n_geo_cnt, t+1)) if ore_cnt >= env.clay_cost and clay_rbt < env.obs_cost_clay: maxg = max(maxg, qual(env, ore_rbt, clay_rbt+1, obs_rbt, geo_rbt, n_ore_cnt - env.clay_cost, n_clay_cnt, n_obs_cnt, n_geo_cnt, t+1)) if ore_cnt >= env.obs_cost_ore and clay_cnt >= env.obs_cost_clay and obs_rbt < env.geo_cost_obs: maxg = max(maxg, qual(env, ore_rbt, clay_rbt, obs_rbt+1, geo_rbt, n_ore_cnt - env.obs_cost_ore, n_clay_cnt-env.obs_cost_clay, n_obs_cnt, n_geo_cnt, t+1)) if ore_cnt >= env.geo_cost_ore and obs_cnt >= env.geo_cost_obs: maxg = max(maxg, qual(env, ore_rbt, clay_rbt, obs_rbt, geo_rbt+1, n_ore_cnt - env.geo_cost_ore, n_clay_cnt, n_obs_cnt-env.geo_cost_obs, n_geo_cnt, t+1)) maxg = max(maxg, qual(env, ore_rbt, clay_rbt, obs_rbt, geo_rbt, n_ore_cnt, n_clay_cnt, n_obs_cnt, n_geo_cnt, t+1)) env.cache[code] = maxg return maxg Env = namedtuple("Env", "ore_cost, clay_cost, obs_cost_ore, obs_cost_clay, geo_cost_ore, geo_cost_obs, cache, t_max, max_ore_needed") def runline(queue, line): bp, ore_cost, clay_cost, obs_cost_ore, obs_cost_clay, geo_cost_ore, geo_cost_obs = [int(x) for x in re.findall("\d+", line)] cache={} t_max={i:0 for i in range(STEPS)} max_ore_needed = max(ore_cost, clay_cost, obs_cost_ore, geo_cost_ore) env = Env(ore_cost, clay_cost, obs_cost_ore, obs_cost_clay, geo_cost_ore, geo_cost_obs, cache, t_max, max_ore_needed) q = qual(env, 1, 0, 0, 0, 0, 0, 0, 0, 0) print (bp, "->", q) queue.put(q) with open("geode_p2.txt") as infile: procs = [] for line in infile: queue = Queue() proc = Process(target=runline, args=(queue, line)) proc.start() procs.append((proc, queue)) total = 1 for p, q in procs: p.join() # this blocks until the process terminates result = q.get() print (result) total *= result print (total)