Advent of Code 2015(!) - Tag 19

[nezzcarth]

Hallo

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()

Mich würde interessieren, wie ihr diese Aufgabe gelöst habt (oder lösen würdet). Nachteilig an meiner Variante ist sicher, dass sie nur funktioniert, weil es eh nur einen Pfad gibt. Mich würde auch interessieren, wie eine theoretisch "sauberere" Lösung aussehen könnte.

[BlackJack]

Meine Lösung vo2015:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
import sys
from collections import defaultdict
from itertools import takewhile


def one_molecule_replacements(molecule, replacement, medicine):
    index = 0
    while True:
        try:
            index = medicine.index(molecule, index)
        except ValueError:
            break
        else:
            end_index = index + len(molecule)
            yield '{0}{1}{2}'.format(
                medicine[:index], replacement, medicine[end_index:]
            )
            index = end_index


def all_molecule_replacements(molecule2replacements, medicine):
    for molecule, replacements in molecule2replacements.iteritems():
        for replacement in replacements:
            for result in one_molecule_replacements(
                molecule, replacement, medicine
            ):
                yield result


def parse_lines(lines):
    lines = (s.strip() for s in lines)

    molecule2replacements = defaultdict(list)
    for line in takewhile(bool, lines):
        molecule, arrow, replacement = line.split()
        if arrow != '=>':
            raise ValueError("'=>' expected")
        molecule2replacements[molecule].append(replacement)

    return (molecule2replacements, next(lines))


def calibration(molecule2replacements, medicine):
    calibration_molecules = set(
        all_molecule_replacements(molecule2replacements, medicine)
    )
    return len(calibration_molecules)
    

def search(long2short, medicine):

    def recurse(molecule, count):
        print(count, molecule)
        if molecule == 'e':
            recurse.min = min(recurse.min, count)
            yield count
        elif count < recurse.min:
            for longer, shorter in long2short.iteritems():
                for reduced_molecule in one_molecule_replacements(
                    longer, shorter, molecule
                ):
                    for sub_count in recurse(reduced_molecule, count + 1):
                        yield sub_count

    recurse.min = float('inf')

    return min(recurse(medicine, 0))


def synthesise(molecule2replacements, medicine):
    replacement2molecule = dict()
    for molecule, replacements in molecule2replacements.iteritems():
        for replacement in replacements:
            assert (
                replacement not in replacement2molecule
                and len(replacement) >= len(molecule)
            )
            replacement2molecule[replacement] = molecule

    return search(replacement2molecule, medicine)


def main():
    molecule2replacements, medicine = parse_lines(sys.stdin)
    print(molecule2replacements)
    print(medicine)
    print(calibration(molecule2replacements, medicine))
    print(synthesise(molecule2replacements, medicine))


if __name__ == '__main__':
    main()

[nezzcarth]

Danke für deine Lösung, wie immer sehr lehrreich (die Variante mit .min als Attribut der Funktion hab ich z.B. bisher noch nicht gesehen ).
Wenn ich es richtig verstehe, wird der gesamte Suchraum untersucht und dann das Minimum bestimmt, oder? Weißt du noch, wie lange das bei dir dauerte?

[BlackJack]

@nezzcarth: Nicht der gesamte Suchraum — wenn ein Weg länger als das bisher gefundene Minimum ist, braucht man ja nicht weitersuchen. Stichwort: branch and bound.

[nezzcarth]

@nezzcarth: Nicht der gesamte Suchraum — wenn ein Weg länger als das bisher gefundene Minimum ist, braucht man ja nicht weitersuchen. Stichwort: branch and bound.

Solche Hinweise sind für mich immer sehr hilfreich, danke für das Stichwort Ich habe dein Skript recht lange auf 'nem Raspberry Pi werkeln lassen, aber bisher noch keine Lösung bekommen. Leider konnte ich bisher noch nicht ganz nachvollziehen, weshalb bzw. hab den Algorithmus noch nicht so recht verstanden; kann es damit zusammenhängen, dass der kürzeste Pfad auch gleichzeitig der einzige ist?