Saya tidak suka perubahan!

19

Memasukkan:

Dua string tanpa baris baru atau spasi putih.

Keluaran:

Kedua string masukan pada baris terpisah, dengan ruang di mana diperlukan untuk salah satu dari dua string. Dan baris ketiga dengan karakter A, R, Mdan , yang mewakili menambahkan , dihapus , dimodifikasi , dan tidak berubah .

Kami menambahkan spasi ke string input atas atau bawah (jika perlu). Tujuan dari tantangan ini adalah untuk menghasilkan dengan jumlah perubahan paling sedikit ( ARM) yang mungkin, juga dikenal sebagai jarak Levenshtein .

Contoh:

Katakanlah string input adalah ABCDEFdan AFBECD, maka outputnya adalah ini:

A B CDEF
AFBECD  
 A A  RR

Berikut adalah beberapa kemungkinan keluaran yang tidak valid sebagai contoh (dan ada banyak lagi):

ABCDEF
AFBECD
 MMMMM

A BCDEF
AFBECD 
 A MMMR

AB CDEF
AFBECD 
 MAMMMR

ABC DEF
AFBECD 
 MMAMMR

ABC  DEF
AFBECD  
 MMAA RR

ABCDEF 
AFB ECD
 MMR MA

 AB CDEF   // This doesn't make much sense,
AFBECD     // but it's to show leading spaces are also allowed
AM A  RR

Namun tidak satupun dari ini hanya memiliki empat perubahan, jadi hanya A B CDEF\nAFBECD \n A A RRoutput yang valid untuk tantangan ini.

Aturan tantangan:

  • Anda dapat mengasumsikan string input tidak akan mengandung baris atau spasi baru.
  • Dua string input dapat memiliki panjang yang berbeda.
  • Salah satu dari dua string input harus tetap apa adanya, kecuali untuk spasi opsional awal / akhir.
  • Jika bahasa Anda tidak mendukung apa pun selain ASCII, Anda dapat menganggap bahwa input hanya akan berisi karakter ASCII yang dapat dicetak.
  • Format input dan output fleksibel. Anda dapat memiliki tiga Strings terpisah, satu array String, satu String dengan baris baru, array karakter 2D, dll.
  • Anda diizinkan menggunakan sesuatu yang lain sebagai ganti ARM, tetapi nyatakan apa yang telah Anda gunakan (yaitu 123, atau abc., dll.)
  • Jika lebih dari satu output yang valid dimungkinkan dengan jumlah perubahan yang sama ( ARM), Anda dapat memilih apakah akan menampilkan salah satu output yang mungkin atau semuanya.
  • Ruang depan dan belakang adalah opsional:

    A B CDEF
    AFBECD
     A A  RR
    

    atau

    "A B CDEF\nAFBECD\n A A  RR"
                     ^
                     Note there are no spaces here
    

Aturan umum:

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa saja'.
  • Aturan standar berlaku untuk jawaban Anda, jadi Anda diperbolehkan menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat, program lengkap. Panggilanmu.
  • Celah default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda.
  • Juga, silakan tambahkan penjelasan jika perlu.

Kasus uji:

In: "ABCDEF" & "AFBECD"

Output (4 changes):
A B CDEF
AFBECD  
 A A  RR                  

In: "This_is_an_example_text" & "This_is_a_test_as_example"

Possible output (13 changes):
This_is_an       _example_text
This_is_a_test_as_example     
         MAAAAAAA        RRRRR

In: "AaAaABBbBBcCcCc" & "abcABCabcABC"

Possible output (10 changes):
AaAaABBbBBcCcCc
 abcABCab cABC 
R MM  MMMR MM R

In: "intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}" & "intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}"

Possible output (60 changes):
intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}
intf(){i ntr=(      i    n      t)(M  ath.r   andom        ()*         10          );returnr>0?r%2:2;}
       MR M  MRRRRRR RRRR RRRRRR MMMRR MMMMRRR     RRRRRRRR  MRRRRRRRRR  RRRRRRRRRR 

In: "ABCDEF" & "XABCDF"

Output (2 changes):
 ABCDEF
XABCD F 
A    R 

In: "abC" & "ABC"

Output (2 changes):
abC
ABC
MM 
Kevin Cruijssen
sumber
Terkait
Kevin Cruijssen
Jika ada beberapa pengaturan yang jaraknya sama, apakah boleh untuk hanya menampilkan salah satunya?
AdmBorkBork
@ AdmBorkBork Ya, hanya satu dari kemungkinan keluaran yang memang keluaran yang dimaksudkan (meskipun keluaran semua opsi yang tersedia juga baik-baik saja). Saya akan mengklarifikasi hal ini dalam aturan tantangan.
Kevin Cruijssen
@Arnauld Saya telah menghapus aturan tentang memimpin spasi, jadi memimpin dan mengekor spasi adalah opsional dan valid pada baris yang tidak dimodifikasi. (Yang berarti test case terakhir dalam jawaban Anda benar-benar valid.)
Kevin Cruijssen
1
@Ferrybig Ah ok, terima kasih atas penjelasannya. Tetapi untuk tantangan ini, hanya mendukung ASCII yang dapat dicetak sebenarnya sudah cukup. Jika Anda ingin mendukung lebih banyak, jadilah tamu saya. Tapi selama itu berfungsi untuk test case yang diberikan saya ok dengan perilaku yang tidak terdefinisi untuk cluster graphene yang terdiri dari lebih dari 1 karakter seperti itu. :)
Kevin Cruijssen

Jawaban:

5

Haskell , 192 181 174 161 158 150 147 143 158 1 byte

e@(a:r)&f@(b:s)=snd$maximum[([1|' '<-s!!2],s)|s<-z(z(:))[a:" R",' ':b:"A",a:b:last("M":[" "|a==b])][r&f,e&s,r&s]]
x&y=[x,y,"RA"!!(0^length x)<$x++y]
z=zipWith

Cobalah online! Contoh penggunaan: "ABCDEF" & "AFBECD". Mengembalikan daftar tiga string. Ini adalah perpanjangan dari solusi rekursif saya untuk pertanyaan jarak Levenshtein biasa .

Penjelasan:

Untuk menghitung modifikasi minimal untuk mendapatkan dari "xyz"ke "yw", kita fokus pada karakter pertama dari kedua string. Ada tiga kemungkinan:

  • Hapus: Lepaskan xdari string pertama dan hitung secara modifikasi untuk mendapatkan dari "yz"ke "yw". Ini menghasilkan tiga garis ["yz","yw"," M"]. Tambahkan xke yang pertama, spasi ke yang kedua dan Rke yang ketiga. Kita mendapatkan
    xyz
    yw
    RM
  • Tambahkan: Jatuhkan ydari string kedua dan hitung "xyz" & "w", yang mengembalikan hasilnya ["xyz","w","MRR"]. Kita perlu menambahkan spasi di baris pertama, yke baris kedua dan Ake baris ketiga:
     xyz
    yw
    AMRR
  • Diubah / tidak berubah: Kami dapat menggabungkan dua kasus karena keduanya membutuhkan untuk menjatuhkan karakter pertama dari kedua string dan menghitung modifikasi minimal antara string yang tersisa: "yz" & "w". Untuk hasilnya ["yz","w","MR"], kita tambahkan xdia pertama dan ydi baris kedua. Hanya untuk baris terakhir kita perlu membedakan apakah karakter awal sama. Jika mereka sama, spasi ditambahkan ke baris ketiga, jika tidak (seperti dalam kasus ini karena x \= y) Mditambahkan:
    xyz
    yw
    MMR

Dari ketiga kandidat itu, kita perlu menemukan satu dengan modifikasi paling sedikit. Ini setara dengan memiliki ruang terbanyak di baris ketiga. Oleh karena itu kami mengkonversi setiap kandidat s(daftar tiga string) menjadi tuple ([1|' '<-s!!2],s), di mana smuncul sebagai komponen kedua dan komponen pertama adalah daftar dengan elemen sebanyak ada spasi di baris ketiga s( s!!2karena pengindeksan 0). Karena elemen daftar 1digunakan, tetapi elemen yang sebenarnya tidak relevan selama itu sama untuk semua kandidat.

Secara keseluruhan, ini menghasilkan daftar tupel

[([1], ["xyz", "yw", "RM"]), ([], ["xyz", "yw", "AMRR"]), ([], ["xyz", " yw "," MMR "])]
Build-in maximummemilih elemen terbesar dari daftar ini, di mana tuple dibandingkan secara leksikografis, yaitu komponen-bijaksana dari kiri ke kanan. Karena [1]lebih besar dari [], tupel pertama dipilih, dan sndmengembalikan komponen kedua, yaitu daftar garis, tupel.


1 +15 byte untuk memperbaiki bug di mana A-perubahan pada akhir string akan ditampilkan sebagai R-perubahan

Laikoni
sumber
lol ini membuat skrip pengguna berpikir bahwa ini adalah 1 byte
HyperNeutrino
8

JavaScript (ES6), 413 ... 343 342 byte

Disimpan 5 byte dengan mengubah indeks loop, seperti yang disarankan oleh @KevinCruijssen

Mengambil input sebagai 2 string dalam sintaks currying. Mengembalikan array 3 string.

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

Uji kasus

Kurang golf

b => a => {
  m = []; x = a.length; y = b.length;

  // initialize the leftmost column and the topmost row
  for(i = j = 0, c = d = ''; i <= y; c += R = 'R')
    m[i] = [[c, i++]];
  for(; j++ < x;)
    m[i = 0][j] = [d += A = 'A', j];

  // walk through the Levenshtein matrix
  for(; i < y; i++)
    for(j = 0; j < x;)
      [C] = m[                                // C = current string, once updated
        [X, S] = m[i][j],                     // substitution
        [Y, I] = m[i + 1][j],                 // insertion
        [Z, D] = m[i][++j],                   // deletion
        Q = [Z + R, D + 1],                   // precomputed update for deletion
        i + 1
      ][j] =
        b[i] == a[j - 1] ?
          [X + ' ', S]                        // unchanged character
        :
          S < I ?
            D < S ? Q : [X + 'M', S + 1]      // deletion or substitution
          :
            D < I ? Q : [Y + A, I + 1];       // deletion or insertion

  return [
    // g = helper function to format the output strings by inserting spaces
    (g = s => C.replace(/./g, c => c == s ? ' ' : b[i++], i = 0))(A),
    g(R, b = a),

    // final modification string, picked from the last visited cell
    C
  ]
}

Contoh

Di bawah ini adalah matriks awal untuk b = "foo" dan a = "ok" :

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ],  (undefined),  (undefined) ],  // 'f'
  [ [ 'RR',  2 ],  (undefined),  (undefined) ],  // 'o'
  [ [ 'RRR', 3 ],  (undefined),  (undefined) ] ] // 'o'

dan di sini adalah matriks terakhir setelah semua iterasi:

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ], [ 'M',   1 ], [ 'MA',  2 ] ],  // 'f'
  [ [ 'RR',  2 ], [ 'R ',  1 ], [ 'R A', 2 ] ],  // 'o'
  [ [ 'RRR', 3 ], [ 'RR ', 2 ], [ 'R M', 2 ] ] ] // 'o'

String modifikasi terakhir bersama dengan jarak Levenshtein disimpan di sel kanan bawah.

Arnauld
sumber
Perubahan yang sama saya sarankan untuk menyimpan 1 byte tentang -1 / + 1 jdan xmasih berlaku untuk hasil edit terakhir Anda: b=>a=>{m=[];x=a.length;y=b.length+1;for(i=y;i--;)m[i]=[[i,'R'.repeat(i)]];for(j=x+1;j--;)m[i=0][j]=[j,'A'.repeat(j)];for(;++i<y;)for(j=-1;++j<x;)R=m[S=(X=m[i-1][j])[0],I=(Y=m[i][j])[0],D=(Z=m[i-1][j+1])[0],Q=[D+1,Z[1]+'R'],i][j+1]=b[i-1]==a[j]?[S,X[1]+' ']:S<I?D<S?Q:[S+1,X[1]+'M']:D<I?Q:[I+1,Y[1]+'A'];return[(g=s=>R[1].replace(/./g,c=>c==s?' ':b[i++],i=0))('A'),g('R',b=a),R[1]]}:)
Kevin Cruijssen
1
@KevinCruijssen Saya menyimpan 5 byte dengan mengambil ide Anda selangkah lebih maju. Terima kasih!
Arnauld
4

Python 2 , 548 536 484 500 1 488 447 381 2 373 371 357 350 byte

s,t=input()
n,m=len(s),len(t)
r=range
L=[[(j,'RA'[i<1]*j)for j in r(i,m-~i)]for i in r(n+1)]
for i in r(n):
 for j in r(m):M,R=L[i][j:j+2];A=L[i+1][j];v,V=min(A,R,M);x=('AR'[v in R],'M_'[s[i]==t[j]])[v in M];_=M;X=eval(x)[1]+x;L[i+1][j+1]=v+(x<'_'),X
for i in r(len(X)):s=s[:i]+' '*('B'>X[i])+s[i:];t=t[:i]+' '*('R'==X[i])+t[i:]
print s+'\n'+t+'\n'+X

Cobalah online!

Gunakan 'ARM_'bukan'ARM '

Bekerja dengan membangun matriks Levenshtein, dan kemudian menelusuri mundur untuk menemukan operasi . Sekarang membangun string operasi pada saat yang sama dengan matriks Levenshtein, seperti dalam jawaban JS Arnauld

1: Lebih banyak byte, karena tidak berfungsi jika string pertama adalah satu karakter.

2: Beralih ke membangun kombinasi dalam matriks Levenshtein.

TFeld
sumber
+1 untuk mengambil kurang dari 60 detik untuk 6 kata karakter seperti usaha awal saya (gagal) lol
HyperNeutrino
Jawaban bagus! +1 dari saya. Karena saya tidak pernah memprogram dengan Python, saya tidak bisa membantu Anda bermain golf, kecuali satu hal: m+i+1bisa m-~i.
Kevin Cruijssen
Anda dapat menggunakan tab alih-alih spasi ganda pada baris 7.
Stephen
Anda bisa mendapatkan 463 byte dengan mengurangi loop wile ke satu baris:while i+j<n+m:v,A=(L[i]+[m,m])[j:j+2];R,M=(L[i+1]+[m,m])[j:j+2];d=min(A,R,M);q=M==d or(R==d)*2;r+=' '*(d==v==M)or'AMR'[q];i+=q>0;j+=q<2
Ov
1

Python 2 , 310 byte

from difflib import*
a,b=input()
U,j=[],' '
for g,s,t,x,y in SequenceMatcher(0,a,b).get_opcodes():
	g,Y,T=g[0],y-x,t-s
	z,A,B=Y-T,a[s:t],b[x:y]
	if'q'<g:U+=[A+z*j,B+j*-z,'M'*min(T,Y)+'A'*z+'R'*-z]
	if'e'==g:U+=[A,B,j*Y]
	if'i'==g:U+=[j*Y,B,'A'*Y]
	if'e'>g:U+=[A,j*T,'R'*T]
for e in[0,1,2]:print''.join(U[e::3])

Cobalah online!

Menggunakan difflib.SequenceMatcheritu menghitung keselarasan antara dua string

mdahmoune
sumber
Ini tampaknya memberikan beberapa hasil yang salah untuk beberapa kasus uji lainnya. Lebih khusus:"This_is_an_example_text","This_is_a_test_as_example"
Kevin Cruijssen
@KevinCruijssen thanx, saya baru saja memperbaikinya ^ _ ^
mdahmoune
Bagus, gj! Tapi umm .. test case ketiga (dan juga keempat) juga sayangnya tidak benar. Salah satu dari dua baris harus tidak dimodifikasi (kecuali untuk spasi awal / akhir). Kedua garis saat ini mengandung spasi di tengah.
Kevin Cruijssen
@KevinCruijssen thanx lagi, saya memperbaikinya
mdahmoune
1

Mathematica, 250 256 259 384 byte

~ 0,00035 detik untuk kasus kode java.

(i=o=p="";a=Array;r=StringLength;If[Length@#>0,g=#&@@#;h=#[[2]];u=r@g;v=r@h;i=i<>g;o=o<>h;w=Abs[v-u];k=a[" "&,w];If[u<v,i=i<>k,o=o<>k];p=p<>a["M"&,u~Min~v];p=p<>a[If[u>v,"R","A"]&,w],i=i<>#;o=o<>#;p=p<>a[" "&,r@#]]&/@SequenceAlignment[#,#2];{i,o,p})&

Pemakaian: f["ABCDE", "ABCDF"]

Cobalah online!

Kode didasarkan pada fakta yang SequenceAlignmentberfungsi secara default aktif

Dengan pengaturan default SimilarityRules-> Otomatis, setiap kecocokan antara dua elemen berkontribusi 1 untuk total skor kesamaan, sedangkan setiap ketidakcocokan, penyisipan, atau penghapusan berkontribusi -1.

Yaitu, skor dihitung oleh M, Adan R, karenanya.

Contoh:

contoh

Keyu Gan
sumber
2
Hmm, saya tidak pernah diprogram dalam Mathemetica, tetapi tidak mungkin untuk mengubah i="";o="";p="";ke i="";o=i;p=i;untuk mengurangi 2 byte?
Kevin Cruijssen
2
Bagaimana dengan i=o=p=""?
DavidC
@ DavidC Ya, saya sudah menyadarinya dan sudah mengubahnya. terima kasih
Keyu Gan
1

D , 351 345 byte

-6 byte byte ke KevinCruijssen

string f(string a,string b){import std.algorithm;string x,y,z;size_t i,j,k;foreach(c;levenshteinDistanceAndPath(a,b)[1]){final switch(c)with(EditOp){case none:x~=a[i++];y~=b[j++];z~=" ";break;case substitute:x~=a[i++];y~=b[j++];z~="M";break;case insert:x~=" ";y~=b[j++];z~="A";break;case remove:x~=a[i++];y~=" ";z~="R";}}return x~"\n"~y~"\n"~z;}

Cobalah online!

mdahmoune
sumber
Anda dapat golf enam byte dengan menghapus yang terakhir break;. 1 meskipun, pertama kali saya melihat bahasa pemrograman D.
Kevin Cruijssen