# 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. – bigyihsuan Oct 31 '19 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. – FryAmTheEggman Oct 31 '19 at 15:34 • I've put in some more clarification – bigyihsuan Oct 31 '19 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. – Kevin Cruijssen Nov 8 '19 at 9:17 • @Arnauld Aight, will remove. – bigyihsuan Nov 12 '19 at 23:39 ## 1 Answer # 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).