133 lines
3.3 KiB
Python
133 lines
3.3 KiB
Python
#!/usr/bin/env python3
|
|
|
|
from collections import defaultdict
|
|
|
|
ORE = "ORE"
|
|
FUEL = "FUEL"
|
|
|
|
class Reactor:
|
|
def __init__(self, reactions, root=ORE):
|
|
self.reactions = reactions
|
|
self.root = root
|
|
self.produced = defaultdict(int)
|
|
self.leftover = defaultdict(int)
|
|
|
|
def produce(self, el, n):
|
|
if el == self.root:
|
|
self.produced[el] += n
|
|
return
|
|
min = self.reactions[el][el]
|
|
if type(min) == float:
|
|
k = (n + min - 1) / min
|
|
else:
|
|
k = (n + min - 1) // min
|
|
for el2, m in self.reactions[el].items():
|
|
if el2 == el:
|
|
continue
|
|
self.get(el2, k * m)
|
|
p = k*min
|
|
self.produced[el] += p
|
|
self.leftover[el] += p - n
|
|
|
|
def get(self, el, n):
|
|
n -= self.leftover[el]
|
|
self.leftover[el] = 0
|
|
if n <= 0:
|
|
self.leftover[el] = -n
|
|
return
|
|
self.produce(el, n)
|
|
|
|
def parse(line):
|
|
el = line.split()[-1]
|
|
line = line.replace(" => ", ', ')
|
|
return el, dict((m.split()[1], int(m.split()[0]))
|
|
for m in line.split(', '))
|
|
|
|
|
|
def ore_per_fuel(reactions, n=1):
|
|
reactor = Reactor(reactions)
|
|
reactor.get(FUEL, n)
|
|
return reactor.produced[ORE]
|
|
|
|
def ore_per_fuel_lim(reactions):
|
|
float_recs = {}
|
|
for el in reactions.keys():
|
|
min = float(reactions[el][el])
|
|
float_recs[el] = dict((el2, n/min) for el2, n in reactions[el].items())
|
|
return ore_per_fuel(float_recs)
|
|
|
|
def search(f, target, best):
|
|
step = best // 100
|
|
i = best
|
|
while step > 0:
|
|
while f(i) <= target:
|
|
i += step
|
|
i -= step
|
|
step //= 10
|
|
return i
|
|
|
|
|
|
def preproc(puzzle_input):
|
|
return dict(map(parse, puzzle_input.split('\n')))
|
|
|
|
def partI(reactions):
|
|
r = ore_per_fuel(reactions)
|
|
return r
|
|
|
|
def partII(reactions):
|
|
ore = 10**12
|
|
best = int(ore // ore_per_fuel_lim(reactions))
|
|
return search(lambda n: ore_per_fuel(reactions, n), ore, best)
|
|
|
|
from main import Tests
|
|
|
|
tests = Tests()
|
|
tests.add(
|
|
"""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""",
|
|
partI=13312)
|
|
|
|
|
|
tests.add(
|
|
"""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""",
|
|
partI=180697)
|
|
|
|
tests.add(
|
|
"""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""",
|
|
partI=2210736)
|
|
|