Levenshtein Sumber Anda

11

Jarak edit Levenshtein antara dua string adalah jumlah penyisipan, penghapusan, atau penggantian minimum yang mungkin untuk mengubah satu kata menjadi kata lain. Dalam hal ini, setiap penyisipan, penghapusan dan penggantian memiliki biaya 1.

Misalnya, jarak antara rolldan rolling3, karena penghapusan berharga 1, dan kami harus menghapus 3 karakter. Jarak antara tolldan talladalah 1, karena biaya penggantian 1.

Dicuri dari pertanyaan Levenshtein asli

Tugas Anda adalah untuk menghitung perbedaan pengeditan Levenshtein antara string input dan sumber Anda. Ini diberi tag , jadi quine curang (misalnya, membaca kode sumber Anda) tidak diizinkan.

Aturan

  • Input tidak akan kosong dan akan terdiri dari ASCII, kecuali jika sumber Anda mengandung non-ASCII, dalam hal ini input mungkin termasuk Unicode. Apapun, jarak Levenshtein akan diukur dalam karakter, bukan byte.

  • Outputnya adalah jarak edit Levenshtein minimum dari input dan sumber Anda.

Ini adalah , jadi jawaban tersingkat, dalam byte, menang.

Stephen
sumber
Sandbox
Stephen
8
Saya akan menyarankan untuk membuat skor sebagai hasil dari program Anda ketika dijalankan dengan sendirinya, tetapi kemudian saya menyadari ...
ETHproduksi
Berhubungan erat .
AdmBorkBork
@ ETHproductions Bagaimana Anda bahkan memikirkan hal itu? o_o
Erik the Outgolfer
Retina sangat dekat dengan memenangkan ini dengan program kosong ...
Leo

Jawaban:

5

Python 2 + sequtils , 101 byte

from sequtils import*;_='from sequtils import*;_=%r;print edit(_%%_,input())';print edit(_%_,input())
Erik the Outgolfer
sumber
4

Python 2 , 278 258 byte

t=input();s,f='t=input();s,f=%r,lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-((s%%s)[m-1]==t[n-1]));print f(len(s%%s),len(t))',lambda m,n:m or n if m*n<1else-~min(f(m-1,n),f(m,n-1),f(m-1,n-1)-((s%s)[m-1]==t[n-1]));print f(len(s%s),len(t))

Cobalah online!

Ini hanya quine biasa dalam Python, dicampur dengan algoritma Levenshtein dari jawaban ini . Perhatikan bahwa itu menjadi sangat sangat (terima kasih kepada Tn. Xcoder: P) lambat.

benar-benar manusiawi
sumber
Apakah ini berfungsi untuk l(s%s,input())(tidak yakin)?
Tn. Xcoder
0

JavaScript, 113 byte

Ini adalah quine yang valid .

f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q

f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q

console.log(f('f=t=>[...t].map((v,j)=>x=x.map((w,k)=>q=k--?Math.min(q,w,x[k]-(v==u[k]))+1:j+1),x=[...[,...u=`f=${f}`].keys()])|q'));
console.log(f('%'));
console.log(f('12345'));

Ide dicuri dari jawaban lain.


sumber
"Ini quine yang valid" - sebenarnya, saya tidak yakin ada konsensus yang jelas dalam meta thread yang Anda tautkan. Dan pada kenyataannya, dengan beberapa suara, opsi "ini curang" sebenarnya menang.
FlipTack