Menemukan Poli Nemo!

11

Oh tidak! Nemo, ikan badut kecil kita hilang di samudera ASCII ini dan ayahnya Marlin berusaha menemukannya.

Tugas Anda adalah membawa Marlin ke Nemo dengan aman. Tapi berhati-hatilah, kita punya Bruce yang hiruk pikuk, jadi lebih baik hindari dia!

Detail

Anda diberi kotak laut ASCII persegi panjang yang hanya berisi huruf kecil a-z. Samudra ini akan memiliki nemo, marlindan brucedi dalamnya dalam bentuk polyomino terus menerus, selalu dimulai dari sel paling atas di kolom pertama polyomino. Jadi misalnya, dari semua tetromino yang mungkin, yang valid tercantum dalam cuplikan di bawah ini

Tampilkan cuplikan kode

Tetapi formulir seperti ini tidak valid dan tidak akan ada di input:

omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

Terakhir, tugas Anda adalah menemukan jalur dari marlinubin polyomino ke nemoubin polyomino memastikan bahwa setiap sel di jalur Anda tidak berdekatan dengan bruceubin polyomino. Output Anda harus mengganti semua huruf yang bukan bagian dari marlinubin, nemoubin dan jalur yang menghubungkan keduanya dengan karakter dari rentang ASCII yang dapat dicetak (termasuk spasi) selain huruf kecil a-z.

Contoh

Jika lautan input adalah sebagai berikut:

oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvtbsalyfrlyn
cicjrucejhiaeb
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

(dengan 3 polyominos adalah:

...n..........
.mli..........
.ar...........
..............
....b.........
....ruce......
..............
.....n........
.....emo......
..............
..............
..............

)

Maka solusi yang valid mungkin terlihat seperti:

...n..........
.mli..........
.ar...........
.u............
.n............
.i............
.z............
.wvjan........
.....emo......
..............
..............
..............

Cuplikan di bawah ini berisi beberapa contoh lagi:

Tampilkan cuplikan kode

Catatan

  • Kotak akan selalu menjadi kotak yang sempurna dan hanya akan berisi satu ubin polyomino nemo, marlindan bruce.
  • Jalur Anda tidak boleh melalui bruceatau salah satu dari 4 sel yang berdekatan (atas, bawah, kiri dan kanan) dari sel mana pun di bruceubin.
  • Selalu dijamin bahwa akan ada setidaknya satu jalur yang valid dari marlinke nemo.
  • Tidak ada persyaratan jalur terpendek di sini, jadi pergilah!
  • Meskipun Anda tidak harus menemukan jalur terpendek, setiap sel di jalur (jalur yang tidak termasuk marlin atau nemo) tidak dapat berdekatan dengan lebih dari dua sel lain di jalur.
  • Jalan itu tidak harus pergi melalui marlinatau nemoubin, karena kemudian akan membingungkan ikan kecil dalam memilih arah.
  • Seperti biasa, Anda dapat menulis program atau fungsi, mengambil input melalui STDIN (atau setara terdekat), argumen baris perintah atau parameter fungsi, dan menghasilkan output melalui STDOUT (atau setara terdekat), mengembalikan nilai atau parameter function (out).
  • Jika input multi-line tidak memungkinkan, maka Anda dapat mengasumsikan bahwa grid digabungkan dengan |karakter, bukan \n. Anda juga dapat mengambil input sebagai larik baris kisi.

Ini adalah kode golf sehingga entri terpendek dalam byte menang.

code-golf grid path-finding Pengoptimal
sumber
Bisakah jalan melewati marlin (atau nemo)? apakah solusi di atas masih berlaku jika di katas ldalam marlin terlihat? (membuat jalan dari n in marlin ke nemo)
KSab
@ Boleh saya katakan tidak karena akan membingungkan marlin :)
Pengoptimal

Jawaban:

4

Matlab 560

560 byte saat menghapus semua ruang yang tidak perlu, semua titik koma, dan semua komentar. Bisa bermain golf lebih banyak tetapi saya lelah sekarang (mungkin besok ...) Selamat malam semuanya.

PS: Saya berasumsi bahwa jalan harus memiliki keterhubungan 4 lingkungan ('+').

function c(A)
Z = [0,1,0;1,1,1;0,1,0];
Br = q('bruce');
Bn = conv2(Br,ones(3),'s')>0;
Ne = q('nemo');
Ma = q('marlin');
%construct path marlin to nemo
U=Ma>0;M=A*Inf;
M(U)=0;
for k=1:2*sum(size(A))%upper bound for path length
    %expand
    V=imdilate(U,Z);
    V(Bn)=0;
    M(V-U==1)=k;
    U=V;
    %disp(M)
end
%go back from nemo to marlin
Pr=reshape(1:numel(A),size(A));
[i,j]=find(Ne);
m=M(i(1),j(1));%value
P=A*0;%path image
P(i(1),j(1))=1;
for k=m:-1:1
    %find neighbour of (i(1),j(1)) with value m-1
    U=imdilate(P,Z);
    F = M==k;
    G = F&U;
    mask = Pr == min(Pr(F & U));
    P(mask)=1; 
end
A(~P & ~Ma & ~Ne)='.';
disp(A)



    function M = q(s)%find string in matrix, A ascii, M mask
        M = A*0;
        m=numel(s);
        N = M+1;%all neighbours
        for k=1:m;
            M(A==s(k) & N)=k;%only set the ones that were in the neighbourhood of last
            L=M==k;
            N=imdilate(L,Z);
        end
        for k=m:-1:2
            %set all that are not neighbour to next higher highest to zero
            L=M==k;
            N=imdilate(L,Z);
            M(M==k-1 & ~N)=0;
        end
    end


end

Fungsi panggilan: (baris baru tidak perlu)

c(['oxknvvolacycxg',
'xmliuzsxpdzkpw',
'warukpyhcldlgu',
'tucpzymenmoyhk',
'qnvtbsalyfrlyn',
'cicjrucejhiaeb',
'bzqfnfwqtrzqbp',
'ywvjanjdtzcoyh',
'xsjeyemojwtyhi',
'mcefvugvqabqtt',
'oihfadeihvzakk',
'pjuicqduvnwscv']);

Keluaran:

...n..........
.mli..........
.ar...........
..c...........
..v...........
..c...........
..q...........
..vjan........
.....emo......
..............
..............
..............

Bagaimana itu bekerja

Mengekstrak nama

Bagian pertama adalah mengekstraksi nama-nama misalnya nemo, yang dilakukan oleh fungsi q(). Fungsi pertama menandai segala sesuatu sebagai 0, kemudian kemunculan huruf pertama dari nama sebagai 1, kemudian huruf kedua seolah- 2olah ada 1di lingkungan, lalu yang ketiga dan seterusnya. Setelah itu seharusnya nemohanya ada satu 4. Dari sana kita mundur sampai kita menemukan 1lagi dan kemudian menghapus semua angka lain yang lebih besar itu, jadi kita mendapatkan kembali topeng yang bagus di mana huruf nemo- hurufnya ditutup. Kami melakukan ini untuk ketiga nama, dan kemudian dapat melanjutkan untuk menemukan jalan.

Menemukan jalan

Kami mulai dari posisi Marlins dan mengirimkan gelombang kejut ke lubang 'gambar' langkah demi langkah. Di setiap langkah kami menambah penghitung jarak dan menandai 'piksel' di bawah muka gelombang dengan jarak saat ini. (Seperti biasanya dilakukan dengan algoritma jalur terpendek.) Gelombang muka ini jelas akan diblokir oleh area Bruce, oleh karena itu akan mengalir di sekitarnya. Langkah ini diulang sampai batas atas tercapai. Batas atas (yang diakui sangat longgar) ini sekarang adalah keliling 'gambar' (jalur terpendek akan jauh lebih pendek dalam hal apa pun). Dalam test case terlihat seperti ini:

 2 1 1  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  1  2  3  4  5  6  7  8  9 10 11
 2 1 1  _  _  _  5  6  7  8  9 10 11 12
 3 2 2  _  _  _  _  _  _  9 10 11 12 13
 4 3 3  _  _  _  _  _  _ 10 11 12 13 14
 5 4 4  _  _  _  _  _  _ 11 12 13 14 15
 6 5 5  6  7  8  9 10 11 12 13 14 15 16
 7 6 6  7  8  9 10 11 12 13 14 15 16 17
 8 7 7  8  9 10 11 12 13 14 15 16 17 18
 9 8 8  9 10 11 12 13 14 15 16 17 18 19
10 9 9 10 11 12 13 14 15 16 17 18 19 20

Sekarang mulailah pada nemopiksel dan kurangi penghitung jarak di setiap langkah dan tambahkan tetangga dengan jarak lebih rendah berikutnya (sesuai dengan peta jarak yang kami hitung sebelumnya) ke jalur kami.

cacat
sumber
3

Python 2 - 658

Sangat sangat tidak efisien baik dalam waktu maupun memori. Fungsi untuk mengidentifikasi pola adalah fungsi rekursif S, dan fungsi untuk menemukan jalur adalah C, yang pada dasarnya merupakan implementasi A * yang sangat tidak efisien.

G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
print'\n'.join(''.join(G[y][x]if(x,y)in N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))else'.'for x in R(X))for y in R(Y))

Untuk pengujian gunakan ini (sangat sedikit) yang kurang golf (yang menghitung lintasan sekali sebagai gantinya untuk setiap ubin)

G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
s=N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))
print'\n'.join(''.join(G[y][x]if(x,y)in s else'.'for x in R(X))for y in R(Y))
KSab
sumber