Expansion bactérienne

25

Colonies de bactéries marquées 1en 9direct sur un segment de cellules également espacées, avec des cellules vides indiquées par0

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

Chaque seconde, chaque colonie se propage aux cellules vides adjacentes. Si deux colonies atteignent une cellule vide en même temps, la colonie à plus gros marqueur la prend.

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

Les colonies ne peuvent pas s'étendre au-delà des frontières. Une colonie n'est jamais déplacée par une autre colonie, donc une fois que toutes les cellules vides sont remplies, plus rien ne change.

Étant donné l'état initial, affichez ou imprimez l'état final. Utilisez une liste ou un format de chaîne raisonnable. Vous ne devez pas générer d'états intermédiaires. L'entrée contiendra au moins une colonie bactérienne.

Connexes: dissimulez des zéros dans une liste . (Les colonies ne s'étendent que vers la droite.)

Cas de test: sortie sous l'entrée.

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

Afficher l'extrait de code

code-golf cellular-automata xnor
la source

Réponses:

14

JavaScript (ES6), 66 62 octets

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

Explication

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

Tester

Afficher l'extrait de code

user81655
la source
10

Pyth, 18 octets

um|@d1eSd.:++0G03Q

Suite de tests

Prend l'entrée comme une liste d'entiers.

Essentiellement, cela utilise une boucle d'application jusqu'à convergence, u . Il applique la mise à jour en formant toutes les listes de chaque cellule et des deux cellules de chaque côté, puis en mettant à jour chaque cellule mise à zéro au maximum de ses voisins.

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
la source
8

Mathematica, 77 octets

Pas très compétitif par rapport à la //.solution alephalpha , mais j'ai pensé qu'un défi cellulaire-automate devrait avoir une CellularAutomatonréponse:

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

La fonction prend une tonne de paramètres ... donnons-leur quelques noms:

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

Voici ce qu'ils font:

  • rest la plage de la règle, c'est-à-dire qu'elle détermine le nombre de voisins pris en compte pour la mise à jour. Nous voulons un voisin de chaque côté, nous utilisons donc1 .
  • n est normalement le nombre ou la liste des couleurs (différents types de cellules), mais si nous spécifions la règle comme une fonction personnalisée au lieu d'un numéro de règle, cela devrait être {} .
  • fest une fonction déterminant la règle de mise à jour. Il faut une liste de 3 cellules (sir = 1 ) et renvoie la nouvelle couleur pour la cellule du milieu.
  • iest la condition initiale. Voilà l'entrée.
  • best l'arrière-plan. Si ce n'est pas donné,CellularAutomaton utilise des limites périodiques, ce que nous ne voulons pas. Au lieu de cela, l'utilisation 0impose une condition limite morte.
  • test le nombre de fois à simuler. Nous n'avons pas besoin de plus d'étapes que l'entrée est large, car après cela, les bactéries auront convergé, donc t = Length@#. Normalement,CellularAutomaton renvoie toutes les étapes intermédiaires. Nous pouvons éviter cela en encapsulant tdans deux listes.
  • ddétermine quelles cellules sont présentées dans la sortie. Par défaut, nous obtiendrions toutes les cellules qui pourraient potentiellement être affectées par la règle (qui sont t*rdes cellules supplémentaires à chaque extrémité de l'entrée). Nous le donnons l-1, car c'est l'une des rares situations dans Mathematica où un index de base zéro est utilisé.
Martin Ender
la source
6

Haskell, 86 83 81 79 73 71 octets

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

Exemple d'utilisation: 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].

Rien à expliquer: si une cellule vaut 0, prenez le maximum des éléments voisins. Répétez la durée de l'entrée. Pour cela, je répète xvia foldlmais j'ignore le deuxième argument de p.

Edit: @Mauris a trouvé 6 octets à enregistrer et @xnor deux autres. Merci!

nimi
la source
Vous pouvez remplacer h ppar p!_puis remplacer (const.h)par (!)pour économiser 6 octets.
Lynn
@Mauris: intelligent. Merci beaucoup!
nimi
@nimi Je pense que la dernière ligne rend anonyme id>>=foldl(!).
2015
@xnor: oui c'est le cas! Bien repéré!
nimi
4

CJam, 27 24 octets

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

Testez-le ici.

Cela pousse un bloc sans nom qui transforme une liste de la pile en une nouvelle liste.

Explication

_,       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
la source
Ignorer la convergence est un bon truc
Luis Mendo
1
... que j'ai emprunté sans vergogne :-)
Luis Mendo
4

J, 24 23 octets

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

Usage:

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

La méthode est similaire à la solution de 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

Essayez-le en ligne ici.

1 octet économisé grâce à Zgarb.

randomra
la source
3

Mathematica, 77 74 66 62 octets

Enregistré 12 octets grâce à Martin Büttner.

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

J, 33 octets

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

Un peu plus longtemps que je ne l'aurais souhaité.

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
la source
C'est tellement différent de ce que j'ai, je pense que vous devriez le poster comme réponse :)
Lynn
3

Python 3.5, 83 octets

Cette fonction prend une liste Python d'entiers. Je ne suis pas sûr qu'il reste beaucoup de golf, mais j'adorerais le rendre compétitif avec une autre langue au moins!

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

A partir de Python 3.5, PEP 448 nous permet de déballer sen 0,*s. Les versions antérieures nécessitent un octet supplémentaire, comme ceci:

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

Nous remercions la solution et l'explication de user81655 pour m'avoir aidé à réaliser que je n'ai pas besoin de tester si la liste a cessé de changer; J'ai juste besoin d'itérer suffisamment de fois pour être sûr que tous les zéros doivent avoir été couverts. (Le nombre maximal d'itérations nécessaires est inférieur de un à la longueur de la liste; cela fait une itération de plus que cela, car cela prend moins de code.)

Tim Pederick
la source
@ChrisH: Il ne fonctionne pas sur Python 3.5, et je ne pense pas que cela fonctionnerait sur les versions antérieures soit: ne pas déplacer la returnà l' intérieur de la for _ in sboucle?
Tim Pederick
commentaire supprimé - il m'est arrivé d'essayer uniquement les cas de test qui résolvent la première fois.
Chris H
3

Matlab, 90 octets

Et quelques circonvolutions?

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

Exemple

>> 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
la source
3

Haskell, 66 65 octets

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

Ceci définit une fonction appelée f.

Explication

Au lieu d'itérer l'automate cellulaire, je calcule directement les valeurs finales. La définition est une compréhension de liste unique. La valeur ivarie de 0à length x - 1, car nous zippons xavec les nombres naturels. Pour chaque index i, nous produisons la liste des listes à 2 éléments

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

À partir de cette liste, nous calculons l'élément maximal dont la deuxième coordonnée est non nulle et prenons ce deuxième élément avec !!1. Cela donne la valeur non nulle la plus proche de l'index i, rompant les liens en prenant la plus grande valeur.

Zgarb
la source
Félicitations pour avoir gagné la prime!
2015 à 5h06
2

Lua, 133 octets

Deux boucles, ternaires imbriqués ... Si je veux continuer à jouer au golf, je devrai trouver une autre façon de le faire, mais je n'en vois pas.

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

Explications

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

La partie

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

sera étendu à 

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)

qui peut être traduit en imbriqué if comme

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
la source
1

Pyth, 17 octets

meeSe#.e,_akdbQUQ

Prend une liste de style Python de stdin, sort vers stdout.

Explication

Il s'agit essentiellement d'une traduction de ma réponse Haskell. Je n'ai pas vraiment utilisé Pyth auparavant, donc les astuces sont les bienvenues.

                   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
la source
1

APL (Dyalog) , 18 octets

Fonction de préfixe tacite anonyme.

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

Essayez-le en ligne!

(… )⍣≡ Appliquez la fonction tacite suivante jusqu'à ce que le résultat soit identique à l'argument:

 ⊢ l'argument

 + plus

  ~ pas
  ∘ le
  × signum

 × fois

 3⌈/ les maxima sur chaque groupe de trois

 0, zéro suivi de

  , l'argument suivi d'
  ∘ un
  0 zéro

Adam
la source
1

Java 8, 155 142 octets

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

Modifie l'entrée int[] au lieu d'en renvoyer une nouvelle pour enregistrer les octets.

Explication:

Essayez-le ici.

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
la source
0

Rubis, 81 octets

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

Je pense que l'intérieur mappourrait être encore golfé.

Harsh Gupta
la source
Je viens de me rendre compte que ma réponse est un peu identique à la réponse de @ user81655 .
Harsh Gupta
Je pense que vous pouvez supprimer les espaces dans le ternaire, c'est-à-dire autour ?et :.
Alex A.
0

PHP - 301 291 289 288 264 Caractères

N'a pas atteint d'autres réponses avant de tenter cela. Ne blâmez pas la langue, blâmez-moi. Très agréable et stimulant non moins. Tous les conseils de golf de code fortement appréciés.

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

Expliqué

// 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;
OIE
la source
1
Sérieusement? Le golf ne consiste pas seulement à supprimer les espaces blancs de votre code. Outre l'algorithme, voici quelques conseils: utilisez 1plutôt que true, splitplutôt que explode, forplutôt que while, joinplutôt que implode, supprimez les accolades inutiles,…
Blackhole
J'ai continué à exploser parce que le split est déprécié. De plus, je ne sais pas comment écrire une boucle while en utilisant for, donc je l'ai gardée pour l'instant, à moins que quelqu'un ici ne puisse partager ses connaissances ou partager un lien. Merci à tous.
Goose
0

Python, 71 octets

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

Le zipcrée toutes les sous-listes de longueur 3 d'un élément et de ses voisins, en traitant au-delà des points finaux comme 0. L'élément central l[1]une sous-listel , s'il est nul, est remplacé par le maxde ses voisins avec l[1]or max(l). La l*all(l)renvoie la liste lquand elle n'a pas 0de.

xnor
la source
0

Rubis, 74 octets

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

fonctionne en trouvant le nombre non nul le plus proche.

MegaTom
la source
0

MATL , 38 octets

Traduction directe de ma réponse Matlab. Les usages la version actuelle du langage / compilateur.

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

Exemple

>> 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: Essayez-le en ligne! avec X+remplacé par Y+et vpar &v, en raison des modifications apportées à la langue.

Luis Mendo
la source