Бактериальная экспансия

25

Колонии бактерий , меченные 1через 9живые на сегменте одинаково отстоящие друг от друга клеток, причем пустые ячейки обозначены0

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

Каждую секунду каждая колония распространяется на соседние пустые клетки. Если две колонии достигают пустой ячейки одновременно, колония, помеченная крупнее, забирает ее.

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

Колонии не могут распространяться за пределы границ. Колония никогда не перемещается другой колонией, поэтому, как только все пустые ячейки заполнены, больше ничего не меняется.

Учитывая начальное состояние, выведите или напечатайте конечное состояние. Используйте любой разумный список или формат строки. Вы не должны выводить какие-либо промежуточные состояния. Вход будет содержать как минимум одну бактериальную колонию.

Связанный: Закрой нули в списке . (Колонии распространяются только вправо.)

Тестовые случаи: вывод ниже ввода.

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-golf cellular-automata XNOR
источник

Ответы:

14

JavaScript (ES6), 66 62 байта

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

объяснение

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

Тест

Показать фрагмент кода

user81655
источник
10

Pyth, 18 байт

um|@d1eSd.:++0G03Q

Тестирование

Принимает ввод как список целых чисел.

По сути, для этого используется цикл применения до схождения u. Он применяет обновление, формируя все списки каждой ячейки и двух ячеек с каждой стороны, затем обновляя каждую обнуленную ячейку до максимума ее соседей.

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
источник
8

Mathematica, 77 байт

Не очень конкурентоспособный по сравнению с решением для alephalpha //., но я полагал, что у клеточного автомата должен быть CellularAutomatonответ:

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

Функция принимает тонну параметров ... давайте дадим им несколько имен:

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

Вот что они делают:

  • rэто диапазон правила, то есть он определяет, сколько соседей рассматривается для обновления. Мы хотим, чтобы по одному соседу с каждой стороны, поэтому мы используем 1.
  • nобычно это число или список цветов (разные типы ячеек), но если мы указываем правило как пользовательскую функцию вместо номера правила, так и должно быть {}.
  • fявляется функцией, определяющей правило обновления. Он принимает список из 3 ячеек (если r = 1) и возвращает новый цвет для средней ячейки.
  • iэто начальное условие. Это вход.
  • bэто фон. Если это не дано, CellularAutomatonиспользуются периодические границы, которые мы не хотим. Вместо этого использование 0накладывает мертвое граничное условие.
  • tколичество раз для симуляции. Нам не нужно больше шагов, чем широкий ввод, потому что после этого бактерии сойдутся, поэтому t = Length@#. Обычно CellularAutomatonвозвращает все промежуточные шаги. Этого можно избежать, свернув tв два списка.
  • dопределяет, какие ячейки представлены в выводе. По умолчанию мы получили бы все ячейки, которые могли бы потенциально быть затронуты правилом (то есть t*rдополнительные ячейки на любом конце ввода). Мы даем это l-1, потому что это одна из немногих ситуаций в Mathematica, где используется нулевой индекс.
Мартин Эндер
источник
6

Haskell, 86 83 81 79 73 71 байт

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

Пример использования: 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].

Ничего особенного объяснить: если ячейка равна 0, возьмите максимум соседних элементов. Повторите время ввода. Для этого я перебираю xчерез, foldlно игнорирую второй аргумент в p.

Изменить: @Mauris нашел 6 байтов для сохранения и @xnor еще два. Благодарность!

Ними
источник
Вы можете заменить h pна p!_затем заменить (const.h)на, (!)чтобы сохранить 6 байтов.
Линн
@Mauris: умный Большое спасибо!
Ними,
@nimi Я думаю, что последняя строка анонимизируется id>>=foldl(!).
xnor
@xnor: да, это так! Хорошо подмечено!
Ними
4

CJam, 27 24 байта

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

Проверьте это здесь.

Это выталкивает неназванный блок, который преобразует список в стеке в новый список.

объяснение

_,       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.
  }%
}*
Мартин Эндер
источник
Конвергенция между сторонами - хороший трюк
Луис Мендо,
1
... которую я беззастенчиво позаимствовал :-)
Луис Мендо
4

J 24 23 байта

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

Использование:

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

Метод похож на решение Мауриса .

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

Попробуйте это онлайн здесь.

1 байт сохранен благодаря Zgarb.

randomra
источник
3

Mathematica, 77 74 66 62 байта

Сохранено 12 байтов благодаря Мартину Бюттнеру.

#//.i_:>BlockMap[If[#2<1,Max@##,#2]&@@#&,Join[{0},i,{0}],3,1]&
alephalpha
источник
3

J, 33 байта

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

Чуть дольше, чем мне бы хотелось.

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.
Линн
источник
Это так сильно отличается от того, что у меня есть, я думаю, вы должны опубликовать это как ответ :)
Линн
3

Python 3.5, 83 байта

Эта функция принимает список целых чисел в Python. Не уверен, что гольфу еще многое осталось, но я бы хотел, чтобы он был конкурентоспособным по крайней мере с другим языком!

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

Начиная с Python 3.5, PEP 448 позволяет нам распаковывать sв 0,*s. Более ранние выпуски требуют дополнительного байта, например так:

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

Кредит решения и объяснения user81655 игровая за помощь мне понять , что мне не нужно , чтобы тест был ли список прекращал меняться; Мне просто нужно перебрать достаточное количество раз, чтобы убедиться, что все нули должны быть покрыты. (Максимальное количество необходимых итераций на единицу меньше длины списка; это делает на одну итерацию больше, потому что для этого требуется меньше кода.)

Тим Педерик
источник
@ChrisH: Это не работает на Python 3.5, и я не думаю , что он будет работать на более ранних версиях либо: не что перемещать returnк внутри в for _ in sцикле?
Тим Педерик
комментарий удален - мне довелось попробовать только те тестовые случаи, которые разрешаются в первый раз.
Крис Х,
3

Matlab, 90 байт

Как насчет некоторых извилин?

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

пример

>> 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
Луис Мендо
источник
3

Haskell, 66 65 байт

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

Это определяет вызываемую функцию f.

объяснение

Вместо итерации клеточного автомата я вычисляю окончательные значения напрямую. Определение - это понимание единого списка. Значение iварьируется от 0до length x - 1, так как мы сжимаем xс натуральными числами. Для каждого индекса iсоставляем список из 2-х элементов

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

Из этого списка мы вычисляем максимальный элемент, вторая координата которого отлична от нуля, и берем этот второй элемент с помощью !!1. Это дает ближайшему ненулевое значение индекса i, разрывая связи, принимая большее значение.

Zgarb
источник
Поздравляю с получением награды!
xnor
2

Lua, 133 байта

Две петли, вложенные троицы ... Если я захочу еще поиграть в гольф, мне придется найти другой способ сделать это, но я не вижу его.

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

Пояснения

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

Часть

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

будет расширен до 

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)

который может быть переведен во вложенный ifкак

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
источник
1

Pyth, 17 байт

meeSe#.e,_akdbQUQ

Принимает список в стиле Python из stdin, выводит в stdout.

объяснение

Это в основном перевод моего ответа на Haskell. Я на самом деле раньше не использовал Pyth, так что подсказки приветствуются.

                   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
источник
1

APL (Dyalog) , 18 байт

Функция анонимного молчаливого префикса.

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

Попробуйте онлайн!

(… )⍣≡ Применять следующую молчаливую функцию, пока результат не будет идентичен аргументу:

 ⊢ Аргумент

 + плюс

  ~ не  сигнум
  ∘
  ×

 × раз

 3⌈/ максимумы по каждой группе из трех

 0, ноль с последующим

  , аргумент следует
  ∘ в
  0 ноле

Адам
источник
1

Java 8, 155 142 байта

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

Изменяет ввод int[] вместо возврата нового, чтобы сохранить байты.

Объяснение:

Попробуй это здесь.

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
Кевин Круйссен
источник
0

Рубин, 81 байт

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

Я думаю, что внутренняя часть mapможет быть дальше в гольфе.

Суровая Гупта
источник
Только что понял, мой ответ в некотором роде идентичен ответу @ user81655 .
Суровая Гупта
Я думаю, что вы можете удалить пробелы в троичной, т.е. вокруг ?и :.
Алекс А.
0

PHP - 301 291 289 288 264 символов

Не пытался найти ответы на другие вопросы, прежде чем пытаться это сделать. Не вините язык, вините меня. Очень приятный и сложный, тем не менее. Весь кодекс совета по гольфу высоко ценится.

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

Разъяснения

// 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;
Гусь
источник
1
Шутки в сторону? Гольф - это не просто удаление пробелов в вашем коде. Кроме того, алгоритм, вот несколько советов: использование 1вместо true, splitа не explode, forа не while, joinа не implode, удалять ненужные фигурные скобки, ...
Blackhole
Я продолжал взрываться, потому что раскол обесценивается. Кроме того, я не знаю, как написать цикл while, используя for, поэтому я сохранил его пока, если кто-то здесь не может поделиться своими знаниями или поделиться ссылкой. Спасибо вам всем.
Гусь
0

Python, 71 байт

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

zipСоздает все длины 3 подсписков элемента и его соседей, лечение за пределами конечных точек как 0. Центральный элемент l[1]подсписка l, если он равен нулю, заменяется на maxсоседних с l[1]or max(l). В l*all(l)возвращает список , lкогда он не имеет 0«S.

XNOR
источник
0

Рубин, 74 байта

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

работает путем нахождения ближайшего ненулевого числа.

MegaTom
источник
0

MATL , 38 байт

Прямой перевод моего ответа Matlab. Использует текущую версию языка / компилятора.

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

пример

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

РЕДАКТИРОВАТЬ: попробуйте это онлайн! с X+заменен Y+и vна &v, из - за изменений , сделанных на языке.

Луис Мендо
источник