Ekspansi bakteri

25

Koloni bakteri yang diberi label 1melalui 9hidup pada segmen sel dengan jarak yang sama, dengan sel kosong ditunjukkan oleh0

0 0 2 0 0 0 1 2 0 0 3 3 0 0

Setiap detik, setiap koloni menyebar ke sel-sel kosong yang berdekatan. Jika dua koloni mencapai sel kosong pada saat yang sama, koloni berlabel besar mengambilnya.

t=0:  0 0 2 0 0 0 1 2 0 0 3 3 0 0
t=1:  0 2 2 2 0 1 1 2 2 3 3 3 3 0
t=2:  2 2 2 2 2 1 1 2 2 3 3 3 3 3

Koloni tidak bisa menyebar melampaui batas. Koloni tidak pernah dipindahkan oleh koloni lain, jadi setelah semua sel kosong diisi, tidak ada perubahan lebih lanjut.

Diberikan status awal, hasilkan atau cetak status akhir. Gunakan format string atau daftar yang masuk akal. Anda seharusnya tidak menghasilkan status perantara. Input akan mengandung setidaknya satu koloni bakteri.

Terkait: Menutupi nol dalam daftar . (Koloni hanya menyebar ke kanan.)

Kasus uji: Output di bawah input.

0 0 2 0 0 0 1 2 0 0 3 3 0 0
2 2 2 2 2 1 1 2 2 3 3 3 3 3

7 0 3 0 0 0 0 0 8 0 9 1
7 7 3 3 3 8 8 8 8 9 9 1

5 0 3 0 0 0
5 5 3 3 3 3

7 7 1
7 7 1

1 0 1
1 1 1

Tampilkan cuplikan kode

code-golf cellular-automata Tidak
sumber

Jawaban:

14

JavaScript (ES6), 66 62 byte

a=>a.map(_=>a=a.map((c,i)=>c||Math.max(a[i-1]|0,a[i+1]|0)))&&a

Penjelasan

a=>                 // a = input as array of numbers
  a.map(_=>         // loop for the length of a, this ensures the end is always reached
    a=a.map((c,i)=> // update a after to the result of t, for each cell c of index i
      c||           // keep the cell if it is not 0
        Math.max(   // else set the cell to the max value of:
          a[i-1]|0, //     the previous cell (or 0 if i - 1 less than 0),
          a[i+1]|0  //     or the next cell (or 0 if i + 1 greater than the length of a)
        )
    )
  )
  &&a               // return a

Uji

Tampilkan cuplikan kode

pengguna81655
sumber
10

Pyth, 18 byte

um|@d1eSd.:++0G03Q

Suite uji

Mengambil input sebagai daftar bilangan bulat.

Pada dasarnya, ini menggunakan loop berlaku hingga konvergensi u,. Itu berlaku pembaruan dengan membentuk semua daftar setiap sel dan dua sel di kedua sisi, kemudian memperbarui setiap sel yang memusatkan perhatian ke max dari tetangganya.

um|@d1eSd.:++0G03Q
                      Implicit: Q = eval(input())
u                Q    Apply the following until convergence, starting with G = Q.
           ++0G0      Pad G with zeros on either side.
         .:     3     Form all 3 element substrings.
                      Now, for each element of G, we have a list of the form
                      [previous, current, next]
 m                    Map over this list
  |@d1                The current element, if it's nonzero
      eSd             Else the max of the list.
isaacg
sumber
8

Mathematica, 77 byte

Tidak terlalu kompetitif dibandingkan dengan //.solusi alephalpha , tetapi saya pikir tantangan seluler-automata harus memiliki CellularAutomatonjawaban:

CellularAutomaton[{If[#2<1,Max@##,#2]&@@#&,{},1},{#,0},{{{l=Length@#}},l-1}]&

Fungsi ini membutuhkan banyak parameter ... mari beri mereka beberapa nama:

CellularAutomaton[{f,n,r},{i,b},{{{t}},d}]

Inilah yang mereka lakukan:

  • radalah rentang aturan, yaitu menentukan berapa banyak tetangga yang dipertimbangkan untuk pembaruan. Kami ingin satu tetangga di setiap sisi, jadi kami gunakan 1.
  • nbiasanya jumlah atau daftar warna (tipe sel yang berbeda), tetapi jika kita menetapkan aturan sebagai fungsi khusus alih-alih nomor aturan, ini seharusnya {}.
  • fadalah fungsi yang menentukan aturan pembaruan. Dibutuhkan daftar 3 sel (jika r = 1) dan mengembalikan warna baru untuk sel tengah.
  • iadalah kondisi awal. Itu inputnya.
  • badalah latar belakang. Jika ini tidak diberikan, CellularAutomatongunakan batas periodik, yang tidak kita inginkan. Sebaliknya menggunakan 0memaksakan kondisi batas mati.
  • tadalah berapa kali untuk disimulasikan. Kita tidak membutuhkan langkah lebih banyak daripada input yang luas, karena setelah itu bakteri akan bertemu, jadi t = Length@#. Biasanya, CellularAutomatonkembalikan semua langkah perantara. Kita bisa menghindarinya dengan membungkus tdalam dua daftar.
  • dmenentukan sel mana yang disajikan dalam output. Secara default, kita akan mendapatkan semua sel yang berpotensi dipengaruhi oleh aturan (yang merupakan t*rsel tambahan di kedua ujung input). Kami memberikannya l-1, karena ini adalah salah satu dari beberapa situasi di Mathematica di mana indeks berbasis nol digunakan.
Martin Ender
sumber
6

Haskell, 86 83 81 79 73 71 byte

(0#r)l=max r l
(o#_)_=o
p!_=zipWith3(#)p(0:p)$tail p++[0] 
id>>=foldl(!)

Contoh penggunaan: id>>=foldl(!) $ [7,0,3,0,0,0,0,0,8,0,9,1]-> [7,7,3,3,3,8,8,8,8,9,9,1].

Tidak banyak yang bisa dijelaskan: jika sel 0, ambil maksimum elemen tetangga. Ulangi panjang waktu input. Untuk ini saya beralih xmelalui foldltetapi mengabaikan argumen kedua di p.

Sunting: @Mauris ditemukan 6 byte untuk disimpan dan @xnor dua lainnya. Terima kasih!

nimi
sumber
Anda dapat mengganti h pdengan p!_lalu ganti (const.h)dengan (!)untuk menyimpan 6 byte.
Lynn
@Mauris: Pintar. Terima kasih banyak!
nimi
@nimi Saya pikir baris terakhir dianonimkan id>>=foldl(!).
xnor
@ xnor: ya itu! Terlihat dengan baik!
nimi
4

CJam, 27 24 byte

{_,{0\0++3ew{~@e>e|}%}*}

Uji di sini.

Ini mendorong blok tanpa nama yang mengubah daftar pada tumpukan menjadi daftar baru.

Penjelasan

_,       e# Duplicate the input and get its length N.
{        e# Run this block N times (convergence won't take that long)...
  0\0++  e#   Wrap the list in two zeroes.
  3ew    e#   Get all sublists of length 3.
  {      e#   Map this block onto each sublist...
    ~    e#     Dump all three elements on the stack.
    @    e#     Pull up the left neighbour.
    e>   e#     Maximum of both neighbours.
    e|   e#     Logical OR between centre cell and maximum of neighbours.
  }%
}*
Martin Ender
sumber
Konvergensi menghindar adalah trik yang bagus
Luis Mendo
1
... yang saya pinjam tanpa malu :-)
Luis Mendo
4

J, 24 23 byte

(+=&0*(0,~}.)>.0,}:)^:_

Pemakaian:

   ((+=&0*(0,~}.)>.0,}:)^:_) 0 1 5 0 0 0 6
1 1 5 5 6 6 6

Metodenya mirip dengan solusi Mauris .

(                  )^:_ repeat until change
               0,}:     concat 0 and tailless input
      (0,~}.)           concat headless input and 0
             >.         elementwise maximum of the former two lists
  =&0*                  multiply by input_is_0 (zeroing out the list at nonzero input positions)
 +                       add to input

Cobalah online di sini.

1 byte disimpan berkat Zgarb.

randomra
sumber
3

Mathematica, 77 74 66 62 byte

Disimpan 12 byte berkat Martin Büttner.

#//.i_:>BlockMap[If[#2<1,Max@##,#2]&@@#&,Join[{0},i,{0}],3,1]&
alephalpha
sumber
3

J, 33 byte

3 :'y+(y=0)*>./(_1,:1)|.!.0 y'^:_

Sedikit lebih lama dari yang saya inginkan.

3 :'                         '^:_   Repeat a "lambda" until a fixed point:
                            y         The input to this lambda.
               (_1,:1)|.!.0           Shift left and right, fill with 0.
            >./                       Maximum of both shifts.
      (y=0)*                          Don't grow into filled cells.
    y+                                Add growth to input.
Lynn
sumber
Itu sangat berbeda dari yang saya miliki, saya pikir Anda harus mempostingnya sebagai jawaban :)
Lynn
3

Python 3.5, 83 byte

Fungsi ini mengambil daftar bilangan bulat Python. Tidak yakin ada banyak yang tersisa untuk golf, tetapi saya ingin membuatnya bersaing dengan bahasa lain setidaknya!

def b(s):
 for _ in s:s=[s[n]or max((0,*s)[n:n+3])for n in range(len(s))]
 return s

Dari Python 3.5, PEP 448 memungkinkan kita membongkar ske 0,*s. Rilis sebelumnya membutuhkan satu byte tambahan, seperti:

def b(s):
 for _ in s:s=[s[n]or max(([0]+s)[n:n+3])for n in range(len(s))]
 return s

Kredit untuk solusi user81655 dan penjelasan untuk membantu saya menyadari bahwa saya tidak perlu menguji apakah daftar telah berhenti berubah; Saya hanya perlu mengulangi waktu yang cukup untuk memastikan semua nol pasti tertutup. (Jumlah maksimum iterasi yang dibutuhkan adalah satu kurang dari panjang daftar; ini melakukan satu iterasi lebih dari itu, karena itu membutuhkan lebih sedikit kode.)

Tim Pederick
sumber
@ChrisH: Ini tidak bekerja pada Python 3.5, dan saya tidak berpikir itu akan bekerja pada versi sebelumnya baik: tidak bahwa memindahkan returnke dalam yang for _ in slingkaran?
Tim Pederick
komentar dihapus - Kebetulan saya hanya mencoba kasus uji yang menyelesaikan pertama kali.
Chris H
3

Matlab, 90 byte

Bagaimana dengan beberapa konvolusi?

x=input('');for n=x;x=x+max(conv(x,[0 0 1],'same'),conv(x,[1 0 0],'same')).*~x;end;disp(x)

Contoh

>> x=input('');for n=x;x=x+max(conv(x,[0 0 1],'same'),conv(x,[1 0 0],'same')).*~x;end;disp(x)
[7 0 3 0 0 0 0 0 8 0 9 1]
     7     7     3     3     3     8     8     8     8     9     9     1
Luis Mendo
sumber
3

Haskell, 66 65 byte

f x=[maximum[[-j*j,a]|(j,a)<-zip[-i..]x,a>0]!!1|(i,_)<-zip[0..]x]

Ini mendefinisikan fungsi yang disebut f .

Penjelasan

Alih-alih iterasi otomat seluler, saya menghitung nilai akhir secara langsung. Definisi adalah pemahaman daftar tunggal. Nilainya iberkisar dari 0hingga length x - 1, karena kami zip xdengan bilangan alami. Untuk setiap indeks i, kami menghasilkan daftar daftar 2-elemen

[-(-i)^2, x0], [-(-i+1)^2, x1], [-(-i+2)^2, x2], ..., [-(-i+n)^2, xn]

Dari daftar ini, kami menghitung elemen maksimal yang koordinat keduanya bukan nol dan membawa elemen kedua !!1. Ini memberikan nilai bukan nol terdekat ke indeks i, memutuskan hubungan dengan mengambil nilai lebih besar.

Zgarb
sumber
Selamat telah memenangkan hadiah!
xnor
2

Lua, 133 byte

Dua loop, terary bersarang ... Jika saya ingin bermain golf lebih jauh, saya harus menemukan cara lain untuk melakukannya, tetapi saya tidak melihatnya.

function f(a)for i=1,#a do b={}for j=1,#a do c,d=a[j+1]or 0,a[j-1]b[j]=0<a[j]and a[j]or(d or 0)>c and d or c end a=b end return a end

Penjelasan

function f(a)
  for i=1,#a                       -- this loop allow us to be sure the cycle is complete
  do
    b={}                           -- set a new pointer for b
    for j=1,#a                     -- loop used to iterate over all elements in a
    do
      c,d=a[j+1]or 0,a[j-1]        -- gains some bytes by attributing these expressions 
                                   -- to a variable
      b[j]=0<a[j]and a[j]or        -- explained below
            (d or 0)>c and d or c
    end
    a=b                            -- we are one cycle further, new value for a
  end                              -- which is our reference array
  return a
end

Bagian

b[j]=0<a[j]and a[j]or(d or 0)>c and d or c

akan diperluas ke 

b[j]=0<a[j]and a[j]or(a[j-1] or 0)>(a[j+1] or 0) and a[j-1] or(a[j+1]or 0)

yang dapat diterjemahkan dalam bersarang ifsebagai

if 0<a[j]
then
    value=a[j]          -- if the cell isn't at 0, it keeps its value
elseif (a[j-1] or 0)<(a[j+1] or 0)
--[[ x or y as the following truth table :
x | y ||x or y
------||-------
0 | 0 || false
0 | 1 ||   y
1 | 0 ||   x
1 | 1 ||   x
    -- It means that when j=1 (1-based) and we try to index a[j-1]
    -- instead of failing, we will fall in the case false or true
    -- and use the value 0
    -- the same trick is used for when we try to use an index > a:len
]]--
then
    value=a[j-1]        -- the left cell propagate to the cell j
else
    value=a[j+1] or 0   -- if j=a:len, we put 0 instead of a[j+1]
                        -- this case can only be reached when we are on the right most cell
                        -- and a[j-1]==0
end
Katenkyo
sumber
1

Pyth, 17 byte

meeSe#.e,_akdbQUQ

Mengambil daftar gaya-Python dari stdin, output ke stdout.

Penjelasan

Ini pada dasarnya adalah terjemahan dari jawaban Haskell saya. Saya belum pernah menggunakan Pyth sebelumnya, jadi isyaratnya disambut.

                   Implicit: Q is input list
m              UQ  Map over input index d:
      .e      Q     Map over input index k and element b:
        ,_akdb       The pair [-abs(k-d), b]
    e#              Remove those where b==0
 eeS                Take the second element of the maximal pair
Zgarb
sumber
1

APL (Dyalog) , 18 byte

Fungsi awalan diam-diam anonim.

(⊢+~∘××3⌈/0,,∘0)⍣≡

Cobalah online!

(... )⍣≡ terapkan fungsi tacit berikut sampai hasilnya identik dengan argumen:

 ⊢ argumen

 + plus

  ~ tidak
  ∘ yang
  × signum

 × waktu

 3⌈/ maksimal atas setiap kelompok tiga dari

 0, nol diikuti oleh

  , argumen diikuti oleh
  ∘ sebuah
  0 nol

Adám
sumber
1

Java 8, 155 142 byte

a->{for(int b[],i,l=a.length,p,n,f=l;f>0;)for(b=a.clone(),i=0,f=l;i<l;f-=a[i-1]>0?1:0)if(a[i++]<1)a[i-1]=(p=i>1?b[i-2]:0)>(n=i<l?b[i]:0)?p:n;}

Memodifikasi input int[]alih-alih mengembalikan yang baru untuk menghemat byte.

Penjelasan:

Coba di sini.

a->{                   // Method with integer-array parameter and no return-type
  for(int b[],         //  Copy array
          i,           //  Index integer
          l=a.length,  //  Length of the array
          p,n,         //  Temp integers (for previous and next)
          f=1;         //  Flag integer, starting at 1
      f>0;)            //  Loop (1) as long as the flag is not 0 (array contains zeroes)
    for(b=a.clone(),   //   Create a copy of the current state of the array
        i=0,           //   Reset the index to 0
        f=l;           //   Reset the flag to the length of the array `l`
        i<l;           //   Inner loop (2) over the array
        f-=a[i-1]>0?   //     After every iteration, if the current item is not a zero:
            1          //      Decrease flag `f` by 1
           :           //     Else:
            0)         //      Leave flag `f` the same
      if(a[i++]<1)     //    If the current item is a 0:
        a[i-1]=        //     Change the current item to:
         (p            //      If `p` (which is:
           =i>1?       //        If the current index is not 0:
             b[i-2]    //         `p` is the previous item
            :          //        Else:
             0)        //         `p` is 0)
         >(n           //      Is larger than `n` (which is:
            =i<l?      //        If the current index is not `l-1`:
              b[i]     //         `n` is the next item
             :         //        Else:
              0)?      //         `n` is 0):
          p            //       Set the current item to `p`
         :             //      Else:
          n;           //       Set the current item to `n`
                       //   End of inner loop (2) (implicit / single-line body)
                       //  End of loop (1) (implicit / single-line body)
}                      // End of method
Kevin Cruijssen
sumber
0

Ruby, 81 byte

->(a){a.map{|o|a=a.map.with_index{|x,i|x!=0 ? x : a[[0,i-1].max..i+1].max}}[-1]}

Saya pikir batin mapbisa lebih jauh golf.

Harsh Gupta
sumber
Baru sadar, jawaban saya agak identik dengan jawaban @ user81655 .
Harsh Gupta
Saya pikir Anda dapat menghapus spasi di ternary, yaitu sekitar ?dan :.
Alex A.
0

PHP - 301 291 289 288 264 Karakter

Tidak memuncak pada jawaban lain sebelum mencoba ini. Jangan salahkan bahasanya, salahkan saya. Sangat menyenangkan dan menantang. Semua saran kode golf sangat dihargai.

$a=explode(' ',$s);$f=1;while($s){$o=1;foreach($a as&$b){
if($b==0){$u=current($a);prev($a);$d=prev($a);if(!$o&&current($a)==0){end($a);$d=prev($a);}if(!$f){$f=1;continue;}if($u>$d)$b=$u;if($u<$d){$b=$d;$f=0;}}
$o=0;}if(!in_array(0,$a))break;}$r=join(' ',$a);echo$r;

Dijelaskan

// Input
$s = '0 0 2 0 0 0 1 2 0 0 3 3 0 0';

// Create array
$a = explode(' ', $s);
// Set skip flag
$f = 1;
while ($s)
{
    // Set first flag
    $o = 1;
    // Foreach
    foreach ($a as &$b)
    {
        // Logic only for non zero numbers
        if ($b == 0)
        {
            // Get above and below value
            $u = current($a);
            prev($a);
            $d = prev($a);

            // Fix for last element
            if (! $o && current($a) == 0)
            {
                end($a);
                $d = prev($a);
            }

            // Skip flag to prevent upwards overrun
            if (! $f)
            {
                $f = 1;
                continue;
            }

            // Change zero value logic
            if ($u > $d)
                $b = $u;
            if ($u < $d)
            {
                $b = $d;
                $f = 0;
            }
        }

        // Turn off zero flag
        $o = 0;
    }

    // if array contains 0, start over, else end loop
    if (! in_array(0, $a))
        break;
}
// Return result
$r = join(' ', $a);
echo $r;(' ', $a);
echo $r;
Angsa
sumber
1
Serius? Golf tidak hanya menghilangkan spasi putih dalam kode Anda. Selain algoritma, berikut adalah beberapa tips: gunakan 1bukan true, splitbukan explode, forbukan while, joinbukan implode, menghapus tanda kurung keriting tidak berguna, ...
Blackhole
Saya terus meledak karena perpecahan disusutkan. Juga, saya tidak tahu cara menulis loop sementara menggunakan untuk, jadi saya menyimpannya untuk saat ini, kecuali seseorang di sini dapat berbagi pengetahuan mereka atau berbagi tautan. Terima kasih semua.
Angsa
0

Python, 71 byte

g=lambda l:l*all(l)or g([l[1]or max(l)for l in zip([0]+l,l,l[1:]+[0])])

The zipmenciptakan semua panjang-3 sublists dari suatu elemen dan tetangganya, memperlakukan di luar titik akhir sebagai 0. Elemen pusat l[1]sublist l, jika nol, digantikan oleh maxtetangganya l[1]or max(l). The l*all(l)kembali daftarl ketika tidak memiliki 0's.

Tidak
sumber
0

Ruby, 74 byte

->a{(r=0...a.size).map{|n|a[r.min_by{|i|[(a[i]<1)?1:0,(i-n).abs,-a[i]]}]}}

bekerja dengan menemukan nomor non-nol terdekat.

MegaTom
sumber
0

MATL , 38 byte

Terjemahan langsung dari jawaban Matlab saya. Menggunakan versi saat ini bahasa / kompiler saat ini.

it:"tttFFTo2X5I$X+wTFFo2X5I$X+vX>w~*+]

Contoh

>> matl it:"tttFFTo2X5I$X+wTFFo2X5I$X+vX>w~*+]
> [7 0 3 0 0 0 0 0 8 0 9 1]
7 7 3 3 3 8 8 8 8 9 9 1

EDIT: Coba online!dengan X+digantikan oleh Y+dan voleh &v, karena perubahan yang dilakukan dalam bahasa.

Luis Mendo
sumber