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 to work 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]

No worries. Hope you get sorted soon.