12
\$\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\$
4
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – Stephen
    Aug 8, 2017 at 16:45
  • 9
    \$\begingroup\$ I was going to suggest making the score the output of your program when run through itself, but then I realized... \$\endgroup\$ Aug 8, 2017 at 16:59
  • \$\begingroup\$ Closely related. \$\endgroup\$ Aug 8, 2017 at 17:29
  • \$\begingroup\$ Retina is so close to winning this with an empty program... \$\endgroup\$
    – Leo
    Aug 8, 2017 at 20:09

6 Answers 6

6
\$\begingroup\$

Python 2 + sequtils, 101 bytes

from sequtils import*;_='from sequtils import*;_=%r;print edit(_%%_,input())';print edit(_%_,input())
\$\endgroup\$
0
5
\$\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\$
1
  • \$\begingroup\$ Does this work for l(s%s,input()) (not sure)? \$\endgroup\$
    – Mr. Xcoder
    Aug 8, 2017 at 17:15
2
\$\begingroup\$

Haskell, 210 bytes

main=interact$show.((x++show x)%);x@(a:c)%y@(b:d)|a==b=c%d|1>0=1+minimum[x%d,c%y,c%d];x%y=length$x++y;x="main=interact$show.((x++show x)%);x@(a:c)%y@(b:d)|a==b=c%d|1>0=1+minimum[x%d,c%y,c%d];x%y=length$x++y;x="

Try it online!

Computes the levenshtein distance modified from here. (I wrote the code there too) This is combined with a standard quine mechanism. Not much special here.

If you want to play around with it I suggest making edits towards the end of the string. The algorithm is more or less \$O(n+m^4)\$ where \$n\$ is the location of the difference between the input and the source, and \$m\$ is the length of the string after the first difference. So if you add a character to the front of this the compute time is exponential with the length of input and you won't see your result on tio.

\$\endgroup\$
2
\$\begingroup\$

Vyxal D, 10 bytes

`:qp꘍`:qp꘍

Try it Online!

Thanks to Aaron Miller for this one.

`:qp `:qp  # Standard quine
    ꘍    ꘍ # Levenshtein distance

Vyxal D, 13 bytes

`q\`:Ė\`+꘍`:Ė

Try it Online!

`q\`:Ė\`+ `:Ė # Standard eval quine (see https://codegolf.stackexchange.com/a/232956/100664)
         ꘍    # Leveshtein distance with input

10 bytes in Vyxal 2.6, whiich hasn't been released yet

\$\endgroup\$
1
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\$
1
  • \$\begingroup\$ "This is a valid quine" - actually, I'm not sure there's any clear consensus in that meta thread you linked. And in fact, by a few votes, the "this is cheating" option is actually winning. \$\endgroup\$
    – FlipTack
    Dec 29, 2019 at 22:27
1
\$\begingroup\$

Python 3.8 (pre-release), 135 bytes

exec(s:="l=lambda a,b:min(l(A:=a[1:],B:=b[1:])-(a[0]==b[0]),l(A,b),l(a,B))+1if b>''<a else len(a+b);print(l('exec(s:=%r)'%s,input()))")

Try it online!

took my solution of levenstein distance (https://codegolf.stackexchange.com/a/233868/103772) and adapted it to a quine. It is very (very) slow but it works

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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