Vanishers stratégiques

15

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.

Taille 9 Vanisher

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

Non-disparitionEnfermé

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

Boîtier plus petit Boîtier encore plus petit

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.

Post Rock Garf Hunter
la source
(bien sûr, vous devez être capable de marquer votre propre code)
user202729
Allez-vous interdire le codage en dur?
FlipTack
1
@FlipTack Je suis sûr que c'est déjà une échappatoire standard. De plus, un programme bien écrit est probablement aussi bon qu'un humain de toute façon.
Post Rock Garf Hunter
1
@ Οurous, je pense que je vais juste retirer le troisième bris d'égalité.
Post Rock Garf Hunter

Réponses:

4

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

Anders Kaseorg
la source
1
Une explication décente de la façon dont cela fonctionne serait bien et gagnerait mon vote positif. Il semble qu'il essaie une force brute d'ajouter des cellules à une zone rectangulaire entourant le polyplet?
Level River St
Il n'était pas clair pour moi pourquoi il y avait des +déconnexions de la forme principale dans certains cas, mais il semble qu'elles soient nécessaires pour éviter de créer de nouvelles cellules. Ces solutions sont-elles donc optimales?
Level River St
Par curiosité, pourquoi utiliser à la z3.Orplace de la vanille a or b? S'agit-il uniquement de performances ou de fonctionnalités différentes?
caird coinheringaahing
@cairdcoinheringaahing On dirait que c'est une solution symbolique.
user202729
1
@AndersKaseorg 1. vous n'avez pas répondu à mon commentaire demandant si vos solutions sont optimales. Ceci est d'une grande importance pour quiconque envisage de publier une réponse. 2. Si vous n'expliquez pas ce que fait Z3 dans votre réponse, je ne peux que deviner ce qu'il fait, car je n'ai pas le temps de lire la documentation, d'où ma supposition aléatoire de la force brute. 3 Cette réponse mérite un vote positif (en fait, elle mérite de nombreux votes positifs) pour son code, mais je ne voterai pas avant qu'une explication couvrant les deux points ci-dessus ne soit ajoutée à la réponse.
Level River St