Skip to main content
12 votes

Damerau-Damerau distance

MATL, 5 4 bytes -20% thanks to Luis Mendo! &<Rz Try it online! or Verify all cases! As long as the list is not sorted, there is always an adjacent pair that ...
ovs's user avatar
  • 59.5k
9 votes

Levenshtein Distance

APL (Dyalog Classic), 34 bytes {0∊≢¨⍵:≢∊⍵⋄⌊/(≢.↑+∘∇↓¨)∘⍵¨1↓,⍳2 2} Try it online!
ngn's user avatar
  • 15.3k
8 votes

Damerau-Damerau distance

Factor + koszul, 10 bytes inversions Try it online!
chunes's user avatar
  • 24.6k
8 votes

Count the size of the Levenshtein neighborhood

Rust, score ≈ (28, 23) The number of strings at distance \$k\$ from \$s\$ with some given prefix \$p\$ is a function of \$s\$, \$k\$, and the last column of the Wagner–Fischer table of \$s\$ and \$p\$....
Anders Kaseorg's user avatar
7 votes

Find the minimum edit distance between two strings

Brachylog (v2), 14 bytes ⟨⊇⊆⟩jg;?clᵐ-ˡṅ Try it online! This question has a surprising lack of golfing language solutions (there's an APL solution, which is a quasi-...
7 votes

Code golf edit distance 2

Retina 0.8.2, 76 58 bytes ^(.*)(.*¶)\1 $2 (.*)(¶.*)\1$ $2 ^.?¶.?$ ^.?(.*).?¶.?\1.?$ Try it online! Takes the two strings on separate lines, but link includes ...
Neil's user avatar
  • 172k
7 votes

Code golf edit distance 2

Haskell, 124 121 99 88 bytes 3 bytes saved by Bubbler x%y=[0,0]==x#y u@(a:b)#v@(c:d)|a==c=b#d|k<-zipWith(+)=0:k(d#u)(k(b#v)$b#d) a#b=a++b>>[0] Try it ...
Wheat Wizard's user avatar
  • 98.8k
7 votes

Damerau-Damerau distance

R, 38 bytes function(x)sum(combn(c(0,x),2,diff)<0) Try it online! Adaptation of ovs's answer. Test harness taken from Dominic van Essen's answer. ...
Giuseppe's user avatar
  • 28.6k
7 votes

Find The Average String Between Two Strings

Vyxal, 14 bytes Þ∪Þx:ƛ□꘍GN;ÞMİ Try it Online! I think Þ∪ can be J, but that makes it so ...
naffetS's user avatar
  • 12.5k
7 votes

Pick a random string at a fixed edit distance

Python, 3453 bytes ...
gsitcia's user avatar
  • 3,301
6 votes

Levenshtein distance & OEIS (Cops)

Haskell, LD = 13, cracked ((snd.span(<'1').reverse.show.(^2)=<<[1..])!!) Try it online! I double-checked that leading zeros are trimmed ;) ...
Laikoni's user avatar
  • 26.2k
6 votes

Levenshtein Distance

Haskell, 67 bytes e@(a:r)#f@(b:s)|a==b=r#s|1<3=1+minimum[r#f,e#s,r#s] x#y=length$x++y Try it online! Example usage: ...
Laikoni's user avatar
  • 26.2k
6 votes

Levenshtein Distance

Python 2, 118 bytes A golf of this solution, but it doesn't look like Willem's been on for a year, so I'll have to post it myself: ...
FlipTack's user avatar
  • 14.7k
6 votes

Levenshtein Your Source

Python 2 + sequtils, 101 bytes from sequtils import*;_='from sequtils import*;_=%r;print edit(_%%_,input())';print edit(_%_,input())
Erik the Outgolfer's user avatar
6 votes

Damerau-Damerau distance

Curry (PAKCS), 35 bytes f(h:t)=length[1|c<-t,c<h]+f t f[]=0 Try it online! A port of ovs' MATL answer.
alephalpha's user avatar
  • 48.5k
6 votes

Find The Average String Between Two Strings

05AB1E, 9 bytes JæΣ.L{R}н Outputs one possible result. Try it online or verify all test cases. Explanation: ...
Kevin Cruijssen's user avatar
6 votes

Find a string in the middle

Python, 459 514 502 bytes +60 bytes, use correct initial condition -11 bytes, thanks to ValueInk -1 byte, thanks to c-- ...
bsoelch's user avatar
  • 6,015
6 votes

Pick a random string at a fixed edit distance

Python, 932 bytes, \$O(4^k\cdot n^{2k+2})\$ ...
bsoelch's user avatar
  • 6,015
5 votes

Levenshtein Your Source

Python 2, 278 258 bytes ...
totallyhuman's user avatar
  • 17.2k
5 votes

Find the min and max number of substitutions

JavaScript (ES10),  169 168  161 bytes Saved 7 bytes thanks to @KevinCruijssen Takes the strings as (s)(t). Returns ...
Arnauld's user avatar
  • 193k
5 votes

Hamiltonian levencycle of 1-dup permutations

Jelly, 110 bytes ñ-ị$X⁸ṣU2¦jɗ 0ịị®ḟ Œ!⁸œṖþẎṣ€Ẏ¥þ⁸Q€;@"Ẏ¥þ@";þ`ạ/Þ€;"Q¥U$ƊẎḅQ¥€⁸ṢFỤ’:‘sʋ1ịLƊƲ©ṛ1ç`X;@ṛÑ¥¹?Ɗ,®Ẉ⁻/Ɗ¿Ñç0ċ1¬Ɗ¿ƲịḢ€Ɗḃ Try it online! A ...
Nick Kennedy's user avatar
  • 21.1k
5 votes

Hamiltonian levencycle of 1-dup permutations

Wolfram Language (Mathematica), 172 bytes ...
Jonah's user avatar
  • 33.6k
5 votes

Find The Average String Between Two Strings

Factor + lcs math.combinatorics, 123 120 78 bytes [ 2dup append all-subsets [ tuck [ levenshtein ] 2bi@ max ] 2with infimum-by ] ...
chunes's user avatar
  • 24.6k
4 votes

Levenshtein distance & OEIS (Robbers)

Haskell, Laikoni ((show.(*1).read.reverse.show.(^2)=<<[1..])!!) Try it online! The (*1) was necessary for type ...
H.PWiz's user avatar
  • 11.6k
4 votes

Find The Average String Between Two Strings

Vyxal, 9 bytes ∑ṗµ?꘍sṘ;h Try it Online! Port of Kevin Cruijssen's answer, go upvote that!
emanresu A's user avatar
  • 38.8k
4 votes

Pick a random string at a fixed edit distance

Python, \$\mathcal{O}((n+k)^{2k})\leq\mathcal{O}(4^k n^{2k})\$ ...
Value Ink's user avatar
  • 12.6k
4 votes

Count the size of the Levenshtein neighborhood

Python, (11, 8); with Python PyPy (12, 10) New version of Value Ink's answer using bit twiddling in place of string manipulation. ...
Jonathan Allan's user avatar
3 votes

Levenshtein distance & OEIS (Cops)

Python 2, 104 bytes, LD=21 Invalid AND Cracked d=lambda y:y if'0'!=str(y)[-1]else d(y/10) lambda n:''.join([str(d(x*x))[::-1]for x in range(1,n)])[n-1] P.S. Is ...
dylnan's user avatar
  • 5,364
3 votes

Levenshtein distance & OEIS (Cops)

cQuents 0, LD = 1, Cracked ":\r$*$ Try it online! I thought this didn't work for leading zeroes, but it actually does - the reverse function in cQuents is ...
Stephen's user avatar
  • 14k
3 votes

Levenshtein distance & OEIS (Cops)

JavaScript (ES6), LD = 103 (cracked) Using such a high Levenshtein distance is probably not the best strategy, but let's try it anyway. ...
Arnauld's user avatar
  • 193k

Only top scored, non community-wiki answers of a minimum length are eligible