Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
up vote 8 down vote accepted

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

share|improve this answer
    
That's one of longest cjam answers I have ever seen. =) – Dr Green Eggs and Iron Man Feb 2 at 3:20
2  
@DJMcGoathem Ummm... – Martin Ender Feb 2 at 7:33
    
Are '# and "#" different in CJam? – ETHproductions Feb 2 at 15:47
    
Yep, they are. "#" is equal to ['#]. – Lynn Feb 2 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>

share|improve this answer
1  
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 at 22:00
    
@edc65 Clever. Thanks! – user81655 Feb 2 at 22:51

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
share|improve this answer
    
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 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 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 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 at 14:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.