Этот пост слабо вдохновлен этим постом mathoverflow .

Исчезновение - это любой паттерн в игре жизни Конвея, который полностью исчезает после одного шага. Например, следующий шаблон - Vanisher размера 9.

Интересным свойством Vanishers является то, что любой шаблон можно превратить в исчезающий, просто добавив больше живых клеток. Например, следующий шаблон может быть полностью заключен в исчезающий шаблон, например

Однако мы можем превратить этот паттерн в Vanisher, добавив еще меньше живых клеток.

Ваша задача - написать программу, которая сделает это за нас. Это задается шаблоном в качестве входных данных для поиска и вывода исчезающего шаблона, содержащего входные данные. Вам не обязательно находить оптимальный шаблон, просто шаблон, который работает.

счет

Чтобы оценить вашу программу, вам нужно будет запустить ее на всех полиплетах размера 6 (не считая дважды симметрично эквивалентных случаев). Вот пастбин, содержащий каждый полиплет в отдельной строке. Всего их должно быть 524. Они представлены в виде списка из шести координат ( (x,y)кортежей), каждая из которых является местоположением живой ячейки.

Ваша оценка будет равна общему количеству добавленных ячеек, чтобы превратить все эти полиплеты в Vanishers.

связи

В случае связей я предоставлю список полиплетов размера 7 для программ, которые будут запущены.

IO

Я хотел бы, чтобы IO был достаточно гибким, вы могли бы вводить и выводить данные в разумных форматах, однако вы, вероятно, захотите получать ввод в том же формате, что и исходные входные данные, которые я предоставил. Ваш формат должен быть одинаковым для нескольких прогонов.

тайминг

Ваша программа должна запускаться в течение разумного периода времени (около 1 дня) на подходящей машине. Я не собираюсь навязывать это слишком сильно, но я бы предпочел, чтобы мы все хорошо играли.

Python + Z3 , оценка = 3647

Работает за 14 секунд на моей восьмиядерной системе.

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)

Полный вывод