#!/usr/bin/python3
#encoding: UTF-8

import fileinput
import sys
import math
from collections import OrderedDict

if len(sys.argv) == 1:
    sys.argv += ["input_14"]

class Reaction(object):
    def __init__(self, line):
        self.reagents = OrderedDict()
        self.product = None
        self.product_count = 0
        
        parts = line.split(" => ")
        reagents = parts[0].split(", ")
        for reagent in reagents:
            words = reagent.split(" ")
            self.reagents[words[1]] = int(words[0])
        
        words = parts[1].split(" ")
        self.product = words[1]
        self.product_count = int(words[0])
    
    def __repr__(self):
        s = " + ".join([repr(self.reagents[r]) + " " + r for r in self.reagents])
        s += " => {0} {1}".format(self.product_count, self.product)
        return s
        
class Chemistry(object):
    def __init__(self, reactions, factor=1):
        self.reactions = reactions
        self.needs = OrderedDict()
        self.products = {}
        
        r_fuel = self.reactions["FUEL"]
        self.needs = r_fuel.reagents.copy()
        for r in self.needs:
            self.needs[r] *= factor
    
    def step(self):
        needs_keys = list(self.needs.keys())
        for r in needs_keys:
            if r == "ORE":
                continue
            need = self.needs[r]
            got = self.products.get(r, 0)
            missing = need - got
            all_done = True
            if missing > 0:
                reaction = self.reactions[r]
                n_reactions = math.ceil(missing / reaction.product_count)
                for reagent in reaction.reagents:
                    self.needs[reagent] = self.needs.get(reagent, 0) + n_reactions * reaction.reagents[reagent]
                self.products[r] = got + n_reactions * reaction.product_count
                all_done = False
        return all_done
    
    def ORE(self):
        return self.needs.get("ORE", 0)


def work_p1(lines):
    reactions = {}
    for line in lines:
        r = Reaction(line.strip())
        reactions[r.product] = r
    
    chem = Chemistry(reactions)
    while not chem.step():
        pass
    return chem.ORE()

def work_p2(lines):
    reactions = {}
    for line in lines:
        r = Reaction(line.strip())
        reactions[r.product] = r
    
    chem = Chemistry(reactions, 1)
    while not chem.step():
        pass
    ore_one = chem.ORE()
    
    factor = 1
    target = 1000000000000
    missing = target
    while True:
        chem = Chemistry(reactions, factor)
        while not chem.step():
            pass
        ore = chem.ORE()
        missing = target - ore
        if missing > 0:
            step = missing // ore_one
            step = 1 if step == 0 else step
            factor += step
        else:
            break

    return factor - 1
    
def test_p1():
    s="""10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL""".split("\n")
    assert work_p1(s) == 31
    
    s="""9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL""".split("\n")
    assert work_p1(s) == 165
    
    s="""157 ORE => 5 NZVS
165 ORE => 6 DCFZ
44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL
12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ
179 ORE => 7 PSHF
177 ORE => 5 HKGWZ
7 DCFZ, 7 PSHF => 2 XJWVT
165 ORE => 2 GPVTF
3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT""".split("\n")
    assert work_p1(s) == 13312
    
    s="""171 ORE => 8 CNZTR
7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL
114 ORE => 4 BHXH
14 VRPVC => 6 BMBT
6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL
6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT
15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW
13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW
5 BMBT => 4 WPTQ
189 ORE => 9 KTJDG
1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP
12 VRPVC, 27 CNZTR => 2 XDBXC
15 KTJDG, 12 BHXH => 5 XCVML
3 BHXH, 2 VRPVC => 7 MZWV
121 ORE => 7 VRPVC
7 XCVML => 6 RJRHP
5 BHXH, 4 VRPVC => 5 LTCX""".split("\n")
    assert work_p1(s) == 2210736
test_p1()

def p1():
    print(work_p1(fileinput.input()))
p1()

def test_p2():
    s="""171 ORE => 8 CNZTR
7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL
114 ORE => 4 BHXH
14 VRPVC => 6 BMBT
6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL
6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT
15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW
13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW
5 BMBT => 4 WPTQ
189 ORE => 9 KTJDG
1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP
12 VRPVC, 27 CNZTR => 2 XDBXC
15 KTJDG, 12 BHXH => 5 XCVML
3 BHXH, 2 VRPVC => 7 MZWV
121 ORE => 7 VRPVC
7 XCVML => 6 RJRHP
5 BHXH, 4 VRPVC => 5 LTCX""".split("\n")
    assert work_p2(s) == 460664
    
    s="""2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG
17 NVRVD, 3 JNWZP => 8 VPVL
53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL
22 VJHF, 37 MNCFX => 5 FWMGM
139 ORE => 4 NVRVD
144 ORE => 7 JNWZP
5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC
5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV
145 ORE => 6 MNCFX
1 NVRVD => 8 CXFTF
1 VJHF, 6 MNCFX => 4 RFSQX
176 ORE => 6 VJHF""".split("\n")
    assert work_p2(s) == 5586022
    
    s="""157 ORE => 5 NZVS
165 ORE => 6 DCFZ
44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL
12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ
179 ORE => 7 PSHF
177 ORE => 5 HKGWZ
7 DCFZ, 7 PSHF => 2 XJWVT
165 ORE => 2 GPVTF
3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT""".split("\n")
    assert work_p2(s) == 82892753 

test_p2()

def p2():
    print(work_p2(fileinput.input()))
p2()
