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


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

CJam, 61 bytes

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


Try it here.

Explanation

Outline:

{   }@,*       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
*                   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!)

• That's one of longest cjam answers I have ever seen. =) – James Feb 2 '16 at 3:20
• @DJMcGoathem Ummm... – Martin Ender Feb 2 '16 at 7:33
• Are '# and "#" different in CJam? – ETHproductions Feb 2 '16 at 15:47
• Yep, they are. "#" is equal to ['#]. – Lynn Feb 2 '16 at 17:34

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>

• Common trick that I use always for this type of task. As you use both l and -l in the same way, you can compute l=~r.search instead of l=1+r.search. (Just 1 byte saved) – edc65 Feb 2 '16 at 22:00
• @edc65 Clever. Thanks! – user81655 Feb 2 '16 at 22:51

Python (3.5) 362331329 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

• 1) use split() instead of splitlines(). 2) t=['.'*(c+2)]+['.'+i+'.'for i in s]+['.'*(c+2)] is shorter. And it can be shortened even more: d='.';t=[d*c]+t+[d*c];t=[d+i+d for i in t] 3) you don't need all the list(zip(....)) thing, use print('\n'.join([''.join(i[1:-1])for i in t]) – Alissa Feb 3 '16 at 10:40
• @Alissa thanks for your help i use your tips for point 1) and 3) but for the 2) i can't remove all bracket, we need a list of list of char and not a list of string because 'str' object does not support item assignment. the list of list allows me to use t[h][x]='X' – Erwan Feb 3 '16 at 12:29
• sorry, I missed the thing about string immutability. You can also move all constants (r, g and d) out of your function (saves you some tabulation). Maybe some playing around split() might help: t=[d+list(i)+d for i in s.split()], then calculate lengths, then add dot-lines to the end an to the beginning, and then alter your cycles to work with these extended lengths. Not sure if it will shorten the code, but it might – Alissa Feb 3 '16 at 13:54
• @Alissa i can't move the g out of the function because it use t i'll test your other comment – Erwan Feb 3 '16 at 14:18