MISE À JOUR DU SCORE : Comme ce défi est plus difficile que prévu, j'ai ajusté le score. Un programme qui peut résoudre une seule entrée miroir est une réponse valide. Les programmes plus sophistiqués obtiennent un bonus à leur score.

Il y a eu plusieurs puzzles sur PPCG pour trouver un chemin laser dans une boîte de miroirs. Dans ce puzzle, vous devez créer une boîte de miroirs pour correspondre à un certain nombre de destinations laser.

On vous donne une boîte et une spécification où les lasers doivent entrer et sortir. Votre programme doit placer exactement N miroirs double face dans la boîte pour répondre aux spécifications. Les rétroviseurs doivent être inclinés à 45 degrés mais peuvent être inclinés vers l'avant ou vers l'arrière.

Contribution

Votre programme doit accepter une grille de boîtes via STDIN, un argument de ligne de commande ou un fichier dans les exemples de format suivants:

+--G--+     +abcde+
G     |     f/////d
|    /|     a//   c
+-----+     f     |
            +-b-e-+

Les paires de lettres ([a-zA-Z] peuvent être utilisées) indiquent l'entrée / sortie d'un maximum de 52 lasers. À l'intérieur de la boîte, il y aura N /miroirs. Les dimensions de la boîte seront de 3 <= W, H <= 200. La boîte est composée de +|-caractères. Il peut y avoir n'importe quel nombre de miroirs dans la boîte, y compris zéro.

Production

La sortie doit correspondre à l'entrée, sauf que les /caractères peuvent être déplacés et / ou transformés en \caractères. Votre programme doit envoyer une chaîne de boîte miroir correcte à STDOUT ou à un fichier, la nouvelle ligne à la fin étant facultative. Si aucun placement de miroirs ne peut répondre à la spécification d'entrée, sortez Impossible\n. Exemples de solutions possibles:

+--G--+     +abcde+
G  /  |     f \ \ d
|     |     a/ \  c
+-----+     f / //|
            +-b-e-+

Exemple de test

Contribution:

+abcdefghijklmnopqrstuvwxyA-+
|///////////////            |
|///////////////            |
|                           |
+-Abcdefghijklmnopqrstuvwxya+

Exemple de sortie:

+abcdefghijklmnopqrstuvwxyA-+
|\                         \|
|/                        / |
|\\\\\\\\\\\\\\\\\\\\\\\\\\ |
+-Abcdefghijklmnopqrstuvwxya+

Notation (MISE À JOUR)

C'est du code-golf avec des bonus. Vous devez indiquer avec votre réponse combien de miroirs votre programme peut résoudre (N). Votre score est la longueur de votre programme en octets divisée par N. Cela permet aux gens d'entrer avec un programme simple, mais récompense plus de programmeurs d'ambition avec un bonus.

Failles standard interdites.

C # - 897 862 octets

J'ai trouvé un bug grave en mettant des miroirs dans des endroits où ils ne pouvaient pas être. Maintenant ça marche, j'espère! A également fait du golf léger, n'a pas pu laisser la boucle tandis que ... honteux.

Programme complet, prend l'entrée de STDIN, sort vers STDOUT.

C'était très amusant, cela résout bien le problème 7 par 5 (et lorsque vous retirez l'un des miroirs, ce qui le rend impossible), il a fallu environ 1 heure pour résoudre le 30 par 5.

using Q=System.Console;class P{static int w,L;static string S(char[]M,int t,int r,int i,int d,int[]B){var s="";if(r<0)return s;M=(char[])M.Clone();B=(int[])B.Clone();B[i]=1;for(i+=d;M[t]<48|t==i;i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1))if(++t>=L){for(i=0;++i<L&r>0;)if(B[i]<1&M[i]<33){M[i]='.';r--;}return r<1?new string(M):s;}int c=M[i];if(c>32)s=c>47|c<46?s=c==M[t]?S(M,t,r,t,0,B):s:S(M,t,r,i,c<47?w/d:-w/d,B);else if((s=S(M,t,r,i,d,B))==""&B[i]<1){M[i]='.';s=S(M,t,r-1,i,w/d,B);if(s==""){M[i]='/';s=S(M,t,r-1,i,-w/d,B);}}return s;}static void Main(){string a,A="",R=A;for(;(a=Q.ReadLine())!=null;A+=a)L+=(w=a.Length);var G=A.ToCharArray();int r=0,i=L;for(;i>0;G[i]=G[i]=='|'?',':G[i])if(G[--i]==47|G[i]==92){r++;G[i]=' ';}a=S(G,0,r,1,w,new int[L]);if(a=="")R="Impossible\n";else for(;i<L;i+=w)R+=a.Substring(i,w)+"\n";Q.Write(R.Replace(".","\\").Replace(",","|"));}}

7 par 5 Exemple:

+abcde+
f/////d
a//   c
f     |
+-b-e-+

+abcde+
f   \ d
a/  //c
f/ \ /|
+-b-e-+

Version impossible:

+abcde+
f ////d
a//   c
f     |
+-b-e-+

Impossible

Quelque chose de différent (le programme ne regarde pas la disposition originale du miroir):

+a----+
|//// |
|/////|
|/////|
+----a+

+a----+
| /\\\|
|\\\\\|
|\\/\\|
+----a+

Solution 30 x 5:

+abcdefghijklmnopqrstuvwxyA-+
| \\\\\\\\\\\\\\\\\\\\\\\\ \|
| /                       //|
|\                         \|
+-Abcdefghijklmnopqrstuvwxya+

Il examine chaque source laser tour à tour, et construit une route valide pour elle (si elle le peut), puis passe à la suivante. C'est une recherche assez simple en profondeur d'abord, qui doit savoir quelle source laser (cible) il regarde, combien de miroirs il lui reste à placer, la cellule actuelle dans laquelle il se trouve, la direction dans laquelle il se déplace et chaque cellule il est déjà visité (pour qu'il ne mette pas de miroir quelque part où il a déjà été). Les 3 derniers sont utilisés pour assembler le chemin de la cible actuelle et lors de la réinitialisation lorsque la cible change. Une fois tous les lasers connectés, il va de l'avant et comble les lacunes dont il n'a pas besoin de rester vide (une autre raison pour laquelle il doit savoir partout où il est visité).

Quand il construit des routes, il préfère aller "en avant" par rapport à l'insertion d'un miroir, et quand il le fait, il favorise un miroir "\" - cela est mieux vu dans l'exemple "quelque chose de différent" ci-dessus, où il saute la première cellule sous la le plus haut 'a', puis remplit continuellement un "\" s'il peut trouver une solution avec une, sinon un "/" (naturellement, si sauter la première cellule l'empêchait de trouver une solution, alors il revenir en arrière et essayer de mettre un miroir à la place).

using Q=System.Console;

class P
{
    static int w,L;

    // M is cur grid
    // t is target edge thing (0->L)
    // r is mirrors remaining
    // i is pos
    // d is dir
    static string S(char[]M,int t,int r,int i,int d,int[]B)
    {
        var s="";

        if(r<0) // no mirrors left
            return s;

        // clone everything
        M=(char[])M.Clone();
        B=(int[])B.Clone();

        B[i]=1; // can't write to this

        for(i+=d; // move i
            M[t]<48|t==i; // only if target is something sensible (increment if i==t)
            i=t+(d=t<w?w:t>L-w?-w:t%w<1?1:-1)) // reflect, should be fine for w=3
            if(++t>=L) // run off the end
            {
                for(i=0;++i<L&r>0;) // don't need I any more (count through everything)
                    if(B[i]<1&M[i]<33) // not been here & it's open space
                    {
                        M[i]='.'; // doesn't matter
                        r--;
                    }
                return r<1?new string(M):s; // none remaining ? victory : defeat
            }

        int c=M[i];
        if(c>32) // not boring
            s=c>47|c<46? // hit edge
                s=c==M[t]? // hit the correct thing
                    S(M,t,r,t,0,B): // i+0=t, tells it to increment t
                    s
            :S(M,t,r,i,c<47?w/d:-w/d,B); // mirror
        else // boring
            if((s=S(M,t,r,i,d,B))==""&B[i]<1) // fwd
            {
                M[i]='.'; // use . instead of \
                s=S(M,t,r-1,i,w/d,B); // \
                if(s=="")
                {
                    M[i]='/';
                    s=S(M,t,r-1,i,-w/d,B); // /
                }
            }

        return s;
    }

    static void Main()
    {
        string a,A="",R=A; // R is free
        for(;(a=Q.ReadLine())!=null;A+=a) // read input
            L+=(w=a.Length); // note width, accumulate length

        var G=A.ToCharArray();

        int r=0,i=L; // count mirrors (I refuse to make these static)
        for(;i>0; // end on i=0
            G[i]=G[i]=='|'?',':G[i]) // replace | with ,
            if(G[--i]==47|G[i]==92) // remove and count mirrors
            {
                r++;
                G[i]=' '; // storing G[i] doesn't seem to save anything
            }

        // search
        a=S(G,0,r,1,w,new int[L]);

        if(a=="") // defeat
            R="Impossible\n";
        else // victory
            for(;i<L;i+=w) // for each line
                R+=a.Substring(i,w)+"\n";

        Q.Write(R.Replace(".","\\").Replace(",","|")); // swap back | and \
    }
}

Python, 671 654 octets

Pas une solution, mais une tentative, lisez ci-dessous.

import random as R
def V(F):
 for S,_x,_y in (F[0],0,1),(F[-1],0,-1),([L[0] for L in F],1,0),([L[-1] for L in F],-1,0):
  for i,C in enumerate(S):
   if not C in '+-|':
    x=_x;y=_y
    if not x: X=i;Y=y
    elif not y: Y=i;X=x
    while F[Y][X] != C:
     if F[Y][X]=='\\':x,y=y,x
     if F[Y][X]=='/':a=x+y;x,y=x-a,y-a
     X+=x;Y+=y
     try:
      if F[Y][X] in '+-|':return False
     except:
      return False
 return True
F=open(input()).read().split('\n')
while 1:
 _=[F[0]]+['\n'.join([L[0]+''.join([R.choice(' \\/')for i in range(len(F[0])-2)])+L[-1] for L in F[1:-1]])]+[F[-1]]
 if V(_):
  for l in _: print l
  break

Je n'ai pas joué au golf au maximum, car je ne suis pas satisfait de la solution. Vvalide une solution donnée en parcourant le champ Fpour chaque personnage Cqu'il trouve sur la touche. Les solutions sont générées au hasard. C'est moche, ça marche pour entry1, mais ça prend beaucoup de temps pour les autres entrées. Puisqu'il essaie au hasard des solutions, je ne considère pas que ce soit une solution réelle pour le problème donné; mais cela pourrait aider les autres.

Courir: echo "entry1.txt" | python script.py