vom Advent of Code 2015 (!) sind bei mir noch einige Aufgaben übrig geblieben,
u.a. http://adventofcode.com/2015/day/19.
Im Prinzip geht es darum, dass man eine Grammatik mit Ersetzungsregeln bekommt,
die Strings ("Moleküle") erzeugen. In Teil b, den ich wesentlich schwieriger
fand, soll man die minimale Anzahl von Regelanwendungen bestimmen, die notwendig
sind, um einen vorgegeben String zu erzeugen. Ich habe es zuerst mit
wildem Brute Force probiert, allerdings war da auch mit längeren Laufzeiten
nicht mal ansatzweise ein Fortschritt zu erkennen.
Das hier hat allerdings gut funktioniert (was mich ehrlich gesagt wundert):
Code: Alles auswählen
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import re
import fileinput
from copy import copy
from itertools import takewhile
from random import shuffle
PATTERN = re.compile(r'[A-Z][a-z]?')
START = 'e'
def iter_chunks(s, window):
for j, i in enumerate(range(len(s) - window + 1)):
yield (tuple(s[i:i+window]), j)
def iter_shuffled_chunks(s, window):
chunks = list(iter_chunks(s, window))
shuffle(chunks)
for chunk in chunks:
yield chunk
def iter_tokens(s, pattern=PATTERN):
for token in re.findall(pattern, s):
yield token
def main():
rules = list()
lines = (line.strip() for line in fileinput.input())
for line in takewhile(len, lines):
value, key = line.split(' => ')
rules.append((tuple(iter_tokens(key)), (value,)))
molecule = next(lines)
molecule_tokens = list(iter_tokens(molecule))
current = copy(molecule_tokens)
reboots = -1
generations = 0
lowest_length = len(current)
replaced = False
while current != [START]:
shuffle(rules)
if not replaced:
replacements = 0
current = copy(molecule_tokens)
reboots += 1
replaced = False
for rule in rules:
key, value = rule
key_length = len(key)
for chunk, position in iter_shuffled_chunks(current, key_length):
if key == chunk:
current[position:position+key_length] = value
replacements += 1
replaced = True
if len(current) < lowest_length:
lowest_length = len(current)
break
generations += 1
print("Replacements:", replacements)
print("Reboots:", reboots)
print("Generations:", generations)
if __name__ == '__main__':
main()