Day - 19
Part 1 - Code
# so this problem was simple but also very hard
# first one is trivial, just simulate the evolutions
# the second one is interesting. i started from the medicine molecule and
# did depth first search with running teh simulation backwards
# the program never finished. i kept thinking of ways until i decided to just print the perhaps local optimas that _were_ computed in my dfs
# after a few millis, the optima was found and was printed and i just entered that and it worked...
# given that the dfs provided the answer very quickly, the underlying data must imply the greedy algorithm approach is guarenteed to also find the global minima
# or i am lucky
# i should look into what makes this the case for the sample data
import os
YEAR = 2015
DAY = 19
def get_advent_folder_name(year, day):
base = os.environ["ADVENT_HOME"]
if not base:
raise "ADVENT_HOME folder not set"
return f"{base}/{year}/data/day{day}"
def get_data(name="data.txt"):
data = []
filename = get_advent_folder_name(YEAR, DAY)
path = f"{filename}/{name}"
try:
file = open(path, 'r')
return file
except IOError:
print(f"Could not fetch file {file} ")
return None
def parse_rule(str):
tt = str.split(" => ")
return tt[0], tt[1]
def one_replacement_count(ini, rule):
pattern, transform = rule
results = set()
scan = len(pattern)
for i in range(len(ini)):
window = ini[i:i+scan]
if pattern == window:
pre = ini[:i]
mid = transform
post = ini[i+scan:]
# print(f"pre={pre}, mid={mid}, post={post}")
next = pre + mid + post
#print(rule, i, next)
results.add(next)
return results
def get_all_possible_molecules_after_single_evolution(ini, rules):
molecules = set()
for rule in rules:
res = one_replacement_count(ini, rule)
molecules.update(res)
return molecules
def part_one(ini, rules):
molecules = get_all_possible_molecules_after_single_evolution(ini, rules)
print("Answer to part 1 = ", len(molecules))
cache = dict()
found = set()
dcache = set()
def populate_n_evolutions_in_cache(ini, n, rules):
sample = set([ini])
for i in range(0, n+1):
next_gen = set()
while len(sample) > 0:
to_evolve = sample.pop()
if to_evolve in cache:
continue
cache[to_evolve] = i
molecules = get_all_possible_molecules_after_single_evolution(to_evolve, rules)
next_gen = set(molecules)
sample.update(next_gen)
print("Answer to part 1 = ", len(molecules))
pass
def part_two(start, end, rev_rules, depth = 0):
# print(start, end)
if start == end:
found.add(depth)
print(depth)
return
# reverse rules to make them sutractive instead of additive
# print(rev_rules)
frontier = set()
for rule in rev_rules:
if rule[1] == 'e' and len(start) != len(rule[0]):
continue
# print(rule, start)
if start.find(rule[0]) >= 0:
res = one_replacement_count(start, rule)
# print("res", res)
if res:
frontier.update(res)
for i in sorted(frontier, key=len):
part_two(i, end, rev_rules, depth+1)
def get_elements(str):
eles = set()
for idx, ch in enumerate(str):
if ch.isupper():
if idx + 1 < len(str):
if str[idx+1].islower():
eles.add(str[idx:idx+2])
else:
eles.add(ch)
else:
eles.add(ch)
else:
pass
return eles
def main():
d = [i.strip() for i in get_data("data.txt")]
rules = [parse_rule(i) for i in d[:-2]]
initial = d[-1]
# print(d, rules)
part_one(initial, rules)
print("medicine molecule=", initial)
print("len of it = ", len(initial))
print("rules", rules)
# populate_n_evolutions_in_cache("e", 200, rules)
print("cache populated")
print("\n\n\n\n\n\n")
catalysts = set((i for i,j in rules))
print(catalysts)
elements = set()
for i in (get_elements(j) for i,j in rules):
elements.update(i)
print(elements)
artifacts = set()
recurrent = set()
consumable = set()
for a in elements:
if a in catalysts:
recurrent.add(a)
else:
artifacts.add(a)
for a in catalysts:
if a not in elements:
consumable.add(a)
print("artifacts", artifacts)
print("recurrent", recurrent)
print("consumable", consumable)
# return
rev_rules = [(j,i) for i,j in rules]
rev_rules = sorted(rev_rules, key= lambda x: -1* len(x[0]))
print(rev_rules)
part_two(initial, "e", rev_rules)
print(min(found))
if __name__ == "__main__":
main()