9
\$\begingroup\$

The Levenshtein edit distance between two strings is the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. In this case, each insertion, deletion and substitution has a cost of 1.

For example, the distance between roll and rolling is 3, because deletions cost 1, and we need to delete 3 characters. The distance between toll and tall is 1, because substitutions cost 1.

Stolen from original Levenshtein question

Your task is to calculate the Levenshtein edit difference between an input string and your source. This is tagged , so cheating quines (for example, reading your source code) are not allowed.

Rules

  • The input will be non-empty and will be composed of ASCII, unless your source contains non-ASCII, in which case the input may include Unicode. Regardless, the Levenshtein distance will be measured in characters, not bytes.

  • The output is the minimum Levenshtein edit distance of the input and your source.

This is , so shortest answer, in bytes, wins.

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Stephen Aug 8 '17 at 16:45
  • 7
    \$\begingroup\$ I was going to suggest making the score the output of your program when run through itself, but then I realized... \$\endgroup\$ – ETHproductions Aug 8 '17 at 16:59
  • \$\begingroup\$ Closely related. \$\endgroup\$ – AdmBorkBork Aug 8 '17 at 17:29
  • \$\begingroup\$ @ETHproductions How did you even think of that? o_o \$\endgroup\$ – Erik the Outgolfer Aug 8 '17 at 17:31
  • \$\begingroup\$ Retina is so close to winning this with an empty program... \$\endgroup\$ – Leo Aug 8 '17 at 20:09
4
\$\begingroup\$

Python 2 + sequtils, 101 bytes

from sequtils import*;_='from sequtils import*;_=%r;print edit(_%%_,input())';print edit(_%_,input())
\$\endgroup\$
4
\$\begingroup\$

Python 2, 278 258 bytes

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))

Try it online!

This is just the usual quine in Python, mixed with the Levenshtein algorithm from this answer. Note that it gets quite extremely (thanks to Mr. Xcoder :P) slow.

\$\endgroup\$
  • \$\begingroup\$ Does this work for l(s%s,input()) (not sure)? \$\endgroup\$ – Don't be a x-triple dot Aug 8 '17 at 17:15
1
\$\begingroup\$

JavaScript, 113 bytes

This is a valid quine.

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'));

Idea stolen from other answer.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.