ASCII-Art Zombie Invasion Simulation

Question

To simulate a zombie invasion, start with a grid of # and representing the map:

##   ##
###   #
## ##  
  # ###
#  ####

• # represents land.
• represents water.

The zombies start at a point on the map...

##   ##
###   #
## %#  
  # ###
#  ####

...and spread. % denotes land infected by zombies.

However, zombies cannot swim. They can move across land in the same way a king moves in chess - one square in any diagonal or orthogonal direction:

!!!
!%!
!!!

At the end of the simulation, some land will be infected with zombies:

%%   ##
%%%   #
%% %%  
  % %%%
#  %%%%

Your task is to simulate the zombie invasion. Write a program (or function) that takes as input a string representing the initial state of the grid, and two numbers representing the coordinates of the initial zombie. The program should output (or return) the final state of the invasion.

Specifications

• Your program may print an optional trailing newline.
• You can assume the input will be in the correct format (padded with spaces), with an optional trailing newline.
• You can assume the initial zombie will start on land and will not die immediately.
• This is code-golf, so the shortest answer (in bytes) wins.
• -100% bonus if your code can also solve the Halting Problem for arbitrary Turing machines.
• Your program should handle board widths of up to 50 chars.

Answer 1

Kotlin, 283 218 bytes

Unnamed lambda (with a nested function, heh).

Golfed

{i:String,x:Int,y:Int->val m=i.lines().map{it.toCharArray()};fun v(x:Int,y:Int){try{if(m[y][x]=='#'){m[y][x]='%';for(c in-1..1)for(d in-1..1)if(!(c==0&&d==0))v(x+c,y+d)}}catch(e:Exception){}};v(x, y);m.map(::println)}

Ungolfed

fun zombies(input: String, startX: Int, startY: Int) {
    val m = input.lines().map(String::toCharArray)      // build game map
    fun invade(x: Int, y: Int) {                        // nested functions, woo!
        try {
            if (m[y][x] == '#') {                       // if land
                m[y][x] = '%'                           // mark as invaded
                for (dx in -1..1) {                      // generate neighbour tiles
                    for (dy in -1..1) {
                        if (!(dx == 0 && dy == 0)) {
                            invade(x + dx, y + dy)        // attempt to invade neighbours
                        }
                    }
                }
            }
        } catch(e: Exception) {}                        // catches ArrayIndexOutOfBounds
    }

    invade(startX, startY)                              // start the invasion
    m.map(::println)                                    // print final state
}

Saved quite a few bytes by switching to a recursive solution.

Answer 2

JavaScript (ES6), 144 bytes

(s,x,y,l=s.search`\n`,g=s=>s==(s=s.replace(eval(`/(#|%)(.?[^]{${l-1}}.?)?(?!\\1)[#%]/`),`%$2%`))?s:g(s))=>g(s.slice(0,x+=y*l)+`%`+s.slice(x+1))

Where \n represents the literal newline character. Takes 0-indexed coordinates.

Answer 3

Befunge, 324 323 bytes

&00p&10p20p~$v<p02+g02*!g02:+1$$$$<
 #<%>\"P"/8+p>1+:::~:0`!#v_:85+`!#^_2%\2%3*1+*\2/:"P"%\"P"/8+g+\2/:"P"
:+**73"="+g00*g02g010$$$$<v
02:\-<v/"P"\%"P":/2::_|#:$<:+1+g02\+g02:\-1+g02:\+1:\-1:\+1-g
\:20g^>g:30p\2%3*1+/4%1->#^_::2%6*2+30g+\2/:"P"%\"P"/p:20g-1-
0<v2\g+8/"P"\%"P":/2::<\_@#`0:-g
2^>%3*1+/4%1g,1+:20g%#^_1+55+,\

Try it online!

Explanation

Implementing this in Befunge was a little bit complicated because we're limited to 80x25 characters of "memory" which has to be shared with the source code itself. The trick to fitting a 50x50 map into that area was to flatten the 2D map into a 1D array with two map locations per byte. This 1D array is then wrapped into a 2D array again so that it can fit in the 80 character width of the Befunge playfield.

The infection algorithm starts by converting the initial coordinates into an offset in the 1D array which it pushes onto the stack. The main loop takes a value from the stack and looks up the map state for that offset. If it's uninfected land, it gets marked as infected, and eight new offsets are pushed onto the stack (representing the land all around the current position). This process continues until the stack is empty.

To avoid having to check for out of range values, the map is stored with a one character water border around all the edges.

Answer 4

APL (Dyalog), 44 bytes

{{c'%'[⌊⌿'%#'∊¨⍵(c←4⊃⍵)]}∘,⌺3 3⍣≡'%'@(⊂⍺)⊢⍵}

Try it online!

Assumes ⎕IO←0.

Left argument: 0-indexed row r of %, 0-indexed column c of %: r c
Right argument: Character matrix

Answer 5

Pip, 59 bytes

{(ac+b+b*Ya@?n):'%L2*#aa:RVaR.`#(.?.?.{`.y-1.`})?%`'%.@>_a}

A function that takes a multiline string, the row of the initial zombie (0-indexed), and the column of the initial zombie (0-indexed). Try it online!

How?

Because Pip has cyclical indexing (usually a good thing, but bad for this problem because we don't want the map edges to wrap), I went for a regex-replacement solution.

Ya@?n finds the index of the first newline (i.e. the width of the grid) and yanks it into y.

(ac+b+b*Ya@?n):'% after doing the above, computes (width + 1) * row + col, i.e. c+b+b*y, and sets the character at that index to %.

L2*#a loops 2*len(a) times, which gives us enough iterations for the flood fill to fully propagate and makes sure the iteration count is even (that's important).

.`#(.?.?.{`.y-1.`})?%` constructs a regex that matches a # followed by a %, with either 0, width-1, width, or width+1 characters in between. (The . at the beginning makes . in the regex match newlines.) This regex matches any of the following configurations:

#  
 % 

 # 
 % 

  #
 % 

#% 

aR ... '%.@>_ replaces matches of this regex with the character % prepended to . all but the first character @> of the match _; in short, replacing the # with %.

a:RV ... reverses that and assigns it back to a. We reverse because the regex only matches # before % in the string, not after; but when the string is reversed, after becomes before and we can match it on the next iteration. This is also why the number of iterations has to be even.

After the loop is complete, we simply return the modified value of a.

Answer 6

TSQL, 267 bytes

Golfed:

USE master
DECLARE @ varchar(max)=
'##   ##
###   #
## %#  
  # ###
#  ####'
    
WHILE @@rowcount>0WITH C as(SELECT x+1i,substring(@,x+1,1)v,x/z r,x%z c
FROM spt_values CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
WHERE type='P'and x<len(@))SELECT @=stuff(@,d.i,1,'%')FROM C,C D
WHERE'#%'=d.v+c.v and abs(c.r-d.r)<2and abs(c.c-d.c)<2PRINT @

Ungolfed:

USE master-- the script needs to be executed on the default master database
DECLARE @ varchar(max)=
'##   ##
###   #
## %#  
  # ###
#  ####'
    
WHILE @@rowcount>0
WITH C as
(
  SELECT x+1i,substring(@,x+1,1)v,x/z r,x%z c
  FROM
    spt_values
  CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
  WHERE type='P'and x<len(@)
)
SELECT @=stuff(@,d.i,1,'%')FROM C,C D
WHERE'#%'=d.v+c.v and abs(c.r-d.r)<2and abs(c.c-d.c)<2

PRINT @

Try it out

Answer 7

PHP, 209 189 188 183 bytes

may be golfable

for($w=strpos($s=($a=$argv)[1],10),$s[$a[2]*++$w+$a[3]]="%";$t<$s;)for($t=$s,$i=0;""<$c=$s[$i++];)if($c>"$")for($y=-2;++$y<2;)for($x=3;$x--;)$s[$p=$i+$y*$w-$x]>"!"?$s[$p]="%":0;echo$s;

Run with php -r '<code>' '<grid>' <y> <x>

Answer 8

J, 152 Bytes

Not very well golfed, I'm sure there's a way to remove those last few control structures.

f=:4 :0
c=.(' '"_)`({~&<y)@.((*./y<$x)*.*./y>:0 0)x if.c='#' do.x=.'%'(<y)}x[i=.0 while.i<9 do.i=.>:i[x=.x f y+i<:@(|~,<.@%)3 end.end.x
)
g=:>@cutLF@[f]

Implements a flood fill algorithm. The function g formats input into a character array before applying f.

Note that coordinates are a bit weird:

0, 0

is the top left corner. Increasing the first coordinate:

1, 0

Moves the position down in the y direction.

Other than that coordinates are normal.

Example:

    land =: 0 : 0    NB. Define a multi-line string
##   ##
###   #
## ##  
  # ###
#  ####
)

    ] l =. >@cutLF land    NB. Cut 'land' on new lines, and form into an array. Assign to 'l'
##   ##
###   #
## ##  
  # ###
#  ####
    NB. Looks the same, but it isn't.

    '%' (<2 3)} l    NB. 'Infect' the land at 2, 3
##   ##
###   #
## %#  
  # ###
#  ####

    l f 2 3    NB. Flood fill on l (already formatted), starting at 2 3
%%   ##
%%%   #
%% %%  
  % %%%
#  %%%%

    land g 2 3    NB. Flood fill on land, formats for us.
%%   ##
%%%   #
%% %%  
  % %%%
#  %%%%