Tahap terakhir dari kontaminasi

10

Ada virus di dalam penerima 5x5. Seperti yang kita ketahui bagaimana ia menyebarkan kontaminasi, misi Anda adalah menghasilkan tahap terakhir kontaminasi.

Penerima

Ini akan direpresentasikan sebagai array dua dimensi 5x5:

0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1

Dimana 1artinya posisi di mana virus sudah terkontaminasi, dan 0posisi tidak terkontaminasi.

Bagaimana virus menyebar

  1. Posisi yang terkontaminasi tidak dapat dibersihkan.
  2. Posisi bersih akan terkontaminasi pada tahap berikutnya hanya jika setidaknya dua posisi yang berdekatan (sel utara, timur, selatan dan barat) terkontaminasi.
  3. Tahap terakhir dari kontaminasi terjadi ketika tidak ada lagi sel yang bersih yang dapat terkontaminasi.

Sampel

Menggunakan sebagai tahap 1 dari kontaminasi penerima yang dijelaskan di atas, tahap 2 akan:

0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1

Tahap 3 dari kontaminasi adalah:

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Tahap 4 dari kontaminasi adalah:

0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Dan tahap 5 (dalam contoh ini, yang terakhir) adalah:

0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Tantangan

Diberikan sebagai input satu tahap kontaminasi, Anda harus menampilkan tahap terakhir kontaminasi.

Anda diperbolehkan menulis program atau fungsi lengkap. Anda dapat mengambil input sebagai array / daftar, sebagai angka yang dipisahkan, atau bahkan sebagai string. Pilih cara terbaik yang sesuai dengan bahasa Anda.

Jawaban terpendek dalam byte menang!

Kasus uji lain

Input:
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
1 0 0 0 1

Output:
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1

Input:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
1 0 0 1 0
0 0 1 0 1
0 0 0 0 0
1 0 0 0 0
0 0 1 0 0

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

Output:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
dihapus
sumber
1
Bagaimana bisa 1 0 1terjadi pada output? Bukankah pusat nol bersebelahan dengan dua 1s?
Lynn
@ Lynn .. Saya telah memperbarui;) ... maaf untuk itu
dihapus
1
Bisakah Anda menambahkan 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0sebagai test case?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ. Ditambahkan terima kasih
dihapus
2
Semua test case sejauh ini hanya memiliki baris dan kolom penuh yang kosong. Saya sarankan 0 1 0 0 0 \ 0 0 0 0 1 \ 0 0 1 0 0 \ 1 0 0 0 0 \ 0 0 0 1 0, yang tetap tidak berubah.
xnor

Jawaban:

12

Karena ini pada dasarnya berbicara tentang otomat seluler saya berikan kepada Anda ..

Aturan Quicklife Golly , 10 byte

01234/234V

Masukkan aturan, rekatkan kisi ke dalam Golly, jalankan pola. Pola yang dihasilkan adalah output.

Penjelasan:

01234 Survive on any number of neighbors
     /234 Born on >2 neighbors
         V Only directly adjacent neighbors count

Atau jika Anda bersikeras aturan RuleLoader penuh, 89 byte:

@RULE X
@TABLE
n_states:2
neighborhood:vonNeumann
symmetries:permute
011001
011101
011111

Rulename adalah X, langkah yang sama seperti sebelumnya.

CalculatorFeline
sumber
3
Apakah ini bahasa pemrograman ?
Lynn
1
Golly Quicklife dapat mensimulasikan B3/S23yang dapat melakukan apa saja! ... Tetapi memang memiliki format input yang ketat (seperti seluruh program dimasukkan dalam input (bagaimana lagi yang akan Anda lakukan?)). TAPI MENGAPA MERENUNGKAN KEGAGALAN ??
CalculatorFeline
Nah, kita hanya perlu menunggu pertanyaan yang bermuara pada perilaku jangka panjang dari sebuah automaton seluler!
CalculatorFeline
1
Saya memiliki keraguan tentang validitas. Jika Golly hanya menampilkan hasil akhir, itu akan baik-baik saja, tetapi juga menampilkan hasil antara (kecuali saya salah)
lirtosiast
1
@CatsAreFluffy Kalau begitu, saya punya upvote saya.
lirtosiast
5

Python 2, 97 byte

s=' '*6+input()
exec"s=s[1:]+('1'+s)[sum(s[i]<'1'for i in[-6,-1,1,6])>2or'/'>s];"*980
print s[6:]

Cobalah online . Input diambil sebagai string yang dikutip dengan setiap baris dibatasi oleh baris baru. Tidak 980optimal dan dapat diganti dengan kelipatan lebih rendah dari 35. Karena tidak berdampak pada panjangnya program ini, saya telah meninggalkan penentuan batas atas aman terendah sebagai latihan untuk pembaca.

xsot
sumber
Membutuhkan kutipan di sekitar input dan \ n lolos dari baris baru.
CalculatorFeline
@CatsAreFluffy Saya percaya tautan Ideone sudah mengklarifikasi bagaimana input diambil.
xsot
Input diambil sebagai string yang dikutip dengan setiap baris dibatasi oleh \ n s.
CalculatorFeline
Baiklah, saya akan mengeditnya untuk membuatnya kurang ambigu.
xsot
3

Javascript (ES6), 91 89 87 byte

Sebagai fungsi yang menerima input sebagai array angka atau string.

-2 byte dari Neil (menggabungkan penugasan ydengan konversi string)

-2 byte (menghapus variabel j)

f=x=>(y=x.map((z,i)=>~(i%5&&x[i-1])+~(i%5<4&x[i+1])+~x[i-5]+~x[i+5]<-5|z))+[]==x?y:f(y)
<!-- Snippet demo with array <-> string conversion for convenience -->
<textarea id="input" cols="10" rows="5">0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1</textarea>
<button id="submit">Run</button>
<pre id="output"></pre>
<script>
strToArray=x=>x.match(/\d/g)
arrayToStr=x=>([]+x).replace(/(.),(.),(.),(.),(.),*/g, '$1 $2 $3 $4 $5\n')
submit.onclick=_=>output.innerHTML=arrayToStr(f(strToArray(input.value)))
</script>

nderscore
sumber
Simpan 2 byte dengan menulis (y=...)+''==xalih-alih (y=...),y+''==x.
Neil
2

MATL , 22 byte

tn:"t5Bt!=~2X53$Y+1>Y|

Ini berfungsi dalam versi bahasa saat ini (15.0.0) .

Cobalah online !

Format input adalah: array 2D dengan baris yang dipisahkan oleh titik koma. Jadi empat kasus uji memiliki input berikut:

[0 0 0 0 1; 0 0 0 0 1; 0 0 0 1 1; 0 0 1 1 1; 0 1 1 1 1]

[1 1 0 0 1; 0 0 0 0 0; 0 1 0 0 1; 0 0 0 0 0; 1 0 0 0 1]

[1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]

[1 0 0 1 0; 0 0 1 0 1; 0 0 0 0 0; 1 0 0 0 0; 0 0 1 0 0]

Penjelasan

Ini berulang kali melakukan konvolusi 2D dari array input dengan mask berikut, yang mendefinisikan tetangga yang dianggap terkontaminasi:

0 1 0
1 0 1
0 1 0

Untuk mendapatkan hasil ukuran yang sama dengan array asli, pertama-tama diisi dengan bingkai nol dan kemudian hanya bagian konvolusi "valid" disimpan (yaitu yang tanpa efek tepi).

Ambang batas 2 diterapkan pada output konvolusi, dan hasilnya adalah elemen ORed dengan input asli.

Ini harus dilakukan dalam jumlah yang cukup untuk memastikan keadaan akhir telah tercapai. Kriteria sederhana yang memenuhi ini adalah: iterate sebanyak jumlah entri dalam array input (yaitu, 25 kali dalam kasus uji).

t          % get input 2D array implicitly. Duplicate
n:"        % repeat as many times as elements in the input array
  t        %   duplicate array
  5B       %   number 5 in binary: row vector [1 0 1] 
  t!       %   duplicate and transpose into column
  =~       %   compare for inequality with broadcast. Gives desired mask
  2X53$Y+  %   2D convolution. Output has same size as input 
  1>       %   true for elements equal or greater than 2
  Y|       %   element-wise OR with previous copy of the array
           % end loop. Implicitly display
Luis Mendo
sumber
1

TI-BASIC, 151 byte

Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
DelVar ADelVar BDelVar CDelVar D
If Y>1:[A](Y-1,X→A
If Y<5:[A](Y+1,X→B
If X>1:[A](Y,X-1→C
If X<5:[A](Y,X+1→D
max(A+B+C+D≥2,[A](Y,X→[B](Y,X
End
End
If [A]≠[B]:Goto 0
[B]

Masukkan sebagai [[1,0,0,1,1][1,0,0,0,0]...].

Conor O'Brien
sumber
1
Saya pikir Anda bisa mendapatkan ini sekitar 100 byte. Kiat pertama: Gunakan satu Repeatlingkaran.
lirtosiast
1

Lua, 236 byte

s=arg[1]u=s.sub while p~=s do p=s s=s:gsub("(%d)()",function(d,p)t=0 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)t=t+(p-7>0 and u(s,p-7,p-7)or 0)t=t+(p+5<30 and u(s,p+5,p+5)or 0)t=t+(p%6>0 and u(s,p,p)or 0)return t>1 and 1 or d end)end print(s)

Menerima input pada baris perintah, dan menggunakan manipulasi string Lua untuk mendapatkan jawabannya.

Tidak Disatukan:

s=arg[1]
u=s.sub
while p~=s do
    p=s
    s=s:gsub("(%d)()", function(d, p)
                 t=0
                 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)
                 t=t+(p-7>0 and u(s,p-7,p-7)or 0)
                 t=t+(p+5<30 and u(s,p+5,p+5)or 0)
                 t=t+(p%6>0 and u(s,p,p)or 0)
                 return t>1 and 1 or d
    end)
end
print(s)
Trebuchette
sumber
1

APL, 76 72 70 byte

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡

Apa yang dilakukan adalah: perluas matriks menjadi 7x7, kemudian pusatkan argumen kami (omega). Dari matriks ini, buat 4 matriks "anak", masing-masing bergeser ke arah yang berbeda (atas / bawah / kiri / kanan), tambahkan bersama-sama (jadi kami mendapatkan jumlah tetangga), jatuhkan bingkai (untuk kembali ke 5x5 matrix). Atau matriks baru ini dengan yang "lama", untuk memastikan kami tidak menjatuhkan sel apa pun dalam proses (yaitu di tepi). Kemudian, gunakan ⍣≡kombinasi untuk mendapatkan nilai titik tetap.

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡
                                                             7 7↑⍵    ⍝ Expand the matrix
                                                       ¯1⊖¯1⌽         ⍝ Center the original matrix
                  (1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂               ⍝ Construct 4 child matrices, each offset from the original one by the values on the left of {}
                +/                                                    ⍝ Sum each matrix into one giant matrix
               ↑                                                      ⍝ Mix
     ¯1 ¯1↓1 1↓                                                       ⍝ Transform the 7x7 matrix back to a 5x5 matrix
   1<                                                                 ⍝ Check which elements are smaller than 1
 ⍵∨                                                                   ⍝ "Or" this matrix and the generated matrix
{                                                                 }⍣≡ ⍝ Find the fixpoint

contoh (mengingat fungsi ditugaskan untuk contaminate):

          stage ⍝ the base matrix
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
      contaminate stage ⍝ apply the function
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
Yang Mulia
sumber