Strategische Vanishers

15

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.

Größe 9 Vanisher

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

Nicht verschwindendBeigefügt

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

Kleineres Gehäuse Noch kleineres Gehäuse

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.

Weizen-Assistent
quelle
(Natürlich müssen Sie in der Lage sein, Ihren eigenen Code zu erzielen)
user202729
Wirst du Hardcoding verbieten?
FlipTack
1
@FlipTack Ich bin mir ziemlich sicher, dass es bereits eine Standardlücke ist. Außerdem ist ein gut geschriebenes Programm wahrscheinlich sowieso genauso gut wie ein Mensch.
Weizen-Assistent
1
@ Οurous Ich denke, ich werde gerade den dritten Krawattenbrecher entfernen.
Weizen-Assistent

Antworten:

4

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

Anders Kaseorg
quelle
1
Eine anständige Erklärung, wie das funktioniert, wäre gut und würde meine Zustimmung gewinnen. Es scheint, als würde es mit einer rohen Kraft versucht, Zellen zu einem rechteckigen Bereich um das Polyplet hinzuzufügen.
Level River St
Es war mir unklar, warum es +in einigen Fällen keine Verbindung zur Hauptform gibt, aber es scheint, dass sie notwendig sind, um das Laichen neuer Zellen zu vermeiden. Sind diese Lösungen daher optimal?
Level River St
Warum aus Neugier z3.Oranstelle von Vanille verwenden a or b? Ist es reine Leistung oder hat es eine andere Funktionalität?
Caird Coinheringaahing
@cairdcoinheringaahing Sieht so aus, als wäre das eine symbolische Lösung.
user202729
1
@AndersKaseorg 1. Sie haben meinen Kommentar nicht beantwortet und gefragt, ob Ihre Lösungen optimal sind. Dies ist von großer Bedeutung für alle anderen, die eine Antwort veröffentlichen möchten. 2. Wenn Sie nicht erklären, was Z3 in Ihrer Antwort tut, kann ich nur raten, was es tut, da ich keine Zeit habe, die Dokumentation zu lesen, daher meine zufällige Vermutung der rohen Gewalt. 3 Diese Antwort verdient eine Aufwertung (in der Tat verdient sie viele Aufwertungen) für ihren Code, aber ich werde keine Aufwertung vornehmen, bis der Antwort eine Erklärung hinzugefügt wird, die die obigen zwei Punkte abdeckt.
Level River St