# Draw a path made by direction changers

This challenge takes place on a grid.

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+


This one's 10 x 10, but it can be any rectangular shape.

There are four directions on this grid. Up, down, left and right.

The task is to draw a path starting with an upper case direction initial. In this example, will go directly upward from the U.

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+


The path will go upwards and be comprised of full-stop characters (.), until it hits a wall, when it will terminate with an asterisk (*).

+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


In addition to path starts, there's also direction changers, represented by a lower case direction initial.

+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


Also, an upper case X us an obstacle which will terminate the path.

+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


# Rules

• The input is a string consisting of a frame, (consisting of |, - and + characters) containing characters denoting path starts, direction changers, and obstacles.
• Your code should add full stop characters to follow the path described by starts and direction changers, and an asterisk when/if the path meets a wall or obstacle.
• There can be multiple path starts.
• The code will still terminate without error if the path describes a loop.
• If a path meets a path start, it will act as a direction changer.
• It's code golf, low-byte code and no standard loopholes, please.
• I always prefer links to an on-line interpreter.

# Test Cases

## 1: Simple

+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


## 2: Right turn

+----------+
|          |
|          |
|          |
|   r      |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


+----------+
|          |
|          |
|          |
|   r  d   |
|          |
| u    l   |
|          |
|          |
|   U      |
+----------+

+----------+
| *        |
| .        |
| .        |
| . r..d   |
| . .  .   |
| u....l   |
|   .      |
|   .      |
|   U      |
+----------+


## 4: 4 Crossing paths

+----------+
|      D   |
|          |
|          |
|R         |
|          |
|         L|
|          |
|          |
|   U      |
+----------+

+----------+
|   *  D   |
|   .  .   |
|   .  .   |
|R........*|
|   .  .   |
|*........L|
|   .  .   |
|   .  .   |
|   U  *   |
+----------+


## 5: First Loop

+----------+
|          |
|          |
|          |
|   r  d   |
|          |
|   u  l   |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|   r..d   |
|   .  .   |
|   u..l   |
|   .      |
|   .      |
|   U      |
+----------+


## 6: Starter as changer

+----------+
|          |
|          |
|          |
|   L      |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|*..L      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


## 7: Straight Loop

+----------+
|          |
|          |
|          |
|          |
|   r  l   |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|          |
|   r..l   |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


## 8: Tight Knot

+----------+
|          |
|          |
|          |
|  d  l    |
|   r u    |
|  r u     |
|          |
|          |
|   U      |
+----------+

+----------+
|    *     |
|    .     |
|    .     |
|  d..l    |
|  .r.u    |
|  r.u     |
|   .      |
|   .      |
|   U      |
+----------+


## 9: An Obstacle

+----------+
|          |
|          |
|          |
|          |
|   r    X |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+


## 10: S Shape

+----------+
|r     d   |
|          |
|  XXXXXXXX|
| d      l |
|ul        |
|XXXXXXX   |
|          |
|R       u |
|          |
+----------+

+----------+
|r.....d   |
|.     *   |
|. XXXXXXXX|
|.d......l |
|ul      . |
|XXXXXXX . |
|        . |
|R.......u |
|          |
+----------+


## 11: 4-Way Knot

+----------+
|      D   |
|          |
|   r      |
|R    d    |
|          |
|    u    L|
|      l   |
|          |
|   U      |
+----------+

+----------+
|    * D   |
|    . .   |
|   r.....*|
|R....d.   |
|   ....   |
|   .u....L|
|*.....l   |
|   . .    |
|   U *    |
+----------+


## 12: Busy Junctions

+----------+
|rrrrr rrrd|
| rlrl     |
|ul rrd    |
|ruX X     |
|udl ll    |
|ull       |
|rlr       |
|rdr  d    |
|Uruull    |
+----------+

+----------+
|rrrrr.rrrd|
|.rlrl    .|
|ul rrd   .|
|ruX.X.   .|
|udl.ll   .|
|ull.     .|
|rlr.     .|
|rdr..d   .|
|Uruull   *|
+----------+


## 13: Starts Into Edge

+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+


+----------+
|          |
|          |
|          |
|      R   |
|          |
|          |
|          |
|          |
|         U|
+----------+

+----------+
|         *|
|         .|
|         .|
|      R..*|
|         .|
|         .|
|         .|
|         .|
|         U|
+----------+

• It seems like all direction changers are always reached in your test cases, which could allow to simplify the algorithm. I'd suggest to add a test case where it's not true. – Arnauld Jan 24 at 16:49
• @Arnauld I'm pretty sure there's some unused direction changers in case 12. – AJFaraday Jan 24 at 16:54
• suggested testcase – tsh Jan 25 at 3:37
• It is stated that the grid can be any rectangular shape, but all test cases seem to be identical in size and shape. – gastropner Jan 25 at 4:18

# JavaScript (ES6),  191 183  181 bytes

Thanks to @tsh for helping fix a bug

Takes input as a matrix of characters. Outputs by modifying the input.

f=(a,X,Y,d,n=0)=>a.map((r,y)=>r.map((v,x)=>(a+0)[i=' .*dlurDLUR'.indexOf(v),n]?X?X-x+~-d%2|Y-y+(d-2)%2?0:~i?f(a,x,y,i>2?i&3:d,n+1,r[x]=i?v:'.'):n?a[Y][X]='*':0:i>6&&f(a,x,y,i&3):0))


Try it online!

### Commented

f = ( a,                           // a[]  = input matrix
X, Y,                        // X, Y = coordinates of the previous cell
d,                           // d    = current direction (0 .. 3)
n = 0                        // n    = number of iterations for the current path
) =>                           //
a.map((r, y) =>                  // for each row r[] a position y in a[]:
r.map((v, x) =>                //   for each character v at position x in r[]:
(a + 0)[                     //
i = ' .*dlurDLUR'          //     i = index of the character
.indexOf(v),           //     blocking characters '-', '|' and 'X' gives -1
n                          //     by testing (a + 0)[n], we allow each cell to be
]                            //     visited twice (once horizontally, once vertically)
?                            //     if it is set:
X ?                        //       if this is not the 1st iteration:
X - x + ~-d % 2 |        //         if x - X is not equal to dx[d]
Y - y + (d - 2) % 2 ?    //         or y - Y is not equal to dy[d]:
0                      //           ignore this cell
:                        //         else:
~i ?                   //           if this is not a blocking character:
f(                   //             do a recursive call:
a,                 //               pass a[] unchanged
x, y,              //               pass the coordinates of this cell
i > 2 ? i & 3 : d, //               update d if v is a direction char.
n + 1,             //               increment n
r[x] = i ? v : '.' //               if v is a space, set r[x] to '.'
)                    //             end of recursive call
:                      //           else (this is a blocking character):
n ?                  //             if this is not the 1st iteration:
a[Y][X] = '*'      //               set the previous cell to '*'
:                    //             else:
0                  //               do nothing
:                          //       else (1st iteration):
i > 6 &&                 //         if v is a capital letter:
f(a, x, y, i & 3)      //           do a recursive call with this direction
:                            //     else ((a + 0)[n] is not set):
0                          //       we must be in an infinite loop: abort
)                              //   end of inner map()
)                                // end of outer map()

• btw, [...""+a].map could create an array with at least 2x length of a. I'm not sure if it helps. – tsh Jan 25 at 9:27
• (a+0)[n] does save a byte, even though n now needs to be initialized. – Arnauld Jan 25 at 9:38

# Python 2, 283279293288 279 bytes

e=enumerate
def f(M):
s=[(x,y,c)for y,l in e(M)for x,c in e(l)if'A'<c<'X'];v=set(s)
for x,y,C in s:
d=ord(C)%87%5;q=d>1;X,Y=x-d+q*3,y+~-d-q;c=M[Y][X];N=(X,Y,[C,c]['a'<c<'x'])
if'!'>c:M[Y][X]='.'
if(c in'-|X')*('/'>M[y][x]):M[y][x]='*'
if(c in'udlr. *')>({N}<v):v|={N};s+=N,


Try it online!

Takes a list of lists.

Outputs by modifying the input array.

# Perl 5, 203188 166 bytes

$l='\K[ a-z](?=';$t='([-|X])?';$s=$_;/
/;$n='.'x"@-";{$_|=s/(?|R[.*]*$l$t)|$t${l}[.*]*L)|D$n(?:[.*]$n)*$l$n$t)|$t$n$l$n([.*]$n)*U))/$&eq$"?$1?'*':'.':uc$&/es?redo:$s}  TIO How it works • $s=$_ to save input into $s to restore lowercase changers. $_|=$s because bitwise or with space will not change . and *, lowercase letters urld will be restored with bitwise or operation.
• /\n/;$n='.'x"@-" to get "width" and $n to match any character "width" times
• $l='\K[ a-z](?=';$t='([-|X])?' to reduce regex length ; $l to match a lowercase letter urld or a space on a path, $t to match a terminator.

After replacement :  (?| R[.*]*\K[ a-z](?=([-|X])?) | ([-|X])?\K[ a-z](?=[.*]*L) | D$n(?:[.*]$n)*\K[ a-z](?=$n([-|X])?) | ([-|X])?$n\K[ a-z](?=$n([.*]$n)*U) )

• switches /e to eval, /s so that . (inside $n) matches also a newline character • $&eq$"?$1?'*':'.':uc$& if matched is a space, if termiator matched * otherwise . otherwise uppercase. • @Arnauld, it works if you input one test case at a time. – Shaggy Jan 24 at 18:29 • yes i posted quickly and couldn't check it's fixed reseting $s in footer. $s is used to save the input and to restaure lowercase letters because are switched to uppercase when drawing the path – Nahuel Fouilleul Jan 25 at 8:03 # Clean, 409 bytes import StdEnv,Data.List q=flatlines$m=foldl(zipWith\a b|a=='*'||b=='*'='*'=max a b)(q m)[q(foldl(\m(_,y,x)=[[if(b<>x||a<>y)if(k=='*')'.'k'*'\\k<-r&b<-[0..]]\\r<-m&a<-[0..]])m(last(takeWhile(not o hasDup)(inits(f 0y 0x)))))\\l<-m&y<-[0..],c<-l&x<-[0..]|isUpper c]
where f a y b x=let(u,v)=(a+y,b+x)in(case toLower((m!!u)!!v)of' '=[((a,b),u,v):f a u b v];'r'=f 0u 1v;'l'=f 0u -1v;'u'=f -1u 0v;'d'=f 1u 0v;_=[])


Try it online!

# Python 2, 250 bytes

def f(G,e=enumerate):
for i,k in e(G):
for j,l in e(k):
v=X=x=y=m,=l,
while(m in'-X|')<(l in'DLRU')>(X in v):v+=X,;y,x=zip((1,0,0,-1,y),(0,-1,1,0,x))['DLRU dlru'.find(m)%5];G[i][j]=(m,'.*'[G[i+y][j+x]in'-X|'])[m<'!'];i+=y;j+=x;X=x,i,j;m=G[i][j]


Try it online!

Takes a list of lists of 1-char strings, as explicitly allowed by the OP.

Changes the list in place.

For easier I/O, use this.