# Follow the Path, but is it valid?

I got directions to my friend's house, but it looks like his map might have some mistakes. He's expecting me soon, so I need some short code to figure out if I can get there.

# The Challenge

The code should, when given an ASCII representation of a path as input, traverse from the start to the end, and output depending on whether there is a valid path.

# Input

Input is an ASCII representation of a map. It will use only the following symbols:

Character = Meaning
(space) = Blocked area
| = Vertical Path
- = Horizontal Path
+ = Intersection
^ or v = Horizontal Bridge
< or > = Vertical Bridge
$= Start Location # = End Location  # Traversal Rules • Execution always starts on $ and will end when all paths are blocked, an infinite loop, or the pointer hits #. It is guaranteed that input will have exactly 1 of each.
• The pointer starts moving to the right and down.
• Vertical paths will only connect to vertical paths, vertical bridges, or intersections.
• Horizontal paths will only connect to horizontal paths, horizontal bridges, or intersections.
• If a vertical and horizontal path meet at a non-bridge, it is considered blocked at that point.
• Bridges function according to the following:
 |      |
-^- OR -v- = Horizontal path going over a vertical path
|      |

|      |
-<- OR ->- = Vertical path going over a horizontal path
|      |

• When the pointer hits an intersection, movement precedence is in the clockwise direction (up, right, down, left). The pointer will not go back the way it came.
• The program must detect/calculate infinite loops and branching paths from +.

# Output

The length of the path, or -1, according to the following conditions:

• If the program reaches #, output the path length.
• If the program detects only blocked paths, return -1.
• If the program detects an infinite loop, return -1.

# Scoring

This is , so the shortest code in bytes wins! Standard loopholes are forbidden.

# Test Cases

   $| +-| #+-+ = 6 (going north at #+- will lead to a blocked path, but going to the west is a valid path) #-+-+ | |$-^-+
+-+
= -1 (Will infinitely loop)

$# = 1 #^^^^+ >$----^-+
> +
+-+
= 20

$------+ |-----+| --#--+| +--+---+ +------+ = 23$ #
= -1 (Blocked by the space)

$|# = -1 (Can't go onto a vertical path from the sides)$
-
#
= -1 (Can't go onto a horizontal path from the top or bottom)

$|# |--| ++++ = -1 (No valid paths exist)  • @FryAmTheEggman If you go north, you will eventually hit a blocked path, meaning that path is invalid. However, this is also a valid path to the west, which is where the 4 should be a 6. I'll add in clarification. Oct 31, 2019 at 15:30 • I see, so you automatically look ahead to see that a turn will be invalid if you would be blocked, but not if there is a loop? I'd highlight that some more since it is fine, but surprising. Oct 31, 2019 at 15:34 • I've put in some more clarification Oct 31, 2019 at 15:47 • Shouldn't the fourth test case result in 20 instead of 19? You first go underneath the bridge at the intersection, and after that a second time across it. So 5 (east) + 4 (south) + 2 (east) + 2 (north) + 7 (west) = 20. Nov 8, 2019 at 9:17 • @Arnauld Aight, will remove. Nov 12, 2019 at 23:39 ## 2 Answers # JavaScript (ES6), 219 bytes Takes input as a list of lists of characters. a=>((g=(X,Y,D,n=o=0)=>!(a+0)[n++]|a.some((r,y)=>r.some((c,x)=>D=='975'[i='-| #+$'.indexOf(c),x-X+1]-'450'[y-Y+1]?i-3?i-2?i>3?[3,0,7,4].some(d=>D^d^4&&g(x,y,d,n)):~i&&i^D&1?0:g(x,y,D,n):0:o=-n:X+1|i<5?0:g(x,y,2))))(),~o)


Try it online!

### How?

Because they need to be tried in a specific order, the way the directions are handled in this code is a bit unusual.

Given a direction $$\D\$$ and the source coordinates $$\(X,Y)\$$, we want to figure out which target coordinates $$\(x,y)\$$ correspond to a move by one square along $$\D\$$.

We use the following test for each candidate pair $$\(x,y)\$$:

D == '975'[x - X + 1] - '450'[y - Y + 1]


This test always fails if $$\|x-X|>1\$$ or $$\|y-Y|>1\$$ because we get an undefined value from at least one of the 2 lookup strings.

Otherwise, we have the following table:

$$\begin{array}{r|c|ccc} &x-X&-1&0&+1\\ \hline y-Y&&9&7&5\\ \hline -1&-4&5&3&1\\ 0&-5&4&2&0\\ +1&-0&9&7&5 \end{array}$$

Because diagonal moves are not used, our final compass looks as follows:

$$\begin{array}{cccc} &&3\\ &&↑\\ 4&←&2&→&0\\ &&↓\\ &&7 \end{array}$$

The lookup values were chosen in such a way that we end up with some handy properties:

• Opposite directions can be detected by testing if $$\d\operatorname{xor}d'=4\$$. Hence the code to try all directions in clockwise order except the one that would make us going back the way we came:

  [3, 0, 7, 4].some(d => D ^ d ^ 4 && g(x, y, d, n))

• Vertical moves are connected to odd values.

• Horizontal moves are connected to even values (except direction $$\2\$$, for no move at all, which is only used at the beginning of the process when the starting point has been identified).

# Python3, 934 bytes:

E=enumerate
V=lambda b,X,Y:0<=X<len(b)and 0<=Y<len(b)and b[X][Y]!=' '
def U(D,x,X):D[x]=D.get(x,[])+[X];D[X]=D.get(X,[])+[x]
def f(b):
m,W=[[0,1,'-^'],[1,0,'|>'],[0,-1,'-^'],[-1,0,'|>']],{'^':'-','>':'|'}
x,y=[[x,y]for x,r in E(b)for y,t in E(r)if'\$'==t]
q,D=[(x,y,0,not V(b,x,y+1))],{}
while q:
x,y,p,l=q.pop(0)
if'#'==b[x][y]:return p
if b[x][y]in'>^':
for j,k,I in[(X,Y,i)for i,(X,Y,u)in E(m)if b[x][y]in u]+[(m[l],m[l],l)]:
if(x+j,y+k)not in D.get((x,y),[])and(b[x+j][y+k]in'>#^+'or b[x+j][y+k]==W[b[x][y]]):U(D,(x,y),(x+j,y+k));q+=[(x+j,y+k,p+1,I)];break
elif'+'==b[x][y]:
T,O=[0,1,2,3],[]
for i in T[l:]+T[:l]:
if V(b,X:=x+m[i],Y:=y+m[i])and(X,Y)not in D.get((x,y),[]):
if'#'==b[X][Y]:return p+1
O+=[((X,Y),i)]
if O:U(D,(x,y),O);q+=[(*O,p+1,O)]
elif V(b,X:=x+m[l],Y:=y+m[l])and b[X][Y]in(m[l]+'#+'):U(D,(x,y),(X,Y));q+=[(X,Y,p+1,l)]


Try it online!