Expansión bacteriana

25

Las colonias de bacterias marcadas 1en 9vivo viven en un segmento de células igualmente espaciadas, con células vacías indicadas por0

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

Cada segundo, cada colonia se propaga a celdas vacías adyacentes. Si dos colonias alcanzan una celda vacía al mismo tiempo, la colonia etiquetada más grande la toma.

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

Las colonias no pueden extenderse más allá de los límites. Una colonia nunca es desplazada por otra, así que una vez que se llenan todas las celdas vacías, nada cambia más.

Dado el estado inicial, imprime o imprime el estado final. Utilice cualquier lista razonable o formato de cadena. No debe generar ningún estado intermedio. La entrada contendrá al menos una colonia bacteriana.

Relacionado: Cubrir ceros en una lista . (Las colonias solo se extienden hacia la derecha).

Casos de prueba: salida por debajo de la entrada.

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

Mostrar fragmento de código

code-golf cellular-automata xnor
fuente

Respuestas:

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

Explicación

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

Prueba

Mostrar fragmento de código

usuario81655
fuente
10

Pyth, 18 bytes

um|@d1eSd.:++0G03Q

Banco de pruebas

Toma entrada como una lista de enteros.

En esencia, este utiliza un bucle hasta que se aplican convergencia, u. Aplica la actualización formando todas las listas de cada celda y las dos celdas a cada lado, luego actualiza cada celda puesta a cero al máximo de sus vecinos.

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

Mathematica, 77 bytes

No es muy competitivo en comparación con la //.solución de alephalpha , pero pensé que un desafío de autómatas celulares debería tener una CellularAutomatonrespuesta:

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

La función toma una tonelada de parámetros ... démosles algunos nombres:

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

Esto es lo que hacen:

  • res el rango de la regla, es decir, determina cuántos vecinos se consideran para la actualización. Queremos un vecino a cada lado, así que usamos 1.
  • nnormalmente es el número o la lista de colores (diferentes tipos de celdas), pero si especificamos la regla como una función personalizada en lugar de un número de regla, debería serlo {}.
  • fes una función que determina la regla de actualización. Toma una lista de 3 celdas (si r = 1) y devuelve el nuevo color para la celda del medio.
  • iEs la condición inicial. Esa es la entrada.
  • bes el fondo Si esto no se da, CellularAutomatonutiliza límites periódicos, que no queremos. En cambio, el uso 0impone una condición de límite muerto.
  • tes la cantidad de veces que se simula No necesitamos más pasos que la entrada es amplia, porque después de eso la bacteria habrá convergido, entonces t = Length@#. Normalmente, CellularAutomatondevuelve todos los pasos intermedios. Podemos evitar eso envolviendo tdos listas.
  • ddetermina qué celdas se presentan en la salida. Por defecto, obtendríamos todas las celdas que potencialmente podrían verse afectadas por la regla (que son t*rceldas adicionales en cualquier extremo de la entrada). Lo damos l-1, porque esta es una de las pocas situaciones en Mathematica donde se usa un índice basado en cero.
Martin Ender
fuente
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(!)

Ejemplo de uso: 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].

No hay mucho que explicar: si una celda es 0, tome el máximo de los elementos vecinos. Repita los tiempos de longitud de la entrada. Para esto, itero a xtravés de foldlpero ignoro el segundo argumento en p.

Editar: @Mauris encontró 6 bytes para guardar y @xnor otros dos. ¡Gracias!

nimi
fuente
Puede reemplazar h pcon p!_luego reemplazar (const.h)con (!)para guardar 6 bytes.
Lynn
@Mauris: inteligente. ¡Muchas gracias!
nimi
@nimi Creo que la última línea anonimiza id>>=foldl(!).
xnor
@xnor: sí lo hace! ¡Bien descrito!
nimi
4

CJam, 27 24 bytes

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

Pruébalo aquí.

Esto empuja un bloque sin nombre que transforma una lista en la pila en una nueva lista.

Explicación

_,       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
fuente
La convergencia lateral es un buen truco
Luis Mendo
1
... que presté descaradamente :-)
Luis Mendo
4

J, 24 23 bytes

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

Uso:

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

El método es similar a la solución 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

Pruébelo en línea aquí.

1 byte guardado gracias a Zgarb.

randomra
fuente
3

Mathematica, 77 74 66 62 bytes

Guardado 12 bytes gracias a Martin Büttner.

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

J, 33 bytes

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

Un poco más de lo que me hubiera gustado.

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
fuente
Eso es muy diferente de lo que tengo, creo que deberías publicarlo como respuesta :)
Lynn
3

Python 3.5, 83 bytes

Esta función toma una lista de enteros de Python. No estoy seguro de que quede mucho para el golf, ¡pero al menos me encantaría hacerlo competitivo con otro idioma!

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 nos permite deshacer las maletas sen 0,*s. Las versiones anteriores requieren un byte extra, de esta manera:

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

El crédito a la solución y la explicación de user81655 por ayudarme a darse cuenta de que no necesito a prueba si la lista ha dejado de cambiar; Solo necesito iterar suficientes veces para asegurarme de que todos los ceros deben haber sido cubiertos. (El número máximo de iteraciones necesarias es uno menos que la longitud de la lista; esto hace una iteración más que eso, porque eso requiere menos código).

Tim Pederick
fuente
@ChrisH: No funciona en Python 3.5, y tampoco creo que funcione en versiones anteriores: ¿eso no se mueve returnal interior del for _ in sbucle?
Tim Pederick el
comentario eliminado: solo probé los casos de prueba que se resuelven por primera vez.
Chris H
3

Matlab, 90 bytes

¿Qué tal algunas convoluciones?

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

Ejemplo

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

Haskell, 66 65 bytes

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

Esto define una función llamada f.

Explicación

En lugar de iterar el autómata celular, calculo los valores finales directamente. La definición es una lista única de comprensión. El valor ivaría de 0a length x - 1, ya que comprimimos xcon los números naturales. Para cada índice i, producimos la lista de listas de 2 elementos

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

A partir de esta lista, calculamos el elemento máximo cuya segunda coordenada no es cero y tomamos ese segundo elemento con !!1. Esto proporciona el valor distinto de cero más cercano al índice i, rompiendo lazos al tomar el valor más grande.

Zgarb
fuente
¡Felicidades por ganar la recompensa!
xnor
2

Lua, 133 bytes

Dos bucles, ternar anidados ... Si quiero seguir jugando al golf, tendré que encontrar otra forma de hacerlo, pero no veo una.

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

Explicaciones

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 parte

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

se ampliará a 

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)

que se puede traducir en anidado ifcomo

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

Pyth, 17 bytes

meeSe#.e,_akdbQUQ

Toma una lista de estilo Python de stdin, salidas a stdout.

Explicación

Esto es básicamente una traducción de mi respuesta de Haskell. Realmente no he usado Pyth antes, así que las sugerencias son bienvenidas.

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

APL (Dyalog) , 18 bytes

Función de prefijo tácito anónimo.

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

Pruébalo en línea!

(... )⍣≡ aplique la siguiente función tácita hasta que el resultado sea idéntico al argumento:

 ⊢ el argumento

 + más

  ~ no
  ∘ el
  × signum

 × veces

 3⌈/ los máximos sobre cada grupo de tres de

 0, cero seguido de

  , el argumento seguido de
  ∘ un
  0 cero

Adán
fuente
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;}

Modifica la entrada en int[]lugar de devolver una nueva para guardar bytes.

Explicación:

Pruébalo aquí.

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
fuente
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]}

Creo que el interior mappodría ser más golfizado.

Harup Gupta
fuente
Acabo de darme cuenta, mi respuesta es un poco idéntica a la respuesta de @ user81655 .
Harsh Gupta
Creo que puede eliminar los espacios en el ternario, es decir, alrededor ?y :.
Alex A.
0

PHP - 301 291 289 288 264 caracteres

No alcanzó su punto máximo en otras respuestas antes de intentar esto. No culpes al lenguaje, culpame a mí. Muy agradable y desafiante, no obstante. Todos los consejos de golf de código muy apreciados.

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

Explicado

// 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;
ganso
fuente
1
¿Seriamente? Jugar al golf no es solo eliminar los espacios en blanco en su código. Además del algoritmo, aquí hay algunos consejos: use en 1lugar de true, en splitlugar de explode, en forlugar de while, en joinlugar de implode, elimine las llaves inútiles, ...
Blackhole
Seguí explotando porque la división se está depreciando. Además, no sé cómo escribir un bucle while usando for, así que lo guardé por ahora, a menos que alguien aquí pueda compartir sus conocimientos o compartir un enlace. Gracias a todos.
Goose
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])])

El zipcrea todas longitud-3 sublistas de un elemento y sus vecinos, el tratamiento más allá de los criterios de valoración como 0. El elemento central de l[1]una sublista l, si es cero, se reemplaza por el maxde sus vecinos con l[1]or max(l). El l*all(l)devuelve la lista lcuando no tiene 0's.

xnor
fuente
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]]}]}}

funciona encontrando el número distinto de cero más cercano.

MegaTom
fuente
0

MATL , 38 bytes

Traducción directa de mi respuesta de Matlab. Utiliza la versión actual del idioma / compilador.

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

Ejemplo

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

EDITAR: ¡ Pruébelo en línea! con X+reemplazado por Y+y vpor &v, debido a los cambios realizados en el idioma.

Luis Mendo
fuente