전략적 소멸자 게임에서 한 단계 후에 완전히 사라지는

이 게시물은 이 mathoverflow 게시물에서 느슨하게 영감을 받았습니다 .

소멸자는 Conway의 삶의 게임에서 한 단계 후에 완전히 사라지는 패턴입니다. 예를 들어 다음 패턴은 크기 9 Vanisher입니다.

사이즈 9 배니 셔

배니 셔의 흥미로운 특성은 단순히 더 많은 라이브 셀을 추가하여 모든 패턴 을 배니싱 패턴 으로 만들 수 있다는 것입니다. 예를 들어 다음 패턴은 소멸 패턴으로 완전히 둘러싸 일 수 있습니다.

사라지지 않는에워싸는

그러나 우리는 더 적은 수의 살아있는 세포를 추가함으로써 그 패턴을 배니 셔로 만들 수 있습니다.

작은 인클로저 더 작은 인클로저

당신의 임무는 우리를 위해이 작업을 수행하는 프로그램을 작성하는 것입니다. 입력으로 패턴이 주어지고 입력을 포함하는 소실 패턴을 출력합니다. 반드시 최적의 패턴을 찾을 필요는 없습니다.

채점

프로그램의 점수를 매기려면 크기가 6 인 polyplet 모두에서 실행해야합니다 (대칭 적으로 동등한 경우는 두 번 세지 않음). 다음 은 각각의 polyplet을 자체 라인에 포함하는 pastebin입니다. 총 524 개가 있어야합니다. 이들은 (x,y)각각 라이브 셀의 위치 인 6 개의 좌표 ( 튜플) 의 목록으로 표시됩니다 .

점수는 이러한 모든 폴리 플렛을 배니 셔로 만들기 위해 추가 된 총 새 셀 수입니다.

의

관계의 경우 프로그램을 실행할 크기 7 폴리 폴릿 목록을 제공합니다.

IO

IO를 매우 유연하게 사용하여 합리적인 형식으로 입력 및 출력 할 수 있지만 제공 한 원시 입력 데이터와 동일한 형식으로 입력을 원할 것입니다. 여러 실행에서 형식이 일관되어야합니다.

타이밍

프로그램은 적절한 시스템에서 적절한 시간 (약 <1 일) 동안 실행되어야합니다. 나는 정말로 이것을 너무 많이 시행하지는 않을 것입니다. 그러나 우리 모두가 좋은 경기를한다면 좋겠습니다.

답변

파이썬 + Z3 , 점수 = 3647

8 코어 시스템에서 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)

전체 출력

답변