Strategiczni Vanishers

15

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.

Rozmiar 9 Vanisher

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

Nie znikanieW załączeniu

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

Mniejsza obudowa Jeszcze mniejsza obudowa

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.

Post Rock Garf Hunter
źródło
(oczywiście musisz być w stanie zdobyć swój własny kod)
user202729
Zamierzasz zakazać kodowania na stałe?
FlipTack
1
@FlipTack Jestem pewien, że to już standardowa luka. Ponadto dobrze napisany program jest prawdopodobnie tak samo dobry jak człowiek.
Post Rock Garf Hunter
1
@ Οurous Myślę, że po prostu usunę trzeci remis.
Post Rock Garf Hunter,

Odpowiedzi:

4

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ść

Anders Kaseorg
źródło
1
Przyzwoite wyjaśnienie, jak to działa, byłoby dobre i wygrałoby moje poparcie. Wydaje się, że próbuje brutalnej siły dodać komórki do prostokątnego obszaru otaczającego polipplet?
Level River St
Nie było dla mnie jasne, dlaczego +w niektórych przypadkach są one odłączone od głównego kształtu, ale wydaje się, że są one konieczne, aby uniknąć tworzenia nowych komórek. Czy te rozwiązania są zatem optymalne?
Level River St
Z ciekawości, po co korzystać z3.Or zamiast wanilii a or b? Czy to czysta wydajność, czy też ma inną funkcjonalność?
caird coinheringaahing
@cairdcoinheringaahing Wygląda na to, że to symboliczne rozwiązanie.
user202729,
1
@AndersKaseorg 1. Nie odpowiedziałeś na mój komentarz pytając, czy twoje rozwiązania są optymalne. Ma to ogromne znaczenie dla każdego, kto rozważa opublikowanie odpowiedzi. 2. Jeśli nie wyjaśnisz, co Z3 robi w twojej odpowiedzi, mogę tylko zgadywać, co robi, ponieważ nie mam czasu na czytanie dokumentacji, stąd moje losowe przypuszczenie o brutalnej sile. 3 Ta odpowiedź zasługuje na pozytywną opinię (w rzeczywistości zasługuje na wiele pozytywnych opinii) na swój kod, ale nie będę głosować, dopóki wyjaśnienie obejmujące powyższe dwa punkty nie zostanie dodane do odpowiedzi.
Level River St