Ekspansja bakteryjna

25

Kolonie bakterii znakowanych 1poprzez 9żyją na segmencie komórkach równomiernie rozmieszczonych w puste komórki wskazuje0

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

Co sekundę każda kolonia rozprzestrzenia się na sąsiednie puste komórki. Jeśli dwie kolonie docierają do pustej komórki w tym samym czasie, kolonia o większej etykiecie bierze ją.

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

Kolonie nie mogą rozprzestrzeniać się poza granice. Kolonia nigdy nie jest przemieszczana przez inną kolonię, więc po zapełnieniu wszystkich pustych komórek nic się nie zmienia.

Biorąc pod uwagę stan początkowy, wyjdź lub wydrukuj stan końcowy. Użyj dowolnego rozsądnego formatu listy lub łańcucha. Nie powinieneś generować żadnych stanów pośrednich. Dane wejściowe będą zawierać co najmniej jedną kolonię bakteryjną.

Powiązane: Ukryj zera na liście . (Kolonie rozprzestrzeniają się tylko w prawo).

Przypadki testowe: Dane wyjściowe poniżej danych wejściowych.

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

Pokaż fragment kodu

code-golf cellular-automata xnor
źródło

Odpowiedzi:

14

JavaScript (ES6), 66 62 bajtów

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

Wyjaśnienie

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

Test

Pokaż fragment kodu

użytkownik 81655
źródło
10

Pyth, 18 bajtów

um|@d1eSd.:++0G03Q

Zestaw testowy

Pobiera dane wejściowe jako listę liczb całkowitych.

Zasadniczo ta wykorzystuje zastosowanie do pętli konwergencji u. Stosuje aktualizację, tworząc wszystkie listy każdej komórki i dwóch komórek po każdej stronie, a następnie aktualizując każdą zerowaną komórkę do maksymalnej liczby sąsiadów.

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
źródło
8

Mathematica, 77 bajtów

Nie bardzo konkurencyjny w porównaniu z //.rozwiązaniem alephalpha , ale pomyślałem, że wyzwanie automatu komórkowego powinno dać CellularAutomatonodpowiedź:

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

Ta funkcja wymaga mnóstwa parametrów ... nadajmy im kilka nazw:

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

Oto, co robią:

  • rto zakres reguły, czyli określa, ilu sąsiadów bierze pod uwagę aktualizacja. Chcemy jednego sąsiada z każdej strony, więc używamy 1.
  • njest zwykle liczbą lub listą kolorów (różne typy komórek), ale jeśli określimy regułę jako funkcję niestandardową zamiast numeru reguły, powinna to być {}.
  • fto funkcja określająca regułę aktualizacji. Pobiera listę 3 komórek (jeśli r = 1) i zwraca nowy kolor dla środkowej komórki.
  • ijest warunkiem początkowym. To jest wkład.
  • bjest tłem. Jeśli nie jest to podane, CellularAutomatonużywa okresowych granic, których nie chcemy. Zamiast tego użycie 0warunku martwej granicy.
  • tto liczba symulacji. Nie potrzebujemy więcej kroków, niż wkład jest szeroki, ponieważ później bakterie się zbiegną, więc t = Length@#. Zwykle CellularAutomatonzwraca wszystkie kroki pośrednie. Możemy tego uniknąć, zawijając tdwie listy.
  • dokreśla, które komórki są prezentowane w danych wyjściowych. Domyślnie otrzymalibyśmy wszystkie komórki, na które reguła może potencjalnie mieć wpływ (czyli t*rdodatkowe komórki na obu końcach danych wejściowych). Dajemy to l-1, ponieważ jest to jedna z niewielu sytuacji w Mathematica, w których stosuje się indeks zerowy.
Martin Ender
źródło
6

Haskell, 86 83 81 79 73 71 bajtów

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

Przykład użycia: 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].

Nic wielkiego do wyjaśnienia: jeśli komórka ma wartość 0, weź maksimum sąsiednich elementów. Powtórz czasy wejściowe. W tym celu powtarzam xvia, foldlale ignoruję drugi argument w p.

Edycja: @Mauris znalazł 6 bajtów do zapisania, a @xnor kolejne dwa. Dzięki!

nimi
źródło
Można wymienić h pz p!_czym zastąpić (const.h)z (!)aby zaoszczędzić 6 bajtów.
Lynn
@Mauris: Clever. Wielkie dzięki!
nimi
@nimi Myślę, że ostatni wiersz jest anonimowy id>>=foldl(!).
xnor
@xnor: tak to robi! Dobrze zauważony!
nimi
4

CJam, 27 24 bajtów

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

Sprawdź to tutaj.

Spycha to nienazwany blok, który przekształca listę na stosie w nową listę.

Wyjaśnienie

_,       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
źródło
Zbieganie się w bok jest fajną sztuczką
Luis Mendo
1
... które bezwstydnie pożyczyłem :-)
Luis Mendo
4

J, 24 23 bajty

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

Stosowanie:

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

Metoda jest podobna do rozwiązania Maurisa .

(                  )^:_ 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

Wypróbuj online tutaj.

1 bajt zapisany dzięki Zgarbowi.

randomra
źródło
3

Mathematica, 77 74 66 62 bajtów

Zaoszczędzono 12 bajtów dzięki Martinowi Büttnerowi.

#//.i_:>BlockMap[If[#2<1,Max@##,#2]&@@#&,Join[{0},i,{0}],3,1]&
alephalpha
źródło
3

J, 33 bajty

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

Trochę dłużej, niż bym chciał.

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
źródło
To tak różni się od tego, co mam, myślę, że powinieneś opublikować to jako odpowiedź :)
Lynn
3

Python 3.5, 83 bajty

Ta funkcja przyjmuje listę liczb całkowitych w języku Python. Nie jestem pewien, czy zostało wiele do gry w golfa, ale chciałbym, aby konkurował przynajmniej z innym językiem!

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

Od Pythona 3.5, PEP 448 pozwala nam rozpakować ssię 0,*s. Wcześniejsze wersje wymagają jednego bajtu dodatkowego, na przykład:

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

Kredyt do rozwiązania i wyjaśnienia user81655 koszulka dla pomagając mi uświadomić sobie, że nie ma potrzeby badania, czy lista przestał zmianie; Muszę tylko powtórzyć tyle razy, aby mieć pewność, że wszystkie zera musiały zostać pokryte. (Maksymalna potrzebna liczba iteracji jest o jeden mniejsza niż długość listy; to robi jedną iterację więcej, ponieważ wymaga to mniej kodu).

Tim Pederick
źródło
@ChrisH: To nie działa na Python 3.5, i nie sądzę, że to działa na starszych wersjach albo: nie, że przesuwanie returnsię wewnątrz tej for _ in spętli?
Tim Pederick,
komentarz usunięty - Zdarzyło mi się tylko wypróbować przypadki testowe, które rozwiązują się po raz pierwszy.
Chris H
3

Matlab, 90 bajtów

Co powiesz na niektóre zwoje?

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

Przykład

>> 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
źródło
3

Haskell, 66 65 bajtów

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

Definiuje funkcję o nazwie f.

Wyjaśnienie

Zamiast iterować automat komórkowy, obliczam bezpośrednio końcowe wartości. Definicja jest zrozumieniem pojedynczej listy. Wartość iwaha się od 0do length x - 1, ponieważ zipujemy xliczbami naturalnymi. Dla każdego indeksu itworzymy listę list 2-elementowych

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

Z tej listy obliczamy maksymalny element, którego druga współrzędna jest różna od zera, i bierzemy ten drugi element !!1. To daje najbliższą niezerową wartość do zindeksowania i, zrywając powiązania, biorąc większą wartość.

Zgarb
źródło
Gratulujemy wygranej nagrody!
xnor
2

Lua, 133 bajty

Dwie pętle, zagnieżdżone trójskładniki ... Jeśli chcę dalej grać w golfa, będę musiał znaleźć inny sposób, ale tego nie widzę.

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

Objaśnienia

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

Część

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

zostanie rozwinięty do 

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)

które można przetłumaczyć ifjako zagnieżdżone jako

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
źródło
1

Pyth, 17 bajtów

meeSe#.e,_akdbQUQ

Pobiera listę w stylu Pythona ze standardowego wejścia, wyświetla na standardowe wyjście.

Wyjaśnienie

Jest to w zasadzie tłumaczenie mojej odpowiedzi Haskella. Tak naprawdę nie korzystałem wcześniej z Pyth, więc wskazówki są mile widziane.

                   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
źródło
1

APL (Dyalog) , 18 bajtów

Anonimowa ukryta funkcja prefiksu.

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

Wypróbuj online!

(… )⍣≡ Zastosuj następującą ukrytą funkcję, aż wynik będzie identyczny z argumentem:

 ⊢ argument

 + plus

  ~ nie  signum
  ∘
  ×

 × czasy

 3⌈/ maksima dla każdej grupy trzech

 0, zero, a następnie

  , argument, po którym
  ∘ następuje
  0 zero

Adám
źródło
1

Java 8, 155 142 bajtów

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;}

Zmienia dane wejściowe int[]zamiast zwracać nowe, aby zapisać bajty.

Wyjaśnienie:

Wypróbuj tutaj.

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
źródło
0

Ruby, 81 bajtów

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

Myślę, że wnętrze mapmoże być jeszcze bardziej golfa.

Ostra Gupta
źródło
Właśnie się zorientowałem, moja odpowiedź jest w pewnym stopniu identyczna z odpowiedzią @ user81655 .
Surowa Gupta,
Myślę, że możesz usunąć spacje w trójce, tj. Wokół ?i :.
Alex A.,
0

PHP - 301 291 289 288 264 znaków

Nie próbowałem osiągnąć innych odpowiedzi przed podjęciem tej próby. Nie obwiniaj języka, obwiniaj mnie. Bardzo przyjemne i wymagające mimo wszystko. Bardzo cenione są wszystkie porady dotyczące gry w golfa.

$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;

Wyjaśnił

// 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;
Gęś
źródło
1
Poważnie? Gra w golfa to nie tylko usuwanie białych znaków w kodzie. Poza tym algorytmie, oto kilka wskazówek: użycie 1zamiast true, splitzamiast explode, forzamiast while, joinzamiast implode, usunąć zbędne klamrowych ...
Blackhole
Eksplodowałem, ponieważ podział jest amortyzowany. Nie wiem też, jak napisać pętlę while, używając, więc zachowałem ją na razie, chyba że ktoś tutaj może udostępnić swoją wiedzę lub link. Dziękuję wam wszystkim.
Gęś
0

Python, 71 bajtów

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

zipTworzy wszystkie długości 3 listy zagnieżdżone danego składnika i jego sąsiadów, traktując poza punktami końcowymi jak 0. Centralny element l[1]podlisty l, jeśli zero, jest zastępowany przez maxjego sąsiadów z l[1]or max(l). Do l*all(l)zwraca listę l, gdy nie ma 0tych.

xnor
źródło
0

Rubinowy, 74 bajty

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

działa poprzez znalezienie najbliższej niezerowej liczby.

MegaTom
źródło
0

MATL , 38 bajtów

Bezpośrednie tłumaczenie mojej odpowiedzi Matlaba. Używa bieżącej wersji języka / kompilatora.

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

Przykład

>> 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

EDYCJA: Wypróbuj online! z X+zastąpieniem przez Y+i vze &vwzględu na zmiany wprowadzone w języku.

Luis Mendo
źródło