Dein Leben könnte davon abhängen. Blinzel nicht. Blinzel nicht mal. Blink und du bist tot. Sie sind schnell. Schneller als Sie glauben können. Drehen Sie nicht den Rücken, schauen Sie nicht weg und blinzeln Sie nicht! Viel Glück.

Weinende Engel sind eine fremde Rasse, die sich nicht bewegen kann, wenn sie von einem anderen Wesen (sogar einem anderen Engel) beobachtet werden. Sie ernähren sich, indem sie ihre Opfer in die Vergangenheit schicken. Sie ( der Doktor ) sind mit einigen in einem Raum gefangen und müssen zu Ihrer TARDIS.

Aufgabe

Schreiben Sie ein Programm, das anhand einer ASCII-Darstellung eines rechteckigen Raums einen Pfad ausgibt, der Sie in Sicherheit bringt. Wenn ein Engel angreifen kann - zu irgendeinem Zeitpunkt während deines Fortschritts - dann ist dieser Weg nicht sicher. Ein Engel kann angreifen, wenn er dich sehen kann, ohne von dir oder einem anderen Engel gesehen zu werden.

Eingang

Die Eingabe besteht aus zwei Teilen. Erstens die Richtung, in die Sie schauen (NSEW). Dann in den folgenden Zeilen eine Darstellung des Raums mit den Start- / Endpositionen und der Position / Ausrichtung aller Engel.

Das folgende Beispiel zeigt, dass es einen Engel gibt, der nach Westen zeigt, und Sie beginnen, nach Süden zu blicken.

S
..........
....D.....
..........
..........
..........
..........
..........
..........
.........W
..........
...T......

• . - Freiraum
• D - Der Doktor (Ausgangsposition)
• T - Die TARDIS (Endposition)
• N,S,E,W - Ein Engel, der der angegebenen Richtung zugewandt ist (Norden, Süden, Osten, Westen)

Sichtlinie

Sie können jeden Raum innerhalb von 45 Grad der Blickrichtung sehen. Die Sichtlinie ist beeinträchtigt, wenn sich entlang einer direkten horizontalen, vertikalen oder 45-Grad-Diagonale ein anderes Objekt befindet. Jede andere Diagonale ist nicht behindern die Sicht. Die Sichtlinie der Engel funktioniert auf die gleiche Weise. Im Folgenden wird beispielsweise -Ihr Sichtfeld dargestellt, vorausgesetzt, Sie sind nach Süden ausgerichtet.

........
...D....
..---...
.-----..
-------.
---N----
---.--N-
---.----

Ausgabe

Die Ausgabe ist eine Zeichenfolge, die den Pfad darstellt, den Sie zum Beenden verwenden. Wenn es mehrere sichere Pfade gibt, wählen Sie einen aus. Wenn kein Pfad sicher ist, wird ausgegeben 0. Wenn die Karte fehlerhaft ist, tun Sie, was Sie möchten, einschließlich des Absturzes. Betrachten Sie es als fehlerhaft, wenn der Raum nicht rechteckig ist, es keinen Ausgang gibt usw. Wenn es keine Engel gibt, ist es nicht fehlerhaft, einfach einfach.

Für jeden Schritt haben Sie zwei Möglichkeiten: Bewegen Sie sich in eine NSEW-Richtung oder drehen Sie sich in eine NSEW-Richtung (ohne die Position zu ändern). Zum Bewegen geben Sie einfach den Buchstaben für diese Richtung aus. Um sich einer Richtung zuzuwenden, geben Sie Fden entsprechenden Buchstaben ein. Zum Beispiel die folgende Ausgabe:

SSFESSSSSSSW

ist ein sicherer Pfad für das im Eingabeabschnitt angegebene Beispiel. Du bewegst dich zweimal nach Süden, nach Osten, um den Engel im Blick zu behalten, und dann noch siebenmal nach Süden und einmal nach Westen, um die TARDIS zu betreten.

Testfälle

1) Sie können um den nach Osten gerichteten Engel herumgehen, um zur TARDIS zu gelangen. Wenn Sie nicht direkt zwischen sie treten, rasten sie sich gegenseitig ein, sodass es egal ist, in welche Richtung Sie sich zu einem bestimmten Zeitpunkt befinden.

W
...D....
........
........
........
.E.....W
........
........
...T....

2) Sie verlieren. Es gibt keine Möglichkeit, an ihnen vorbei zu kommen. Sie können sich sehen, bis Sie zwischen sie treten. An diesem Punkt können Sie nicht beide konfrontieren und Sie sind fertig. Könnte auch nur die Augen schließen und es hinter sich bringen.

S
...D....
........
........
........
E......W
........
........
...T....

Gewinnen

Es gelten die Standard-Golfregeln und -Lücken , die Mindestanzahl an Gewinnen. Ich werde versuchen, bald weitere Testfälle zu bekommen, kann aber in der Zwischenzeit gerne eigene vorschlagen.

^{Bild und Zitat von Doktor Who.}

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"

Die Eingabe muss folgendermaßen erfolgen:

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

Im Wesentlichen ist es dieser Ansatz, der angewendet wird, um alle Zustände (Position und Richtung) zu finden, die der Arzt sicher erreichen kann, um zu speichern, wie er dort ankommt, und um den Weg im Erfolgsfall auszudrucken. Positionen und Richtungen werden mit komplexen Zahlen realisiert.

Ich könnte wahrscheinlich einige Zeichen mit Sages komplexer Zahlenarithmetik sparen, aber das würde extrem lange dauern.

Ich dachte zuerst, ich könnte sechs Zeichen einsparen, indem der Doktor nach Erreichen der Tardis in eine bestimmte Richtung gedreht wird, aber ich erkannte, dass dies zu falschen Lösungen führen könnte. Auch habe ich zuerst die Regeln falsch verstanden.

Hier ist eine meist ungolfte 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"

Testfälle

Testfall 1:

SSSFSWWWSSSSFWEFSEFWE

Testfall 2:

0

VisualMelons Testfall:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

C # 1771 2034 1962 1887 1347 Bytes

Die blockierende LOS-Prüfung wurde in einer Schleife neu geschrieben, wodurch sie viel aufgeräumter und etwa 450 Byte kürzer ist

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);}}

Dies ist ein vollständiges Programm, bei dem erwartet wird, dass die Eingabe mit einem EOF beendet und an STDIN übergeben wird. Es gibt (hoffentlich) den kürzesten Pfad zur TARDIS aus oder "0", wenn kein Pfad vorhanden ist. Es verwendet eine miese Breitensuche, um alle möglichen Routen zu verfolgen, und fährt dann von der TARDIS zurück zu The Doctor, um die Ausgabe zusammenzusetzen.

Formatierter 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);
    }
}

Ausgabe zum Beispiel Eingabe

SFESWSSSSSSS

Ausgang für Testfall 1)

WSWSWSSSESESE

Ausgang für Testfall 2)

0

Ich präsentiere auf Wunsch einen neuen Testfall:

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

Mein Programm gibt aus

SESESESESFNSSSSWW

WozzeCs Testfall 1:

EEEEFWSSSFNWWN

WozzeCs Testfall 2:

FSEEEESFWSSSSWFNWWWNFENNEES

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;}}

Richtig. Also habe ich beschlossen, es zu versuchen, und Junge hat es eine Weile gedauert. Es ist hauptsächlich mit logischen Operatoren aufgebaut.

• Nord = 1 = N
• Süd = 2 = S
• Ost = 4 = E
• West = 8 = W
• Doktor = 6 = D
• TARDIS = 5 = T
• 15 =. <-Alle freien Plätze

Um nicht nach Null zu suchen, habe ich beschlossen, ein Feld mit [MAX_SIZE * 3] * [MAX_SIZE] * 3 zu verwenden und das Spielbrett in die Nähe der Mitte zu legen.

Schleifenprüfungen werden von innen nach außen bis zu 50 (MAX_SIZE) durchgeführt. So etwas in der Art:

22222
21112
21D12
21112
22222

Wenn ein EWS oder N gefunden wird, mache ich ihrerseits die gleiche Überprüfung. Wenn etwas gefunden wird, das die Engel (nicht den Doktor) ansieht, geben sie 15 als freien Durchgang zurück. Wenn sie nicht angeschaut werden, kehren sie in die Richtung zurück, in die sich der Arzt aus Sicherheitsgründen begeben sollte. Dh N würde 2 für Süden zurückgeben. Es sei denn, es ist NW oder NE. In diesem Fall wird 6 (2 + 4) bzw. 10 (2 + 8) zurückgegeben.

Wenn zwei Engel den Doktor beobachten, würden die Rückgabewerte von diesen "UND-verknüpft" sein, so dass im Testbeispiel 2 Crunch-Positionen 4 UND 8 zu 0 werden würden. Dies bedeutet, dass die Position schlecht ist und vermieden werden sollte.

Erweiterter 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;
    }
}

Testergebnisse

1 Beispiel: FNSSSWNNNWSSSWSSSSENNESES

2 Beispiel: Kein Ausweg

VisualMelon-Beispiel: FNSSSSSSSWNNNNNNNWSSSSSSSSSEEEE

Mein Testfall1: FSSENEEEFWSSFNSWWN

Mein Testfall2: FSEEEESFWSSSSFNWWWNFENNFSEES

Wie zu sehen ist, stolziert mein Doktor gerne wie eine Dusche herum, um den Engeln zu zeigen, wie viel Spaß es macht, sich zu bewegen. Ich kann die Software veranlassen, den kürzesten Pfad zu finden, aber es dauert länger und benötigt mehr Code.

Testfälle für euch

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

Noch einer:

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