SKOR YANG DIPERBARUI : Karena tantangan ini lebih sulit daripada yang saya perkirakan, saya telah menyesuaikan skor. Suatu program yang dapat memecahkan input satu mirror adalah jawaban yang valid. Program yang lebih canggih mendapatkan bonus untuk skor mereka.

Ada beberapa teka-teki pada PPCG untuk menemukan jalur laser di dalam kotak cermin. Dalam teka-teki ini, Anda harus membuat sekotak cermin agar sesuai dengan sejumlah tujuan laser.

Anda diberi kotak dan spesifikasi tempat laser masuk dan keluar. Program Anda perlu menempatkan persis N cermin dua sisi dalam kotak untuk memenuhi spesifikasi. Cermin harus miring pada 45 derajat tetapi dapat miring ke depan atau miring ke belakang.

Memasukkan

Program Anda harus menerima kisi kotak melalui STDIN, argumen baris perintah, atau file dalam contoh format berikut:

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

Pasangan huruf ([a-zA-Z] dapat digunakan) menunjukkan input / output hingga 52 laser. Di dalam kotak akan ada N /mirror. Dimensi kotak akan menjadi 3 <= W, H <= 200. Kotak terbuat dari +|-karakter. Mungkin ada sejumlah mirror di dalam kotak termasuk nol.

Keluaran

Keluaran harus sesuai dengan input, kecuali /karakter dapat dipindahkan dan / atau diubah menjadi \karakter. Program Anda harus mengirim string kotak cermin yang benar ke STDOUT atau file, mengikuti baris baru opsional. Jika tidak ada penempatan mirror yang dapat memenuhi spesifikasi input, output Impossible\n. Contoh solusi yang mungkin:

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

Contoh pengujian

Memasukkan:

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

Contoh output:

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

Penilaian (DIPERBARUI)

Ini adalah kode-golf dengan bonus. Anda harus mencalonkan dengan jawaban Anda berapa banyak mirror yang dapat diselesaikan oleh program Anda (N). Skor Anda adalah panjang program Anda dalam byte yang dibagi dengan N. Ini memungkinkan orang untuk masuk dengan program sederhana, tetapi memberi penghargaan lebih banyak programmer ambisi dengan bonus.

Celah standar tidak diijinkan.

C # - 897 862 byte

Menemukan bug serius dengan meletakkan cermin di tempat yang tidak mungkin. Semoga berhasil, semoga! Juga melakukan golf ringan, tidak bisa meninggalkan loop sementara di sana ... memalukan.

Program lengkap, mengambil input dari STDIN, output ke STDOUT.

Ini sangat menyenangkan, bisa mengatasi masalah 7 dengan 5 (dan ketika Anda menghapus salah satu cermin, membuatnya tidak mungkin), butuh sekitar 1 jam untuk menyelesaikan 30 dengan 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 oleh 5 Contoh:

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

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

Versi yang mustahil:

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

Impossible

Sesuatu yang berbeda (program tidak melihat tata letak cermin asli):

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

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

30 oleh 5 solusi:

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

Ia melihat setiap sumber laser secara bergantian, dan membangun rute yang valid untuk itu (jika bisa), dan kemudian bergerak ke yang berikutnya. Ini adalah pencarian mendalam-pertama yang cukup sederhana, yang harus mengetahui sumber laser (target) yang dilihatnya, berapa banyak cermin yang tersisa untuk ditempatkan, sel saat ini "di", arahnya bergerak, dan setiap sel sudah dikunjungi (sehingga tidak menaruh cermin di tempat yang sudah ada). 3 terakhir digunakan untuk merakit jalur untuk target saat ini, dan pada reset ketika target berubah. Setelah semuanya terhubung dengan laser, ia melanjutkan dan mengisi setiap celah yang tidak perlu dikosongkan (alasan lain yang perlu diketahui di mana saja ia dikunjungi).

Ketika membangun rute, ia lebih memilih "maju" daripada memasukkan cermin, dan ketika itu melakukannya, ia lebih menyukai cermin "\" - ini paling baik dilihat dalam contoh "sesuatu yang berbeda" di atas, di mana ia melewatkan sel pertama di bawah paling atas 'a', maka terus mengisi "\" jika dapat menemukan solusi dengan satu, jika tidak, "/" (secara alami, jika melewatkan sel pertama mengakibatkan ia tidak dapat menemukan solusi, maka itu akan mundur dan coba letakkan cermin di sana).

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 byte

Bukan solusi, tetapi upaya, baca di bawah ini.

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

Saya tidak menggunakan golf ini secara maksimal, karena saya tidak puas dengan solusinya. Vmemvalidasi solusi yang diberikan dengan berjalan bidang Funtuk setiap karakter Cyang ditemukannya di sampingan. Solusi dihasilkan secara acak. Itu jelek, itu berfungsi untuk entri1, tetapi membutuhkan banyak waktu untuk entri lain. Karena secara acak mencoba solusi, saya tidak menganggap ini sebagai solusi aktual untuk masalah yang diberikan; tetapi mungkin membantu orang lain.

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