ZAKTUALIZOWANY PUNKTACJA : Ponieważ to wyzwanie jest trudniejsze niż się spodziewałem, poprawiłem punktację. Program, który może rozwiązać pojedyncze wejście lustrzane, jest poprawną odpowiedzią. Bardziej wyrafinowane programy otrzymują premię do swojego wyniku.

Na PPCG pojawiło się kilka zagadek pozwalających znaleźć ścieżkę lasera w pudełku z lustrami. W tej układance musisz stworzyć pudełko luster, które pasują do wielu miejsc laserowych.

Dostajesz pudełko i specyfikację, w której lasery mają wchodzić i wychodzić. Twój program musi umieścić dokładnie N dwustronnych lusterek w pudełku, aby spełnić specyfikację. Lustra muszą być ustawione pod kątem 45 stopni, ale mogą być nachylone do przodu lub do tyłu.

Wejście

Twój program powinien zaakceptować siatkę pól poprzez STDIN, argument wiersza poleceń lub plik w następujących przykładach formatu:

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

Pary liter (można zastosować [a-zA-Z]) wskazują wejście / wyjście do 52 laserów. Wewnątrz pudełka będzie N /lusterek. Wymiary pudełka będą wynosić 3 <= W, H <= 200. Pudełko składa się ze +|-znaków. W pudełku może znajdować się dowolna liczba kopii lustrzanych, w tym zero.

Wynik

Dane wyjściowe powinny pasować do danych wejściowych, z tym wyjątkiem, że /znaki można przenosić i / lub zamieniać na \znaki. Twój program powinien wysłać poprawny ciąg kopii lustrzanej do STDOUT lub pliku, opcjonalnie wstawić nowy wiersz. Jeśli żadne umieszczenie serwerów lustrzanych nie może spełnić specyfikacji wejściowej, wyjdź Impossible\n. Przykłady możliwych rozwiązań:

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

Przykład testowy

Wejście:

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

Przykładowe dane wyjściowe:

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

Punktacja (AKTUALIZACJA)

To jest golf golfowy z bonusami. Powinieneś wskazać swoją odpowiedzią liczbę kopii lustrzanych, które Twój program może rozwiązać (N). Twój wynik to długość twojego programu w bajtach podzielona przez N. To pozwala ludziom wejść z prostym programem, ale nagradza więcej programistów ambicji premią.

Standardowe luki zabronione.

C # - 897 862 bajtów

Znaleziono poważny błąd polegający na umieszczaniu serwerów lustrzanych w miejscach, w których nie mogą być. Mam nadzieję, że teraz działa! Grałem też trochę w golfa, nie mogłem zostawić tam pętli while ... wstyd.

Kompletny program, pobiera dane wejściowe z STDIN, dane wyjściowe do STDOUT.

To była świetna zabawa, dobrze radzi sobie z problemem 7 na 5 (a kiedy zdejmujesz jedno z lusterek, co uniemożliwia), zajęło około 1 godziny na rozwiązanie 30 na 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 na 5 Przykład:

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

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

Wersja niemożliwa:

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

Impossible

Coś innego (program nie wygląda na oryginalny układ lustra):

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

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

Rozwiązanie 30 na 5:

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

Po kolei patrzy na każde źródło lasera i buduje dla niego prawidłową trasę (jeśli to możliwe), a następnie przechodzi do następnego. Jest to dość proste wyszukiwanie w głąb, które musi wiedzieć, na które źródło lasera (cel) patrzy, ile luster pozostało, aby je umieścić, bieżącą komórkę, w której jest „w”, kierunku, w którym się porusza oraz każdą komórkę jest już odwiedzony (aby nie umieścił lustra w miejscu, w którym już był). Ostatnie 3 są używane do zestawiania ścieżki dla bieżącego celu i resetowane, gdy cel się zmienia. Po połączeniu wszystkich laserów idzie naprzód i wypełnia luki, których nie potrzebuje pozostawić puste (kolejny powód, dla którego musi wiedzieć wszędzie, gdzie jest odwiedzany).

Kiedy buduje trasy, preferuje pójście „do przodu” zamiast wstawiania lustra, a kiedy to robi, preferuje lustro „\” - najlepiej to widać w powyższym przykładzie „czegoś innego”, w którym pomija pierwszą komórkę poniżej na górze „a”, a następnie stale wypełnia „\”, jeśli może znaleźć rozwiązanie z jednym, w przeciwnym razie „/” (naturalnie, jeśli pominięcie pierwszej komórki spowoduje, że nie będzie w stanie znaleźć rozwiązania, wówczas cofnij się i spróbuj umieścić tam lustro).

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 bajtów

Nie rozwiązanie, ale próba, czytaj poniżej.

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

Nie grałem w golfa na maksa, ponieważ nie jestem zadowolony z rozwiązania. Vsprawdza poprawność danego rozwiązania, chodząc po polu Fdla każdego znaku, Cktóry znajdzie na linii bocznej. Rozwiązania są generowane losowo. Jest brzydki, działa na wejście1, ale zajmuje dużo czasu na inne wpisy. Ponieważ losowo wypróbowuje rozwiązania, nie uważam tego za rzeczywiste rozwiązanie danego problemu; ale może pomóc innym.

Biegać: echo "entry1.txt" | python script.py