이 게시물은 이 mathoverflow 게시물에서 느슨하게 영감을 받았습니다 .
소멸자는 Conway의 삶의 게임에서 한 단계 후에 완전히 사라지는 패턴입니다. 예를 들어 다음 패턴은 크기 9 Vanisher입니다.
배니 셔의 흥미로운 특성은 단순히 더 많은 라이브 셀을 추가하여 모든 패턴 을 배니싱 패턴 으로 만들 수 있다는 것입니다. 예를 들어 다음 패턴은 소멸 패턴으로 완전히 둘러싸 일 수 있습니다.
그러나 우리는 더 적은 수의 살아있는 세포를 추가함으로써 그 패턴을 배니 셔로 만들 수 있습니다.
당신의 임무는 우리를 위해이 작업을 수행하는 프로그램을 작성하는 것입니다. 입력으로 패턴이 주어지고 입력을 포함하는 소실 패턴을 출력합니다. 반드시 최적의 패턴을 찾을 필요는 없습니다.
채점
프로그램의 점수를 매기려면 크기가 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)