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 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 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
- 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
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
- If the program detects an infinite loop, return
$ | +-| #+-+ = 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)