-
Notifications
You must be signed in to change notification settings - Fork 0
/
14.py
76 lines (63 loc) · 2.4 KB
/
14.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import math
import os
inputFile = open(os.path.dirname(__file__) + '/input.txt', 'r')
lines = inputFile.readlines()
inputFile.close()
def solve():
reactions = {}
amounts = {}
# Preprocess into dict for faster location of product
for line in lines:
left, right = line[:-1].split(' => ')
amount, product = right.split(' ')
amounts[product] = int(amount)
reactions[product] = []
for ingredient in left.split(', '):
amount, reactant = ingredient.split(' ')
reactions[product].append((int(amount), reactant))
fuel = ores = 1
change = 1000000
# Using binary search for part2 to find most fuel produced under 1 trillion ores
while change > 1 or ores > 1000000000000:
ores = 0
needed = {'FUEL': fuel}
extra = {}
while len(needed):
# Pick a product from dict
product = list(needed)[0]
# Check if we have extra product
if product in extra:
if extra[product] > needed[product]:
extra[product] -= needed[product]
del needed[product]
continue
else:
needed[product] -= extra[product]
del extra[product]
# Find number of times to make reaction
times = math.ceil(needed[product] / amounts[product])
# Store extra product from the reaction
extra_product = times * amounts[product] - needed[product]
if extra_product > 0:
if product in extra:
extra[product] += times * amounts[product] - needed[product]
else:
extra[product] = times * amounts[product] - needed[product]
# Add product's reactants to needed dict
for amount, reactant in reactions[product]:
if reactant == 'ORE':
ores += amount * times
elif reactant in needed:
needed[reactant] += amount * times
else:
needed[reactant] = amount * times
del needed[product]
if fuel == 1:
print(f'Part one: {ores}')
if ores > 1000000000000:
change = 1 if change < 4 else change // 2
fuel -= change
else:
fuel += change
print(f'Part two: {fuel - 1}')
solve()