Jest to kontynuacja tego wyzwania: Kod zbliżony do wyzwania: Suma liczb całkowitych

Wyzwanie w tym jest nieco trudniejsze, a także tworzy fajny tytuł (dlatego go wybrałem):

Oblicz odległość Levenshteina między dwoma strunami

Podobnie jak w ostatnim wyzwaniu, twój wynik w tym wyzwaniu to odległość Levenshteina między twoim kodem a cytatem powyżej.

A teraz szczegóły!

Twój program pobierze 2 dane wejściowe, oba ciągi bez spacji i znaków nowej linii, i wyświetli odległość Levenshteina między nimi. Odległość Levenshtien definiuje się jako liczbę dodatków, usunięć i podstawień niezbędnych do przekształcenia jednego łańcucha na inny. Aby uzyskać więcej informacji na temat tego, jak to obliczyć, zobacz stronę Wikipedii, do której prowadzi link powyżej. Aby sprawdzić, czy Twój program działa, użyj tego kalkulatora . Twój program musi wyświetlać tylko odległość Levenshteina między dwoma łańcuchami. Zostanie zdyskwalifikowany, jeśli zostanie wydane cokolwiek innego. Przykład I / O:

Inputs:
test
test2
Output:
1

Inputs:
222
515
Output:
3

Inputs:
Test
test
Output:
1

Twój kod może nie zawierać braków ani komentarzy.

Frink , odległość 24

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

Aby tego użyć, wywołaj funkcję Oblicz z dwoma ciągami, a ponieważ to zwraca, musisz także otoczyć połączenie print[]. Jeśli nie jest to dozwolone, mój wynik to 30.

Przykład:

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

Musisz pobrać Frink, ponieważ interpreter internetowy nie pozwala na definiowanie funkcji. Powinien działać na wszystkich systemach, zważywszy, że jest to aplet Java. Pobierz instrukcje tutaj. .

^{Psst. Hej! Oto realizacja Levenshteina w symboliczny, czymś pracuję nad: k=λ:Δ(ί,ί).}

R, odległość 35

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

To tworzy funkcję Calculatez parametrami thei Levenshtein. Wykorzystuje wbudowaną funkcję R adistdo obliczenia odległości. Parametry ciągu znaków adistsą w zasadzie zmienione thei Levenshteinzmienione na betweeni two.

PHP4.1, odległość 32 22 15 14

Bardzo podstawowy, nic ekscytującego.

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

Lub krótsza wersja:

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

Aby to zadziałało, musisz wysłać / ustawić zmienną sesji POST / GET / COOKIE / za pomocą klawiszy:

• distance( istancedla krótszego)
• between_two_strings( etweentwostrindla krótszego)

Argumenty są w tej kolejności.

Przetestuj wynik na http://ideone.com/QzNZ8T

Przykład:

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

PHP, odległość 44

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

Użyj wbudowanej levenshteinfunkcji ze standardowej biblioteki PHP i nazwij argumenty, aby spróbować zminimalizować odległość.

Pip, odległość 50

Nie używa wbudowanej funkcji Levenshtein!

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

Ten kod implementuje rekurencyjny algorytm Levenshteina ; jako taki jest bardzo powolny, zajmuje kilka sekund nawet dla ciągów o długości 5. Nie polecam uruchamiania programu przez siebie, aby go sprawdzić!

Oto mój kod podstawowy z białymi znakami i komentarzami:

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

Główną zmianą w ostatecznej wersji jest przypisanie wartości do pewnych zmiennych tymczasowych ci e, które pojawiają się w ciągu wyzwania, a tym samym zmniejszyć dystans Levenshteina trochę.