Penghilang Strategis

15

Posting ini secara longgar terinspirasi oleh pos mathoverflow ini .

Vanisher adalah pola apa pun dalam Permainan Kehidupan Conway yang benar-benar menghilang setelah satu langkah. Misalnya pola berikut adalah ukuran 9 Vanisher.

Ukuran 9 Vanisher

Properti Vanishers yang menarik adalah bahwa pola apa pun dapat dibuat menjadi lenyap dengan hanya menambahkan lebih banyak sel hidup. Sebagai contoh, pola berikut dapat sepenuhnya tertutup ke dalam pola menghilang seperti itu

Non-VanishingTertutup

Namun kita dapat membuat pola itu menjadi Vanisher dengan menambahkan lebih sedikit sel hidup.

Enclosure yang Lebih Kecil Enclosure Lebih Kecil

Tugas Anda adalah menulis program yang melakukan tugas ini untuk kami. Yaitu diberi pola sebagai input find dan output pola menghilang yang berisi input. Anda tidak perlu harus menemukan pola optimal hanya pola yang berfungsi.

Mencetak gol

Untuk menilai program Anda, Anda harus menjalankannya pada semua polyplet ukuran 6 (bukan penghitungan ganda kasus yang secara simetris setara). Ini adalah pastebin yang berisi setiap polyplet pada barisnya masing-masing. Harus ada total 524 di antaranya. Mereka direpresentasikan sebagai daftar enam koordinat ( (x,y)tuple) yang masing-masing menjadi lokasi sel hidup.

Skor Anda akan menjadi jumlah total sel baru yang ditambahkan untuk membuat semua polyplet ini menjadi Penghilang.

Dasi

Dalam hal ikatan saya akan memberikan daftar ukuran 7 polyplet untuk program yang akan dijalankan.

IO

Saya ingin IO menjadi cukup fleksibel Anda dapat mengambil input dan output dalam format yang masuk akal namun Anda mungkin ingin mengambil input dalam format yang sama dengan data input mentah yang saya berikan. Format Anda harus konsisten di berbagai proses.

Pengaturan waktu

Program Anda harus berjalan dalam jumlah waktu yang wajar (kira-kira <1 hari) pada mesin yang masuk akal. Saya tidak akan terlalu memaksakan ini, tapi saya lebih suka jika kita semua bermain bagus.

Posting Rock Garf Hunter
sumber
(tentu saja Anda harus dapat mencetak kode Anda sendiri)
user202729
Apakah Anda akan melarang hardcoding?
FlipTack
1
@ Lipup Saya cukup yakin ini sudah merupakan celah standar. Ditambah program yang ditulis dengan baik mungkin sama baiknya dengan manusia.
Post Rock Garf Hunter
1
@ Οurous Saya pikir saya hanya akan menghapus pemutus dasi ketiga.
Post Rock Garf Hunter

Jawaban:

4

Python + Z3 , skor = 3647

Berjalan dalam 14 detik pada sistem delapan inti saya.

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)

Output penuh

Anders Kaseorg
sumber
1
Penjelasan yang layak tentang bagaimana ini bekerja akan baik dan akan memenangkan upvote saya. Tampaknya ia mencoba kekuatan kasar menambahkan sel ke area persegi panjang di sekitar polyplet?
Level River St
Tidak jelas bagi saya mengapa ada yang +terputus dari bentuk utama dalam beberapa kasus tetapi tampaknya mereka perlu untuk menghindari pemijahan sel-sel baru. Apakah solusi ini optimal?
Level River St
Karena penasaran, mengapa menggunakan z3.Orvanili a or b? Apakah ini murni kinerja, atau apakah ia memiliki fungsi yang berbeda?
caird coinheringaahing
@cairdcoinheringaahing Sepertinya itu solusi simbolis.
user202729
1
@AndersKaseorg 1. Anda belum menjawab komentar saya menanyakan apakah solusi Anda optimal. Ini sangat penting bagi orang lain untuk mempertimbangkan mengirim jawaban. 2. Jika Anda tidak menjelaskan apa yang Z3 lakukan dalam jawaban Anda, saya hanya bisa menebak apa yang dilakukan Z3, karena saya tidak punya waktu untuk membaca dokumentasi, maka tebakan acak saya tentang kekuatan kasar. 3 Jawaban ini layak mendapatkan upvote (sebenarnya layak banyak upvotes) untuk kodenya, tetapi saya tidak akan membenarkan sampai penjelasan yang mencakup dua poin di atas ditambahkan ke jawabannya.
Level River St