Day 18: Medicine for Rudolph

In [74]:

    

import csv

target = ''
reactions = []
with open('inputs/input18.txt', 'rt') as f_input:
    csv_reader = csv.reader(f_input, delimiter=' ')
    for line in csv_reader:
        if len(line) == 3:
            reactions.append((line[0], line[2]))
        elif len(line) == 1:
            target = line[0]


    

In [75]:

    

print(reactions)


    

    




[('Al', 'ThF'), ('Al', 'ThRnFAr'), ('B', 'BCa'), ('B', 'TiB'), ('B', 'TiRnFAr'), ('Ca', 'CaCa'), ('Ca', 'PB'), ('Ca', 'PRnFAr'), ('Ca', 'SiRnFYFAr'), ('Ca', 'SiRnMgAr'), ('Ca', 'SiTh'), ('F', 'CaF'), ('F', 'PMg'), ('F', 'SiAl'), ('H', 'CRnAlAr'), ('H', 'CRnFYFYFAr'), ('H', 'CRnFYMgAr'), ('H', 'CRnMgYFAr'), ('H', 'HCa'), ('H', 'NRnFYFAr'), ('H', 'NRnMgAr'), ('H', 'NTh'), ('H', 'OB'), ('H', 'ORnFAr'), ('Mg', 'BF'), ('Mg', 'TiMg'), ('N', 'CRnFAr'), ('N', 'HSi'), ('O', 'CRnFYFAr'), ('O', 'CRnMgAr'), ('O', 'HP'), ('O', 'NRnFAr'), ('O', 'OTi'), ('P', 'CaP'), ('P', 'PTi'), ('P', 'SiRnFAr'), ('Si', 'CaSi'), ('Th', 'ThCa'), ('Ti', 'BP'), ('Ti', 'TiTi'), ('e', 'HF'), ('e', 'NAl'), ('e', 'OMg')]

In [76]:

    

print(target)


    

    




CRnCaCaCaSiRnBPTiMgArSiRnSiRnMgArSiRnCaFArTiTiBSiThFYCaFArCaCaSiThCaPBSiThSiThCaCaPTiRnPBSiThRnFArArCaCaSiThCaSiThSiRnMgArCaPTiBPRnFArSiThCaSiRnFArBCaSiRnCaPRnFArPMgYCaFArCaPTiTiTiBPBSiThCaPTiBPBSiRnFArBPBSiRnCaFArBPRnSiRnFArRnSiRnBFArCaFArCaCaCaSiThSiThCaCaPBPTiTiRnFArCaPTiBSiAlArPBCaCaCaCaCaSiRnMgArCaSiThFArThCaSiThCaSiRnCaFYCaSiRnFYFArFArCaSiRnFYFArCaSiRnBPMgArSiThPRnFArCaSiRnFArTiRnSiRnFYFArCaSiRnBFArCaSiRnTiMgArSiThCaSiThCaFArPRnFArSiRnFArTiTiTiTiBCaCaSiRnCaCaFYFArSiThCaPTiBPTiBCaSiThSiRnMgArCaF

In [66]:

    

import re

def count_molecules(target, reactions):
    visited = set()
    count = 0
    while reactions:
        r = reactions.pop()
        le = len(r[0])
        if le == 1:
            m = re.finditer('({0}[A-Z]|{0}$)'.format(r[0]), target)
        elif le == 2:
            m = re.finditer(r[0], target)
        for overlap in m:
            i = overlap.span()[0]
            outcome = hash(target[:i] + r[1] + target[i + le:])
            if outcome not in visited:
                visited.add(outcome)
                count += 1
    return count


    

In [67]:

    

target_test = 'HOHOHO'
reactions_test = [('H', 'HO'), ('H', 'OH'), ('O', 'HH')]
assert(count_molecules(target_test, reactions_test) == 7)


    

In [68]:

    

count_molecules(target, reactions)


    

    
Out[68]:





535

In [114]:

    

def replace(rpl, motif, molecule):
    le = len(motif)
    m = re.finditer(motif, molecule)
    for overlap in m:
        i = overlap.span()[0]
        yield molecule[:i] + rpl + molecule[i + le:]
        
def all_ancestors(molecule, reactions):
    for r in sorted(reactions, key=lambda x: x[1], reverse=True):
        for ancestor in replace(r[0], r[1], molecule):
            yield ancestor
            
def min_path(molecule, reactions):
    min_length = 30
    queue = [(molecule, 0)]
    visited = set()
    while queue:
        mol, path_len = queue.pop()
        if mol == 'e':
            min_length = min(min_length, path_len)
            print(min_length)
        else:
            if path_len < min_length:
                for ancestor in all_ancestors(mol, reactions):
                    if ('e' not in ancestor) or (ancestor == 'e'):
                        ancestor_hash = hash(ancestor) 
                        if ancestor_hash not in visited:
                            queue.append((ancestor, path_len + 1))
                            visited.add(ancestor_hash)
    return min_length


    

In [111]:

    

%%time
def test():
    reactions_test = [('H', 'HO'), ('H', 'OH'), ('O', 'HH'), ('e', 'H'), ('e', 'O')]
    assert(min_path('HOH', reactions_test) == 3)
    assert(min_path('HOHOHO', reactions_test) == 6)
test()


    

    




CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3.83 ms

In [112]:

    

%%time
reactions_test = [('H', 'HO'), ('H', 'OH'), ('O', 'HH'), ('e', 'H'), ('e', 'O')]
print(min_path('HOHOHOHOHOHHOHOHHOH', reactions_test))


    

    




19
CPU times: user 184 ms, sys: 4 ms, total: 188 ms
Wall time: 190 ms

In [116]:

    

min_path(target, reactions)


    

In [ ]: