Wyjaśnienie

Odległość edytować między dwóch ciągów jest funkcją minimalnej możliwej liczby insercji, delecji lub podstawienia do konwersji jednego słowa do słowa.

Wstawienia i usunięcia kosztują 1, a zamiany kosztują 2.

Na przykład odległość między ABi Awynosi 1, ponieważ usunięcie kosztuje 1, a jedyną potrzebną edycją jest usunięcie Bznaku.

Odległość między CARi FARwynosi 2, ponieważ podstawienia kosztują 2. Innym sposobem na to jest jedno usunięcie i jedno wstawienie.

Zasady

Biorąc pod uwagę dwa ciągi wejściowe (dostarczone jest jednak wygodne w twoim języku), twój program musi znaleźć minimalną odległość edycji między tymi dwoma ciągami.

Możesz założyć, że ciągi zawierają tylko znaki A-Zi mają mniej niż 100 znaków i więcej niż 0 znaków.

To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie.

Przykładowe przypadki testowe

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

pieprzenie mózgu, 2680

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

Oczywiście przy użyciu programowania dynamicznego.

Ciągi wejściowe powinny być oddzielone spacją, a następnie nowy wiersz. Na przykład:

INTENTION EXECUTION
008

Python, 138 148 152 znaków

Ok, znałem tę zasadę, ale nigdy wcześniej nie wdrożyłem odległości edycji, więc oto:

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

Przestrzega zasad, jak podano, ale nie ducha zasad:

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

Jako argument przyjmuje dwa parametry. Przykład numerem: php edit_dist.php word1 word2.
Zwykle levenshtein()uważa podstawienie za jedną operację, ale ma on postać przeciążoną, w której można określić wagi wstawiania / sub / usuwania. W tym przypadku jest to 1/2/1.

APL (90 znaków)

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

Używam Dyalog APL jako mojego interpretera, z ⎕IOustawieniem na 1 i ⎕MLustawieniem na 0. Funkcja direct ( { ... }) oblicza, podając wiersz jako dane wejściowe, następny wiersz w macierzy odległości. (Rozpoczyna się od pierwszego wiersza:. 0,⍳x) Operator mocy ( ⍣) służy do zagnieżdżenia funkcji raz dla każdego znaku w drugim ciągu ( ⊃⍴b). Po tym wszystkim ostatni wiersz jest odwracany ( ⌽) i pobierany jest jego pierwszy element ( ⊃).

Przykład:

      ⊃⌽({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

Odczytuje to dwa wiersze od użytkownika (które są danymi wejściowymi), a następnie po prostu używa adistfunkcji do obliczenia odległości. Ponieważ podstawienia kosztują 2 za ten problem, musimy dodać nazwany wektor dla parametru kosztów dla adist. Ponieważ istnieje także parametr counts dla adist, możemy jedynie skrócić koszty do cos, więc nadal mamy unikalne dopasowanie dla nazw parametrów.

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

Przykładowe użycie

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

Ruby 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]

Golfowa wersja powolnej, rekurencyjnej metody Ruby tutaj , zmodyfikowana w celu podwojenia wagi zastępstw. Fakt, że usunięcie pierwszego znaku ciągu zajmuje 7 znaków, naprawdę boli i fajnie byłoby zastąpić (a[0]==b[0]?-1:1)go czymś takim, -1**a[0]<=>b[0]ale kolejność operacji nie jest moim przyjacielem.

Smalltalk (Smalltalk / X), 34

Mam szczęście - standardowa klasa „String” zawiera już levenshtein:

wprowadź a, b:

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

(dodatkowe parametry pozwalają na różne wagi przy podstawianiu, usuwaniu itp.)

Testowe uruchomienie:

#( '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