Diberikan bilangan bulat positif N, tentukan pola awal pada kisi-kisi N x N yang menghasilkan urutan non-berulang terpanjang di bawah Game of Life-rules, dan berakhir dengan pola tetap (siklus panjang 1), dimainkan pada torus.
Tujuannya bukan program terpendek, tetapi tercepat.
Karena dunia terbatas, Anda pada akhirnya akan berakhir dalam satu lingkaran, sehingga mengulangi keadaan yang sudah dikunjungi. Jika loop ini memiliki periode 1, maka pola awal adalah kandidat yang valid.
Output: Pola awal dan jumlah total status unik dalam urutan (termasuk pola awal).
Sekarang, 1x1-torus adalah spesial, karena sebuah sel dapat dianggap bertetangga dengan dirinya sendiri atau tidak, tetapi dalam praktiknya, tidak ada masalah, sel hidup tunggal akan mati (karena kepadatan atau kesepian). Jadi, input 1 menghasilkan urutan panjang 2, urutannya adalah satu sel yang hidup, lalu mati selamanya.
Motivasi untuk pertanyaan ini adalah yang merupakan analog dari fungsi berang-berang yang sibuk, tetapi jelas kurang kompleks, karena kita memiliki ingatan. Ini juga akan menjadi urutan yang bagus untuk disertakan pada OEIS.
Untuk N = 3, panjang urutannya adalah 3, pola apa pun di sisi kiri mencapai kotak hitam 3x3, dan kemudian mati. (Semua pola yang merupakan bagian dari 1 siklus dihapus).
sumber
Jawaban:
C ++ hingga N = 6
Teknik ini berpusat di sekitar fungsi keadaan cepat berikutnya. Setiap papan direpresentasikan sebagai bitmask N ^ 2 bit, dan trik bit-twiddly digunakan untuk menghitung status berikutnya untuk semua sel sekaligus.
next
mengkompilasi hingga sekitar200100 instruksi perakitan untuk N <= 8. Kemudian kita lakukan standar coba-semua-keadaan-sampai-mereka-ulangi dan pilih yang terpanjang.Memakan waktu beberapa detik hingga 5x5, beberapa jam untuk 6x6.
sumber
next
dengan menghitung daripada menyortir.#define H(x,y){x^=y;y&=(x^y);}
dan kemudian sesuatu sepertiH(n1,n2);H(n3,n4);H(n5,n6);H(n7,n8);H(n1,n3);H(n5,n7);H(n2,n4);H(n6,n8);H(n1,n5);H(n3,n7);H(n2,n6);H(n2,n3);H(n2,n5); return n2 & (b | n1) & ~(n3|n4|n5|n6|n7|n8) & ALL;
Saya melihat kemungkinan pendekatan solusi berikut:
Next(board)
benda mati dan bahwa kita dapat dengan mudah membalik fungsi, kita melihat bahwa ia memiliki beberapa manfaat, meskipun tidak sebanyak yang saya harapkan semula.Prev2
,.Saya tidak berpikir bahwa optimasi mikro akan membiarkan saya mengejar kode Keith, tetapi demi kepentingan saya akan memposting apa yang saya miliki. Ini memecahkan N = 5 dalam waktu sekitar satu menit pada mesin 2GHz menggunakan Mono 2.4 atau .Net (tanpa PLINQ) dan dalam sekitar 20 detik menggunakan PLINQ; N = 6 berjalan selama berjam-jam.
sumber
Faktor
Beberapa statistik waktu:
Dan pengujian 5 crash REPL. Hmph. Bagian yang paling tidak efisien dari program ini mungkin adalah urutan fungsi permainan. Saya mungkin bisa membuatnya lebih baik nanti.
sumber