# Bacterial expansion

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>

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

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


## Mathematica, 77 bytes

Not very competitive compared with alephalpha's //. solution, but I figured a 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.

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

• You can replace h p with p!_ then replace (const.h) with (!) to save 6 bytes. – Lynn Dec 22 '15 at 16:58
• @Mauris: Clever. Thanks a lot! – nimi Dec 22 '15 at 17:09
• @nimi I think the last line anonymizes to id>>=foldl(!). – xnor Dec 22 '15 at 22:27
• @xnor: yes it does! Well spotted! – nimi Dec 22 '15 at 22:44

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

• Sidestepping convergence is a nice trick – Luis Mendo Dec 22 '15 at 16:39
• ... which I shamelessly borrowed :-) – Luis Mendo Dec 22 '15 at 17:05

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


Try it online here.

1 byte saved thanks to Zgarb.

# Mathematica, 777466 62 bytes

Saved 12 bytes thanks to Martin Büttner.

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


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

• That's so different from what I have, I think you should post it as an answer :) – Lynn Dec 23 '15 at 13:55

## 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.)

• @ChrisH: It doesn't work on Python 3.5, and I don't think it would work on earlier versions either: doesn't that move the return to inside the for _ in s loop? – Tim Pederick Dec 23 '15 at 11:32
• comment deleted -- I happened to only try the test cases that resolve first time. – Chris H Dec 23 '15 at 11:33

# Matlab, 90 bytes

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


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.

• Congrats on winning the bounty! – xnor Dec 31 '15 at 5:06

# 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


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


# 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

# 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


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

• Just realized, my answer is kinda identical to @user81655 's answer. – Harsh Gupta Dec 22 '15 at 11:47
• I think you can remove the spaces in the ternary, i.e. around ? and :. – Alex A. Dec 22 '15 at 16:45

## PHP - 301291289288 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;  • Seriously? Golfing isn't just removing the whitespaces in your code. Besides the algorithm, here are some tips: use 1 rather than true, split rather than explode, for rather than while, join rather than implode, remove useless curly brackets, … – Blackhole Dec 24 '15 at 1:57 • I kept explode because split is being depreciated. Also, I don't know how to write a while loop using for, so I kept it for now, unless someone here can share their knowledge or share a link. Thank you all. – Goose Dec 24 '15 at 14:23 ## 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. # 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. # 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.