Diberikan 2 input integer yang mewakili ukuran bidang, xdan y, output jalur melalui bidang tersebut.

Contoh output untuk 5, 4:

#    
#    
# ###
### #

Seluruh bidang adalah 5 dengan 4, dan ada jalur yang terbuat dari tanda hash yang melintasi bidang.

Jalan harus selalu dimulai di sudut kiri atas, dan pergi ke kanan bawah. Seluruh jalur harus diacak setiap kali program dijalankan. Setiap jalur yang valid harus berupa output yang mungkin.

Aturan untuk jalur adalah:

• Terbuat dari hashmark

• Setiap hash hanya terhubung ke 2 hash lainnya (yaitu jalan tidak berpotongan atau berjalan di samping itu sendiri)

Spasi non-hash dapat diisi dengan karakter lain, tetapi harus konsisten (yaitu semua spasi, semua periode, dll.)

Contoh:

2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

## ###
 # # #
## # #
# ## #
###  #

7, 9

#######
      #
####  #
#  #  #
#  #  #
#  #  #
#  ####
#
#######

Jenis jalan ini mirip dengan jalan acak yang menghindari diri sendiri, namun tidak dapat berbatasan dengan dirinya sendiri tidak seperti SAW sejati.

Kontinuitas jalur dan jalur sentuhan keduanya ditentukan tanpa diagonal.

MATLAB, 316 305 300 293 byte

function P=f(a,b);z(a,b)=0;P=z;c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');B=1;while B;P=z;P(1)=1;for K=1:a*b;S=z;S(a,b)=1;for L=2:a*b;S(~S&c(S)&~P)=L;end;[i,j]=find(S&c(P==K));if i;r=randi(nnz(i));else;break;end;P(i(r),j(r))=K+1;if P(a,b);break;end;end;B=any(any(c(P>0)>3));end;P(P>0)=35;P=[P,'']

Terima kasih @LuisMendo untuk berbagai saran dan banyak byte =)

Cobalah online! (Tanpa jaminan: Perhatikan bahwa beberapa penyesuaian diperlukan untuk menjalankannya pada Oktaf: Pertama-tama saya perlu menghapus functionkata kunci dan nilai-nilai hardcode, kedua: Ruang tidak bisa dicetak dengan benar seperti pada Matlab. Juga saya tidak periksa perintah konvolusi Oktaf, yang mungkin bertindak berbeda.)

Contoh output untuk input (7,10)(sudah cukup lama):

#         
#         
##        
 ##       
  #   ### 
  #   # ##
  #####  #

Penjelasan

Ini menghasilkan jalur secara berurutan dari kiri atas ke kanan bawah dengan 4-konektivitas yang diinginkan, dan kemudian menggunakan sampel penolakan untuk menolak jalur yang melanggar kriteria bahwa Anda tidak dapat memiliki bagian yang berdekatan.

function P=f(a,b);
z(a,b)=0;                                 % a matrix of zeros of the size of th efield
P=z;                                    
c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');  % our convolution function, we always convolute with the same 4-neighbourhood kernel
B=1;
while B;                                  % while we reject, we generate paths:
    P=z;
    P(1)=1;                               % P is our path, we place the first seed
    for K=1:a*b;                          % in this loop we generate the all shortest paths (flood fill) from the bottom right, withot crossing the path to see what fiels are reachable from the bottom left
        S=z;
        S(a,b)=1;                         % seed on the bottom left
        for L=2:a*b;
            S(~S&c(S)&~P)=L;              % update flood front
        end;
        [i,j]=find(S&c(P==K));            % find a neighbour of the current end of the path, that is also reachable from the bottom left
        if i;                             % if we found some choose a random one
            r=randi(nnz(i));
        else;
            break;                        % otherwise restart (might not be necessary, but I'm too tired to think about it properly=)
        end;
        P(i(r),j(r))=K+1;                 % update the end of the current path
        if P(a,b);                        % if we finished, stop continuing this path
            break;
        end;
    end;
    B=any(any(c(P>0)>3));                 % check if we actually have a valid path
end;
P(P>0)=35;                                % format the path nicely
P=[P,''];

Oh dan seperti biasa:

Konvolusi adalah kunci kesuksesan.

Befunge, 344 byte

&v>>>#p_:63p:43g`\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v
 40$ v++!\`g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v
#11^$_83p73v >1+:41g`!#v_$,1+:43g`!#v_@>->2>+00p+141^_
<p1^     vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35*
8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^
443>:!#v_>>1-::3%1-:53g+00p\3/1-:63g+01p^
^>^>>$#<"#"53g63g7+p41g53g-43g63g-+!#^_

Cobalah online!

Seperti @flawr disebutkan dalam jawaban MATLAB mereka, ini mungkin memakan waktu jika ukuran bidang adalah ukuran non-sepele. Sebenarnya cukup mudah untuk masuk ke situasi di mana itu benar-benar tidak layak untuk mencoba menunggu sampai selesai, karena Anda kemungkinan besar akan menunggu sampai akhir waktu.

Untuk memahami mengapa hal ini terjadi, akan sangat membantu untuk melihat program saat dijalankan di salah satu dari banyak "pengadu visual" Befunge. Karena data dan kode adalah hal yang sama di Befunge, Anda akan dapat melihat lintasan karena berubah seiring waktu. Sebagai contoh, berikut ini adalah animasi pendek yang menunjukkan seperti apa bagian dari lari di jalur lambat.

Setelah algoritma memutuskan untuk membuat belokan yang menentukan ke kiri di bagian bawah batas lapangan, pada dasarnya mengutuk dirinya sendiri untuk seumur hidup berkeliaran tanpa tujuan. Sejak saat itu, ia harus mengikuti setiap jalur yang mungkin ada di area berpagar itu sebelum dapat mundur dan mencoba belokan ke kanan. Dan jumlah jalur potensial dalam kasus ini dapat dengan mudah menjadi astronomi.

Intinya: Jika sepertinya butuh waktu lama, mungkin ide yang bagus untuk membatalkan eksekusi dan memulai lagi.

Penjelasan

Ini pada dasarnya adalah algoritma rekursif, mencoba setiap jalur yang mungkin melalui bidang, dan kemudian membatalkan langkah-langkah yang telah diikuti setiap kali macet. Karena Befunge tidak memiliki konsep fungsi, fungsi rekursif keluar dari pertanyaan, tetapi kita dapat meniru prosesnya dengan melacak keadaan pada stack.

Ini berfungsi dengan mengisi tumpukan dengan koordinat potensial yang mungkin ingin kita ikuti. Kemudian kami menarik satu set dari tumpukan dan memeriksa apakah itu cocok (yaitu dalam jangkauan dan tidak tumpang tindih dengan jalur yang ada). Setelah kami mendapat tempat yang bagus, kami menulis a #ke playfield di lokasi itu, dan menambahkan detail itu ke tumpukan jika kami perlu mundur nanti.

Kami kemudian mendorong empat set koordinat tambahan ke stack (dalam urutan acak) yang menunjukkan jalur potensial yang dapat kita ambil dari lokasi baru ini, dan melompat kembali ke awal loop. Jika tidak ada jalur potensial yang layak, kami akan sampai ke titik di tumpukan tempat kami menyimpan lokasi yang #kami tulis, jadi kami akan membatalkan langkah itu dan terus mencoba koordinat potensial dari satu langkah sebelumnya.

Seperti inilah bentuk kode dengan berbagai bagian komponen yang disorot:

Baca lebar dan tinggi bidang, dan dorong koordinat awal bersama dengan 0penanda jenis untuk menunjukkan jalur potensial daripada lokasi mundur.
Periksa lokasi pelacakan ulang (ditunjukkan oleh 1penanda jenis) yang dikembalikan dengan pperintah sederhana , karena disimpan dalam format yang tepat yang diperlukan untuk menulis spasi kembali ke dalam playfield.
Periksa apakah koordinat masih di dalam playfield. Jika mereka di luar jangkauan, jatuhkan dari tumpukan dan putar kembali untuk mencoba koordinat potensial berikutnya.
Jika berada dalam jangkauan, dapatkan dua nilai berikutnya dari tumpukan, yang merupakan lokasi langkah sebelumnya (diperlukan dalam tes yang mengikuti ini).
Periksa apakah koordinat akan bersentuhan dengan segmen jalan yang ada. Lokasi langkah sebelumnya jelas diabaikan dari pemeriksaan ini.
Jika semua tes berhasil, tulis a #ke dalam playfield, dan periksa apakah kita telah mencapai lokasi tujuan.
Jika sudah, tuliskan jalur terakhir, dan keluar.
Jika tidak, simpan koordinat ke tumpukan dengan 1spidol tipe untuk mundur kembali nanti.
Ini terputus dengan perhitungan angka acak yang akan segera kita butuhkan.
Dorong empat tujuan potensial yang dapat dicapai dari lokasi saat ini. Angka acak menentukan urutan mereka mendorong dan dengan demikian urutan mereka akan diikuti.
Bungkus kembali ke awal loop utama dan proseskan nilai selanjutnya pada stack.

QBasic, 259 byte

Saya yakin cinta GOTO.

RANDOMIZE TIMER
INPUT w,h
DO
CLS
x=1
y=1
REDIM a(w+3,h+3)
2a(x+1,y+1)=1
LOCATE y,x
?"#"
d=INT(RND*4)
m=1AND d
x=x+m*(d-2)
y=y-d*m+m+d-1
c=a(x,y+1)+a(x+2,y+1)+a(x+1,y)+a(x+1,y+2)=1
IF(x=w)*c*(y=h)GOTO 9
IF(x*y-1)*x*y*c*(x<=w)*(y<=h)GOTO 2
LOOP
9LOCATE y,x
?"#"

Strategi dasar: pada setiap langkah, cetak a #ke lokasi saat ini dan bergerak dalam arah acak. Array a0s dan 1s melacak dari mana kita berada. Jika langkah tersebut legal dan membawa kami ke titik akhir, GOTO 9untuk keluar dari loop dan mencetak final #. Lain, jika tindakan itu sah, ambil langkah lain. Lain, kosongkan layar dan mulai lagi (jauh lebih golf daripada coding algoritma backtracking!).

Diuji pada laptop saya di QB64, ini umumnya menghasilkan hasil 9, 9dalam lima detik atau kurang. Proses 10, 10telah berlangsung antara tiga dan 45 detik. Secara teoritis, semua jalur hukum memiliki probabilitas bukan nol, tetapi probabilitas jalur dengan kurva besar semakin kecil. Saya terkadang melihat jalur dengan satu atau dua kurva kecil, meskipun:

Versi yang tidak digabungkan dan / atau penjelasan mendalam tersedia berdasarkan permintaan.

R, 225 byte

function(x,y){library(igraph);a=matrix(rep(" ",x*y),c(y,x));g=make_lattice(c(y,x));w=runif(ecount(g));for (i in 1:2){v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];w[]=1;w[E(g)[v%--%v]]=0;};a[v]="#";cat(rbind(a,"\n"),sep="")}

Penjelasan:

Kami menghasilkan grafik tak beraturan (kisi) [x * y] reguler dengan bobot acak di tepian, lalu kami menemukan jalur terpendek dari awal hingga akhir. Namun di jalur yang dihasilkan mungkin ada sel yang memiliki lebih dari dua tetangga misalnya:

#
#
####
  ##
  #
  ###

Jadi kita harus menerapkan algoritma jalur terpendek dua kali. Di kedua kalinya kami mengatur semua bobot ke 1 kecuali yang ada di jalur ditemukan saat ini yang diatur ke 0;

hasil

#
#
### 
  # 
  #
  ###

Tidak Disatukan:

function(x,y){
    library(igraph);#igraph library should be installed
    a=matrix(rep(" ",x*y),c(y,x));#ASCII representation of the graph
    g=make_lattice(c(y,x));# regular graph
    w=runif(ecount(g));#weights
    for (i in 1:2){
        #find vertices that are in the path
        v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];
        #set all weights to 1 except those that are in the current found path that set to 0
        w[]=1;
        w[E(g)[v%--%v]]=0;
    }
    a[v]="#";
    cat(rbind(a,"\n"),sep="")
}

JavaScript (ES7), 333 331 330 329 324 318 312 byte

f=
(h,w,c=[...Array(h)].map(_=>Array(w).fill` `),g=a=>{for(z of b=[[[h-1,w-1]]])a.map(([x,y])=>b.every(([[i,j]])=>i-x|j-y)&(z[0][0]-x)**2+(z[0][1]-y)**2<2&&b.push([[x,y],...z]));return b.find(([[x,y]])=>!x&!y)||g([...a,[h,w].map(n=>Math.random()*n|0)])})=>g([]).map(([x,y])=>c[x][y]=`#`)&&c.map(a=>a.join``).join`
`

Height: <input type=number min=1 id=h>Width: <input type=number min=1 id=w><input type=button value="Generate!" onclick=o.textContent=f(+h.value,+w.value)><pre id=o>

Expanation: #s ditempatkan secara acak di dalam array sampai sebuah path ditemukan melalui field menggunakan pencarian pertama; yang pertama, dan karena itu terpendek, jalur tersebut kemudian keluaran; ini menjamin bahwa jalan tidak berpotongan dengan sendirinya. Perhatikan bahwa khususnya untuk bidang yang lebih besar dimungkinkan untuk melebihi tumpukan mesin JS sebelum jalur ditemukan. Tidak Terkumpul:

function r(n) {
    return Math.floor(Math.random() * n);
}
function f(h, w) {
    var a = []; // array of placed #s
    var b; // breadth-first search results
    var c;
    do {
        a.push([r(h), r(w)]); // place a # randomly
        b = [[[h - 1, w - 1]]]; // start from bottom right corner
        for (z of b) // breadth-first search
            for ([x, y] of a) // find possible next steps
                if (!b.some(([[i, j]]) => i == x && j == y))
                    if ((z[0][0] - x) ** 2 + (z[0][1] - y) ** 2 < 2)
                        if (x || y)
                            b.push([[x, y], ...z]); // add to search
                        else if (!c)
                            c = [[x, y], ...z]; // found path
    } while (!c);
    a = [...Array(h)].map(() => Array(w).fill(' '));
    for ([x, y] of c) // convert path to output
        a[x][y] = '#';
    return a.map(b => b.join('')).join('\n');
}