Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Explanation

The edit distance between two strings is a function of the minimum possible number of insertions, deletions, or substitutions to convert one word into another word.

Insertions and deletions cost 1, and substitutions cost 2.

For example, the distance between AB and A is 1, because deletions cost 1 and the only edit needed is the deletion of the B character.

The distance between CAR and FAR is 2, because substitutions cost 2. Another way to look at this is one deletion and one insertion.

Rules

Given two input strings (supplied however is convenient in your language), your program must find the minimum edit distance between the two strings.

You may assume that the strings only contain the characters A-Z and have fewer than 100 characters and more than 0 characters.

This is code golf, so the shortest solution wins.

Sample Test Cases

ISLANDER, SLANDER
> 1
MART, KARMA
> 5
KITTEN, SITTING
> 5
INTENTION, EXECUTION
> 8
share|improve this question
    
I did this in excel in my algorithms class once. Was kinda fun to turn the project in as an .xls document. It actually worked pretty well. I'll see if I can find it. –  CMP Mar 16 '12 at 17:32
    
PHP should win this easily. –  st0le Mar 19 '12 at 12:13
    
@st0le - The built in levenshtein function treats substitutions as one edit (substitute), not two (delete + insert). –  GigaWatt Mar 20 '12 at 17:25
add comment

8 Answers

Python, 138 148 152 characters

Ok, I knew the principle but had never implemented edit distance before, so here goes:

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]
share|improve this answer
add comment

PHP, 40

Follows the rules as stated, but not the spirit of the rules:

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

Takes it's two parameters as arguments. Example calling: php edit_dist.php word1 word2.
Normally levenshtein() considers a substitution as one operation, but it has an overloaded form where the insert/sub/delete weights can be specified. In this case, its 1/2/1.

share|improve this answer
add comment

brainfuck, 2680

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

Using dynamic programming, of course.

Input strings should be separated by a space, and followed by a new line. For example:

INTENTION EXECUTION
008
share|improve this answer
    
Neatly aligned and very readable - I like it, +1! –  Thomas Nov 18 '12 at 11:45
add comment

APL (90 characters)

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

I'm using Dyalog APL as my interpreter, with ⎕IO set to 1 and ⎕ML set to 0. The direct function ({ ... }) computes, given a row as input, the next row in the distance matrix. (It is started with the initial row: 0,⍳x.) The power operator () is used to nest the function once for each character in the second string (⊃⍴b). After all of that, the final row is reversed (), and its first element is taken ().

Example:

      ⊃⌽({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
share|improve this answer
add comment

R 51

This reads in two lines from the user (which are the input) and then just uses the adist function to calculate the distance. Since substitutions cost 2 for this problem we need to add a named vector for the costs parameter for adist. Since there is also a counts parameter for adist we can only shorten costs to cos so we still have a unique match for the parameter names.

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

Example use

> x=readLines(n=2);adist(x[1],x[2],cos=c(i=1,d=1,s=2))
MART
KARMA
     [,1]
[1,]    5
share|improve this answer
add comment

D

int d(string a,string b){
int s;foreach(c;levenshteinDistanceAndPath(a,b)[1]){s+=(c=='i'||c=='r'?1:c=='s'?2:0);}
return s;
}

built in function

share|improve this answer
2  
Levenshtein distance counts substitutions as 1 step, while this question requires that it be counted as 2. –  PhiNotPi Mar 16 '12 at 18:36
    
@PhiNotPi fixed –  ratchet freak Mar 16 '12 at 18:51
2  
@ratchetfreak: Correct me if I'm wrong, but since the Levenshtein distance between ABB and BCC is 3 (based on 3 substitutions), your code would return 6, instead of the correct answer that should be 4 (based on 2 deletions and 2 insertions). –  han Mar 18 '12 at 10:49
add comment

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]

Golfed version of the slow, recursive Ruby method here, modified to double the weight for substitutions. The fact that it takes 7 characters to remove the first character of a string really hurts, and it'd be cool to replace (a[0]==b[0]?-1:1) with something like -1**a[0]<=>b[0] but the order of operations is not my friend.

share|improve this answer
add comment

Smalltalk (Smalltalk/X), 34

I am lucky - the standard "String" class already contains levenshtein:

input a, b:

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

(the additional parameters allow for different weights on substitution, deletion, etc.)

Test run:

#( '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
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.