Esta é uma sequência deste desafio: Código próximo ao desafio: Soma de números inteiros

O desafio deste é um pouco mais difícil e também cria um título interessante (e foi por isso que o escolhi):

Calcular a distância de Levenshtein entre duas cordas

Assim como no último desafio, sua pontuação nesse desafio é a distância de Levenshtein entre seu código e a citação acima.

Então agora para os detalhes!

Seu programa terá 2 entradas, ambas as strings sem espaços à direita ou novas linhas, e produzirá a distância de Levenshtein entre elas. A distância de Levenshtien é definida como o número de adições, exclusões e substituições necessárias para transformar uma string em outra. Para mais informações sobre como calculá-lo, consulte a página da Wikipedia vinculada acima. Para testar se o seu programa funciona, use esta calculadora . Seu programa não deve produzir nada além da distância de Levenshtein entre as duas cadeias. Será desqualificado se algo mais for produzido. Exemplo de E / S:

Inputs:
test
test2
Output:
1

Inputs:
222
515
Output:
3

Inputs:
Test
test
Output:
1

Seu código pode não ter no-ops ou comentários.

Frink , distância 24

Calculate[the,Levenshtein]:=editDistance[the,Levenshtein]

Para usar isso, você chamaria Calcular com as duas cadeias e, como isso está retornando, você também precisará cercar a chamada print[]. Se isso não for permitido, minha pontuação é 30.

Exemplo:

Calculate["kitten","spork"]        -> returns 6
print[Calculate["kitten","spork"]] -> prints 6.

Você precisa fazer o download do Frink, pois o intérprete da web não permite definir funções. Ele deve ser executado em todos os sistemas, considerando que é um applet Java. Faça o download das instruções aqui. .

^{Psst. Ei! Aqui está uma implementação Levenshtein em simbólica, algo que eu estou trabalhando em: k=λ:Δ(ί,ί).}

R, distância 35

Calculate=function(the,Levenshtein)adist(between<-the,two<-Levenshtein)

Isso cria uma função Calculatecom parâmetros thee Levenshtein. Ele usa a função adistinterna R para calcular a distância. Os parâmetros de cadeia em adistsão essencialmente thee Levenshteinrenomeado para betweene two.

PHP4.1, distância 32. 22 15 14

Muito básico, nada emocionante.

<?=$Calculate_the=Levenshtein($distance,$between_two_strings);

Ou uma versão mais curta:

<?=$ulatethe=Levenshtein($istance,$etweentwostrin);

Para que isso funcione, você precisa enviar / definir uma variável POST / GET / COOKIE / session com as teclas:

• distance( istancepara o menor)
• between_two_strings( etweentwostrinpara o menor)

Os argumentos estão nessa ordem.

Teste a pontuação em http://ideone.com/QzNZ8T

Exemplo:

http://localhost/distance.php?distance=string1&between_two_strings=string2

PHP, distância 44

function Calculate($two,$strings){echo levenshtein($two,$strings);}

Use a levenshteinfunção interna da biblioteca padrão do PHP e nomeie os argumentos para tentar minimizar a distância.

Pip, distância 50

Não usa nenhuma função Levenshtein embutida!

xINg?#JgMN[1+(fac:b@>1)1+(fe:a@>1b)(a@0NEb@0)+(fec)]

Esse código implementa o algoritmo recursivo de Levenshtein ; Como tal, é extremamente lento, demorando alguns segundos, mesmo para seqüências de comprimento 5. Não recomendo executar o programa por si só para verificá-lo!

Aqui está o meu código base, com espaço em branco e comentários:

; Note: a Pip program is an implicit function f, which is called with the command-line
; arguments. The args are stored in the list g, as well as being assigned to the local
; variables a-e.

; Is one of the args the empty string? (NB x is initialized to "")
x IN g ?
 ; If so, join args together and take the length (i.e., length of the non-empty string).
 # J g
 ; If not, take the min of the following:
 MN [
  ; Recursively call f with the first character of a removed; add 1 to the result
  (f a@>1 b) + 1
  ; Recursively call f with the first character of b removed; add 1 to the result
  (f a b@>1) + 1
  ; Recursively call f with the first characters of both removed; iff the two characters
  ; were not equal, add 1 to the result
  (f a@>1 b@>1) + (a@0 NE b@0)
 ]

A principal mudança na versão final é atribuir alguns valores a variáveis ​​temporárias ce e, que aparecem na sequência de desafio e, assim, reduzem um pouco a distância de Levenshtein.