Semoga yang keempat menderita flu

12

Karena besok adalah tanggal 4 Mei, di sini ada posting bertema Star Wars kecil untuk mempersiapkan Anda secara mental terhadap semua lelucon buruk yang akan terjadi besok.

BACKSTORY

Selama sesi senat galaksi semua senator duduk di n*nkotak. Tiba-tiba wabah flu JarJar (yang berlangsung selamanya dan menyebabkan orang yang terinfeksi berbicara seperti JarJar Binks) menyebabkan beberapa senator terinfeksi.

Berikut ini contoh dengan 6*6kisi di mana Xsenator yang terinfeksi, daftar terkait adalah [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]::

masukkan deskripsi gambar di sini

Setelah itu infeksi mulai menyebar langkah demi langkah. Dua senator berbatasan jika mereka berbagi seluruh tepi pada kisi (yaitu, atas, bawah, kanan, kiri), yang berarti kita mengecualikan diagonal.

Kami dapat menyimpulkan bahwa seorang senator dapat bersebelahan dengan 2,3 atau 4 senator lainnya dan mengklaim aturan infeksi berikut:

  • Seorang senator yang telah terinfeksi tetap terinfeksi selamanya
  • Seorang senator terinfeksi pada suatu langkah jika ia berdekatan dengan 2 atau lebih senator yang terinfeksi pada langkah sebelumnya

Berikut ini contoh dengan kisi sebelumnya yang menunjukkan 2 langkah pertama infeksi:

masukkan deskripsi gambar di sini

Setelah langkah selanjutnya semua senat akan terinfeksi

TUGAS ANDA

Kode Anda tidak perlu menangani input yang tidak valid seperti daftar yang lebih besar dari n*natau koordinat yang tidak berbeda.

Kode Anda akan dimasukkan sebagai input daftar pasangan bilangan bulat (atau kisi biner atau format lain yang sesuai dengan bahasa Anda) dan bilangan bulat n(yang tidak perlu jika Anda menggunakan format lain selain daftar), misalnya:

8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

n menjadi sisi dari kisi yang berarti kisi akan menjadi kisi * n, dan daftar pasangan bilangan bulat menjadi koordinat sel-sel dari senator yang terinfeksi secara resmi.

Kiri bawah grid adalah [0,0] dan kanan atas adalah [n-1, n-1]. Kiri atas adalah [0, n-1].

Kode Anda harus menampilkan bilangan bulat:

-1 atau nilai palsu atau kesalahan jika seluruh jaringan tidak akan pernah sepenuhnya terinfeksi atau jumlah langkah minimum yang diperlukan untuk menginfeksi seluruh jaringan

Uji kasus

6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

Ingat bahwa ini adalah , sehingga jawaban terpendek dalam byte menang!


sumber
Terkait
Beta Decay
Berapa nilai minimum n? Apakah ada nilai maksimal?
mbomb007
@ mbomb007 tidak ada nilai maksimum dalam teori tetapi harus dapat dihitung. Untuk nilai minimum saya akan mengatakan 1 yang menghasilkan 0 atau -1
2
Sepertinya pekerjaan untuk Mathematica CellularAutomaton...
mbomb007

Jawaban:

2

MATL, 29 28 byte

tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

Input dalam bentuk matriks 2D dari 1 dan 0

Cobalah di MATL Online

Penjelasan

        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if 
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element
Suever
sumber
@LuisMendo Sayangnya saya tidak berpikir begitu karena ada beberapa 0 dalam output konvolusi yang akan menjadi -1 dan karenanya menjadi "benar"
Suever
Bagaimana dengan tn:"tlY6Z+1>Z|t?x@D.]]N?xl_? (Saya belum banyak diuji). Jika semua elemen adalah 1 di beberapa titik, segera tampilkan indeks loop dan hapus tumpukan. Di akhir perulangan, jika stack tidak kosong, hapus dan tekan-1
Luis Mendo
3

APL (Dyalog 16.0), 54 karakter atau 60 byte

Membawa matriks terlampir sebagai argumen, mengembalikan nomor langkah yang menyelesaikan infeksi, yaitu 1 = sudah sepenuhnya terinfeksi. 0 = tidak sepenuhnya menyebar, yang hanya 1 + angka OP.

54 karakter (Unicode):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

60 byte (Klasik):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

setara dengan ⎕U233A

Contoh menjalankan:

      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

Langkah-langkahnya adalah sebagai berikut:

┌────────────┬────────────┬─────────────────── ────────────────────────────────────────────┬─ ────────────┐
│ XX │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │
│ X │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ │ X │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ X │ XX │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
└────────────┴────────────┴─────────────────── ────────────────────────────────────────────┴─ ────────────┘
┌────────┬─────────┬────────┬────────┬───────── ┬────────┬─────────┬────────┬────────┬───────── ┐
│ XX │ XX │ XX │ XX │ XX │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ │ │ │ │ X │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ X │ X │ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │ XXXX │
│ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │
└────────┴─────────┴────────┴────────┴───────── ┴────────┴─────────┴────────┴────────┴───────── ┘
Adm
sumber
2

Pyth , 49 byte

J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

Suite uji .

Menggunakan pengindeksan 1 untuk output.

Biarawati Bocor
sumber
2

Python, 231 byte

g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

Ini memunculkan kesalahan jika tidak mungkin.

Cobalah online!

Neil
sumber
0/0menyimpan dua byte dari raise. Mungkin 1/(g!=h)akan bekerja (maka keseluruhan whilebisa diuraikan juga).
Jonathan Allan
@ JonathanAllan saya memperbaruinya, terima kasih atas masukannya.
Neil
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0menghemat 12. Anda dapat menghapus ruang antara (a) 1dan fordan (b) ]dan forjuga.
Jonathan Allan
@JonathanAllan Diperbarui lagi. Terima kasih
Neil
1

JavaScript (ES6), 132 byte

f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

Dimana \nmewakili karakter baris baru literal. Mengambil input sebagai string 0s dan 1s dalam array yang dibatasi baris baru. Kembali NaNjika grid tidak akan sepenuhnya terinfeksi.

Neil
sumber