15
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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=λ:Δ(ί,ί).

\$\endgroup\$
  • 3
    \$\begingroup\$ Interesting language, reminds me of Mathematica. \$\endgroup\$ – Alex A. Jul 23 '15 at 16:33
  • \$\begingroup\$ This counts as using a built-in function to solve the challenge, which could be considered a standard loophole (but so seem to 90℅ of all answers to this challenge) \$\endgroup\$ – John Dvorak Jul 24 '15 at 14:57
  • 1
    \$\begingroup\$ @JanDvorak Built-ins are kind of a gray area since the vote breakdown on the meta answer listing built-ins as a standard loophole is near half and half. \$\endgroup\$ – Alex A. Jul 24 '15 at 18:34
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @AboveFire Sorry, but I can't accept your edit. Quoting the O.P.: "Your code may not have no-ops or comments." and your edit simply added an HTML comment. \$\endgroup\$ – Ismael Miguel Jul 23 '15 at 17:50
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't it be $two,$strings? \$\endgroup\$ – Ismael Miguel Jul 23 '15 at 17:03
  • \$\begingroup\$ indeed, it should. \$\endgroup\$ – 永劫回帰 Jul 23 '15 at 17:05
  • 1
    \$\begingroup\$ Also, you are missing a ; \$\endgroup\$ – Ismael Miguel Jul 23 '15 at 17:05
  • \$\begingroup\$ I offer you a solution with a distance of 28: echo$Calculate_the=levenshtein($_GET[distance_between_two],$_GET[strings]); \$\endgroup\$ – Ismael Miguel Jul 23 '15 at 18:07
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy