6
\$\begingroup\$

Follow the Path

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)
\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – bigyihsuan Oct 31 at 15:30
  • \$\begingroup\$ 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. \$\endgroup\$ – FryAmTheEggman Oct 31 at 15:34
  • \$\begingroup\$ I've put in some more clarification \$\endgroup\$ – bigyihsuan Oct 31 at 15:47
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Nov 8 at 9:17
  • 1
    \$\begingroup\$ @Arnauld Aight, will remove. \$\endgroup\$ – bigyihsuan 2 days ago
4
+100
\$\begingroup\$

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).
\$\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.