Vanishers Estratégicos

15

Esta publicación está ligeramente inspirada en esta publicación de mathoverflow .

Un Vanisher es cualquier patrón en el Juego de la vida de Conway que desaparece por completo después de un paso. Por ejemplo, el siguiente patrón es un Vanisher talla 9.

Tamaño 9 Vanisher

Una propiedad interesante de Vanishers es que cualquier patrón puede desaparecer simplemente agregando más células vivas. Por ejemplo, el siguiente patrón puede estar completamente encerrado en un patrón de fuga como este

No desaparecerAdjunto

Sin embargo, podemos convertir ese patrón en un Vanisher agregando aún menos células vivas.

Recinto más pequeño Caja incluso más pequeña

Su tarea es escribir un programa que haga esta tarea por nosotros. Se le da un patrón como entrada para encontrar y generar un patrón de fuga que contiene la entrada. No necesariamente tiene que encontrar el patrón óptimo, solo un patrón que funcione.

Puntuación

Para calificar su programa, deberá ejecutarlo en todos los polyplets de tamaño 6 (no contando dos casos simétricamente equivalentes) Aquí hay un pastebin que contiene cada polyplet en su propia línea. Debería haber 524 de ellos en total. Se representan como una lista de seis coordenadas ( (x,y)tuplas), cada una de las cuales es la ubicación de una célula viva.

Su puntaje será el número total de nuevas celdas agregadas para convertir todos estos polyplets en Vanishers.

Corbatas

En el caso de los vínculos, proporcionaré una lista de los polyplets de tamaño 7 para los programas que se ejecutarán.

IO

Me gustaría que IO sea bastante flexible, puede tomar entradas y salidas en formatos razonables, sin embargo, es probable que desee tomar entradas en el mismo formato que los datos de entrada sin formato que proporcioné. Su formato debe ser coherente en varias ejecuciones.

Sincronización

Su programa debe ejecutarse en un tiempo razonable (aproximadamente <1 día) en una máquina razonable. Realmente no voy a hacer cumplir demasiado esto, pero preferiría que todos jugáramos bien.

Post Rock Garf Hunter
fuente
(por supuesto, debe poder anotar su propio código)
user202729
¿Vas a prohibir el hardcoding?
FlipTack
1
@FlipTack Estoy bastante seguro de que ya es una escapatoria estándar. Además, un programa bien escrito es probablemente tan bueno como un humano de todos modos.
Post Rock Garf Hunter
1
@ Οurous Creo que solo quitaré el tercer desempate.
Post Rock Garf Hunter

Respuestas:

4

Python + Z3 , puntaje = 3647

Se ejecuta en 14 segundos en mi sistema de ocho núcleos.

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)

Salida completa

Anders Kaseorg
fuente
1
Una explicación decente de cómo funciona esto sería buena y ganaría mi voto positivo. Parece que intenta una fuerza bruta de agregar células a un área rectangular que rodea el polyplet?
Level River St el
No estaba claro para mí por qué están +desconectados de la forma principal en algunos casos, pero parece que son necesarios para evitar el desove de nuevas células. ¿Son estas soluciones óptimas?
Level River St el
Por curiosidad, ¿por qué usar en z3.Orlugar de vainilla a or b? ¿Es puramente rendimiento o tiene una funcionalidad diferente?
caird coinheringaahing
@cairdcoinheringaahing Parece que es una solución simbólica.
user202729
1
@AndersKaseorg 1. no has respondido a mi comentario preguntando si tus soluciones son óptimas. Esto es de gran importancia para cualquier persona que esté considerando publicar una respuesta. 2. Si no explica lo que hace Z3 en su respuesta, solo puedo adivinar lo que hace, ya que no tengo tiempo para leer la documentación, de ahí mi suposición aleatoria de la fuerza bruta. 3 Esta respuesta merece un voto positivo (de hecho, merece muchos votos positivos) por su código, pero no votaré hasta que se agregue una explicación que cubra los dos puntos anteriores a la respuesta.
Level River St