15
\$\begingroup\$

So, here's a map of, let's say, a dungeon...

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

Let's say that the hero is in Room A (at the top left) and their goal (a prince in distress?) is in Room B (to the bottom right). Our map does not allow the hero to progress to their goal.

We need to add a passageway...

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

There, much better!


Rules

  • A program or function which accepts a dungeon map (made up of hashes and spaces, with rows separated by new line characters).
  • It will output a map with dots added to denote passages in all spaces which are on a direct path between the space characters.
  • It will not change the line length, or number of lines.
  • Passages are all in a direct line from spaces to spaces.
    • Passages can not turn around corners
    • They will not be between spaces and the edge of the map.
  • Use any language.
  • Attempt to perform the conversion in the fewest bytes.
  • If no passageways can be drawn, return the map, unchanged.
  • The map should always have hashes around all edges (You do not need to handle spaces at the edge).
  • Input maps are always rectangular, each row should be the same width.

Test cases

####       ####
#  #   =>  #  #
#  #       #  #
####       ####

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        ####.#####
##########    =>  ####.#####
##########        ####.##### 
##########        ####.#####
####    ##        ####    ##
####    ##        ####    ##
##########        ##########

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        ##########
##########    =>  ##########
##########        ########## 
##########        ##########
######  ##        ######  ##
######  ##        ######  ##
##########        ##########

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        ####.#####
##########    =>  ####.#####
####   ###        ####   ### 
##########        ######.###
######  ##        ######  ##
######  ##        ######  ##
##########        ##########

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        ##..######
##########    =>  ##..######
##########        ##..###### 
##########        ##..######
## #######        ## .######
##  ######        ##  ######
##########        ##########

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        #.########
##########    =>  #.########
##########        #.######## 
#######  #        #.#####  #
#######  #        #.#####  #
# #####  #        # .....  #
##########        ##########

##########        ##########
#    #####        #    #####
#    #####        #    #####
##########        #.########
#####  ###    =>  #.###  ###
#####  ###        #.###  ### 
#######  #        #.#####  #
#######  #        #.#####  #
# #####  #        # .....  #
##########        ##########

##########        ##########
##       #        ##       #
##########        ##......##
##########        ##......##
##########    =>  ##......##
##########        ##......## 
##########        ##......##
##########        ##......##
#       ##        #       ##
##########        ##########

##########        ##########
####  ####        ####  ####
####### ##        ####..# ##
###### ###        ####.. ###
# ### ## #    =>  # ... .. #
# ## ### #        # .. ... # 
### ######        ### ..####
## #######        ## #..####
####  ####        ####  ####
##########        ##########
\$\endgroup\$
10
  • \$\begingroup\$ Can I use different characters than # and .? \$\endgroup\$ – user202729 Apr 5 '18 at 14:36
  • 1
    \$\begingroup\$ @user202729 Nope. It was in the rules from the start, and there's already been one answer with it. Probably best to leave the reqs consistent. \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:37
  • \$\begingroup\$ @user202729 The test case you suggested is similar to my penultimate case. I might add it when i next change the question, but it doesn't add much. \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:57
  • \$\begingroup\$ ... I just didn't scroll down. No problem. \$\endgroup\$ – user202729 Apr 5 '18 at 14:57
  • \$\begingroup\$ @l4m2 Same rules apply, wherever there's a straight line between rooms, it's a passage. So a u-shaped room would have the gap filled in with passages. \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:58
7
\$\begingroup\$

Jelly, 17 bytes

ỴḲaLḊṖƊ¦”.KƊ€Z$⁺Y

Try it online!

Tricky -1 thanks to user202729.

Explanation:

ỴḲaLḊṖƊ¦”.KƊ€Z$⁺Y Arguments: S
Ỵ                 Split S on newlines
 ḲaLḊṖƊ¦”.KƊ€Z$   Monadic link
 ḲaLḊṖƊ¦”.KƊ€      Map over left argument
 ḲaLḊṖƊ¦”.KƊ        Monadic link
 Ḳ                   Split on spaces
  aLḊṖƊ¦”.           Dyadic link with right argument '.'
  aLḊṖƊ¦              Apply at specific indices
  a                    Logical AND (vectorizes)
   LḊṖƊ                Monadic link
   L                    Length
    Ḋ                   Range [2..n]
     Ṗ                  Remove last element
          K          Join with spaces
             Z     Zip
               ⁺  Previous link
                Y Join with newlines
\$\endgroup\$
9
  • 2
    \$\begingroup\$ It always amazes me how quickly people can meet these challenges, and in so few characters. \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:07
  • \$\begingroup\$ @AJFaraday Well, then you can be a part of it too. :) Just start with stack-based golfing languages (e.g. CJam, 05AB1E) and work your way from there. \$\endgroup\$ – Erik the Outgolfer Apr 5 '18 at 14:08
  • \$\begingroup\$ It does seem a long way beyond me, to be honest, but I love seeing how the process works. \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:09
  • 7
    \$\begingroup\$ Wait, is TNB short for 'tea and biscuits'? Or am I just being super-British right now? \$\endgroup\$ – AJFaraday Apr 5 '18 at 14:24
  • 5
    \$\begingroup\$ An explanation would be cool for this answer. \$\endgroup\$ – Tamás Sengel Apr 5 '18 at 15:53
5
\$\begingroup\$

Perl 5 -p0, 56 bytes

#!/usr/bin/perl -p0
/
/;$n="(.{@+})*";s%#%/ #*\G#+ |(?= )$n\G$n /s?".":$&%eg

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL+WIN, 87 bytes

Prompts for character matrix:

n←(' '=m←⎕)⋄c←(∨⍀n)+⊖∨⍀⊖n⋄r←(∨\n)+⌽∨\⌽n⋄((,c>1)/,m)←'.'⋄((,r>1)/,m)←'.'⋄((,n)/,m)←' '⋄m
\$\endgroup\$
3
\$\begingroup\$

Haskell, 209 165 162 bytes.

import Data.List
t=transpose
k=concat
j a=(foldr1 max<$>)<$>t<$>t[a,f<$>a,t$f<$>t a]
f b|(e:g:d@(h:_:_))<-group b=k[f$e++g,'.'<$h,drop(length h)$f$k d]|1>0=' '<$b

Try it online!

Not the most efficient way of doing it in Haskell I'm sure. It's got too many parentheses for my liking but I'm not sure how to remove any more.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to the site! You can reduce some of the parentheses by using $ ((k(take 2 c)) becomes (k$take 2 c)). You can also use !!0 instead of head in some cases. \$\endgroup\$ – Wheat Wizard Apr 7 '18 at 17:48
  • \$\begingroup\$ Actually in the particular case of (k(take 2 c)) you can just remove the outer parentheses, they are not needed. But in the case of drop(length(head d)) you can still use the $, replacing it with drop(length$head d) (and even drop(length$d!!0)). \$\endgroup\$ – Wheat Wizard Apr 7 '18 at 17:53
  • \$\begingroup\$ In addition if you use k instead of ++ you can greatly reduce the last line. k[' '<$k(take 2 c),'.'<$d!!0,drop(length$d!!0)$f$k$d]. \$\endgroup\$ – Wheat Wizard Apr 7 '18 at 17:55
  • \$\begingroup\$ One last golf, the last line can be replaced with f b|(e:g:d@(h:_:_))<-group b=k[' '<$e++g,'.'<$h,drop(length h)$f$k d]|1>0=' '<$b, this uses a pattern match to do a lot of the heavy lifting that was being done before. \$\endgroup\$ – Wheat Wizard Apr 7 '18 at 18:10
  • 1
    \$\begingroup\$ Thanks for the heavy duty golfing @user56656! Ungolfed I had f as 2 functions and just pasted them together without optimizing them as a whole. That's a good thing to keep in mind. \$\endgroup\$ – aoemica Apr 7 '18 at 20:24
2
\$\begingroup\$

Python 2, 173 148 bytes

m=input().split('\n')
exec"m=zip(*[[c*(c!='#')or'#.'[(' 'in r[i:])*(' 'in r[:i])]for i,c in enumerate(r)]for r in m]);"*2
for r in m:print''.join(r)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 95 bytes

+`(?<=(.)*)#(?=.*¶(?>(?<-1>.)*)[ .])
.
+`\.(?=(.)*)(?<![ .](?>(?<-1>.)*)¶.*)
#
 (\S+) 
 $.1$*. 

Try it online! Explanation:

+`(?<=(.)*)#(?=.*¶(?>(?<-1>.)*)[ .])
.

This looks for # signs that are above spaces or .s and turns them into dots until there are none left. The lookbehind finds the #'s column and then the lookahead skips to the next line and atomically to the same column below so that the space or . can only match if it's exactly below the #.

+`\.(?=(.)*)(?<![ .](?>(?<-1>.)*)¶.*)
#

This looks for .s that are not below spaces or .s and turns them back into #s until there are none left. The lookahead finds the .'s column and then the lookbehind skips to the previous line and atomically to the same column above in much the same way so that the space or . can only match if it's exactly above the #. A negative lookbehind is used so that this also works for .s in the top row.

 (\S+) 
 $.1$*. 

(Note trailing space on both lines) This simply looks for all runs of non-whitespace characters between spaces and ensures that they are all .s.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 104 bytes

->s{2.times{s=((0...s=~/\n/).map{|i|s.lines.map{|b|b[i]}*""}*"\n").gsub(/ [#.]+(?= )/){$&.tr(?#,?.)}};s}

Try it online!

Well, it's not great, but at least it's convoluted. I'm sure it can be improved.

\$\endgroup\$
1
\$\begingroup\$

Stax, 19 bytes

╛XA╟φkôα`æbπ┐w↨╙j≥☺

Run and debug it

\$\endgroup\$
2
  • \$\begingroup\$ I'm afraid your debug link shows blank code. \$\endgroup\$ – AJFaraday Apr 13 '18 at 18:56
  • \$\begingroup\$ @AJFaraday: Which browser are you using? It's working for me on Chrome for Windows. \$\endgroup\$ – recursive Apr 13 '18 at 20:24
1
\$\begingroup\$

JavaScript (Node.js),205 193 190 186 181 175 172 bytes

r=>r.split`
`.map(x=>[...x]).map((R,y,r)=>R.map((c,x)=>{for(D=2;c<"#"&&D--;){for(;(T=(r[y+=D]||0)[x+=!D])>" ";);for(;r[y-=D][x-=!D]>c;)T?r[y][x]=".":0}})&&R.join``).join`
`

Try it online!

Commented

f=r=>r.split`
` ->                                     //getting as string with lines
.map(x=>[...x])                          //to 2d string array
  .map((R,y,r)=>                         //r - the new 2d string array
    R.map((c,x)=>{                       //
      for(D=2;c<"#"&&D--;)              //instead of using if joining c==" " with the loop,D=1/0
        {for(;                           //
         (T=(r[y+=D]||0)[x+=!D])>" ";);  //0[num] = undefined. checking for a path - consisting of # or .(or not consisting of space or undefined), we dont need temp (X,Y) because in the next loop we will return to our original position regardless of the correctness of the path
           for(;T&&r[y-=D][x-=!D]>c;)    //again instead of if(T) combine with loop. if T is not undefined it will be a space because the array can return .#(space). and we then go back to the source(x,y)
                                         //remeber that c==" "
             r[y][x]="."                 //and just putting . where weve been
     }})&&R.join``                       //instead of return r as string at the end , we know that we cant change a row at a smaller index(due to D-0/1) so we can return R.join`` already
    ).join`
`
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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