CCC 2016: Lingkaran Kehidupan

8

Sebelum saya mulai, tantangan ini bukan milik saya awalnya

Kredit ke The University of Waterloo. Ini berasal dari Kompetisi Komputasi Kanada 2016, Masalah Senior 5. Ini adalah tautan yang dapat diklik untuk kontes PDF:

http://cemc.uwaterloo.ca/contests/computing/2016/stage%201/seniorEn.pdf

Berikut ini tautan ke situs tersebut:

http://cemc.uwaterloo.ca/contests/past_contests.html

Tantangan

Diberikan array pembungkus dari dua nilai konstan, tentukan konfigurasi setelah nevolusi untuk input integer positif n. Kedua nilai ini mewakili sel hidup dan sel mati. Evolusi bekerja seperti ini:

Evolusi!

Setelah setiap iterasi, sel hidup jika memiliki tepat satu tetangga yang hidup di iterasi sebelumnya. Kurang dan itu mati karena kesepian; lagi dan mati karena kepadatan. Lingkungannya eksklusif: yaitu setiap sel memiliki dua tetangga, bukan tiga.

Sebagai contoh, mari kita lihat bagaimana 1001011010berevolusi, di mana 1sel hidup dan 0sel mati.

(0) 1 0 0 1 0 1 1 0 1 0 (1)
    *   $         %

Sel di *memiliki sel mati di kedua sisi sehingga mati kesepian.
Sel di $memiliki sel hidup di satu sisi dan sel mati di sisi lain. Menjadi hidup.
Cel di %memiliki sel hidup di kedua sisi sehingga tetap mati karena kepadatan.

Kriteria Menang

Kode terpendek menang.

I / O

Input akan menjadi daftar status sel sebagai dua nilai yang konsisten, dan integer yang mewakili jumlah input, dalam beberapa format yang masuk akal. Keluaran adalah daftar status sel setelah jumlah iterasi yang ditentukan.

Uji Kasus

start, iterations -> end
1001011010, 1000 -> 1100001100
100101011010000, 100 -> 000110101001010
0000000101011000010000010010001111110100110100000100011111111100111101011010100010110000100111111010, 1000 -> 1001111111100010010100000100100100111010010110001011001101010111011011011100110110100000100011011001

Test Case Case
uji ini membekukan hastebin dan melebihi batas ukuran pada pastebin

code-golf cellular-automata HyperNeutrino
sumber
2
Saya tidak berpikir ini harus ditandai sebagai kode golf jika byte hanya sebatas tiebreak. Saya juga tidak yakin apakah itu tiebreak yang bagus, karena kontes akan berubah menjadi kompetisi golf kode jika Anda dapat dengan mudah mengirimkan jawaban ke bahasa yang lebih ringkas untuk menang.
Dennis
@ Dennis Benar, saya akan menghapus tag. Apa yang Anda sarankan untuk tiebreak? pengiriman paling awal adalah salah satu ide saya.
HyperNeutrino
2
Saya memberikan suara sebagai tidak jelas untuk saat ini karena tidak diketahui apa yang dimaksud dengan kompleksitas ketika ada beberapa parameter.
feersum
1
@feersum, ada sedikit permainan dalam algoritma tercepat . Algoritma naif mengambil di Theta(nt)mana npanjang array dan tjumlah evolusi; algoritma yang lebih cepat dibutuhkan Theta(n lg t).
Peter Taylor
1
@ Notts90 Saya harap hasil edit terbaru saya lebih menjelaskan.
HyperNeutrino

Jawaban:

6

APL (Dyalog) , 14 byte

Anjuran untuk memulai status sebagai daftar Boolean dan kemudian untuk jumlah iterasi

(1∘⌽≠¯1∘⌽)⍣⎕⊢⎕

Cobalah online!

⎕ numeric prompt (untuk daftar negara mulai Boolean)

⊢ untuk itu, terapkan

(... )⍣⎕ fungsi tersembunyi berikut, waktu numerik-prompt

 ¯1∘⌽ argumen diputar satu langkah ke kanan

 ≠ berbeda dari (XOR)

 1∘⌽ argumen diputar satu langkah ke kiri

Adm
sumber
3

Jelly , 7 byte

ṙ2^ṙ-µ¡

Cobalah online!

Extra Test Case (catatan kaki untuk pemformatan) .

Penjelasan

ṙ2^ṙ-µ¡
     µ¡  - repeat a number of times equal to input 2:
ṙ2         - previous iteration rotated 2 to the left
  ^        - XOR-ed with:
           - (implicit) previous iteration
   ṙ-      - rotate back (by negative 1 to the left)
fireflame241
sumber
1

05AB1E , 6 byte

FDÀÀ^Á

Cobalah online!

Penjelasan

F        # input_1 times do
 D       # duplicate last iteration (input_2 the first iteration)
  ÀÀ     # rotate left twice
    ^    # XOR
     Á   # rotate right
Emigna
sumber