Your life could depend on this. Don't blink. Don't even blink. Blink and you're dead. They are fast. Faster than you can believe. Don't turn your back, don't look away, and don't blink! Good luck.
Weeping Angels are an alien race that cannot move while being observed by another being (even another Angel). They feed by sending their victims back in time. You (The Doctor) are trapped in a room with some, and you need to get to your TARDIS.
Task
Write a program that will, given an ASCII representation of a rectangular room, output a path that will lead you to safety. If any Angel can attack — at any time during your progress — then that path is not safe. An Angel can attack if it can see you while not being seen by you or another Angel.
Input
Input is two parts. First, the direction you're facing (NSEW). Then on succeeding lines, a representation of the room, showing start/end locations, and the location/facing of all Angels.
The sample below shows that there is one angel facing west, and you start facing south.
S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......
.
- Empty spaceD
- The Doctor (starting position)T
- The TARDIS (end position)N,S,E,W
- An Angel, facing the direction specified (north, south, east, west)
Line of sight
You can see any space withing 45 degrees of the direction you're facing. Line of sight is obstructed if there is another entity along a direct horizontal, vertical, or 45-degree diagonal. Any other diagonal does not obstruct the view. Angels' line of sight works in the same way. For example, in the following, -
represents your field of view, assuming you're facing south.
........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----
Output
The output is a string representing the path you will take to exit. If there are multiple safe paths, choose any one. If no path is safe, output 0
. If the map is malformed, do whatever you like, including crashing out. Consider it malformed if the room is not rectangular, there is no exit, etc. If there are no Angels, it's not malformed, simply easy.
For each step, you can do one of two things: move in a NSEW direction, or turn to a NSEW direction (without changing positions). To move, simply output the letter for that direction. To turn to face a direction, output F
followed by the appropriate letter. For example, the following output:
SSFESSSSSSSW
is a safe path for the sample given in the input section. You move south twice, face east to keep the angel in sight, then move south seven more times and west once to enter the TARDIS.
Test Cases
1) You can go around the east-facing Angel to get to the TARDIS. Unless you step directly between them, they lock each other in place, so it doesn't matter which way you're facing at any point.
W
...D....
........
........
........
.E.....W
........
........
...T....
2) You lose. There's no way to get past them. They can see each other until you step between them. At that point, you can't face them both and you're done. Might as well just shut your eyes and get it over with.
S
...D....
........
........
........
E......W
........
........
...T....
Winning
Standard golf rules and loopholes apply, least bytes wins. I'll try to get some more test cases soon, but feel free to suggest your own in the meantime.
Image and quote from Doctor Who.
J
). \$\endgroup\$