Стратегические исчезающие

15

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

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

Размер 9 Vanisher

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

Неисчезающемзакрытый

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

Меньший корпус Даже меньше корпус

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

счет

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

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

связи

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

IO

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

тайминг

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

Пост Рок Гарф Хантер
источник
(конечно, вы должны иметь возможность набрать свой собственный код)
user202729
Собираетесь ли вы запретить жесткое кодирование?
FlipTack
1
@FlipTack Я уверен, что это уже стандартная лазейка. Плюс хорошо написанная программа, вероятно, так же хороша, как и человек.
Сообщение Рок Гарф Хантер
1
@ Я думаю, я просто уберу третий прерыватель связи.
Пост Рок Гарф Хантер

Ответы:

4

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)

Полный вывод

Андерс Касеорг
источник
1
Приличное объяснение того, как это работает, было бы хорошо и выиграло бы мое повышение. Кажется, он пытается грубой силой добавить клетки в прямоугольную область, окружающую полиплет?
Уровень Река St
Мне было непонятно, почему +в некоторых случаях отключаются от основной формы, но кажется, что они необходимы, чтобы избежать появления новых клеток. Являются ли эти решения оптимальными?
Уровень Река St
Из любопытства зачем использовать z3.Orвместо ванили a or b? Это чисто производительность или другой функционал?
января 18
@cairdcoinheringaahing Похоже, это символическое решение.
user202729
1
@AndersKaseorg 1. Вы не ответили на мой комментарий, спрашивая, являются ли ваши решения оптимальными. Это очень важно для всех, кто планирует опубликовать ответ. 2. Если вы не объясните, что Z3 делает в своем ответе, я могу только догадываться, что он делает, так как у меня нет времени читать документацию, отсюда мое случайное предположение о грубой силе. 3 Этот ответ заслуживает положительного ответа (на самом деле он заслуживает многих положительных отзывов) за свой код, но я не буду одобрять, пока к ответу не будет добавлено объяснение, охватывающее два вышеуказанных пункта.
Уровень River St