Ce post est vaguement inspiré de ce post mathoverflow .

Un Vanisher est n'importe quel modèle du jeu de la vie de Conway qui disparaît complètement après une étape. Par exemple, le motif suivant est un Vanisher de taille 9.

Une propriété intéressante des Vanishers est que tout motif peut être transformé en disparaissant en ajoutant simplement plus de cellules vivantes. Par exemple, le motif suivant peut être complètement enfermé dans un motif de fuite comme

Cependant, nous pouvons transformer ce modèle en Vanisher en ajoutant encore moins de cellules vivantes.

Votre tâche consiste à écrire un programme qui effectue cette tâche pour nous. On donne à ce motif un motif en entrée, et en sortie un motif disparaissant contenant l'entrée. Vous n'avez pas nécessairement à trouver le modèle optimal juste un modèle qui fonctionne.

Notation

Pour noter votre programme, vous devrez l'exécuter sur tous les polyplets de taille 6 (sans compter les cas symétriquement équivalents). Ici une boîte à pâte contenant chaque polyplet sur sa propre ligne. Il devrait y en avoir 524 au total. Ils sont représentés sous la forme d'une liste de six coordonnées ( (x,y)tuples) correspondant chacune à l'emplacement d'une cellule vivante.

Votre score sera le nombre total de nouvelles cellules ajoutées pour faire de tous ces polyplets des Vanishers.

Cravates

En cas d'égalité, je fournirai une liste des polyplets de taille 7 pour les programmes à exécuter.

IO

J'aimerais que IO soit assez flexible, vous pouvez prendre des entrées et des sorties dans des formats raisonnables, mais vous voudrez probablement prendre des entrées dans le même format que les données d'entrée brutes que j'ai fournies. Votre format doit être cohérent sur plusieurs exécutions.

Horaire

Votre programme doit s'exécuter dans un délai raisonnable (environ <1 jour) sur une machine raisonnable. Je ne vais pas vraiment imposer cela trop, mais je préférerais que nous jouions tous bien.

Python + Z3 , score = 3647

Fonctionne en 14 secondes sur mon système à huit cœurs.

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)

Sortie complète