Votre vie pourrait en dépendre. Ne cligne pas des yeux. Ne cligne même pas des yeux. Cligne des yeux et tu es mort. Ils sont rapides. Plus rapide que vous ne pouvez le croire. Ne tourne pas le dos, ne détourne pas le regard et ne cligne pas des yeux! Bonne chance.

Les anges pleureurs sont une race extraterrestre qui ne peut pas bouger sous l'observation d'un autre être (même un autre ange). Ils se nourrissent en renvoyant leurs victimes dans le temps. Vous ( le docteur ) êtes pris au piège dans une pièce avec certains et vous devez vous rendre à votre TARDIS.

Tâche

Ecrivez un programme qui, à partir d’une représentation ASCII d’une pièce rectangulaire, affichera un chemin menant à la sécurité. Si un ange peut attaquer - à n'importe quel moment de votre progression - alors ce chemin n'est pas sûr. Un ange peut attaquer s'il peut vous voir sans être vu par vous ou par un autre ange.

Contribution

L'entrée est en deux parties. Tout d’abord, la direction à laquelle vous faites face (NSEW). Ensuite, sur les lignes suivantes, une représentation de la salle, indiquant les emplacements de début / fin, ainsi que l’emplacement / le visage de tous les anges.

L'échantillon ci-dessous montre qu'il y a un ange faisant face à l'ouest et que vous commencez à faire face au sud.

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

• . - Espace libre
• D - Le docteur (position de départ)
• T - Le TARDIS (position finale)
• N,S,E,W - un ange face à la direction indiquée (nord, sud, est, ouest)

Ligne de mire

Vous pouvez voir n’importe quel espace dont l’angle est inférieur à 45 degrés. La ligne de mire est obstruée s’il existe une autre entité le long d’une diagonale directe horizontale, verticale ou à 45 degrés. Toute autre diagonale ne gêne pas la vue. La ligne de mire des anges fonctionne de la même manière. Par exemple, dans ce qui suit, -représente votre champ de vision, en supposant que vous soyez face au sud.

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

Sortie

La sortie est une chaîne représentant le chemin que vous emprunterez pour sortir. S'il existe plusieurs chemins sécurisés, choisissez-en un. Si aucun chemin n'est sécurisé, sortie0 . Si la carte est mal formée, faites ce que vous voulez, y compris en vous écrasant. Considérez-le malformé si la pièce n'est pas rectangulaire, s'il n'y a pas de sortie, etc. S'il n'y a pas d'Anges, ce n'est pas mal formé, c'est tout simplement facile.

Pour chaque étape, vous pouvez effectuer l'une des deux opérations suivantes: vous déplacer dans une direction NSEW ou vous orienter vers une direction NSEW (sans changer de position). Pour vous déplacer, écrivez simplement la lettre correspondant à cette direction. Pour faire face à une direction, la sortie Fsuivie de la lettre appropriée. Par exemple, la sortie suivante:

SSFESSSSSSSW

est un chemin sécurisé pour l'échantillon indiqué dans la section d'entrée. Vous vous déplacez au sud deux fois, face à l'est pour garder l'ange en vue, puis au sud sept fois de plus et à l'ouest une fois pour entrer dans le TARDIS.

Cas de test

1) Vous pouvez contourner l’Ange face à l’est pour vous rendre au TARDIS. À moins que vous ne vous mettiez directement entre eux, ils se verrouillent mutuellement, peu importe la direction à laquelle vous faites face.

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

2) tu perds. Il n'y a aucun moyen de les dépasser. Ils peuvent se voir jusqu'à ce que vous vous mettiez entre eux. À ce stade, vous ne pouvez pas les affronter tous les deux et vous avez terminé. Vous pourriez aussi bien fermer les yeux et en finir.

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

Gagnant

Les règles de golf standard et les échappatoires s’appliquent, la perte d’octets est la plus faible J'essaierai bientôt d'obtenir d'autres tests, mais n'hésitez pas à suggérer les vôtres d'ici là.

^{Image et citation de Doctor 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"

L'entrée doit être fournie comme ceci:

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

Essentiellement c'est cette approche s’applique à rechercher tous les états (position et direction) que le médecin peut atteindre en toute sécurité, en enregistrant comment il s’y est rendu et en imprimant le chemin en cas de succès. Les positions et les directions sont réalisées avec des nombres complexes.

Je pourrais probablement protéger certains personnages avec les arithmétiques de nombres complexes de Sage, mais cela prendrait énormément de temps.

J'ai d'abord pensé pouvoir sauver six personnages en laissant le Docteur prendre une direction spécifique après avoir atteint le Tardis, mais je me suis rendu compte que cela pourrait entraîner de mauvaises solutions. De plus, j'ai mal interprété les règles.

Voici une version pour la plupart non-golfée:

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"

Cas de test

Cas de test 1:

SSSFSWWWSSSSFWEFSEFWE

Cas de test 2:

0

Le cas de test de VisualMelon:

SSFWSSSSSFSWWSSWWWFWEEEEFSEFWEFSE

C # 1771 2034 1962 1887 1347octets

Réécriture de la vérification de la NDS bloquante en une boucle, la rendant beaucoup plus ordonnée et plus courte d'environ 450 octets

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

C'est un programme complet qui s'attend à ce que l'entrée se termine par un EOF et soit transmise à STDIN. Il (espérons) affiche le chemin le plus court vers le TARDIS, ou "0" si aucun chemin n’existe. Il utilise une recherche médiocre en largeur d'abord pour suivre tous les itinéraires possibles, puis il effectue un retour arrière du TARDIS au Doctor pour assembler la sortie.

Code formaté:

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

Sortie pour exemple entrée

SFESWSSSSSSS

Sortie pour le cas de test 1)

WSWSWSSSESESE

Sortie pour le cas de test 2)

0

Je présente, comme demandé, un nouveau cas de test:

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

Mes sorties de programme

SESESESESFNSSSSWW

Cas de test 1 de WozzeC:

EEEEFWSSSFNWWN

Cas de test 2 de WozzeC:

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

Droite. Alors j'ai décidé de tenter le coup, et ça a pris un moment. Il est construit principalement à l'aide d'opérateurs logiques.

• Nord = 1 = N
• Sud = 2 = S
• Est = 4 = E
• Ouest = 8 = W
• Docteur = 6 = D
• TARDIS = 5 = T
• 15 =. <-Tous les espaces libres

Pour éviter de devoir vérifier Null, etc., j'ai décidé d'utiliser un champ de [MAX_SIZE * 3] * [MAX_SIZE] * 3 et de placer le plateau de jeu à proximité du centre.

Les contrôles de boucle sont effectués à l'intérieur et à l'extérieur jusqu'à 50 (MAX_SIZE). Donc, quelque chose comme ça:

22222
21112
21D12
21112
22222

Lorsqu'un EWS ou N est trouvé, je fais la même vérification de leur part. Si quelque chose est trouvé en regardant les anges (pas le docteur), ils retournent 15 comme passage libre. S'ils ne sont pas vus, ils reviennent de quelle manière le médecin devrait faire face pour être en sécurité. c'est-à-dire que N retournerait 2 pour le sud. À moins que ce soit NW ou NE, auquel cas il renverrait respectivement 6 (2 + 4) et 10 (2 + 8).

Si deux anges surveillent le Docteur, les valeurs renvoyées par ces valeurs seraient "ANDées". Ainsi, dans l'exemple de test 2, les positions 1 et 4 deviendront 0. Cela signifie que la position est mauvaise et doit être évitée.

Code développé:

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

Résultats de test

1 Exemple: FNSSSWNNNWSSSWSSSSENNENNES

2 Exemple: pas de sortie

Exemple VisualMelon: FNSSSSSSSWNNNNNNWSSSSSSSSSEEEE

Mon cas de test1: FSSENEEEFWSSFNSWWN

Mon cas de test2: FSEEEESFWSSSSFNWWWWNFENNFSEES

Comme on peut le constater, mon médecin adore se pavaner comme une douche pour montrer aux anges combien il est amusant de se déplacer. Je peux faire en sorte que le logiciel trouve le chemin le plus court, mais cela prend plus de temps et nécessite plus de code.

Cas de test pour vous les gars

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

Un autre:

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