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
15 votes
5 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 ...
user avatar
  • 3,337
9 votes
5 answers
309 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 ...
user avatar
  • 89.4k
16 votes
16 answers
1k 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-...
user avatar
  • 89.4k
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 ...
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 ...
user avatar
44 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 ...
user avatar
  • 12.1k
10 votes
6 answers
651 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 ...
user avatar
  • 1,317
22 votes
2 answers
948 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 ...
user avatar
  • 8,040