AKTUALISIERTE WERTUNG : Da diese Herausforderung schwieriger ist als erwartet, habe ich die Bewertung angepasst. Ein Programm, das eine einzelne Spiegeleingabe lösen kann, ist eine gültige Antwort. Anspruchsvollere Programme erhalten einen Bonus auf ihre Punktzahl.

Bei PPCG gab es mehrere Rätsel, um einen Laserpfad in einer Schachtel mit Spiegeln zu finden. In diesem Puzzle musst du eine Schachtel mit Spiegeln erstellen , die mit einer Reihe von Laserzielen übereinstimmen.

Sie erhalten eine Box und eine Spezifikation, in die Laser ein- und aussteigen sollen. Ihr Programm muss genau N doppelseitige Spiegel in der Box platzieren, um die Spezifikation zu erfüllen. Die Spiegel müssen um 45 Grad abgewinkelt sein, können jedoch vorwärts oder rückwärts geneigt sein.

Eingang

Ihr Programm sollte ein Box-Grid über STDIN, ein Befehlszeilenargument oder eine Datei in den folgenden Formatbeispielen akzeptieren:

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

Die Buchstabenpaare ([a-zA-Z] können verwendet werden) geben die Eingabe / Ausgabe von bis zu 52 Lasern an. In der Box wird N sein/ Spiegel. Die Boxmaße betragen 3 <= B, H <= 200. Die Box besteht aus+|- Zeichen. Es kann eine beliebige Anzahl von Spiegeln in der Box geben, einschließlich Null.

Ausgabe

Die Ausgabe sollte mit der Eingabe übereinstimmen, außer dass die /Zeichen verschoben und / oder in \Zeichen geändert werden können . Ihr Programm sollte eine korrekte Mirror-Box-Zeichenfolge an STDOUT oder eine Datei senden, wobei die neue Zeile optional nachgestellt wird. Wenn keine Platzierung von Spiegeln die Eingangsspezifikation erfüllen kann, wird ausgegeben Impossible\n. Beispiele für mögliche Lösungen:

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

Testbeispiel

Eingang:

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

Beispielausgabe:

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

Wertung (AKTUALISIERT)

Dies ist Code-Golf mit Boni. Sie sollten mit Ihrer Antwort angeben, wie viele Spiegel Ihr Programm lösen kann (N). Ihre Punktzahl ist die Länge Ihres Programms in Bytes geteilt durch N. Dies ermöglicht den Teilnehmern an einem einfachen Programm, belohnt jedoch ambitioniertere Programmierer mit einem Bonus.

Standardlücken sind nicht erlaubt.

C # - 897 862 Bytes

Es wurde ein schwerwiegender Fehler gefunden, bei dem Spiegel an Stellen platziert wurden, an denen sie nicht vorhanden sind. Jetzt klappt es hoffentlich! Habe auch ein bisschen Golf gespielt, konnte die while-Schleife nicht mehr hinterlassen ... beschämend.

Vollständiges Programm, nimmt Eingaben von STDIN entgegen und gibt sie an STDOUT aus.

Das hat sehr viel Spaß gemacht, es ist gut mit dem 7 mal 5 Problem umgegangen (und als Sie einen der Spiegel entfernt haben, was es unmöglich machte), hat es ungefähr 1 Stunde gedauert, um die 30 mal 5 zu lösen.

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 von 5 Beispiel:

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

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

Unmögliche Version:

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

Impossible

Etwas anderes (das Programm schaut nicht auf das ursprüngliche Spiegel-Layout):

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

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

30 mal 5 Lösung:

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

Es überprüft nacheinander jede Laserquelle, erstellt eine gültige Route (sofern dies möglich ist) und wechselt dann zur nächsten. Es ist eine ziemlich einfache Tiefensuche, die wissen muss, auf welche Laserquelle (Ziel) sie schaut, wie viele Spiegel es noch gibt, in welche Richtung es sich bewegt und in welche Zelle es sich bewegt Es wurde bereits besucht (damit es keinen Spiegel an eine Stelle setzt, an der es bereits war). Die letzten 3 werden zum Zusammenstellen des Pfads für das aktuelle Ziel und zum Zurücksetzen verwendet, wenn sich das Ziel ändert. Sobald alle Laser miteinander verbunden sind, wird der Vorgang fortgesetzt und alle nicht benötigten Lücken werden ausgefüllt (ein weiterer Grund, warum er wissen muss, wo er besucht wird).

Wenn Routen erstellt werden, wird das Einfügen eines Spiegels vorgezogen, und wenn dies der Fall ist, wird ein Spiegel "\" vorgezogen. Dies ist am besten im obigen Beispiel "etwas anderes" zu sehen, in dem die erste Zelle unter dem Spiegel übersprungen wird top-most 'a', dann füllt es kontinuierlich ein "\" aus, wenn es eine Lösung mit einem finden kann, andernfalls ein "/" (wenn das Überspringen der ersten Zelle dazu führte, dass es keine Lösung finden konnte, dann würde es dies tun zurückverfolgen und stattdessen versuchen, dort einen Spiegel anzubringen).

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

Keine Lösung, sondern ein Versuch, lesen Sie weiter unten.

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

Ich habe dies nicht bis zum Äußersten golfen, da ich mit der Lösung nicht zufrieden bin. VValidiert eine gegebene Lösung, indem das Feld Ffür jedes Zeichen Cdurchlaufen wird, das es an der Seitenlinie findet. Lösungen werden zufällig generiert. Es ist hässlich, es funktioniert für entry1, nimmt aber viel Zeit für die anderen Einträge in Anspruch. Da es zufällig nach Lösungen sucht, halte ich dies nicht für eine tatsächliche Lösung für das gegebene Problem. aber es könnte anderen helfen.

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