Varje blueprint blir en matris med de state-förÀndringar som sker om man bygger en robot av typ X. Blueprint-matrisen adderas till matrisen med alla nuvarande state och ut kommer en 5 gÄnger sÄ stor matris. Det blir snabbt en ohÄllbart stor sökrymd. Följande fyra regler hÄller ner antalet states sÄ det faktiskt funkar att köra BFS.
Den sista regeln Àr det som gör det möjligt att köra BFS. Det skulle gÄ att klippa mer i sökrymden, men det funkar OK nu. MinnesÄtgÄngen hÄller sig under 5GB.
import re
import numpy as np
from collections import defaultdict
from math import prod
adm, res, cost, robots, br = 0, 1, 1, 2, 3 # adm, resources, cost, robots, built robot
ore, cly, obs, geo = 0, 1, 2, 3
bm, cbm, lbm, lcbm = 0, 1, 2, 3 # Built Mask, Can Build Mask, Last Build Mask, Last Can Build Mask
bp = []
for l in open("input19").readlines():
_, or0, cl0, ob0, ob1, ge0, ge2 = tuple(map(int, re.findall(r'\d+', l)))
bp.append(
np.array(
# Adm, Cost Owned robots Built Robot
[[[1, 0, 0, 0], [-or0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]],
[[2, 0, 0, 0], [-cl0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0]],
[[4, 0, 0, 0], [-ob0, -ob1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]],
[[8, 0, 0, 0], [-ge0, 0, -ge2, 0], [0, 0, 0, 0], [0, 0, 0, 1]],
[[0, 0, 0, 0], [ 0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]],
dtype=np.int_))
def tick(states, bp, limit):
s = (states.reshape((-1, 16)) + bp.reshape((-1, 1, 16))).reshape(-1, 4, 4)
# Did we have enough resources to build?
s = s[s[:,res,:].min(axis = 1) >= 0,:]
# No need to have more robots than the resource use each minute
s = s[(s[:,robots,:geo] <= limit).all(axis = 1),:]
# Can we build geode robot?
s = s[((s[:, adm, cbm] & 8) != 0) == s[:, br, geo],:]
# Should have built earlier?
s = s[
~np.logical_and(
np.logical_and(s[:, adm, bm] != 0, s[:, adm, lbm] == 0),
(s[:, adm, bm] & s[:, adm, lcbm]) != 0),:]
# Each robot collects one resource
s[:, res, :] += s[:,robots,:]
# Built any new robots?
s[:, robots, :] += s[:, br,:]
# Bookkeeping
s[:, adm, lbm] = s[:, adm, bm]
s[:, adm, lcbm] = s[:, adm, cbm]
s[:, adm, bm] = 0
s[:, adm, cbm] = ( (s[:, res, :] + bp[geo, cost, :] >= 0).all(axis = 1) << 3
| (s[:, res, :] + bp[obs, cost, :] >= 0).all(axis = 1) << 2
| (s[:, res, :] + bp[cly, cost, :] >= 0).all(axis = 1) << 1
| (s[:, res, :] + bp[ore, cost, :] >= 0).all(axis = 1))
s[:, br: ,:] = 0
return s
def bfs(bp, minutes):
l = []
for i,b in enumerate(bp):
limit = -b[:, cost, :geo].min(axis=0)
s = np.array([[0,0,0,0], [0,0,0,0], [1,0,0,0], [0,0,0,0]])
for j in range(minutes):
s = tick(s, b, limit)
l.append((i + 1, s[:, res, geo].max()))
return l
print(sum(map(prod, bfs(bp, 24))),
prod(map(lambda x: x[1], bfs(bp[:3], 32))))