Ten post jest luźno zainspirowany tym postem mathoverflow .

Vanisher to jakikolwiek wzór w Grze życia Conwaya, który całkowicie znika po jednym kroku. Na przykład następujący wzór to Vanisher w rozmiarze 9.

Interesującą właściwością Vanisherów jest to, że każdy wzór można przekształcić w zanikający, po prostu dodając więcej żywych komórek. Na przykład poniższy wzór może być całkowicie zamknięty w znikający wzór

Możemy jednak przekształcić ten wzór w Vanishera, dodając jeszcze mniej żywych komórek.

Twoim zadaniem jest napisanie programu, który wykona to zadanie za nas. Otrzymuje się wzorzec jako wejście i wyszukuje znikający wzorzec zawierający dane wejściowe. Niekoniecznie musisz znaleźć optymalny wzór, tylko wzór, który działa.

Punktacja

Aby zaliczyć swój program, musisz go uruchomić na wszystkich wielpletach wielkości 6 (nie licząc symetrycznie równoważnych przypadków). Oto paczka zawierająca każdy polipplet na osobnej linii. Łącznie powinno ich być 524. Są one reprezentowane jako lista sześciu współrzędnych ( (x,y)krotek), z których każda jest lokalizacją żywej komórki.

Twój wynik będzie całkowitą liczbą nowych komórek dodanych do przekształcenia wszystkich tych poliplinków w Vanishera.

Krawaty

W przypadku powiązań dostarczę listę multipletów rozmiaru 7 dla programów, które mają być uruchomione.

IO

Chciałbym, aby IO było dość elastyczne, możesz przyjmować dane wejściowe i wyjściowe w rozsądnych formatach, jednak prawdopodobnie będziesz chciał pobierać dane wejściowe w tym samym formacie, co dane wejściowe surowe, które podałem. Twój format powinien być spójny na wielu uruchomieniach.

wyczucie czasu

Twój program powinien działać w rozsądnym czasie (około <1 dzień) na rozsądnej maszynie. Nie zamierzam tego zbytnio egzekwować, ale wolałbym, żeby wszyscy grali dobrze.

Python + Z3 , wynik = 3647

Działa w ciągu 14 sekund na moim ośmiordzeniowym systemie.

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)

Pełna wydajność