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.
źródło
Odpowiedzi:
Python + Z3 , wynik = 3647
Działa w ciągu 14 sekund na moim ośmiordzeniowym systemie.
Pełna wydajność
źródło
+
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?z3.Or
zamiast waniliia or b
? Czy to czysta wydajność, czy też ma inną funkcjonalność?