Bacterial expansion

Question

Colonies of bacteria labelled 1 through 9 live on a segment of equally-spaced cells, with empty cells indicated by 0

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

Every second, each colony spreads to adjacent empty cells. If two colonies reach an empty cell at the same time, the larger-labeled colony takes it.

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  

The colonies cannot spread beyond the boundaries. A colony is never displaced by another colony, so once all empty cells are filled, nothing further changes.

Given the initial state, output or print the final state. Use any reasonable list or string format. You should not output any intermediate states. The input will contain at least one bacterial colony.

Related: Cover up zeroes in a list. (The colonies only spread to the right.)

Test cases: Output below input.

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

    var QUESTION_ID=64812,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/67346/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

    body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

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

Explanation

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

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

Cell numbers separated by spaces = <input type="text" id="input" value="7 0 3 0 0 0 0 0 8 0 9 1" />
<button onclick="result.textContent=solution(input.value.split(' ').map(n=>+n)).join(' ')">Go</button>
<pre id="result"></pre>

Answer 2

Pyth, 18 bytes

um|@d1eSd.:++0G03Q

Test suite

Takes input as a list of integers.

Essentially, this uses a apply until convergence loop, u. It applies the update by forming all lists of each cell and the two cells on either side, then updating each zeroed cell to the max of its neighbors.

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.

Answer 3

Mathematica, 77 bytes

Not very competitive compared with alephalpha's //. solution, but I figured a cellular-automata challenge should have a CellularAutomaton answer:

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

The function takes a ton of parameters... let's give them some names:

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

Here is what they do:

• r is the range of the rule, that is, it determines how many neighbours are considered for the update. We want one neighbour on each side, so we use 1.
• n is normally the number or list of colours (different cell types), but if we specify the rule as a custom function instead of a rule number, this should be {}.
• f is a function determining the update rule. It takes a list of 3 cells (if r = 1) and returns the new colour for the middle cell.
• i is the initial condition. That's the input.
• b is the background. If this isn't given, CellularAutomaton uses periodic boundaries, which we don't want. Instead using 0 imposes a dead boundary condition.
• t is the number of times to simulate. We don't need more steps than the input is wide, because after that the bacteria will have converged, so t = Length@#. Normally, CellularAutomaton returns all intermediate steps. We can avoid that by wrapping t in two lists.
• d determines which cells are presented in the output. By default, we would get all the cells that could potentially be affected by the rule (which is t*r additional cells on either end of the input). We give it l-1, because this is one of the few situations in Mathematica where a zero-based index is used.

Answer 4

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(!)

Usage example: 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].

Nothing much to explain: if a cell is 0, take the maximum of the neighbor elements. Repeat length-of-the-input times. For this I iterate over x via foldl but ignore the second argument in p.

Edit: @Mauris found 6 bytes to save and @xnor another two. Thanks!

Answer 5

CJam, 27 24 bytes

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

Test it here.

This pushes an unnamed block which transforms a list on the stack into a new list.

Explanation

_,       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.
  }%
}*

Answer 6

J, 24 23 bytes

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

Usage:

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

Method is similar to Mauris' solution.

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

Try it online here.

1 byte saved thanks to Zgarb.

Answer 7

Mathematica, 77 74 66 62 bytes

Saved 12 bytes thanks to Martin Büttner.

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

Answer 8

Python 3.5, 83 bytes

This function takes a Python list of integers. Not sure there's much left to golf, but I'd love to get it competitive with another language at least!

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

From Python 3.5, PEP 448 lets us unpack s into 0,*s. Earlier releases require one byte extra, like so:

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

Credit to user81655's solution and explanation for helping me realise that I don't need to test whether the list has stopped changing; I just need to iterate enough times to be sure all zeroes must have been covered. (The maximum number of iterations needed is one less than the length of the list; this does one iteration more than that, because that takes less code.)

Answer 9

J, 33 bytes

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

A bit longer than I would've liked.

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.

Answer 10

Matlab, 90 bytes

How about some convolutions?

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

Example

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

Answer 11

Haskell, 66 65 bytes

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

This defines a function called f.

Explanation

Instead of iterating the cellular automaton, I compute the final values directly. The definition is a single list comprehension. The value i ranges from 0 to length x - 1, since we zip x with the natural numbers. For each index i, we produce the list of 2-element lists

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

From this list, we compute the maximal element whose second coordinate is nonzero and take that second element with !!1. This gives the closest nonzero value to index i, breaking ties by taking the larger value.

Answer 12

Lua, 133 bytes

Two loops, nested ternaries... If I want to golf it further, I will have to find an other way to do it, but I don't see one.

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

Explanations

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

The part

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

will be expanded to

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) 

which can be translated in nested if as

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

Answer 13

APL (Dyalog), 18 bytes

Anonymous tacit prefix function.

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

Try it online!

(…)⍣≡ apply the following tacit function until the result is identical to the argument:

 ⊢ the argument

 + plus

  ~ not
  ∘ the
  × signum

 × times

 3⌈/ the maxima over each group of three of

 0, zero followed by

  , the argument followed by
  ∘ a
  0 zero

Answer 14

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

Modifies the input int[] instead of returning a new one to save bytes.

Explanation:

Try it here.

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

Answer 15

Pyth, 17 bytes

meeSe#.e,_akdbQUQ

Takes a Python-style list from stdin, outputs to stdout.

Explanation

This is basically a translation of my Haskell answer. I haven't really used Pyth before, so hints are welcome.

                   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

Answer 16

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

I think the inner map could be further golfed.

Answer 17

PHP - 301 291 289 288 264 Characters

Didn't peak at other answers before attempting this. Don't blame the language, blame me. Very enjoyable and challenging non the less. All code golf advice heavily appreciated.

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

Explained

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

Answer 18

MATL, 38 bytes

Direct translation of my Matlab answer. Uses current version of language/compiler.

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

Example

>> 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: Try it online! with X+ replaced by Y+ and v by &v, owing to changes done in the language.

Answer 19

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

The zip creates all length-3 sublists of an element and its neighbors, treating beyond the endpoints as 0. The central element l[1] a sublist l, if zero, is replaced by the max of its neighbors with l[1]or max(l). The l*all(l) returns the list l when it has no 0's.

Answer 20

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

works by finding the closest non-zero number.