The Levenshtein Distance between two strings a, b is the number of changes to transform one string into another. For example to transform mouse into house would take 1 (change the m to an h). If the strings are different length then either characters need to be added or removed. The total number of operations needed (inserts, deletes or changes) is the Levenshtein distance.
In this challenge you are given a txt file of 100 word pairs, each pair is on a separate line and comma separated. You must write a function
int getLevenshteinDistance(string a,string b)
int getLevenshteinDistance(char * a,char * b)
that calculates the distance between the two strings and returns it then outputs a text file with the 100 numbers in and the total time it took (excluding reading the text file and writing it). This is a speed challenge.
Note to keep it simple the lengths of the two words will only differ by at most 2 characters. So you may get a 6 letter word to transform into a 4,5, 6,7 or 8 letter word but not 9 or more, or 3 or less.
Input Files
There is one file, located in the same folders as your exe.
- Input.txt. This is a text file holding 100 word pairs, two per line, that are comma separated.
The Output
Output a file output.txt in the same location as your exe. The first line should have the average time of a run. A run is all 100 word pairs. If your code is lightning fast redo the calculation so it takes a few seconds.
"Average time = 0.87 sec"
The rest of the file should be 100 lines containing the two words (comma separated) and the distance like this on each line:
Fred,Fredd,1
Final Results
Congrats to Pedro Graca for a very fast time. I know that one or two of the others are very interested in seeing how your time was so fast! Thanks to everyone who entered, all 13. We had entries from Australia, Cuba, Japan, Egypt, Sweden and USA. (Apols if I've left anyone off). I'll update this with countries tomorrow.
- Pedro Graca - C 0
- James Borden - C# 0.000007564333-
- Dinh Viet Huy - C 0.00001-
- Calvin Lin - C++ 0.000027-
- Peter Jansson - C++ 0.0000270791-
- Shravan Kumar - C 0.000037
- Mahmoud Mohamed Hassan - C++0.0000396872
- David - C++ 0.0000454985-
- Gabriel Dubois - C++ 0.0000477027-
- Shashi Sadasivan - C# 0.00013853
- Felipe Ramos - C# 0.001154-
- Dinh Viet Huy - C# 0.0029761-
- Scott Hein - C# 0.015853
Timing Code
Please time from the start of the run, after reading in the input file until just before the output file is opened for writing. This code below will do high speed timing.
Rules
This is for glory only. About.com does not permit prizes to be given.Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Contest 39 email address with the subject line Programming Contest 39.
It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is September 30 2010.
The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
- An index of Every Past Programming Contest on this site
