Explicação

A distância de edição entre duas cadeias é uma função do número mínimo possível de inserções, exclusões ou substituições para converter uma palavra em outra palavra.

Inserções e exclusões custam 1 e substituições custam 2.

Por exemplo, a distância entre ABe Aé 1, porque as exclusões custam 1 e a única edição necessária é a exclusão do Bcaractere.

A distância entre CARe FARé 2, porque as substituições custam 2. Outra maneira de ver isso é uma exclusão e uma inserção.

Regras

Dadas duas seqüências de entrada (fornecidas no entanto, é conveniente no seu idioma), seu programa deve encontrar a distância mínima de edição entre as duas seqüências.

Você pode assumir que as seqüências contêm apenas os caracteres A-Ze têm menos de 100 caracteres e mais de 0 caracteres.

Isso é código de golfe , então a solução mais curta vence.

Casos de teste de amostra

ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8

brainfuck, 2680

+>>>>>>>>>>>>>>>>>>>>>>++++++>,<[->-----<]>--[+++++++++++++++++++++
+++++++++++>>[->>+<<]>>+<<,--------------------------------]>>[-<<<
+>>>]<<<<[>[-<<+>>]<<<]>[-<<<<<+>>>>>]>[>>],----------[++++++++++>>
[->>+<<]>>+<<,----------]>>[-<<<+>>>]<<<<[>[-<<+>>]<<<]>[-<<+>>]<<[
-<+>>+<]<<<[->+<]>[-<+>>>>+<<<]>>>[-<+>]<[->+>+<<]<[-<+>]<[->+>+<<]
<[-<+>>+<]<[->+<]>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<[->>+
>+<<<]>>>[-<<<+>>>]<[->>+[->+>+<<]<<[->>+<<]>>]>>[-]<[<<]<<<+[->>>+
<<<]>>>[-<+<<+>>>]<<<<<[->>[->>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>>>]>>[->>>>+<<<<]>>>>[-<<<<+<<+>>>>>>]<<+[->>+<<]>>[-<<+<+>>>
]<<<<<<<<]>>[-]>>[-]>>[-]-[+<<-]+>>>>>>>>>>>>>>>>>[-<+>]<[->+<<<<+>
>>]<<<[->>>>>>[-<+>]<[->+<<<<+>>>]<<<<<<<[-]<<+>>>>>>[-<<<<+>>>>>>>
>>>[-<+>]<[->+>+<<]<<<<<<<<<[->+<]>[->>>>>>>>+<<<<<<<<<+>]<<<[->+<]
>[->>>>>>>>+<<<<<<<<<+>]>>>>>>>>>[-<<<<<+>>>>>]<<<<<[->>+>>>+<<<<<]
>>>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>>>]<<<<<<+>>-
[-<<[-<<<<+>>>>]<<<<[->>+>>+<<<<]>>[->>>>>>[->>+<<]<<[->>+<<]<<[->>
+<<]<<[->>+<<]>>]>>>>]>>[->>+<<]>>[-<<+>>>>+<<]->>-[-[->>+<<]>>]>[-
>+<]>[-<+>>>+<<]<<<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]>>[-<<+>>]<<<<<<+
]<<<<<<[->>>>>>+<<<<<<]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>>>+<<<<]
-<<[-]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<<<<[->>[->>+<<]<<[->>+<<]>>]>>-[
-[->>+<<]>>]<[->+<]>[-<+>>>+<<]+[->>[-<<+>>]<<<<+]>>[-<<+>>]<<<<<<<
<-[+>>[-<<+>>]>>[-<<+>>]>>[-<<+>>]<<<<<<<<-]+>>>[-]<[->+<]>>>[-]<[-
>+<]>>>[-]<[->+<]>>>[->+<]>[-<+>>>>>>>>>>>>>+<<<<<<<<<<<<]>>>>>>>>>
>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>>[-<+>]>
>>>>>>>>[->+<]>[-<+>>>>>>>>>>>+<<<<<<<<<<]>>>>>[->+<]>[-<+>>>>>+<<<
<]>>>>-[-[->>+<<]>>]>[->+<]>[-<+<+>>]<<<<-[+>>[-<<+>>]<<<<-]+>[->-<
]>[-<[-]+>]<[->>>+<<<]>>>[-<<+<+>>>]<<-[+>[->+<]<]<[->>+<-[[-]>[->+
<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>[-<+>>>+<<]+>>[-<<[-]>>]<[->+<]>
[-<+>>>+<<]+>>[-<<[-]>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<[-<<[-]+>>]<<<+
>->->>->>-<<<<<]<[->+<]]>[-<+>]>>[-<<<+>>>]<<<[->>>>>>>>>>>>>+<<<<<
<<<<<<<<]>>>>>>>>[->+<]>[-<+>>>>>>>>>+<<<<<<<<]>[->+<]>[-<+>>>>>>>>
>+<<<<<<<<]>>>>>>>>>[->>>+<<<]>>>[-<<+<+>>>]<<<<<[->>>>>+<<<<<]>>>>
>[-<<<<<+<<<+>>>>>>>>]<<<<<<<<+>>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]
<<[->>+<<]<<[->>+<<]>>>>>>>>>>]<<<<[-<<[-<<<<<<+>>>>>>]<<<<<<[->>+>
>>>+<<<<<<]>>[->>>>>>>>[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>+<<]<<[->>
+<<]>>]>>>>>>]<<[-]<<[->>>>+<<<<]>>>>>>[-[->>+<<]<<[->>+<<]>>>>]<<[
->>>>>+<<<<<]-[+<<-]+>>>>>>>>>>>>>>>]<<]>>>>>>>>[->+<]<<[->+<]<<[->
+<]>>>>>[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<[->>[->>>>+<<<<]>>
>>[-<<+<<+>>>>]<<+[-[->>+<<]<<[->>+<<]<<[->>+<<]>>>>>>]<<<<]>>[-[->
>+<<]>>]>>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>[->-[>+>>]>
[+[-<+>]>+>>]<<<<<]>[-]<++++++[->++++++++[->+>+<<<<+>>]<]>>>.<.<<<.

Usando programação dinâmica, é claro.

As seqüências de entrada devem ser separadas por um espaço e seguidas por uma nova linha. Por exemplo:

INTENTION EXECUTION
008

Python, 138 148 152 caracteres

Ok, eu conhecia o princípio, mas nunca havia implementado a distância de edição antes, então aqui vai:

x,y=raw_input().split()
d=range(99)
for a in x:
 c=d;d=[d[0]+1]
 for b,p,q in zip(y,c[1:],c):d+=[min(d[-1]+1,p+1,q+2*(a!=b))]
print d[-1]

PHP, 40

Segue as regras conforme indicado, mas não o espírito das regras:

<?=levenshtein($argv[1],$argv[2],1,2,1);

São dois parâmetros como argumentos. Exemplo chamando: php edit_dist.php word1 word2.
Normalmente levenshtein()considera uma substituição como uma operação, mas possui uma forma sobrecarregada na qual os pesos de inserção / sub / exclusão podem ser especificados. Nesse caso, é 1/2/1.

APL (90 caracteres)

⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞

Estou usando o Dyalog APL como meu intérprete, com ⎕IOdefinido como 1 e ⎕MLdefinido como 0. A função direta ( { ... }) calcula, dada uma linha como entrada, a próxima linha na matriz de distância. (É iniciado com a linha inicial:. 0,⍳x) O operador de energia ( ⍣) é usado para aninhar a função uma vez para cada caractere na segunda sequência ( ⊃⍴b). Depois de tudo isso, a linha final é invertida ( ⌽) e seu primeiro elemento é obtido ( ⊃).

Exemplo:

      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
LOCKSMITH
BLACKSMITH
3
      ⊃⌽({h←1+c←⊃⍵⋄d←h,1↓⍵⋄h,(⊂⍵){y←⍵+1⋄d[y]←⍺{h⌷b=⍵⌷a:⍵⌷⍺⋄1+d[⍵]⌊y⌷⍺}⍵}¨⍳x}⍣(⊃⍴b←,⍞))0,⍳x←⍴a←,⍞
GATTTGTGACGCACCCTCAGAACTGCAGTAATGGTCCAGCTGCTTCACAGGCAACTGGTAACCACCTCATTTGGGGATGTTTCTGCCTTGCTAGCAGTGCCAGAGAGAACTTCATCATTGTCACCTCATCAAAGACTACTTTTTCAGACATCTCCTGTAG
AAGTACTGAACTCCTAATATCACCAATTCTTCTAAGTTCCTGGACATTGATCCGGAGGAGGATTCGCAGTTCAACATCAAGGTAAGGAAGGATACAGCATTGTTATCGTTGTTGAGATATTAGTAAGAAATACGCCTTTCCCCATGTTGTAAACGGGCTA
118

R 51

Isso lê em duas linhas do usuário (que são a entrada) e, em seguida, apenas usa a adistfunção para calcular a distância. Como as substituições custam 2 para esse problema, precisamos adicionar um vetor nomeado para o parâmetro de custos para o adist. Como também há um parâmetro de contagem para o adist, só podemos reduzir os custos para cos, portanto ainda temos uma correspondência exclusiva para os nomes dos parâmetros.

x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))

Exemplo de uso

> x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))
MART
KARMA
     [,1]
[1,]    5

Rubi 1.9, 124

l=->a,b{a[0]?b[0]?[(a[0]==b[0]?-1:1)+l[a[1..-1],b[1..-1]],l[a[1..-1],b],l[a,b[1..-1]]].min+1: a.size: b.size}
puts l[*ARGV]

Versão em golfe do método Ruby lento e recursivo aqui , modificado para dobrar o peso de substituições. O fato de que são necessários 7 caracteres para remover o primeiro caractere de uma string realmente dói, e seria legal substituir (a[0]==b[0]?-1:1)por algo como, -1**a[0]<=>b[0]mas a ordem das operações não é minha amiga.

Smalltalk (Smalltalk / X), 34

Tenho sorte - a classe "String" padrão já contém levenshtein:

entrada a, b:

a levenshteinTo:b s:2 k:2 c:1 i:1 d:1

(os parâmetros adicionais permitem pesos diferentes na substituição, exclusão etc.)

Execução de teste:

#( 'ISLANDER'  'SLANDER' 
   'MART'      'KARMA'   
   'KITTEN'    'SITTING' 
   'INTENTION' 'EXECUTION'  
) pairWiseDo:[:a :b|
    a print. ' ' print. b print. ' ' print.
    (a levenshteinTo:b
            s:2 k:2 c:1 i:1 d:1) printCR.
].

->

ISLANDER SLANDER 1
MART KARMA 5
KITTEN SITTING 5
INTENTION EXECUTION 8