Explication
La distance d'édition entre deux chaînes est fonction du nombre minimal possible d'insertions, de suppressions ou de substitutions pour convertir un mot en un autre mot.
Les insertions et les suppressions coûtent 1 et les substitutions coûtent 2.
Par exemple, la distance entre AB
et A
est 1, car les suppressions coûtent 1 et la seule modification nécessaire est la suppression du B
caractère.
La distance entre CAR
et FAR
est 2, car les substitutions coûtent 2. Une autre façon de voir cela est une suppression et une insertion.
Règles
Étant donné deux chaînes d'entrée (fournies cependant est pratique dans votre langue), votre programme doit trouver la distance d'édition minimale entre les deux chaînes.
Vous pouvez supposer que les chaînes contiennent uniquement les caractères A-Z
et ont moins de 100 caractères et plus de 0 caractères.
C'est le golf de code , donc la solution la plus courte l'emporte.
Exemples de cas de test
ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8
levenshtein
fonction intégrée traite les substitutions comme une seule modification (substitut) et non deux (suppression + insertion).Réponses:
brainfuck, 2680
Bien sûr, en utilisant la programmation dynamique.
Les chaînes d'entrée doivent être séparées par un espace et suivies d'une nouvelle ligne. Par exemple:
la source
Python, 138
148152 152caractèresOk, je connaissais le principe mais je n'avais jamais implémenté la distance d'édition auparavant, alors voici:
la source
PHP, 40
Suit les règles comme indiqué, mais pas l'esprit des règles:
Prend ses deux paramètres comme arguments. Exemple d' appel:
php edit_dist.php word1 word2
.Considère normalement
levenshtein()
une substitution comme une opération, mais elle a une forme surchargée où les poids d'insertion / sous / suppression peuvent être spécifiés. Dans ce cas, son 1/2/1.la source
APL (90 caractères)
J'utilise Dyalog APL comme interprète, avec
⎕IO
la valeur 1 et⎕ML
la valeur 0. La fonction directe ({ ... }
) calcule, en fonction d'une ligne en entrée, la ligne suivante dans la matrice de distance. (Il commence par la ligne initiale:.0,⍳x
) L'opérateur de puissance (⍣
) est utilisé pour imbriquer la fonction une fois pour chaque caractère de la deuxième chaîne (⊃⍴b
). Après tout cela, la dernière ligne est inversée (⌽
) et son premier élément est pris (⊃
).Exemple:
la source
R 51
Cela lit sur deux lignes de l'utilisateur (qui sont l'entrée), puis utilise simplement la
adist
fonction pour calculer la distance. Étant donné que les substitutions coûtent 2 pour ce problème, nous devons ajouter un vecteur nommé pour le paramètre des coûts pour adist. Puisqu'il existe également un paramètre count pour adist, nous ne pouvons que réduire les coûts en cos, nous avons donc toujours une correspondance unique pour les noms des paramètres.Exemple d'utilisation
la source
Rubis 1.9, 124
Version golfée de la méthode Ruby lente et récursive ici , modifiée pour doubler le poids des substitutions. Le fait qu'il faut 7 caractères pour supprimer le premier caractère d'une chaîne fait vraiment mal, et ce serait cool de le remplacer
(a[0]==b[0]?-1:1)
par quelque chose comme,-1**a[0]<=>b[0]
mais l'ordre des opérations n'est pas mon ami.la source
Smalltalk (Smalltalk / X), 34
J'ai de la chance - la classe "String" standard contient déjà levenshtein:
entrée a, b:
(les paramètres supplémentaires permettent différents poids sur la substitution, la suppression, etc.)
Essai:
->
la source