86 lines
2.5 KiB
Python
86 lines
2.5 KiB
Python
from lib import *
|
|
|
|
input = read_input(2019, 14)
|
|
|
|
|
|
def ceil(a, b):
|
|
return a // b + (a % b > 0)
|
|
|
|
|
|
reactions = {}
|
|
for line in input.splitlines():
|
|
reactants, product = line.split(" => ")
|
|
reactants = [reactant.split() for reactant in reactants.split(", ")]
|
|
amount, product = product.split()
|
|
assert product not in reactions
|
|
reactions[product] = ([(reactant, int(amount)) for amount, reactant in reactants], int(amount))
|
|
|
|
ore_used = 0
|
|
chemicals = {}
|
|
Q = [("FUEL", 1)]
|
|
while Q:
|
|
chemical, prod_amount = Q.pop(0)
|
|
if chemical == "ORE":
|
|
ore_used += prod_amount
|
|
continue
|
|
chem_amount = chemicals.get(chemical, 0)
|
|
reaction_amount = prod_amount - chem_amount
|
|
if reaction_amount <= 0:
|
|
chemicals[chemical] -= prod_amount
|
|
continue
|
|
reactants, product_amount = reactions[chemical]
|
|
reaction_count = ceil(reaction_amount, product_amount)
|
|
for reactant, amount in reactants:
|
|
Q.append((reactant, amount * reaction_count))
|
|
chemicals[chemical] = chem_amount + reaction_count * product_amount - prod_amount
|
|
print(ore_used)
|
|
|
|
|
|
def ceil(a, b):
|
|
return a // b + (a % b > 0)
|
|
|
|
|
|
reactions = {}
|
|
for line in input.splitlines():
|
|
reactants, product = line.split(" => ")
|
|
reactants = [reactant.split() for reactant in reactants.split(", ")]
|
|
amount, product = product.split()
|
|
assert product not in reactions
|
|
reactions[product] = ([(reactant, int(amount)) for amount, reactant in reactants], int(amount))
|
|
|
|
|
|
def get_ore_used(amount):
|
|
ore_used = 0
|
|
chemicals = {}
|
|
Q = [("FUEL", amount)]
|
|
while Q:
|
|
chemical, prod_amount = Q.pop(0)
|
|
if chemical == "ORE":
|
|
ore_used += prod_amount
|
|
continue
|
|
chem_amount = chemicals.get(chemical, 0)
|
|
reaction_amount = prod_amount - chem_amount
|
|
if reaction_amount <= 0:
|
|
chemicals[chemical] -= prod_amount
|
|
continue
|
|
reactants, product_amount = reactions[chemical]
|
|
reaction_count = ceil(reaction_amount, product_amount)
|
|
for reactant, amount in reactants:
|
|
Q.append((reactant, amount * reaction_count))
|
|
chemicals[chemical] = chem_amount + reaction_count * product_amount - prod_amount
|
|
return ore_used
|
|
|
|
|
|
LIMIT = 1000000000000
|
|
low = 0
|
|
high = LIMIT
|
|
while low < high:
|
|
guess = (low + high) // 2
|
|
used = get_ore_used(guess)
|
|
if used <= LIMIT:
|
|
if get_ore_used(guess + 1) > LIMIT:
|
|
print(guess)
|
|
break
|
|
low = guess
|
|
elif used > LIMIT:
|
|
high = guess
|