Label dead ends

Question

Given an input of an ASCII art "road," output the road with all dead ends labelled.

This is a road:

########.....######..#..###
#......#######....#..#..#.#
#.##......#...#####..#..###
#..#####..#....#..#######.#
#......#...#####.....##...#
#..###.#...#...###...#..###
##########.#..#..##..#.##.#
..#......#.######.#..#.#.#.
..#......#.#..#.#.#..#.#.#.
..######.###..##..#########

This is the road with dead ends labelled with the letter X:

########.....######..X..###
#......#######....#..X..#.#
#.XX......X...X####..X..###
#..XXXXX..X....#..#######.#
#......X...#####.....##...#
#..###.X...#...###...#..###
##########.#..X..##..#.##.X
..X......#.#XXXXX.#..#.#.X.
..X......#.#..X.X.#..#.#.X.
..XXXXXX.###..XX..######XXX

A dead end is defined as any road tile that borders n other road tiles, at least n-1 of which are considered dead ends already by this rule. "Bordering" is in the four cardinal directions, so tiles bordering diagonally don't count.

This rule is applied repeatedly, as newly created dead ends can, themselves, create more dead ends. Also note that any road tile that borders only one other road tile is considered a dead end the first time the rule is applied.

Input and output may be either a single string (with lines separated by any character that is not # or .) or an array/list/etc. If your language supports it, you may also take input with each line being a function argument.

You may assume the following about the input:

• There will always be at least one "loop"—that is, a group of # characters that can be followed infinitely. (Otherwise every single tile would become a dead end.)

• This implies that the input will always be 2×2 or larger, since the smallest loop is:

  ##
  ##
  

  (Which, incidentally, should be output with no change.)

• All # characters will be connected. That is, if you were to perform a flood fill on any #, all of them would be affected.

Since this is code-golf, the shortest code in bytes will win.

The example above and the tiny 2×2 grid can be used as test cases (there aren't a lot of edge cases to cover in this challenge).

Answer 1

CJam, 61 bytes

q_N/{{0f+zW%}4*3ew:z3few::z{e__4=_@1>2%'#e=*"#"='X@?}f%}@,*N*

Try it here.

Explanation

Outline:

    q_N/               Read input lines
        {   }@,*       Perform some operation as many times as there are bytes
                N*     Join lines

Operation:

    {0f+zW%}4*         Box the maze with zeroes
    3ew:z3few::z       Mystical 4D array neighborhood magic.
                       (Think: a 2D array of little 3x3 neighborhood arrays.)

    {                        }f%    For each neighborhood, make a new char:
     e_                                 Flatten the neighborhood
       _4=_                             Get the center tile, C
           @1>2%                        Get the surrounding tiles
                '#e=                    Count surrounding roads, n
                    *                   Repeat char C n times
                     "#"=               Is it "#"? (i.e., C = '# and n = 1)
                         'X@?           Then this becomes an 'X, else keep C.

(Martin saved two bytes, thanks!)

Answer 2

JavaScript (ES6), 110 109 bytes

r=>[...r].map(_=>r=r.replace(g=/#/g,(_,i)=>(r[i+1]+r[i-1]+r[i+l]+r[i-l]).match(g)[1]||"X"),l=~r.search`
`)&&r

1 byte saved thanks to @edc65!

Explanation

Very simple approach to the problem. Searches for each #, and if there are less than 2 #s around it, replaces it with an X. Repeats this process many times until it's guaranteed all the dead-ends have been replaced with Xs.

var solution =

r=>
  [...r].map(_=>                    // repeat r.length times to guarantee completeness
    r=r.replace(g=/#/g,(_,i)=>      // search for each # at index i, update r once done
      (r[i+1]+r[i-1]+r[i+l]+r[i-l]) // create a string of each character adjacent to i
      .match(g)                     // get an array of all # matches in the string
        [1]                         // if element 1 is set, return # (the match is a #)
        ||"X"                       // else if element 1 is undefined, return X
    ),
    l=~r.search`
`                                   // l = line length
  )
  &&r                               // return the updated r

<textarea id="input" rows="10" cols="40">########.....######..#..###
#......#######....#..#..#.#
#.##......#...#####..#..###
#..#####..#....#..#######.#
#......#...#####.....##...#
#..###.#...#...###...#..###
##########.#..#..##..#.##.#
..#......#.######.#..#.#.#.
..#......#.#..#.#.#..#.#.#.
..######.###..##..#########</textarea><br>
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

Answer 3

Python (3.5) 362 331 329 314 bytes

thanks to @Alissa. she helps me to win ~33 bytes

d='.'
r=range
def f(s):
 t=[list(d+i+d)for i in s.split()]
 c=len(t[0])
 u=[[d]*c]
 t=u+t+u
 l=len(t)
 g=lambda h,x:t[h][x]=='#'
 for k in r(l*c):
  for h in r(1,l):
   for x in r(1,c):
    if g(h,x) and g(h+1,x)+g(h-1,x)+g(h,x+1)+g(h,x-1)<2:
     t[h][x]='X'
 print('\n'.join([''.join(i[1:-1])for i in t][1:-1]))

Explanations

d='.'
r=range

Function definition

def f(s):

Add a border of '.' on right and left of the board

 t=[list(d+i+d)for i in s.split()]
 c=len(t[0])
 u=[[d]*c]

Add a border of '.' on top and bottom

 t=u+t+u
 l=len(t)

Lambda function to test '#'

 g=lambda h,x:t[h][x]=='#'

Loop on the input length to be sure we don't forget dead ends

 for k in r(l*c):

Loop on columns and lines

  for h in r(1,l):
   for x in r(1,c):

Test if we have '#' around and on the position

    if g(h,x) and g(h+1,x)+g(h-1,x)+g(h,x+1)+g(h,x-1)<2:

Replace '#' by 'X'

     t[h][x]='X'

Crop the border filled with '.' and join in string

 print('\n'.join([''.join(i[1:-1])for i in t][1:-1]))

Usage

f("########.....######..#..###\n#......#######....#..#..#.#\n#.##......#...#####..#..###\n#..#####..#....#..#######.#\n#......#...#####.....##...#\n#..###.#...#...###...#..###\n##########.#..#..##..#.##.#\n..#......#.######.#..#.#.#.\n..#......#.#..#.#.#..#.#.#.\n..######.###..##..#########")

########.....######..X..###
#......#######....#..X..#.#
#.XX......X...X####..X..###
#..XXXXX..X....#..#######.#
#......X...#####.....##...#
#..###.X...#...###...#..###
##########.#..X..##..#.##.X
..X......#.#XXXXX.#..#.#.X.
..X......#.#..X.X.#..#.#.X.
..XXXXXX.###..XX..######XXX