PUNTUACIÓN ACTUALIZADA : como este desafío es más difícil de lo que esperaba, he ajustado la puntuación. Un programa que puede resolver una sola entrada espejo es una respuesta válida. Los programas más sofisticados obtienen una bonificación en su puntaje.

Ha habido varios acertijos en PPCG para encontrar un camino láser en una caja de espejos. En este rompecabezas, debe crear una caja de espejos para que coincida con varios destinos láser.

Se le da una caja y una especificación donde los láseres deben entrar y salir. Su programa necesita colocar exactamente N espejos de doble cara en la caja para cumplir con las especificaciones. Los espejos deben estar en ángulo a 45 grados, pero pueden inclinarse hacia adelante o hacia atrás.

Entrada

Su programa debe aceptar una cuadrícula de cuadro a través de STDIN, argumento de línea de comando o archivo en los siguientes ejemplos de formato:

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

Los pares de letras ([a-zA-Z] pueden usarse) indican la entrada / salida de hasta 52 láseres. Dentro de la caja habrá N /espejos. Las dimensiones de la caja serán 3 <= W, H <= 200. La caja está hecha de +|-caracteres. Puede haber cualquier número de espejos en la caja, incluido cero.

Salida

La salida debe coincidir con la entrada, excepto que los /caracteres se pueden mover y / o cambiar a \caracteres. Su programa debe enviar una cadena de caja espejo correcta a STDOUT o un archivo, arrastrando una nueva línea opcional. Si ninguna colocación de espejos puede cumplir con la especificación de entrada, salida Impossible\n. Ejemplos de posibles soluciones:

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

Ejemplo de prueba

Entrada:

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

Salida de ejemplo:

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

Puntuación (ACTUALIZADO)

Este es el código de golf con bonos. Con su respuesta, debe nominar cuántos espejos puede resolver su programa (N). Su puntaje es la duración de su programa en bytes dividido por N. Esto permite que las personas ingresen con un programa simple, pero recompensa a más programadores de ambición con un bono.

Lagunas estándar no permitidas.

C # - 897 862 bytes

Encontró un error grave al poner espejos en lugares donde no pueden estar. ¡Ahora funciona, con suerte! También hice un poco de golf ligero, no podía dejar el bucle while allí ... vergonzoso.

Programa completo, toma entrada de STDIN, salidas a STDOUT.

Esto fue muy divertido, resuelve bien el problema de 7 por 5 (y cuando quitas uno de los espejos, haciéndolo imposible), tomó aproximadamente 1 hora resolver los 30 por 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 por 5 Ejemplo:

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

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

Versión imposible:

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

Impossible

Algo diferente (el programa no mira el diseño espejo original):

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

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

Solución 30 por 5:

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

Observa cada fuente láser a su vez, y construye una ruta válida para ella (si puede), y luego pasa a la siguiente. Es una búsqueda bastante simple de profundidad, que tiene que saber qué fuente láser (objetivo) está mirando, cuántos espejos le quedan para colocar, la celda actual en la que se encuentra, la dirección en la que se mueve y cada celda. ya ha sido visitado (para que no ponga un espejo en algún lugar donde ya ha estado). Los últimos 3 se utilizan para ensamblar la ruta para el objetivo actual y en el restablecimiento cuando el objetivo cambia. Una vez que tiene todos los láseres conectados, continúa y llena los vacíos que no necesita dejar vacíos (otra razón por la que necesita saber en todos los lugares que visita).

Cuando está construyendo rutas, favorece avanzar "hacia adelante" sobre la inserción de un espejo, y cuando lo hace, favorece un espejo "\"; esto se ve mejor en el ejemplo "algo diferente" anterior, donde omite la primera celda debajo de 'a' superior, luego llena continuamente una "\" si puede encontrar una solución con una, de lo contrario una "/" (naturalmente, si omitir la primera celda resultara incapaz de encontrar una solución, entonces sería retrocede e intenta poner un espejo allí).

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 bytes

No es una solución, sino un intento, lea a continuación.

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

No jugué golf al máximo, ya que no estoy satisfecho con la solución. Vvalida una solución dada recorriendo el campo Fpara cada personaje Cque encuentra en la línea lateral. Las soluciones se generan al azar. Es feo, funciona para la entrada 1, pero toma mucho tiempo para las otras entradas. Dado que intenta soluciones al azar, no considero que sea una solución real para el problema dado; Pero podría ayudar a otros.

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