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.
23
questions
5
votes
5
answers
672
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 ...
- 1,493
6
votes
3
answers
477
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.
...
- 1,493
10
votes
2
answers
473
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)\$ (...
- 1,493
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 ...
- 5,271
9
votes
5
answers
325
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 ...
- 95.5k
17
votes
21
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-...
- 95.5k
4
votes
2
answers
665
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 ...
user106435
10
votes
4
answers
200
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 ...
- 73.1k
9
votes
5
answers
648
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 ...
user7467
5
votes
1
answer
292
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, ...
user9207
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 ...
user9207
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 ...
- 46.1k
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 ...
- 46.1k
12
votes
6
answers
589
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, ...
- 13.7k
45
votes
23
answers
4k
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 ...
- 12.2k
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 ...
- 49.9k
10
votes
6
answers
676
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 ...
- 1,377
22
votes
2
answers
997
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 ...
- 8,100
8
votes
9
answers
853
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 ...
- 71.4k
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 ...
- 71.4k
6
votes
6
answers
749
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 ...
user9206
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 ...
user9206
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 ...
- 7,712