-
Notifications
You must be signed in to change notification settings - Fork 0
/
breath
47 lines (27 loc) · 3.51 KB
/
breath
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Do you like puzzles? So do we.
If you love puzzles like we do, become a fan of the new Puzzle Master Facebook Page . Notes are regularly posted to answer questions, explain puzzles, and announce new things. While you're here, try your hand at the following puzzles. The larger the difficulty, the harder it gets (hors d'oeuvres are simple tests to help you out).
Breathalyzer
To safeguard against the dreaded phenomenon of wall posting while drunk, Facebook is implementing a feature that detects when post content is too garbled to have been done while sober and informs the user that they need to take an online breathalyzer test before being allowed to post.
Unfortunately, there is far too much content for a given set of persons to evaluate by hand. Fortunately, you are a programmer of some repute and can write a program that processes and evaluates wall posts. You realize that such a program would be of great use to society and intend to resolve the problem once and for all. The program you write must compute a score for a body of text, returning this score upon completion.
Your program will be given a list of accepted words and run on one wall post at a time. For each word W in the post, you must find word W' from the list of accepted words such that the number of changes from W to W' is minimized. It is possible that W is already W' and thus the number of changes necessary is zero. A change is defined as replacing a single letter with another letter, adding a letter in any position, or removing a letter from any position. The total score for the wall post is the minimum number of changes necessary to make all words in the post acceptable.
Input Specification
Your program must take a single string argument, representing the file name containing the wall post to analyze. In addition, your program must open up and read the accepted word list from the following static path location:
/var/tmp/twl06.txt
For testing purposes, you may download and examine the accepted word list here. When submitting your code, you do not need to include this file, as it is already present on the machine.
The input file consists entirely of lower case letters and space characters. You are guaranteed that the input file will start with a lower case letter, and that all words are separated by at least one space character. The file may or may not end with a new line character.
Example input file:
tihs sententcnes iss nout varrry goud
You are guaranteed that your program will run against well formed input files and that the accepted word list is identical to the one provided for testing.
Output Specification
Your program must print out the minimum number of changes necessary to turn all words in the input wall post into accepted words as defined by the word list file. Words may not be joined together, or separated into multiple words. A change in a word is defined as one of the following:
Replacing any single letter with another letter.
Adding a single letter in any position.
Removing any single letter.
This score must be printed out as an integer and followed by a single new line.
Example Output (newline after number):
8
You need more than a fast way to determine the minimum number of changes from one word to another.
A compiled inner loop is particularly helpful for this puzzle.
For some words, every acceptable word with the minimum number of changes starts with a different letter (e.g., korrect → correct).
twl06.txt is a Scrabble word list.
"c" and "v" each require two changes.