Don't. Even. Blink

Question

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 space
• D - 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.}

Answer 1

C# 1771 2034 1962 1887 1347bytes

Re-wrote the blocking LOS checking in 1 loop, making it much tidier, and about 450bytes shorter

using C=System.Console;using T=System.Math;struct P{int x,y,d;static void Main(){int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;var R=C.In.ReadToEnd().Replace("\r","");var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];for(;o<h;o++)for(i=0;i<w;i++)if((M[i,o]=R[o+o*w+i])==68)M[x=i,y=o]=e;System.Func<int,int,int,bool>S=null;S=(X,Y,D)=>{var Z="SSSE_WNNNE_W___E_W";int I=0,H=0,L=0,J=Y,K=M[X,Y],B;M[X,Y]=D>0?D:K;for(H=0;H<9;H++)for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;){if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))goto W;if(B!=e)break;}for(B=I=-1;++I<w;B=1)for(J=0;J<h;J++)if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))goto W;W:M[X,Y]=K;return B>1;};P a,p=new P{x=x,y=y,d=v};var A=new System.Collections.Generic.List<P>();System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};q();for(o=0;(O=A.Count)!=o;o=O)for(i=O;i-->o;){p=A[i];if((E=M[p.x,p.y])==84)for(R="";;p=a){i=0;n:a=A[i++];O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);if(O==1&p.d==a.d)R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;else if(O<1)R="F"+(char)p.d+R;else goto n;if(i<2)goto Z;}if(E==e){if(p.x-->0)q();p.x+=2;if(p.x<w)q();p.x--;if(p.y-->0)q();p.y+=2;if(p.y<h)q();p.y--;for(F=0;F<4;q())p.d="NESW"[F++];}}R="0";Z:C.WriteLine(R);}}

This is a complete program that expects the input to terminate with an EOF and be passed to STDIN. It (hopefully) prints the shortest path to the TARDIS, or "0" if no path exists. It uses a shoddy Breadth First Search to follow all possible routes, then it backtracks from the TARDIS to The Doctor to assemble the output.

Formatted code:

using C=System.Console;
using T=System.Math;

struct P
{
    int x,y,d;

    static void Main()
    {
        int v=C.ReadLine()[0],w,h,i,o=0,x=0,y=0,O,E,F,e=46;
        var R=C.In.ReadToEnd().Replace("\r","");
        var M=new int[w=R.IndexOf("\n"),h=(R.Length+1)/(w+1)];

        for(;o<h;o++)
            for(i=0;i<w;i++)
                if((M[i,o]=R[o+o*w+i])==68)
                    M[x=i,y=o]=e;

        System.Func<int,int,int,bool>S=null;
        S=(X,Y,D)=>
        {
            var Z="SSSE_WNNNE_W___E_W";

            int I=0,H=0,L=0,J=Y,K=M[X,Y],B;
            M[X,Y]=D>0?D:K;

            for(H=0;H<9;H++)
                for(I=X,J=Y;H!=4&(I+=H%3-1)<w&I>=0&(J+=H/3-1)<h&&J>=0;)
                {
                    if(((B=M[I,J])==Z[H]|B==Z[H+9])&(D<1||!S(I,J,0)))
                        goto W;
                    if(B!=e)
                        break;
                }

            for(B=I=-1;++I<w;B=1)
                for(J=0;J<h;J++)
                    if(I!=X&J!=Y&(((B=M[I,J])==87&I>X&(H=T.Abs(J-Y))<I-X)|(B==69&I<X&H<X-I)|(B==78&J>Y&(L=T.Abs(I-X))<J-Y)|(B==83&J<Y&L<Y-J))&(D<1||!S(I,J,0)))
                        goto W;
        W:
            M[X,Y]=K;
            return B>1;
        };

        P a,p=new P{x=x,y=y,d=v};
        var A=new System.Collections.Generic.List<P>();
        System.Action q=()=>{if(((E=M[p.x,p.y])==e|E==84)&!A.Contains(p)&!S(p.x,p.y,p.d))A.Add(p);};
        q();

        for(o=0;(O=A.Count)!=o;o=O)
            for(i=O;i-->o;)
            {
                p=A[i];
                if((E=M[p.x,p.y])==84)
                    for(R="";;p=a)
                    {
                        i=0;
                    n:
                        a=A[i++];

                        O=T.Abs(p.y-a.y)+T.Abs(a.x-p.x);
                        if(O==1&p.d==a.d)
                            R=(a.y-p.y==1?"N":p.y-a.y==1?"S":a.x-p.x==1?"W":"E")+R;
                        else if(O<1)
                            R="F"+(char)p.d+R;
                        else goto n;

                        if(i<2)
                            goto Z;
                    }
                if(E==e)
                {
                    if(p.x-->0)q();
                    p.x+=2;if(p.x<w)q();p.x--;
                    if(p.y-->0)q();
                    p.y+=2;if(p.y<h)q();p.y--;

                    for(F=0;F<4;q())
                        p.d="NESW"[F++];
                }
            }
        R="0";
    Z:
        C.WriteLine(R);
    }
}

Output for example input

SFESWSSSSSSS

Output for test case 1)

WSWSWSSSESESE

Output for test case 2)

0

I present, as requested, a new test case:

S
..E..DS....
...........
...........
...........
...........
...........
...........
...........
....SSSSS.W
.......T...

My program outputs

SESESESESFNSSSSWW

WozzeC's Test Case 1:

EEEEFWSSSFNWWN

WozzeC's Test Case 2:

FSEEEESFWSSSSWFNWWWNFENNEES

Answer 2

Python – 559 565 644 633

M=input()
I=1j
Q={"S":I,"N":-I,"E":1,"W":-1}
A=[]
e=enumerate
for y,l in e(M[2:].split()):
 for x,c in e(l):
    P=x+y*1j
    if c=="D":D=(P,Q[M[0]])
    elif c=="T":T=P
    elif c!=".":A+=[(P,Q[c])]
def s(D,h,r=[]):
 def L(X,p,d):
    S=[p+d*(i+j*I)for i in range(x+y)for j in range(-i+1,i)if j]
    for f in[1,1+I,1-I]:
     i=0
     while i<x+y>1>(S[-1]in[a[0]for a in[D]+A]+[T])*i:i+=1;S+=[p+i*f*d]
    return X[0]in S
 if y>=D[0].imag>=(D[0]in[a[0]for a in A])<all(any(L(a,*b)for b in[D]+A)for a in A if L(D,*a))>(D in r)<=D[0].real<=x:
    r+=[D]
    if D[0]==T:print h;exit()
    for n in"SWEN":s((D[0]+Q[n],D[1]),h+n,r);s((D[0],Q[n]),h+"F"+n,r)
s(D,"")
print"0"

Input has to be provided like this:

"W\n...D....\n........\n........\n........\nE......W\n........\n........\n...T....\n"

Essentially it’s this approach applied to finding all states (position and direction) the Doctor can safely reach, storing how he got there and printing the way in case of success. Positions and directions are realised with complex numbers.

I could probably safe some chars using Sage’s complex number arithmetics, but that would run extremely long.

I first thought I could save six characters by having the Doctor turn into a specific direction after reaching the Tardis, but I realised that this could result in wrong solutions. Also I first misread the rules.

Here is a mostly ungolfed version:

Map = input()

I = 1j
string_to_dir = {"S":I,"N":-I,"E":1,"W":-1}

Angels = []
Pos = 0
direction = string_to_dir[Map[0]]
for y,line in enumerate(Map[2:].split()):
    for x,char in enumerate(line):
        Pos = x+y*1j
        if char == "D":
            Doctor = (Pos, direction)
        elif char == "T":
            Tardis = (Pos, direction)
        elif char != ".":
            Angels += [(Pos,string_to_dir[char])]

reachables = []

def display(LoS, Doctor):
    string = ""
    for y,line in enumerate(Map[2:].split()):
        for x,char in enumerate(line):
            if x+y*1j == Doctor[0]:
                string += "D"
            elif x+y*1j in LoS:
                if char in ".D":
                    string += "*"
                else:
                    string += "X"
            elif char != "D":
                string += char
            else:
                string += "."

        string += "\n"
    print string

def LoS(angel,Doctor):
    p,d = angel
    Sight = []
    for i in range(x+y):
        for j in set(range(-i+1,i))-{0}:
            Sight += [p+d*i+d*j*I]
    for line in [d, (1+I)*d, (1-I)*d]:
        for i in range(1,x+y):
            Pos = p + i*line
            Sight += [Pos]
            if Pos in [angel[0] for angel in Angels+[Doctor, Tardis]]:
                break
    return Sight

def search(Doctor, history):
    global reachables

    Sight = sum([LoS(angel, Doctor) for angel in [Doctor]+Angels],[])

    if (
                all(angel[0] in Sight for angel in Angels if Doctor[0] in LoS(angel, Doctor))
            and not (Doctor in reachables)
            and (0<=Doctor[0].imag<=y)
            and (0<=Doctor[0].real<=x)
            and (Doctor[0] not in [angel[0] for angel in Angels])
        ):

        reachables += [Doctor]

        if Doctor[0] == Tardis[0]:
            print history
            exit()
        for new_direction in "SWEN":
            search((Doctor[0]+string_to_dir[new_direction], Doctor[1]), history + new_direction)
            search((Doctor[0], string_to_dir[new_direction]), history + "F" + new_direction)

search(Doctor, "")
print "0"

Test Cases

Test case 1:

SSSFSWWWSSSSFWEFSEFWE

Test case 2:

0

VisualMelon’s test case:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

Answer 3

C# 1454, 1396, 1373, 1303 1279

class P{static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;static string[,]t=new string[o,o];static int[,]m=new int[o,o];static string e=" NS ETD W      .",q="0";static void Main(string[]s){m[0,1]=m[1,8]=-1;m[0,2]=m[1,4]=1;u=e.IndexOf(s[0][0]);for(;k<s[0].Length;k++){var c=s[0][k];if(c=='D'){X=x;Y=y;}if(c=='\\'){y++;x=d;k++;}else m[y,x++]=e.IndexOf(c);}k=A(X,Y,1);if((k&u)!=0){W(X,Y,k,"");}System.Console.Write(q);}static void W(int x,int y,int h,string s){t[y,x]=s;for(int i=1;i<9;i*=2){int l=y+m[0,i],g=x+m[1,i];if(m[l,g]==5)q=t[l,g]=s+e[i];else if(m[l,g]==15){m[l,g]=6;m[y,x]=15;int n=A(g,l,1),U;for(int j=1;j<9;j*=2){var z=t[l,g]??s;if((n&h&j)!=0&z.Length>=s.Length){U=u;u=j;W(g,l,n,s+((u!=j)?"F"+e[j]:"")+e[i]);u=U;}}m[y,x]=6;m[l,g]=0;}}}static int A(int x,int y,int L){int r=15,a,b,c,f=0,g,h,R,B;for(a=1;a<d-5;a++){g=1;for(b=y-a;b<=y+a;b++)for(c=x-a;c<=x+a;c++){B=m[b,c];R=0;bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V;if(B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0)){h=R;if(b==y-a){R=1;if(c==x-a){h=4;R=9;}else if(c==x+a){h=8;R=5;}B&=h&2;}else if(b==y+a){R=2;if(c==x-a){h=4;R=10;}else if(c==x+a){h=8;R=6;}B&=h&1;}else if(c==x-a){B&=4;R=8;}else if(c==x+a){B&=8;R=4;}else B=0;if(B!=0){if(L==1&&A(c,b,0)==15)r&=R;if(L==0)return R;}}if(z){if(B<9&B>0&!(c==x&y==b))f|=g;g*=2;}}}return r;}}

Right. So I decided to give this a go, and boy did it take a while. It's built up mostly using logical operators.

• North = 1 = N
• South = 2 = S
• East = 4 = E
• West = 8 = W
• Doctor = 6 = D
• TARDIS = 5 = T
• 15 = . <-All free spaces

To avoid having to check for Null etc. I decided to use a field of [MAX_SIZE*3]*[MAX_SIZE]*3 and put the game board close to the center.

Loop checks are done inside and out all the way to 50(MAX_SIZE). So something like this:

22222
21112
21D12
21112
22222

When a E W S or N is found I do the same check on their part. If anything is found looking at the Angels (Not the Doctor) they return 15 as free passage. If they are not looked upon they return in which way the Doctor should face to be safe. i.e N would return 2 for south. Unless it is NW or NE in which case it would return 6(2+4) and 10(2+8) respectively.

If two angels are watching the Doctor the return values from these would be "ANDed" so in the test example 2 crunchpositions 4 AND 8 would turn into 0. Meaning that the position is bad and should be avoided.

Expanded code:

class P
{
    static int x,d,y=x=d=55,o=170,X=0,Y=0,u,k=3;
    static string[,] t = new string[o, o];
    static int[,] m = new int[o, o];
    static string e = " NS ETD W      .", q="0";
    static void Main(string[]s)
    {   
        m[0, 1]=m[1, 8]=-1;
        m[0, 2]=m[1, 4]=1;
        u=e.IndexOf(s[0][0]);
        for (;k<s[0].Length;k++)
        {
            var c = s[0][k];
            if (c == 'D') { X = x; Y = y; }
            if (c == '\\') { y++; x = d; k++; }
            else m[y, x++] = e.IndexOf(c);
        }
        k=A(X,Y,1);
        if ((k&u)!=0)
        {
            W(X, Y, k,"");
        }
        System.Console.Write(q);
    }
    static void W(int x,int y,int h,string s){
        t[y, x] = s;
        for (int i = 1; i < 9; i*=2)
        {
            int l = y+m[0, i], g = x+m[1, i];
            if (m[l, g] == 5)
                q = t[l, g] = s + e[i];
            else if (m[l, g] == 15)
            {
                m[l, g] = 6;
                m[y, x] = 15;
                int n = A(g, l,1),U;
                for (int j = 1; j < 9; j *= 2)
                {
                    var z = t[l, g]??s;
                    if ((n & h & j) != 0 & z.Length>=s.Length)
                    {
                        U = u;
                        u = j;
                        W(g, l, n,s+((u != j) ? "F" + e[j] : "") + e[i]);
                        u = U;
                    }
                }
                m[y, x] = 6;
                m[l, g] = 0;
            }
        }
    }
    static int A(int x, int y,int L)
    {
        int r = 15,a,b,c,f=0,g,h,R,B;
        for (a = 1; a < d - 5; a++)
        {
            g = 1;
            for (b = y - a; b <= y + a; b++)
                for (c = x - a; c <= x + a; c++)
                {
                    B=m[b, c];
                    R=0;
                    bool W=(c+a-x)%a==0,V=(b+a-y)%a==0,z=W&V; 
                    if (B>0&B<9&B!=6&B!=5&g!=16&!((W|V)&(f&g)!=0))
                    {
                        h=R;
                        if (b==y-a)
                        {
                            R=1;
                            if(c==x-a){h=4;R=9;}
                            else if(c==x+a){h=8;R=5;}
                            B&=h&2;
                        }
                        else if (b==y+a)
                        {
                            R=2;
                            if(c==x-a){h=4;R=10;}
                            else if (c==x+a){h=8;R=6;}
                            B&=h&1;
                        }
                        else if(c==x-a){B&=4;R=8;}
                        else if(c==x+a){B&=8;R=4;}
                        else B=0;
                        if (B!=0)
                        {
                            if(L==1&&A(c,b,0)==15)r&=R;
                            if (L==0)return R;
                        }
                    }
                    if (z)
                    {
                        if (B < 9 & B > 0 & !(c==x&y==b))
                           f |= g;
                        g *= 2;
                    }
                }
        }
        return r;
    }
}

Test results

1 Example: FNSSSWNNNWSSSWSSSSENNESES

2 Example: No way out

VisualMelon Example: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE

My Test case1: FSSENEEEFWSSFNSWWN

My Test case2: FSEEEESFWSSSSFNWWWWNFENNFSEES

As can be seen my Doctor loves strutting around like a douche to show the Angels how fun it is to move around. I can make the software find the shortest path, but it takes longer and needs more code.

Test cases for you guys

S
D....
..NE.
.WTS.
.S...

Another one:

E
D....
WNNN.
...E.
.WTE.
.SSE.
.....