Advent of Code 2015 Day 19

Author

Nathan Moore

— Day 19: Medicine for Rudolph —

Your puzzle input describes all of the possible replacements and, at the bottom, the medicine molecule for which you need to calibrate the machine. How many distinct molecules can be created after all the different ways you can do one replacement on the medicine molecule?

import re
import copy
from itertools import product

with open('data-2015-19.txt', 'r') as f:
    inp = f.read().splitlines()

mol = inp[-1]
rep = inp[:-2]

Split the molecule into its parts, which means knowing what replacements are possible.

mm = []
p = re.compile(r'[A-Z][a-z]')

for i in range(len(mol)):
    if i == len(mol) - 1:
        break
    elif re.match(r'[A-Z][a-z]', mol[i:i+2]):
        mm.append(mol[i:i+2])
        i += 1
    elif re.match(r'[a-z]', mol[i:i+2]):
        pass # lower case, skip
    else: 
        mm.append(mol[i])

mm
['C',
 'Rn',
 'Ca',
 'Si',
 'Rn',
 'B',
 'Si',
 'Rn',
 'F',
 'Ar',
 'Ti',
 'B',
 'P',
 'Ti',
 'Ti',
 'B',
 'F',
 'Ar',
 'P',
 'B',
 'Ca',
 'Si',
 'Th',
 'Si',
 'Rn',
 'Ti',
 'B',
 'P',
 'B',
 'P',
 'Mg',
 'Ar',
 'Ca',
 'Si',
 'Rn',
 'Ti',
 'Mg',
 'Ar',
 'Ca',
 'Si',
 'Th',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Ar',
 'Rn',
 'Si',
 'Rn',
 'F',
 'Ar',
 'Ti',
 'Ti',
 'B',
 'F',
 'Ar',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'Si',
 'Th',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'Mg',
 'Ar',
 'F',
 'Y',
 'Si',
 'Rn',
 'F',
 'Y',
 'Ca',
 'F',
 'Ar',
 'Si',
 'Th',
 'Ca',
 'Si',
 'Th',
 'P',
 'B',
 'P',
 'Ti',
 'Mg',
 'Ar',
 'Ca',
 'P',
 'Rn',
 'Si',
 'Al',
 'Ar',
 'P',
 'B',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Y',
 'Si',
 'Th',
 'Ca',
 'Rn',
 'F',
 'Ar',
 'Ar',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'P',
 'B',
 'Si',
 'Rn',
 'F',
 'Ar',
 'Mg',
 'Y',
 'Ca',
 'Ca',
 'Ca',
 'Ca',
 'Si',
 'Th',
 'Ca',
 'Ca',
 'Si',
 'Al',
 'Ar',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'P',
 'B',
 'Si',
 'Al',
 'Ar',
 'B',
 'Ca',
 'Ca',
 'Ca',
 'Ca',
 'Si',
 'Th',
 'Ca',
 'P',
 'B',
 'Si',
 'Th',
 'P',
 'B',
 'P',
 'B',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Y',
 'F',
 'Ar',
 'Si',
 'Th',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Ar',
 'B',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Y',
 'F',
 'Ar',
 'Si',
 'Th',
 'Ca',
 'P',
 'B',
 'Si',
 'Th',
 'Ca',
 'Si',
 'Rn',
 'P',
 'Mg',
 'Ar',
 'Rn',
 'F',
 'Ar',
 'P',
 'Ti',
 'B',
 'Ca',
 'P',
 'Rn',
 'F',
 'Ar',
 'Ca',
 'Ca',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'Ca',
 'Ca',
 'Si',
 'Rn',
 'F',
 'Y',
 'F',
 'Ar',
 'F',
 'Ar',
 'B',
 'Ca',
 'Si',
 'Th',
 'F',
 'Ar',
 'Th',
 'Si',
 'Th',
 'Si',
 'Rn',
 'Ti',
 'Rn',
 'P',
 'Mg',
 'Ar',
 'F',
 'Ar',
 'Ca',
 'Si',
 'Th',
 'Ca',
 'P',
 'B',
 'Ca',
 'Si',
 'Rn',
 'B',
 'F',
 'Ar',
 'Ca',
 'Ca',
 'P',
 'Rn',
 'Ca',
 'Ca',
 'P',
 'Mg',
 'Ar',
 'Si',
 'Rn',
 'F',
 'Y',
 'F',
 'Ar',
 'Ca',
 'Si',
 'Th',
 'Rn',
 'P',
 'B',
 'P',
 'Mg',
 'Ar']

Let’s organise the replacements into lists, then we can insert those lists into the big list, and then we can use itertools combinations() or similar to expand those lists and count how many there are.

froms = [x.split(' => ')[0] for x in rep]
tos = [x.split(' => ')[1] for x in rep]

froms = list(set(froms))

present = {x: x in mol for x in froms}
print(present)
print()

reps = {}

for r in rep:
    a,b = r.split(' => ')
    if a in reps.keys():
        reps[a].append(b)
    else: 
        reps[a] = [b]

reps
{'Mg': True, 'N': False, 'Ti': True, 'e': False, 'B': True, 'Ca': True, 'Si': True, 'H': False, 'O': False, 'Th': True, 'P': True, 'Al': True, 'F': True}

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

Now we need to put reps into mm - create a new list of the molecule or its replacements.

mmr = []

for m in mm:
    if m in reps.keys():
        mmr.append(reps[m])
    else: 
        mmr.append(m)

mmr
['C',
 'Rn',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['BP', 'TiTi'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BP', 'TiTi'],
 ['BP', 'TiTi'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaSi'],
 'Rn',
 ['BP', 'TiTi'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BF', 'TiMg'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['BP', 'TiTi'],
 ['BF', 'TiMg'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 'Rn',
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['BP', 'TiTi'],
 ['BP', 'TiTi'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['BF', 'TiMg'],
 'Ar',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BP', 'TiTi'],
 ['BF', 'TiMg'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 'Rn',
 ['CaSi'],
 ['ThF', 'ThRnFAr'],
 'Ar',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['BF', 'TiMg'],
 'Y',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThF', 'ThRnFAr'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaSi'],
 ['ThF', 'ThRnFAr'],
 'Ar',
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaSi'],
 ['ThCa'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BF', 'TiMg'],
 'Ar',
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BP', 'TiTi'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['ThCa'],
 ['CaSi'],
 ['ThCa'],
 ['CaSi'],
 'Rn',
 ['BP', 'TiTi'],
 'Rn',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BF', 'TiMg'],
 'Ar',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 'Rn',
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 'Rn',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BF', 'TiMg'],
 'Ar',
 ['CaSi'],
 'Rn',
 ['CaF', 'PMg', 'SiAl'],
 'Y',
 ['CaF', 'PMg', 'SiAl'],
 'Ar',
 ['CaCa', 'PB', 'PRnFAr', 'SiRnFYFAr', 'SiRnMgAr', 'SiTh'],
 ['CaSi'],
 ['ThCa'],
 'Rn',
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BCa', 'TiB', 'TiRnFAr'],
 ['CaP', 'PTi', 'SiRnFAr'],
 ['BF', 'TiMg'],
 'Ar']

Create a list of possible molecules by flattening the list of options

mmrl = [x for x in mmr if isinstance(x, list)]

num = 0

for m in mmrl:
    num = num + len(m)

num
627

Actually, use mm and then if it’s a list do the replacements from a list - get the unique combinations with set()

new_m = []

for e,m in enumerate(mm):
    if m in reps.keys():
        for r in reps[m]:
            tmp = mm[:e] + [r] + mm[e+1:]
            new_m.append(''.join(tmp))

len(new_m)
len(set(new_m))

# 509
509

— Part Two —

How long will it take to make the medicine? Given the available replacements and the medicine molecule in your puzzle input, what is the fewest number of steps to go from e to the medicine molecule?

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

Which of these replacements are in the molecule and do any of them overlap? It looks like some of them overlap, especially when involved with Ca.

for k,v in reps.items():
    for s in v: 
        if s in mol: 
            print(s + ': ' + str(mol.count(s)))
ThF: 1
BCa: 8
TiB: 5
CaCa: 16
PB: 12
PRnFAr: 1
SiRnFYFAr: 4
SiRnMgAr: 1
SiTh: 16
CaF: 1
PMg: 5
SiAl: 3
BF: 3
TiMg: 2
CaP: 7
PTi: 3
SiRnFAr: 5
CaSi: 24
ThCa: 10
BP: 6
TiTi: 2

If I just go ahead and loop through and try to do some replacements I’m worried that I’m going to end up in some state that is not solvable, i.e. can’t make any more reduction replacements. I’m assuming I need to start at the current molecule and work backwards to get to e. This seems inefficient in computation and in number of replacements but I think I have to try it and see.

# get another version of mol that I can operate backwards on
bk = inp[-1]
rr = 0

# loop through the molecule
for i,s in enumerate(bk[:20]):
    # loop through the possible replacements
    if s == s.lower(): 
        continue
    for k,v in reps.items():
        for s in v:
            # if the replacement is possible, display it 
            if s == bk[i:i+len(s)]:
                print(s)
                print(bk[i:i+len(s)])
                print()
CaSi
CaSi

SiRnFAr
SiRnFAr

TiB
TiB

BP
BP

Let’s try going through and restarting at the start each time we find a replacement. Other strategies: sort by longest replacements, and use those first.

# get another version of mol that I can operate backwards on
bk = inp[-1]
# print(bk)
rr = 0
found = False

# loop through the molecule
for i,s in enumerate(bk):
    # replacement not possible on the second letter of element
    if s == s.lower(): 
        continue
    # loop through the possible replacements
    for k,v in reps.items():
        for z in v:
            # if the replacement is possible, display it 
            if z == bk[i:i+len(z)]:
                # print()
                # print(z + ': ' + k)
                bk = bk[:i] + k + bk[i+len(z):]
                # print(bk)
                found = True
                continue

Actually,

https://www.reddit.com/r/adventofcode/comments/3xflz8/day_19_solutions/

NumSymbols - #Rn - #Ar - 2 * #Y - 1

len(mm)
mm.count('Rn')
mm.count('Ar')
mm.count('Y')

274 - 31 - 31 - 2*8 - 1

# 195
195