Di Twitch Plays Pokémon , salah satu rintangan paling menyebalkan yang bisa dihadapi adalah teka-teki es, di mana Anda harus melakukan perjalanan dari satu tempat ke tempat lain dengan menggeser semua jalan ke satu arah sampai Anda menabrak dinding atau batu besar.

Tugas Anda adalah membangun sebuah program yang akan menghasilkan teka-teki es acak yang sulit.

Program Anda akan menerima tiga angka, M, N, dan P, sebagai masukan (dengan 10 <= M <= 30, 15 <= N <= 40, dan 0 <= P < 65536):

12 18

dan akan menampilkan:

• Sebuah kotak Mdengan masing-masing Nterdiri dari .dan O, mewakili es dan batu besar.
• Penanda posisi yang menunjukkan dari mana puzzle itu masuk. Penanda posisi ini terdiri dari surat L, R, T, atauB , mewakili kiri, kanan, atas, dan bawah, diikuti dengan angka yang mewakili posisi (dari kiri atau atas) di sisi itu akan masuk dari.
• Penanda posisi serupa yang mewakili tempat keluarnya puzzle.
• Solusi terpendek untuk teka-teki, yang terdiri dari urutan L, R, U, dan Dmasing-masing.

Contoh output:

..O...O...........
............O.....
..O...............
.......O..........
..................
...........O......
O..O...........O..
..........O.......
..O..........O....
........O.........
O....O.........O..
............O.....
R 4
B 5
LDLDRULD
(Note that this output is actually invalid because it is not actually long enough.)

Untuk input Mdan N, solusi untuk puzzle harus memiliki setidaknya min(M, N)langkah dan memindahkan setidaknya 2 (M + N)total ruang. (Untuk referensi, teka-teki di atas bergerak total 12 langkah, bergerak 69 ruang.) Generator puzzle Anda harus menghasilkan yang berbeda Mdengan Nteka-teki dengan jalan solusi yang berbeda (yaitu urutan yang berbeda dari langkah-langkah untuk setiap solusi) untuk masing-masing benih P.

• Perhatikan bahwa persyaratan jalur solusi yang berbeda adalah untuk menghindari solusi yang mencoba menghasilkan jalur batu secara sistematis, seperti solusi Claudiu di sini . Jika ada dua atau tiga pasang solusi identik karena keanehan dalam keacakan, itu akan baik-baik saja, asalkan program tidak sengaja mencoba secara sistematis menghasilkan teka-teki dengan urutan gerakan yang sama.

Kode terpendek untuk melakukan hal di atas menang.

Python, 672 548 karakter, teka-teki yang lebih menarik

Meskipun mengikuti aturan ketat, program Python saya yang lain mengalahkan yang ini, saya memutuskan untuk menulis yang akan menghasilkan lebih banyak teka-teki yang menarik. Ini dia:

R=range;import random as J;X=J.randint
x=(0,1,-1,0);y=x[2:]+x
g=lambda r,c:(0<=r<H)+(0<=c<W)>1and f[r][c]or x[(r,c)in(A,E)]
l=lambda r,c:g(r+y[d],c+x[d])<1and(r,c)or l(r+y[d],c+x[d])
H,W,P=input();J.seed(P)
while 1:
 A=(-1,X(0,W));E=(H,X(0,W));f=[[X(0,7)for _ in R(W)]for _ in R(H)]
 q=[(A,'')];n=z={}
 while q and n!=E:
    n,O=q.pop()
    for d in R(4):
     N=l(*n)
     if g(n[0]+y[d],n[1]+x[d])and N not in z:q[:0]=[(N,O+"URLD"[d])];z[N]=1
 if(n==E)*len(O)>min(H,W):print"\n".join(''.join('O.'[c>0]for c in T)for T in f),"\nT",A[1],"\nB",E[1],"\n",O;break

Level indentasi adalah spasi, tab, tab + spasi.

Sampel :

$ echo [10,15,0] | python ice2.py
.....OO........
...............
...O....O.OO..O
...........O...
..O....O.......
.......O....O..
....O..........
.............O.
..............O
...............
T 1
B 10
DLURDRURULDRD

Ini digunakan Psebagai benih, sehingga masing P- masing akan menghasilkan puzzle yang sama, dan masing-masing berbeda Psangat mungkin berbeda:

$ echo [10,15,1] | python ice2.py
.OOO.O.........
...O......O.O.O
.......O.......
..O..........OO
.....O.........
.............O.
.O.............
.O............O
O....O.........
......O........
T 14
B 8
DLDRDLURULD

Ini bekerja cukup cepat hingga ukuran M=25,N=40tetapi melewati itu menjadi sangat lambat. Secara teori itu seharusnya bekerja M=30, N=40jika Anda membiarkannya berjalan cukup lama. Saya sudah menulis secara manual di sini karena sulit untuk diikuti - program hanya menampilkan puzzle.

$ echo [25,40,0] | python ice2.py
                   *
...................dO....urrrO..O..O....
....O.....O........dO....u..dO..........
..........O.....O..d....Ou.Odrrrrrrrrrrr
...........O.......d.O..Ou..O.....OOllld
.O....O.OO.........drrrrrrO....Olllud..O
O......O...O.O.....O............dO.ud...
O........OO..........O.........Od..ud..O
.........O......................d..ud...
....O.....O.O....O.....O........d..ud.O.
.....O..O...................O...d..udO..
.........O.........O..O.........d..ud...
.......O.O...O..O.OO....O...OOlldOOld...
........Olllllllllu....OO.OO..dOO...O...
.O.O....Od........u......O....d..O...O..
..O....O.d........u..O........d..O..O...
....O....d..O.....uO.....O....d.........
.........d........u...........d.........
.........d....O...u.O..O.....Od.O.......
........Od...O....u...........d.........
.O.....OuxrrrrO...u...OOOO..O.d.........
........udO..dO.O.u...........d.........
O..O.O..ud...d..urrO..........d.O...O...
........ud...d..u.O.O........Od..O...O..
..OO....ud..Od..u......OllllludO.....O..
..O....OldO..dOOlllllllld...Old...O..O..
             *
T 19
B 13
DRURDRDLDLULDLDLULDLURULDLURD

Penjelasan :

Program loop, menghasilkan posisi awal acak di atas, posisi akhir acak di bagian bawah, dan kotak acak dengan 12.5%kesempatan untuk batu besar di tempat tertentu. Ini kemudian memecahkan teka-teki dengan pencarian pertama yang luas dan jika solusinya ada dan lebih besar dari min(H,W), ia mencetak dan keluar.

Jawa - 2632

Sementara saya mengagumi kemurnian teknis jawaban Claudiu , saya memutuskan untuk mencoba membuat puzzle yang sedikit lebih sulit;)

Langkah-langkah dasar (sangat sederhana):

Randomize entry location
Step forward
For min(m,n)-1 steps:
    Rotate left or right
    Slide until I hit something or go a random distance
    Place a rock in front of stopping location
If I can slide straight to any wall:
    Slide to exit
Else
    Create another step and try again

If at any step I get trapped, start over
If BFS finds shorter path, start over

Saya juga menandai setiap tempat sebagai 'nogo' saat saya meluncur. Jika saya berakhir di tempat nogo (atau tepat di depan salah satu yang berarti ada batu di sana), itu adalah langkah yang tidak valid.

Jadi, pada dasarnya idenya adalah membuat banyak peta secara acak , dan menyimpan yang pertama yang valid. Saya berencana untuk membuat ini lebih pintar (mundur, dll), tetapi berfungsi dengan baik sekarang. Mungkin juga mengurangi beberapa kode yang berlebihan, kita akan lihat.

Seperti itu, ia menghasilkan peta kecil (15x10) hampir secara instan, sedang (30x20) peta dalam beberapa detik, dan besar (40x30) dalam beberapa waktu acak antara 20 detik dan 20 menit, tergantung pada biji. Ini menguji antara 300k-500k peta / detik pada mesin saya, tergantung pada ukuran.

Catatan: Kadang-kadang peta tidak terlalu keras, hanya karena hanya ada batu sebanyak langkah, dan kecuali langkah membawa Anda ke dinding, seringkali hanya ada satu pilihan jika Anda ingin menabrak batu yang sebenarnya. Saya akan memperbaikinya nanti dengan menempatkan batu "acak" di tempat yang aman setelah semua langkah diambil. Karena nogo spot sudah ditandai, itu seharusnya cukup sederhana. Untuk saat ini, nikmati saja contoh-contoh ini:

Output menunjukkan ukuran / biji yang berbeda:

$ java I 30 20 6851              $ java I 15 10 1     $ java I 15 10 65513  

............................O.      .......O.......     ....O..........     
..............................      ...............     ...............     
..............................      .........O.....     .........O.....     
..........O......O............      .............O.     ..............O     
...............O...........O..      ...............     ...............     
..............................      .......O.......     .....O.O.......     
..............................      O..............     ...............     
........................O.....      ...............     ..........O....     
..............................      ...............     O..............     
...O.......................O..      ......O........     ...............     
O...............O.OO..........          
..............O..........O....          
...........O..................      T 14                R 6         
....O.........................      T 7                 T 14            
..............................      DLDLULURU           LULDLDRURU
..............................
..............................
.................O............
.O............................
..............................


B 28
R 9
ULURDLDLDRURDLDRURUR

Ukuran maksimal 40x30:

$ java I 40 30 2

........................................
........................................
........................................
........................................
................O.......................
..........O.............................
........................................
.......O................................
.....................O..........O.......
......................O.................
.................................O......
......................................O.
........................................
........................................
..............................O.........
...........O............................
........................................
.......................................O
.........O...................O..........
....................O...................
...............................O........
............O..O......................O.
......O...........O.....................
..................O....O................
..................................O.....
........................................
..............................O.........
.....................................O..
...........O............................
...................O....................

B 19
B 11
URURDLULULDRDRDLULDLDLULURDLD

Golf:

import java.util.*;import java.awt.*;class I{int m,n,p,g,a[][],b[][];Random r;Point s,e,c;ArrayList<Integer>z;void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}void G(String[]y){m=Integer.valueOf(y[0]);n=Integer.valueOf(y[1]);p=Integer.valueOf(y[2]);r=new Random(p);Q("",1);int o=0,i,j,u=0;char t,f[]={85,76,68,82};while(o<3){if(++u%20000==0)Q("\r#"+u,0);a=new int[m+2][n+2];b=new int[m+2][n+2];for(i=0;i<m+2;i++)for(j=0;j<n+2;j++)if(i==0||i==m+1||j==0||j==n+1)a[i][j]=2;s=new Point();int e=r.nextInt(m*2+n*2);if(e<m*2){s.x=e%m+1;s.y=e<m?0:n+1;}else{s.y=(e-m*2)%n+1;s.x=(e-m*2)<n?0:m+1;}if(s.x<1)g=3;else if(s.x>m)g=1;else if(s.y<1)g=2;else if(s.y>n)g=0;a[s.x][s.y]=0;c=new Point(s);z=new ArrayList<Integer>();z.add(g);for(i=0;i++<Math.min(m,n)-1;)if(N()<1&&N()<1)break;o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);}Q("\r",0);for(j=1;j<n+1;j++){for(i=1;i<m+1;i++)Q(String.valueOf(a[i][j]>0?'O':'.'),0);Q("",1);}Q("\n\n",0);if(s.x<1||s.x>m){t=s.x<1?'L':'R';u=s.y;}else{t=s.y<1?'T':'B';u=s.x;}Q(t+" "+u,1);if(e.x<1||e.x>m){t=e.x<1?'L':'R';u=e.y;}else{t=e.y<1?'T':'B';u=e.x;}Q(t+" "+u,1);for(i=0;i<z.size();)Q(String.valueOf(f[z.get(i++)]),0);Q("",1);}public static void main(String[]a){new I().G(a);}int F(){int c=0;while(C()<1&&c++<10)if(N()<1)return 0;return e==null?0:1;}int C(){int d=g<2?-1:1;if(g%2<1){int y=c.y;while(y>0&&y<n+1){y+=d;if(a[c.x][y]==1)return 0;}e=new Point(c.x,y);}else{int x=c.x;while(x>0&&x<m+1){x+=d;if(a[x][c.y]==1)return 0;}e=new Point(x,c.y);}a[e.x][e.y]=0;return 1;}int V(){if((s.x-e.x)+(s.y-e.y)<2)return 0;Queue<Point>q=new ArrayDeque<Point>();Queue<Integer>d=new ArrayDeque<Integer>();a[s.x][s.y]=-2;q.add(s);d.add(0);while(q.size()>0){Point t=q.poll();int h=d.poll(),i=0;if(t.equals(e))return h;for(;i<4;i++){Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);if(a[n.x][n.y]==-2)continue;a[n.x][n.y]=-2;q.add(n);d.add(h+1);}}return 0;}int N(){Point q;int d=g<2?-1:1,x,y;System.arraycopy(a,0,b,0,a.length);q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)return 0;x=q.x;y=q.y;if(g%2<1)y+=d;else x+=d;if(b[x][y]<0)return 0;b[q.x][q.y]=-1;b[x][y]=1;int f=r.nextInt(2)<1?-1:1;g=g%2<1?(f<0?1:3):(g=f<0?0:2);c=q;System.arraycopy(b,0,a,0,a.length);z.add(g);return 1;}Point S(int[][]u,Point f,int w,int d,int q,int s){int i=1,x=f.x,y=f.y;for(;i<=q;i++){if(w%2<1)y=f.y+i*d;else x=f.x+i*d;if(e!=null&&e.x==x&&e.y==y)return e;if(y<0||y>n+1||x<0||x>m+1)return f;if(s<1&&u[x][y]<1)u[x][y]=-1;if(u[x][y]>0){if(w%2<1)y-=d;else x-=d;return new Point(x,y);}}if(w%2<1)return new Point(f.x,f.y+i*d);else return new Point(f.x+i*d,f.y);}}

Dengan jeda baris:

import java.util.*;
import java.awt.*;

class I{
    int m,n,p,g,a[][],b[][];
    Random r;
    Point s,e,c;
    ArrayList<Integer>z;

    void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}

    void G(String[]y){
        m=Integer.valueOf(y[0]);
        n=Integer.valueOf(y[1]);
        p=Integer.valueOf(y[2]);
        r=new Random(p);
        Q("",1);

        int o=0,i,j,u=0;
        char t,f[]={85,76,68,82};
        while(o<3){
            if(++u%20000==0)
                Q("\r#"+u,0);

            a=new int[m+2][n+2];
            b=new int[m+2][n+2];
            for(i=0;i<m+2;i++)
                for(j=0;j<n+2;j++)
                    if(i==0||i==m+1||j==0||j==n+1)
                        a[i][j]=2;

            s=new Point(); 
            int e=r.nextInt(m*2+n*2);
            if(e<m*2){
                s.x=e%m+1;
                s.y=e<m?0:n+1;
            }else{
                s.y=(e-m*2)%n+1;
                s.x=(e-m*2)<n?0:m+1;
            }
            if(s.x<1)g=3;
            else if(s.x>m)g=1;
            else if(s.y<1)g=2;
            else if(s.y>n)g=0;

            a[s.x][s.y]=0;
            c=new Point(s);
            z=new ArrayList<Integer>();
            z.add(g);

            for(i=0;i++<Math.min(m,n)-1;)
                if(N()<1&&N()<1)
                        break;
            o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);
        }

        Q("\r",0);
        for(j=1;j<n+1;j++){
            for(i=1;i<m+1;i++)
                Q(String.valueOf(a[i][j]>0?'O':'.'),0);
            Q("",1);
        }
        Q("\n\n",0);
        if(s.x<1||s.x>m){
            t=s.x<1?'L':'R';
            u=s.y;
        }else{
            t=s.y<1?'T':'B';
            u=s.x;
        }
        Q(t+" "+u,1);
        if(e.x<1||e.x>m){
            t=e.x<1?'L':'R';
            u=e.y;
        } else {
            t=e.y<1?'T':'B';
            u=e.x;
        }
        Q(t+" "+u,1);
        for(i=0;i<z.size();)
            Q(String.valueOf(f[z.get(i++)]),0);
        Q("",1);
    }

    public static void main(String[]a){
        new I().G(a);
    }

    int F(){
        int c=0;
        while(C()<1&&c++<10)
            if(N()<1)
                return 0;
        return e==null?0:1;
    }

    int C(){
        int d=g<2?-1:1;
        if(g%2<1){
            int y=c.y;
            while(y>0&&y<n+1){
                y+=d;
                if(a[c.x][y]==1)
                    return 0;
            }
            e=new Point(c.x,y);
        }else{
            int x=c.x;
            while(x>0&&x<m+1){
                x+=d;
                if(a[x][c.y]==1)
                    return 0;
            }
            e=new Point(x,c.y);
        }
        a[e.x][e.y]=0;
        return 1;
    }


    int V(){
        if((s.x-e.x)+(s.y-e.y)<2)
            return 0;
        Queue<Point>q=new ArrayDeque<Point>();
        Queue<Integer>d=new ArrayDeque<Integer>();
        a[s.x][s.y]=-2;

        q.add(s);
        d.add(0);
        while(q.size()>0){
            Point t=q.poll();
            int h=d.poll(),i=0;
            if(t.equals(e))
                return h;
            for(;i<4;i++){
                Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);
                if(a[n.x][n.y]==-2)
                    continue;
                a[n.x][n.y]=-2;
                q.add(n);d.add(h+1);
            }
        }
        return 0;
    }


    int N(){
        Point q;
        int d=g<2?-1:1,x,y;
        System.arraycopy(a,0,b,0,a.length);
        q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);      
        if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)
            return 0;
        x=q.x;
        y=q.y;
        if(g%2<1)
            y+=d;
        else
            x+=d;
        if(b[x][y]<0)
            return 0;
        b[q.x][q.y]=-1;
        b[x][y]=1;
        int f=r.nextInt(2)<1?-1:1;          
        g=g%2<1?(f<0?1:3):(g=f<0?0:2);
        c=q;
        System.arraycopy(b,0,a,0,a.length);
        z.add(g);
        return 1;
    }

    Point S(int[][]u,Point f,int w,int d,int q,int s){
        int i=1,x=f.x,y=f.y;
        for(;i<=q;i++){
            if(w%2<1)
                y=f.y+i*d;
            else
                x=f.x+i*d;
            if(e!=null&&e.x==x&&e.y==y)
                return e;
            if(y<0||y>n+1||x<0||x>m+1)
                return f;
            if(s<1&&u[x][y]<1)
                u[x][y]=-1;
            if(u[x][y]>0){
                if(w%2<1)
                    y-=d;
                else
                    x-=d;
                return new Point(x,y);
            }
        }
        if(w%2<1)
            return new Point(f.x,f.y+i*d);
        else
            return new Point(f.x+i*d,f.y);              
    }
}

Python, 235 206 185 176 karakter

H,W,P=input()
t=''
for x in range(16):t+=".O"[(P>>x)%2]
for n in[t[1:],t[0],"O","...O"]+["."]*(H-5)+[".O.."]:print(n*W)[:W]
print"B 1\nR",(H,3)[-W%4/2],"\n",("URDR"*W)[:W+W%2]

Penggunaan :

Masukan melalui stdin formulir [M, N, P].

$ echo [14, 17, 2] | python ice.py
O..............O.
.................
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

Anda bilang peta harus berbeda untuk setiap seed P... dan mereka adalah:

$ echo [14, 17, 233] | python ice.py
..O.OOO..........
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR
$ echo [14, 17, 65133] | python ice.py
.OO.OO..OOOOOOO.O
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

Dan contoh dengan ukuran yang berbeda:

$ echo [10, 15, 65133] | python ice.py
.OO.OO..OOOOOOO
OOOOOOOOOOOOOOO
OOOOOOOOOOOOOOO
...O...O...O...
...............
...............
...............
...............
...............
.O...O...O...O.
B 1
R 10
URDRURDRURDRURDR

Memenuhi semua kriteria objektif yang disediakan:

• Masing-masing Pmengarah ke teka-teki yang berbeda
• Hanya ada satu solusi, jadi itu adalah yang terpendek
• Solusinya mengambil N + N%2langkah - langkah, setidaknyaN
• Solusinya selalu membutuhkan lebih dari 2 (M + N)total ruang

Penjelasan :

Setiap baris dikonstruksi dengan mengulang Wkali elemen string tertentu dan membatasi panjangnya W(saya menggunakan Hdan Wbukannya Mdan N).

Dua baris pertama bergantung pada Puntuk membuat setiap puzzle unik. Pada dasarnya, note yang Pcocok dengan integer unsigned 16-bit. Saya mengonversi Pke biner, menggunakan .untuk 0 dan Ountuk 1:

t=''
for x in range(16):t+=".O"[(P>>x)%2]

Elemen baris pertama adalah 15 bit terakhir t[1:], sedangkan elemen baris kedua adalah bit 1 t[0],. Saya tidak bisa meletakkan semuanya di satu baris karena lebar minimum adalah 15, yang tidak akan cocok dengan 16 bit jika P> 32767. Jadi, dua baris pertama secara unik mewakili masing-masing nilai yang mungkin dari P.

Baris ketiga adalah dinding penuh sehingga nilai Ptidak mempengaruhi solusi.

Kemudian ikuti elemen maze yang sebenarnya. Baris ini mencetak semuanya, mengulanginya hingga tutup. Hasilnya seperti yang Anda lihat di atas:

for n in[t[1:],t[0],"O","O..."]+["."]*(H-5)+["..O."]:print(n*W)[:W]

Sisanya hanya mencari tahu bagaimana menyelesaikan labirin yang dihasilkan secara dinamis. Ini hanya tergantung pada lebar labirin. Saya mencatat bahwa solusi, untuk lebar yang diberikan, adalah:

  W  | solution 
-----+---------
  1  | UR
  2  | UR
  3  | UR DR
  4  | UR DR 
  5  | UR DR UR
  6  | UR DR UR
  7  | UR DR UR DR
  8  | UR DR UR DR

dll. Oleh karena itu hanya URDRdiulang dan terputus di tempat yang tepat W+W%2,.

print"B 1\nR",(H,3,3,H)[W%4],"\n",("URDR"*W)[:W+W%2]