Facebook Puzzle Challenge - Breathalyzer - Difficulty: Snack (easy)

I originally wrote a custom algorithm which calculated the difference based on a sequence of probability outcomes. However, the method was too slow (execution time of over 200 seconds). I then decided to use the Levenshtein Distance algoritm Matt sent me which, when I wrote a Python algorithm, cut the execution time down to 50 seconds. I was able to optimize this algorithm to cut it down to 30. However, the main drawback with Python is that it is an interpreted language (which actually isn't a drawback, it's one of it's strengths, but it does mean an intensive algorithm like that is always going to perform far worse than a compiled solution in a language like C). I therefore used the contributed Python extension pylevenshtein which got it down to 0.5 seconds (while it is a contributed extension, I'm not sure if that would class it as cheating - my original solution was working, but this extension just makes it 1000x more efficient).

#!/usr/bin/python

import time, Levenshtein, sys



# Let's read our word list in to a string

words = file('/var/tmp/twl06.txt').read().lower().split("\r\n")



# Calculate the amount of changes required to make the change

def shortest(check):

	shortest = -1

	for word in words:

		if shortest == 0:

			break

		tmpDif = Levenshtein.distance(check, word)

		if shortest == -1 or tmpDif < shortest:

			shortest = tmpDif

			

	return shortest

	

# Let's grab the word count

sentence = file(sys.argv[1]).read().lower().replace("\n", "")

sentenceWords = sentence.split(" ")

count = 0

for word in sentenceWords:

	count += shortest(word)

print count



# Debug: measure execution time

# print "Execution time: " + str(time.clock())[/1]

edit: actually, now I think about it, if Facebook's checker was working, this wouldn't pass, since it does use a contributed module. I stupidly closed the file without saving my original algorithm, so I'll rewrite it this afternoon and post it back up.

Like the previous challenge, FB are trying to trick you a bit. The question isn't asking you to change the words to what YOU think they should be. i.e. it is logical to assume:

tihs sententcnes iss nout varrry goud

Should be changed to:

this sentence is not very good

And then, after calculating the differences between the two strings, you'll arrive at the answer. However. that's not what it's asking, and if you try to write that you won't arrive at the correct answer.

So originally since Artificial used the most obvious solution out there (thanks Artificial), I was going to attempt to use either the Soundex Algorithm or the Double Metaphone.

Three minutes later, I realized it would be a complete and utter waste of time (and wouldn't actually work) when I could just implement the same one he did in a different language.

Used some edit distance code I found online as opposed to an actual Java Levenshtein library, even though technically edit distance and Levenshtein aren't always referred to as the same thing. Unfortuanately I didn't really have anything new to bring to this challenge and the code isn't optimized yet.

Any contributions/edits would be welcomed. Maybe in a bit I'll try coming up with a custom algorithm, though I doubt it.
Just wanted to attempt it real quick, even though Artificial already implemented it.


DrunkProofer.java

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;



/**

 * @author Isonyx

 * @date 11/28/2012

 *

 * A class created for the Facebook Puzzle Breathalyzer Challenge

 * Takes advantage of the edit distance algorithm.

 */



public class DrunkProofer {

	private String myFile;



	public DrunkProofer(String drunkFile) {

		this.myFile = drunkFile;

	}



	public int minimumChanges() {

		File drunkenFile = new File(myFile);

		String[] drunkenText = new String[0];

		try {

			Scanner theInput = new Scanner(drunkenFile);

			String drunkPhrase = "";

			while (theInput.hasNextLine()) {

				drunkPhrase += (theInput.nextLine()).replaceAll("\\r\\n|\\r|\\n", " ");

			}

			drunkenText = drunkPhrase.split(" ");

			theInput.close();

		} catch (FileNotFoundException e) {

			e.printStackTrace();

		}

		return (drunkenText.length > 0 ?  findChanges(drunkenText) : -1);		

	}



	public int findChanges(String[] drunkenText)  {

		String nextWord = ""; 

		int finalCount = 0;

		Scanner theInput = null;

		for (String drunkenWord: drunkenText) {

			int wordCount = 0;

			int shortest = -1;

			try {

				File dictionaryList = new File("twl06.txt");

				 theInput = new Scanner(dictionaryList);

				 while (theInput.hasNext()) {

					 nextWord = theInput.next().toLowerCase();

					 if (shortest == 0) { break; }

					 if (editDistance(drunkenWord, nextWord) < shortest || shortest == -1) { 

						 shortest = editDistance(drunkenWord, nextWord);

					 }

				 }

				 wordCount =+ shortest;

			} catch (FileNotFoundException e) {

				e.printStackTrace();

			}	

			finalCount += wordCount;

			theInput.close();

		}

		return finalCount;

	}



	public void changeFile(String newFile) {

		this.myFile = newFile;

	}



	private int editDistance(String s, String t){

	    int m = s.length();

	    int n = t.length();

	    int[][] d = new int[m + 1][n + 1];

	    for (int i = 0; i <= m; i++) { d[i][0] = i; }

	    for (int j = 0; j <= n; j++) { d[0][j] = j; }

	    for (int j = 1; j <= n; j++) {

	      for (int i = 1; i <= m; i++) {

	        if (s.charAt(i - 1) == t.charAt(j - 1)) { d[i][j] = d[i - 1][j - 1]; }

	        else { d[i][j] = minimum((d[i - 1][j] + 1),(d[i][j - 1] + 1),(d[i - 1][j - 1] + 1)); }

	      }

	    }

	    return (d[m][n]);

	}



	private int minimum(int a, int b, int c) {

	    return (Math.min(Math.min(a,  b), c));

	}

}[/n][/m][/i][/j][/j][/i][/j][/i][/j][/0][/0][/i][/0]

Main.java

/**

 * @author Isonyx

 * @date 11/28/2012

 *

 * A class created for the Facebook Puzzle Breathalyzer Challenge

 */



public class Main {

	public static void main(String[] args) {

		DrunkProofer drunk = new DrunkProofer("sentence.txt");

		

		long start = System.nanoTime();

		

		int minimumChanges = drunk.minimumChanges();

		

		long end = System.nanoTime();

		

		double seconds = (double)(end - start) / 1000000000.0;

		System.out.println("Elapsed Time: " + seconds);

		System.out.println("Changes: " + minimumChanges);

	}

}

twl06.txt
/var/tmp/twl06.txt

Although Artificial didn't link to it, the link for twl06.txt is hosted on Facebook, but I forgot where. You can find it --here.

Sentence.txt

tihs sententcnes iss nout varrry goud

The project is also hosted on my Github -- here.