Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [edit-distance]

Challenges which relate to calculating some type of edit distance (such as Levenshtein distance), or where answers are expected to satisfy some property related to edit distance.

Filter by
Sorted by
Tagged with
45 votes
23 answers
5k views

Levenshtein Distance

While there are many edit distance questions, such as this one, there isn't a simple question to write a program that calculates the Levenshtein distance. Some Exposition The Levenshtein edit ...
Sherlock9's user avatar
  • 12.3k
27 votes
13 answers
3k views

Recover the mutated source code

In a very unusual accident involving a small sample of radium, an electrocuted whale, and three gummy bears, some of The Management™'s source code has been mutated. Little does The Management™'s boss ...
Doorknob's user avatar
  • 71.5k
23 votes
16 answers
2k views

Monday Mini-Golf #3: Anagram distance

Monday Mini-Golf: A series of short code-golf challenges, posted (hopefully!) every Monday. (Sorry this one's a little late.) I'm sure most of you folks have heard of Levenshtein distance, an ...
ETHproductions's user avatar
22 votes
2 answers
1k views

Each step of the Levenshtein distance

In this challenge you will write a program that takes two newline-separated strings, s1 (the first line) and s2 (the second line), as input (STDIN or closest). You can assume that the length of s1 ...
xenia's user avatar
  • 8,142
18 votes
7 answers
1k views

Find The Average String Between Two Strings

Inspired by this Your task today: given two strings, find the string with the lowest maximum Levenshtein distance to the input strings. For example, using Steffan ...
Seggan's user avatar
  • 5,347
17 votes
23 answers
2k views

Damerau-Damerau distance

Given a list of the integers from \$1\$ to some \$n\$, give the minimum number of adjacent swaps required to put the list in ascending order. You will receive a list as input and should output a non-...
Wheat Wizard's user avatar
  • 98.8k
17 votes
11 answers
8k views

Find the minimum edit distance between two strings

Explanation The edit distance between two strings is a function of the minimum possible number of insertions, deletions, or substitutions to convert one word into another word. Insertions and ...
Peter Olson's user avatar
  • 7,732
16 votes
4 answers
1k views

Code golf edit distance 2

The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other. This task is simply to write ...
user avatar
15 votes
15 answers
2k views

Levenshtein distance & OEIS (Cops)

This is the Cop post. The Robber post is here. Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942. The sequence consists of the square numbers written ...
Stewie Griffin's user avatar
12 votes
6 answers
601 views

Levenshtein Your Source

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, ...
Stephen's user avatar
  • 13.9k
10 votes
6 answers
691 views

Levenshtein distance bias

Write a program in a language with name A that, given a string S, outputs the name of a different programming language ...
Seadrus's user avatar
  • 1,395
10 votes
13 answers
1k views

Levenshtein distance & OEIS (Robbers)

This is the Robber post. The Cop post is here. Your task is to take an integer input N and output the Nth digit in the sequence OEIS A002942. The sequence consists of the square numbers written ...
Stewie Griffin's user avatar
10 votes
4 answers
201 views

Hamiltonian levencycle of 1-dup permutations

The word "levencycle" is inspired by cyclic levenquine challenge. Definitions A 1-dup permutation of order \$n\$ is some permutation of \$1, \cdots, n\$ plus one duplicate number in the ...
Bubbler's user avatar
  • 76.8k
10 votes
2 answers
482 views

Find a string in the middle

Given two strings \$A\$ and \$B\$ with edit (Levenshtein) distance \$x\$, find a third string with edit distance \$a\$ to \$A\$ and edit distance \$b\$ to \$B\$ so that \$a+b=x\$ and \$a=int(x/2)\$ (...
Simd's user avatar
  • 2,926
9 votes
3 answers
1k views

Restricted memory optimization

The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. If the two ...
user avatar
9 votes
5 answers
330 views

Find the closest swap

Take as input two strings \$A\$ and \$B\$. Output a string \$C\$ that is \$A\$ but with two characters swapped such that the Levenshtein distance \$d(C,B)\$ is as small as possible. You must swap ...
Wheat Wizard's user avatar
  • 98.8k
9 votes
5 answers
663 views

Edit distance where a substitution only costs the first time

This challenge is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...
user avatar
8 votes
9 answers
857 views

Recover the mutated source code (for robbers)

This is the companion thread to the main Recover the mutated source code (link) challenge. If you have successfully cracked a cop's answer, post your solution as an answer to this question. As a ...
Doorknob's user avatar
  • 71.5k
6 votes
5 answers
754 views

Count the size of the Levenshtein neighborhood

Input A binary string \$s\$ of length \$n\$ and a positive integer \$k \leq n\$. Output The number of binary strings with Levenshtein distance exactly \$k\$ from the string \$s\$. Example outputs Each ...
Simd's user avatar
  • 2,926
6 votes
3 answers
519 views

Pick a random string at a fixed edit distance

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly. ...
Simd's user avatar
  • 2,926
6 votes
6 answers
768 views

Find all strings at distance k

The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other. The challenge ...
user avatar
5 votes
1 answer
319 views

Find the min and max number of substitutions

The Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other. Let us call insertions, ...
user avatar
4 votes
2 answers
740 views

Give the minimum Levenshtein distance to a string that matches the regex

Your task, at the moment that you choose to accept it, is to write a program that, when given a string and a PCRE-regex, calculates the minimum Levenshtein distance to another string that matches the ...
user avatar