Code close to the challenge: Inception

Question

This is a sequel to this challenge: Code close to the challenge: Sum of integers

The challenge in this one is a bit harder, and also makes for a cool title (Which is why I picked it):

Calculate the Levenshtein distance between two strings

Just like last challenge, your score in this challenge is the Levenshtein distance between your code and the quote above.

So now for the details!

Your program will take 2 inputs, both strings with no trailing spaces or newlines, and will output the Levenshtein distance between them. Levenshtien distance is defined as the number of of additions, deletions, and substitutions necessary to transform one string to another. For more information on how to calculate it, see the Wikipedia page linked above. To test if your program works, use this calculator. Your program must output nothing but the Levenshtein distance between the two strings. It will be disqualified if anything else is outputted. Example I/O:

Inputs:
test
test2
Output:
1

Inputs:
222
515
Output:
3

Inputs:
Test
test
Output:
1

Your code may not have no-ops or comments.

Answer 1

Frink, distance 24

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

To use this, you would call Calculate with the two strings, and since this is returning, you also need to surround the call with print[]. If this isn't allowed, my score is 30.

Example:

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

You need to download Frink, as the web interpreter doesn't allow defining functions. It should run on all systems, considering it's a Java applet. Download instructions here..

---

^{Psst. Hey! Here's a Levenshtein implementation in Symbolic, something I'm working on: k=λ:Δ(ί,ί).}

Answer 2

R, distance 35

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

This creates a function Calculate with parameters the and Levenshtein. It uses the R built-in function adist to compute the distance. The string parameters in adist are essentially the and Levenshtein renamed to between and two.

Answer 3

PHP4.1, distance 32 22 15 14

Very basic one, nothing exciting.

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

Or a shorter version:

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

For this to work, you need to send/set a POST/GET/COOKIE/session variable with the keys:

• distance (istance for the shorter one)
• between_two_strings (etweentwostrin for the shorter one)

The arguments are in that order.

Test the score on http://ideone.com/QzNZ8T

Example:

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

Answer 4

PHP, distance 44

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

Use the built-in levenshtein function from PHP standard library and named the arguments in order to try to minimize the distance.

Answer 5

Pip, distance 50

Uses no builtin Levenshtein function!

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

This code implements the recursive Levenshtein algorithm; as such, it is extremely slow, taking a few seconds even for strings of length 5. I wouldn't recommend running the program through itself to check it!

Here's my base code, with whitespace and comments:

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

The main change in the final version is assigning some values to temporary variables c and e, which appear in the challenge string and thus reduce the Levenshtein distance a bit.