Dieser Beitrag ist locker von diesem Mathoverflow-Beitrag inspiriert .

Ein Vanisher ist ein beliebiges Muster in Conways Spiel des Lebens, das nach einem Schritt vollständig verschwindet. Das folgende Muster ist beispielsweise ein Vanisher der Größe 9.

Eine interessante Eigenschaft von Vanishers ist, dass jedes Muster in ein verschwindendes umgewandelt werden kann, indem einfach mehr lebende Zellen hinzugefügt werden. Zum Beispiel kann das folgende Muster wie folgt vollständig in ein verschwindendes Muster eingeschlossen werden

Wir können dieses Muster jedoch zu einem Vanisher machen, indem wir noch weniger lebende Zellen hinzufügen.

Ihre Aufgabe ist es, ein Programm zu schreiben, das diese Aufgabe für uns erledigt. Diesem wird ein Muster als Eingabe gegeben, und es wird ein verschwindendes Muster ausgegeben, das die Eingabe enthält. Sie müssen nicht unbedingt das optimale Muster finden, sondern nur ein Muster, das funktioniert.

Wertung

Um ein Ergebnis für Ihr Programm zu erzielen, müssen Sie es auf allen Polyplets der Größe 6 ausführen (wobei symmetrisch äquivalente Fälle nicht doppelt gezählt werden). Hier ist ein Pastebin, das jedes Polyplet in einer eigenen Zeile enthält. Es sollten insgesamt 524 sein. Sie werden als Liste von sechs Koordinaten ( (x,y)Tupeln) dargestellt, die jeweils den Standort einer lebenden Zelle darstellen.

Ihre Punktzahl ist die Gesamtzahl der neuen Zellen, die hinzugefügt wurden, um alle diese Polyplets in Vanishers zu verwandeln.

Krawatten

Im Falle von Bindungen werde ich eine Liste der Polyplets der Größe 7 für die Programme bereitstellen, auf denen ausgeführt werden soll.

IO

Ich würde mir wünschen, dass IO ziemlich flexibel ist. Sie können Eingaben und Ausgaben in vernünftigen Formaten vornehmen, aber Sie werden wahrscheinlich Eingaben in demselben Format vornehmen wollen wie die von mir bereitgestellten Rohdaten. Ihr Format sollte über mehrere Läufe hinweg konsistent sein.

Zeitliche Koordinierung

Ihr Programm sollte in angemessener Zeit (ca. <1 Tag) auf einem angemessenen Computer ausgeführt werden. Ich werde das nicht wirklich durchsetzen, aber ich würde es vorziehen, wenn wir alle nett spielen würden.

Python + Z3 , Score = 3647

Läuft in 14 Sekunden auf meinem achtkernigen System.

from __future__ import print_function

import ast
import multiprocessing
import sys
import z3

def solve(line):
    line = ast.literal_eval(line)
    x0, x1 = min(x for x, y in line) - 2, max(x for x, y in line) + 3
    y0, y1 = min(y for x, y in line) - 2, max(y for x, y in line) + 3
    a = {(x, y): z3.Bool('a_{}_{}'.format(x, y)) for x in range(x0, x1) for y in range(y0, y1)}
    o = z3.Optimize()
    for x in range(x0 - 1, x1 + 1):
        for y in range(y0 - 1, y1 + 1):
            s = z3.Sum([
                z3.If(a[i, j], 1 + ((i, j) != (x, y)), 0)
                for i in (x - 1, x, x + 1) for j in (y - 1, y, y + 1) if (i, j) in a
            ])
            o.add(z3.Or(s < 5, s > 7))
    o.add(*(a[i, j] for i, j in line))
    o.minimize(z3.Sum([z3.If(b, 1, 0) for b in a.values()]))
    assert o.check() == z3.sat
    m = o.model()
    return line, {k for k in a if z3.is_true(m[a[k]])}

total = 0
for line, cells in multiprocessing.Pool().map(solve, sys.stdin):
    added = len(cells) - len(line)
    print(line, added)
    x0, x1 = min(x for x, y in cells), max(x for x, y in cells) + 1
    y0, y1 = min(y for x, y in cells), max(y for x, y in cells) + 1
    for y in range(y0, y1):
        print(''.join('#' if (x, y) in line else '+' if (x, y) in cells else ' ' for x in range(x0, x1)))
    total += added
print('Total:', total)

Volle Leistung