Esta es una secuela de este desafío: Código cercano al desafío: Suma de enteros

El desafío en este es un poco más difícil, y también lo convierte en un título genial (por eso lo elegí):

Calcule la distancia de Levenshtein entre dos cuerdas

Al igual que en el último desafío, su puntaje en este desafío es la distancia de Levenshtein entre su código y la cita anterior.

Así que ahora para los detalles!

Su programa tomará 2 entradas, ambas cadenas sin espacios finales o líneas nuevas, y generará la distancia de Levenshtein entre ellas. La distancia de Levenshtien se define como el número de adiciones, eliminaciones y sustituciones necesarias para transformar una cadena en otra. Para obtener más información sobre cómo calcularlo, consulte la página de Wikipedia vinculada anteriormente. Para probar si su programa funciona, use esta calculadora . Su programa no debe generar nada más que la distancia de Levenshtein entre las dos cadenas. Será descalificado si sale algo más. Ejemplo de E / S:

Inputs:
test
test2
Output:
1

Inputs:
222
515
Output:
3

Inputs:
Test
test
Output:
1

Su código puede no tener no-ops o comentarios.

Frink , distancia 24

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

Para usar esto, debe llamar a Calcular con las dos cadenas, y dado que esto está regresando, también debe rodear la llamada con print[]. Si esto no está permitido, mi puntaje es 30.

Ejemplo:

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

Necesita descargar Frink, ya que el intérprete web no permite definir funciones. Debería ejecutarse en todos los sistemas, considerando que es un applet de Java. Descargue las instrucciones aquí. .

^{Psst. ¡Oye! Aquí hay una aplicación en Levenshtein simbólico, algo que estoy trabajando en: k=λ:Δ(ί,ί).}

R, distancia 35

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

Esto crea una función Calculatecon parámetros they Levenshtein. Utiliza la función incorporada R adistpara calcular la distancia. Los parámetros de cadena en adistson esencialmente they Levenshteinrenombrados a betweeny two.

PHP4.1, distancia 32 22 15 14

Muy básico, nada emocionante.

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

O una versión más corta:

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

Para que esto funcione, debe enviar / configurar una variable POST / GET / COOKIE / session con las teclas:

• distance( istancepara el más corto)
• between_two_strings( etweentwostrinpara el más corto)

Los argumentos están en ese orden.

Prueba la puntuación en http://ideone.com/QzNZ8T

Ejemplo:

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

PHP, distancia 44

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

Use la levenshteinfunción incorporada de la biblioteca estándar de PHP y nombre los argumentos para intentar minimizar la distancia.

Pip, distancia 50

¡No utiliza la función incorporada de Levenshtein!

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

Este código implementa el algoritmo recursivo de Levenshtein ; como tal, es extremadamente lento, toma unos segundos incluso para cadenas de longitud 5. ¡No recomendaría ejecutar el programa por sí mismo para verificarlo!

Aquí está mi código base, con espacios en blanco y comentarios:

; 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)
 ]

El cambio principal en la versión final es asignar algunos valores a variables temporales cy e, que aparecen en la cadena de desafío y, por lo tanto, reducen un poco la distancia de Levenshtein.