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

[Artificial]

URL to challenge:

http://www.facebook.com/careers/puzzles.php?puzzle_id=17

I haven't actually wrote a solution for this yet. I've just had a brief look at it. The principle behind it doesn't look too difficult, so I shouldn't imagine it would present too many problems. I'll complete it soon and share my solution. If you also want to do it, feel free! If you have any questions/experience any difficulty, please don't hesitate to ask questions.



As always, I only ask you put your solutions in spoiler tags to give everyone a fair go.

[The Unintelligible]

Looks fun. As you said, the whole concept of it looks relatively simple.
If I have the spare time, I guess I'll take a crack at it.

[Artificial]

My solution:

Spoiler:

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())

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.

[The Unintelligible]

gr8. now that im looking at this from more of an abstract level, it seems a bit more difficult than i originally thought it'd be.

ill see if i can muster up the time trk on this tonight.

[Artificial]

Here's a spolier if you're a bit stuck:

Spoiler:

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.

If you do get around to it, I look forward to reading your solution.

[The Unintelligible]

sorry Art'. was never able to get back with this. the computer I have going is really inefficient. 0.5 GBs of RAM and 25+ GBs of HD. i'm going to have to wait 'til these things get situated before attempting anything (or at least anything programming-related). this PC needs a revamp from the ground up. if these issues get addressed relatively soon, i'll be more than glad to get back to these, though.

again, i know this all seems really sudden — but I can assure you it's why I've chosen not to tend to this right now. and I apologize if I gave you any form of impression. also, nice work with the puzzles and all. they really add some appeal to this section you know.

[Artificial]

Nrries. Hope you get sorted soon.

[irfan]

Please provide a solution. I was expecting a solution ti this, but I do no see anything. It will be of great help.

[The Unintelligible]

He has already provided a solution. You're either a frivolous bot, or just stupid.

This reminds me, I was supposed to do this a while ago. It's too bad I don't own a personal computer anymore. Saving up for one as we speak.

[Isonyx]

Spoiler:

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

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.

[The Unintelligible]

Good work man. I guess I won't be doing this after all since I no longer have an incentive to. Seems a bit played out now.

Unrelated note: still cannot be on actively for a good couple months. Bawww ):

[Isonyx]

Good work man. I guess I won't be doing this after all since I no longer have an incentive to. Seems a bit played out now.

Unrelated note: still cannot be on actively for a good couple months. Bawww ):

Yeah, there are an unlimited number of ways to do it, but a limited number of practical/efficient ways to do it if you know what I mean.

[The Unintelligible]

Yeah, there are an unlimited number of ways to do it, but a limited number of practical/efficient ways to do it if you know what I mean.

But yea, I sort of see that now. In retrospect, never attempted it but planned on doing it from scratch. Naive was I, although I imagine there's still at least a handful of creative ways to go about it.

[Isonyx]

But yea, I sort of see that now. In retrospect, never attempted it but planned on doing it from scratch. Naive was I, although I imagine there's still at least a handful of creative ways to go about it.

[The Unintelligible]

Ur mom .

[The Unintelligible]

Also by "naive" im referring to my original idea of going about the challenge. Imprudent. Shortsighted. Foolish. Naive.

My initial angle of plan was to just do it. No use of standard algorithms/my own custom one/everything from scratch.

Basically i had intended to hack together some quick-and-dirty code. In hindsight, that doesn't really seem like a solid approach.

[Artificial]

Your solution looks quite nice.

[Isonyx]

Your solution looks quite nice.

Thanks but it's very similar to yours.
I assume you deleted that less efficient custom algorithm you referenced in your post.
If not it would be cool to see.

[Artificial]

I never recreated it after deleting it. I could probably throw down some pseudocode from what I remember of it this afternoon if required.

[Isonyx]

I never recreated it after deleting it. I could probably throw down some pseudocode from what I remember of it this afternoon if required.

Whenever you feel like sharing it'd be interesting to see.