Bakterielle Expansion

25

1Durchmarkierte Bakterienkolonien 9leben auf einem Segment von Zellen mit gleichem Abstand, wobei leere Zellen durch gekennzeichnet sind0

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

Jede Sekunde breitet sich jede Kolonie auf benachbarte leere Zellen aus. Erreichen zwei Kolonien gleichzeitig eine leere Zelle, nimmt die Kolonie mit der größeren Markierung diese.

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

Die Kolonien können sich nicht über die Grenzen hinaus ausbreiten. Eine Kolonie wird nie von einer anderen Kolonie verdrängt. Sobald alle leeren Zellen gefüllt sind, ändert sich nichts mehr.

Geben Sie den Endzustand aus, oder drucken Sie ihn aus, wenn der Ausgangszustand gegeben ist. Verwenden Sie ein angemessenes Listen- oder Zeichenfolgenformat. Sie sollten keine Zwischenzustände ausgeben. Die Eingabe enthält mindestens eine Bakterienkolonie.

Verwandte: Vertuschen Sie Nullen in einer Liste . (Die Kolonien breiten sich nur nach rechts aus.)

Testfälle: Ausgabe unterhalb der Eingabe.

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

Code-Snippet anzeigen

code-golf cellular-automata xnor
quelle

Antworten:

14

JavaScript (ES6), 66 62 Bytes

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

Erläuterung

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

Prüfung

Code-Snippet anzeigen

user81655
quelle
10

Pyth, 18 Bytes

um|@d1eSd.:++0G03Q

Testsuite

Nimmt die Eingabe als Liste von ganzen Zahlen.

Hierbei wird im Wesentlichen eine Schleife zum Anwenden bis zur Konvergenz verwendet u. Es wendet die Aktualisierung an, indem es alle Listen jeder Zelle und der beiden Zellen auf beiden Seiten bildet und dann jede auf Null gesetzte Zelle auf das Maximum ihrer Nachbarn aktualisiert.

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

Mathematica, 77 Bytes

Im Vergleich zu Alephalphas //.Lösung nicht sehr wettbewerbsfähig , aber ich fand, dass eine Herausforderung mit Zellularautomaten eine CellularAutomatonAntwort haben sollte:

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

Die Funktion nimmt eine Menge Parameter auf ... geben wir ihnen einige Namen:

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

Folgendes machen sie:

  • rist der Bereich der Regel, dh es wird festgelegt, wie viele Nachbarn für die Aktualisierung berücksichtigt werden. Wir wollen einen Nachbarn auf jeder Seite, also benutzen wir1 .
  • n ist normalerweise die Anzahl oder Liste der Farben (verschiedene Zelltypen), aber wenn wir die Regel als benutzerdefinierte Funktion anstelle einer Regelnummer angeben, sollte dies so sein {} .
  • fist eine Funktion, die die Aktualisierungsregel bestimmt. Es dauert eine Liste von 3 Zellen (wennr = 1 ) und gibt die neue Farbe für die mittlere Zelle zurück.
  • iist der Ausgangszustand. Das ist der Input.
  • bist der Hintergrund. Wenn dies nicht gegeben ist, CellularAutomatonwerden periodische Grenzen verwendet, die wir nicht wollen. Stattdessen 0legt die Verwendung eine tote Randbedingung fest.
  • tGibt an, wie oft simuliert werden soll. Wir brauchen nicht mehr Schritte, als die Eingabe breit ist, da die Bakterien danach konvergiert haben t = Length@#. Normalerweise werden CellularAutomatonalle Zwischenschritte zurückgegeben. Wir können dies vermeiden, indem wir tzwei Listen einschließen.
  • dbestimmt, welche Zellen in der Ausgabe dargestellt werden. Standardmäßig werden alle t*rZellen abgerufen , die möglicherweise von der Regel betroffen sind (dh zusätzliche Zellen an beiden Enden der Eingabe). Wir geben es l-1, weil dies eine der wenigen Situationen in Mathematica ist, in denen ein auf Null basierender Index verwendet wird.
Martin Ender
quelle
6

Haskell, 86 83 81 79 73 71 Bytes

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

Anwendungsbeispiel: 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].

Es gibt nicht viel zu erklären: Wenn eine Zelle 0 ist, nimm das Maximum der Nachbarelemente. Wiederholen Sie die Eingabezeiten. Dazu iteriere ich xvia foldl, ignoriere aber das zweite Argument in p.

Edit: @Mauris hat 6 Bytes zum Speichern gefunden und @xnor weitere zwei. Vielen Dank!

nimi
quelle
Sie können ersetzen h pmit p!_dann ersetzen (const.h)mit (!)zu speichern 6 Byte.
Lynn
@ Mauris: Clever. Vielen Dank!
nimi
@nimi Ich denke die letzte Zeile anonymisiert sich zu id>>=foldl(!).
Xnor
@xnor: ja das tut es! Gut beobachtet!
Nimi
4

CJam, 27 24 Bytes

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

Teste es hier.

Dadurch wird ein unbenannter Block verschoben, der eine Liste auf dem Stapel in eine neue Liste umwandelt.

Erläuterung

_,       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
quelle
Das Umgehen der Konvergenz ist ein guter Trick
Luis Mendo
1
... was ich schamlos ausgeliehen habe :-)
Luis Mendo
4

J, 24 23 Bytes

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

Verwendung:

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

Die Methode ähnelt der von 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

Probieren Sie es hier online aus.

1 Byte gespart dank Zgarb.

randomra
quelle
3

Mathematica, 77 74 66 62 Bytes

12 Bytes gespart dank Martin Büttner.

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

J, 33 Bytes

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

Ein bisschen länger als ich es mir gewünscht hätte.

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
quelle
Das ist so anders als das, was ich habe, ich denke, Sie sollten es als Antwort posten :)
Lynn
3

Python 3.5, 83 Bytes

Diese Funktion erstellt eine Python-Liste mit ganzen Zahlen. Ich bin mir nicht sicher, ob es noch viel zu Golf zu tun gibt, aber ich würde es gerne schaffen, zumindest mit einer anderen Sprache konkurrenzfähig zu werden!

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

Von Python 3.5, PEP 448 lässt uns auspacken sin 0,*s. Frühere Releases erfordern ein Byte mehr:

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

Wir danken der Lösung und Erklärung von user81655, mit der ich feststellen konnte, dass ich nicht mehr testen muss, ob sich die Liste nicht mehr ändert. Ich muss nur oft genug iterieren, um sicherzugehen, dass alle Nullen abgedeckt wurden. (Die maximal erforderliche Anzahl von Iterationen ist eine weniger als die Länge der Liste. Dies führt eine Iteration mehr als das aus, da dies weniger Code benötigt.)

Tim Pederick
quelle
@ChrisH: Es funktioniert nicht auf Python 3.5, und ich glaube es auch nicht auf früheren Versionen funktionieren würde: nicht, die sie bewegen die returnzu innerhalb der for _ in sSchleife?
Tim Pederick
Kommentar gelöscht - Ich habe nur die Testfälle ausprobiert, die beim ersten Mal behoben wurden.
Chris H
3

Matlab, 90 Bytes

Wie wäre es mit einigen Windungen?

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

Beispiel

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

Haskell, 66 65 Bytes

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

Dies definiert eine aufgerufene Funktion f .

Erläuterung

Anstatt den zellularen Automaten zu iterieren, berechne ich die Endwerte direkt. Die Definition ist ein einzelnes Listenverständnis. Der Wert ireicht von 0bis length x - 1, da wir xmit den natürlichen Zahlen zip . Für jeden Index ierstellen wir die Liste der Listen mit zwei Elementen

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

Aus dieser Liste berechnen wir das maximale Element, dessen zweite Koordinate ungleich Null ist, und nehmen das zweite Element mit !!1. Dies gibt dem Index den nächstgelegenen Wert ungleich Null iund unterbricht die Bindung, indem der größere Wert verwendet wird.

Zgarb
quelle
Herzlichen Glückwunsch zum Gewinn der Prämie!
xnor
2

Lua, 133 Bytes

Zwei Loops, verschachtelte Ternaries ... Wenn ich weiter Golf spielen möchte, muss ich einen anderen Weg finden, aber ich sehe keinen.

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

Erklärungen

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

Der Teil

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

wird erweitert um 

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)

was in verschachtelt übersetzt werden kann ifals

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

Pyth, 17 Bytes

meeSe#.e,_akdbQUQ

Nimmt eine Liste im Python-Stil von stdin und gibt sie nach stdout aus.

Erläuterung

Dies ist im Grunde eine Übersetzung meiner Haskell-Antwort. Ich habe Pyth noch nie wirklich benutzt, daher sind Hinweise willkommen.

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

APL (Dyalog) , 18 Bytes

Anonyme implizite Präfixfunktion.

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

Probieren Sie es online!

(... )⍣≡ gilt die folgende stillschweigende Funktion , bis das Ergebnis auf das Argument identisch ist:

 ⊢ das Argument

 + Plus

  ~ nicht
  ∘ das
  × signum

 × mal

 3⌈/ die Maxima über jede Dreiergruppe von

 0, Null gefolgt von

  , das Argument gefolgt von
  ∘ einer
  0 Null

Adam
quelle
1

Java 8, 155 142 Bytes

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

Ändert die Eingabe, int[]anstatt eine neue zurückzugeben, um Bytes zu sparen.

Erläuterung:

Probieren Sie es hier aus.

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

Ruby, 81 Bytes

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

Ich denke, das Innere mapkönnte weiter golfen werden.

Harte Gupta
quelle
Ich habe gerade festgestellt, dass meine Antwort mit der Antwort von @ user81655 identisch ist .
Harsh Gupta
Ich denke, Sie können die Leerzeichen im Ternär, dh um ?und entfernen :.
Alex A.
0

PHP - 301 291 289 288 264 Zeichen

Ich habe keine anderen Antworten gefunden, bevor ich dies versucht habe. Beschuldige nicht die Sprache, beschuldige mich. Sehr angenehm und trotzdem herausfordernd. Alle Code Golf Ratschläge sehr geschätzt.

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

Erklärt

// 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;
Gans
quelle
1
Ernst? Beim Golfen werden nicht nur die Leerzeichen in Ihrem Code entfernt. Neben dem Algorithmus, sind hier einige Tipps: Verwenden Sie 1statt true, spliteher als explode, foranstatt while, joinanstatt implodenutzlose geschweiften Klammern entfernen, ...
Blackhole
Ich bin weiter explodiert, weil der Split abgeschrieben wird. Außerdem weiß ich nicht, wie man eine while-Schleife mit for schreibt. Deshalb habe ich sie vorerst beibehalten, es sei denn, hier kann jemand sein Wissen oder einen Link teilen. Danke euch allen.
Gans
0

Python, 71 Bytes

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

Das ziperstellt alle 3-Längen-Unterlisten eines Elements und seiner Nachbarn und behandelt diese über die Endpunkte hinaus als 0. Das zentrale Element l[1]einer Unterliste l, falls Null, wird durch das maxseiner Nachbarn mit ersetzt l[1]or max(l). Der l*all(l)gibt die Liste zurückl wenn er keine hat 0.

xnor
quelle
0

Ruby, 74 Bytes

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

funktioniert, indem die nächstgelegene Zahl ungleich Null ermittelt wird.

MegaTom
quelle
0

MATL , 38 Bytes

Direkte Übersetzung meiner Matlab-Antwort. Verwendet die aktuelle Version der Sprache / des Compilers.

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

Beispiel

>> 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: Probieren Sie es online! mit X+nach Y+und vnach &vaufgrund von Änderungen in der Sprache ersetzt.

Luis Mendo
quelle