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
, M
dan , 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 ABCDEF
dan 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 RR
output 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 (yaitu123
, atauabc.
, 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 kode-golf , 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
Jawaban:
Haskell ,
192181174161158150147143158 1 byteCobalah 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:x
dari string pertama dan hitung secara modifikasi untuk mendapatkan dari"yz"
ke"yw"
. Ini menghasilkan tiga garis["yz","yw"," M"]
. Tambahkanx
ke yang pertama, spasi ke yang kedua danR
ke yang ketiga. Kita mendapatkany
dari string kedua dan hitung"xyz" & "w"
, yang mengembalikan hasilnya["xyz","w","MRR"]
. Kita perlu menambahkan spasi di baris pertama,y
ke baris kedua danA
ke baris ketiga:"yz" & "w"
. Untuk hasilnya["yz","w","MR"]
, kita tambahkanx
dia pertama dany
di 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 karenax \= y
)M
ditambahkan: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 manas
muncul sebagai komponen kedua dan komponen pertama adalah daftar dengan elemen sebanyak ada spasi di baris ketigas
(s!!2
karena pengindeksan 0). Karena elemen daftar1
digunakan, tetapi elemen yang sebenarnya tidak relevan selama itu sama untuk semua kandidat.Secara keseluruhan, ini menghasilkan daftar tupel
Build-inmaximum
memilih 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, dansnd
mengembalikan komponen kedua, yaitu daftar garis, tupel.1 +15 byte untuk memperbaiki bug di mana
A
-perubahan pada akhir string akan ditampilkan sebagaiR
-perubahansumber
JavaScript (ES6),
413...343342 byteDisimpan 5 byte dengan mengubah indeks loop, seperti yang disarankan oleh @KevinCruijssen
Mengambil input sebagai 2 string dalam sintaks currying. Mengembalikan array 3 string.
Uji kasus
Tampilkan cuplikan kode
Kurang golf
Contoh
Di bawah ini adalah matriks awal untuk b = "foo" dan a = "ok" :
dan di sini adalah matriks terakhir setelah semua iterasi:
String modifikasi terakhir bersama dengan jarak Levenshtein disimpan di sel kanan bawah.
sumber
j
danx
masih 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]]}
:)Python 2 ,
548536484500 1488447381 2373371357350 byteCobalah 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 Arnauld1: Lebih banyak byte, karena tidak berfungsi jika string pertama adalah satu karakter.
2: Beralih ke membangun kombinasi dalam matriks Levenshtein.
sumber
m+i+1
bisam-~i
.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
Python 2 , 310 byte
Cobalah online!
Menggunakan
difflib.SequenceMatcher
itu menghitung keselarasan antara dua stringsumber
"This_is_an_example_text","This_is_a_test_as_example"
Mathematica, 250
256259384byte~ 0,00035 detik untuk kasus kode java.
Pemakaian:
f["ABCDE", "ABCDF"]
Cobalah online!
Kode didasarkan pada fakta yang
SequenceAlignment
berfungsi secara default aktifYaitu, skor dihitung oleh
M
,A
danR
, karenanya.Contoh:
sumber
i="";o="";p="";
kei="";o=i;p=i;
untuk mengurangi 2 byte?i=o=p=""
?D ,
351345 byte-6 byte byte ke KevinCruijssen
Cobalah online!
sumber
break;
. 1 meskipun, pertama kali saya melihat bahasa pemrograman D.