/-/S'pht-Translator-Active/-/


Re: PID for OS X
Posted By: Ron HunsingerDate: 4/18/13 1:01 a.m.

In Response To: Re: PID for OS X (Hopper)

: : the code to talk to the dead.

: Could you please explain how the spelling correction works in the
: conversation input? It doesn't work in the OS X port, so I presume it
: wasn't in the source code Mark received. I can't come up with an algorithm
: to replicate the results .

Sure. I was impressed when I saw it, that they would go to so much trouble to try to understand. They exploit the fact that the vocabulary is small, and the game is paused so they have the full power of the processor at their disposal, which means they don't have to worry about efficiency.

What they do is for each word in what you type, and for each word in the vocabulary, they calculate a "percentage agreement". The vocabulary word in the pair that has the highest percentage agreement is the one they use, provided it's better than 80% agreement.

Well, that's what they meant to do. They calculate the percentage agreement for each pair, as I describe, but they reset the "best found so far" inside the loop across your words instead of outside, so in effect they only find the vocabulary word that best matches your last word.

The vocabulary is given at the point in the script where the corpse is listening. For example, if you're talking to the Nazi on We Can See In the Dark (and you are in the dark, because otherwise he freaks out), the words he's listening for are:

"name", "death", "die", "dead", "they", "who", "things", "rats", "rat", "torch", "shriek", "ladder", "light", "flashlight", "family", "parents", "party", "nazi", "expedition", "jungle", "mother", "father", "home", "germany", "sorry", "invasion", "united", "states", "mexico", "friedrich", "behrens", "claude", "joachim", "gunther", and "muller".

If you type "xyz death", he'll tell you how he died. Typing "death xyz" should produce the exact same output, but instead he says he doesn't understand.

The agreement between two words is defined recursively as the length of the longest common substring, plus the agreement between the fragments before that common substring, plus the agreement between the fragments after the common substring.

For example, agreement("expedition", "axpaditiorate") = length("detio") + agreement("expo","axpa") + agreement("n","rate") = 5 + 2 + 0 = 7. The combined lengths of those two words is 10+13=23, so the "percent agreement" is (agreement * 200)/(combined length) = 1400/23 = 60. Since that's not more than 80, the words aren't considered to be a match.

If you'd typed "axpadition", you'd get agreement("expedition","expedition") = length("detion") + agreement ("expe","axpa") = 6 + 2 = 8. The combined length is 20. 8*200/20 = 80. Close, but not quite close enough. It needs to exceed 80. Leave out either of the "a"s, and it would be 8*200/19 = 84, and you'd have a match.

agreement("death","xeath") = 4. 4*200/10 = 80, and he doesn't understand.
agreement("death","dexath") = 5. 5*200/11 = 90, and he'll tell you how he died.

"Words you type" are separated by spaces, using strtok(..., " "). Characters are converted to lowercase (using the tolower() function) before being compared.

I recall having disassembled an earlier version of this code, where he counted the minimum number of of "corrections" that have to be made to transform one word to another. A correction is one of (exchange adjacent letters, add a letter, delete a letter). But that was a long time ago, and I don't recall the details.

[ Post a Reply | Message Index | Read Prev Msg | Read Next Msg ]
Pre-2004 Posts

Replies:

PID for OS XGodot 4/9/13 7:02 a.m.
     Re: PID for OS Xtreellama 4/9/13 7:39 a.m.
     Re: PID for OS XMark Levin 4/9/13 8:28 a.m.
           Re: PID for OS XDestiny 4/9/13 8:49 a.m.
           Re: PID for OS XHopper 4/9/13 10:03 a.m.
                 Re: PID for OS XMark Levin 4/9/13 10:28 a.m.
           Re: PID for OS Xlucas93 4/9/13 3:08 p.m.
           Re: PID for OS XYossarian 4/9/13 3:59 p.m.
           Re: PID for OS Xselbstmord 4/11/13 7:40 a.m.
                 Re: PID for OS XPresident People 4/11/13 3:00 p.m.
                       Re: PID for OS Xukimalefu 4/11/13 11:38 p.m.
                             Re: PID for OS XPerseusSpartacus 4/12/13 12:04 a.m.
     Re: PID for OS XPerseusSpartacus 4/9/13 8:25 p.m.
     Re: PID for OS Xukimalefu 4/10/13 12:17 a.m.
           Re: PID for OS XGodot 4/10/13 12:34 a.m.
                 Re: PID for OS Xukimalefu 4/10/13 12:36 a.m.
                 Re: PID for OS XMark Levin 4/10/13 6:08 a.m.
                       Re: PID for OS XGodot 4/10/13 6:29 a.m.
                             Re: PID for OS XGodot 4/10/13 6:32 a.m.
                       Re: PID for OS XHopper 4/10/13 7:31 a.m.
                             Re: PID for OS XMark Levin 4/10/13 8:20 a.m.
     Re: PID for OS XPerseusSpartacus 4/10/13 9:22 a.m.
           Re: PID for OS XHopper 4/10/13 11:07 a.m.
                 Re: PID for OS XPerseusSpartacus 4/10/13 11:21 a.m.
     Re: PID for OS XMrM12LRV 4/10/13 2:29 p.m.
           SPOILER ALERT! You need to find thisukimalefu 4/11/13 2:08 a.m.
     Re: PID for OS XRon Hunsinger 4/15/13 7:53 p.m.
           Re: PID for OS XMark Levin 4/16/13 6:54 a.m.
                 Re: PID for OS XRon Hunsinger 4/16/13 5:21 p.m.
                       Re: PID for OS XMark Levin 4/16/13 6:00 p.m.
                             Re: PID for OS XRon Hunsinger 4/16/13 7:50 p.m.
                                   Re: PID for OS XMark Levin 4/16/13 8:46 p.m.
                                   Re: PID for OS XHopper 4/17/13 6:11 a.m.
                                         Re: PID for OS XMark Levin 4/17/13 7:16 a.m.
                                               Re: PID for OS XHopper 4/17/13 8:14 a.m.
                                         Re: PID for OS XRon Hunsinger 4/18/13 1:01 a.m.
                                               Re: PID for OS XRon Hunsinger 4/18/13 1:09 a.m.
                                               Re: PID for OS XHopper 4/19/13 7:32 a.m.
                                                     Re: PID for OS XMark Levin 4/19/13 8:28 a.m.
                                                           Re: PID for OS XRon Hunsinger 4/19/13 7:33 p.m.
                                         Re: PID for OS XRon Hunsinger 4/18/13 3:11 a.m.
                 Re: PID for OS XHopper 4/17/13 7:01 a.m.
                       Re: PID for OS XMark Levin 4/17/13 7:12 a.m.
                             Re: PID for OS XHopper 4/17/13 7:50 a.m.
     Re: PID for OS XPerseusSpartacus 4/18/13 8:14 p.m.
           Re: PID for OS Xukimalefu 4/19/13 2:41 a.m.
           Re: PID for OS XRon Hunsinger 4/19/13 4:10 a.m.
                 Re: PID for OS XPerseusSpartacus 4/19/13 6:31 p.m.
                       Re: PID for OS XRon Hunsinger 4/19/13 7:55 p.m.
                             Re: PID for OS Xtreellama 4/20/13 5:11 a.m.
                             Re: PID for OS XPerseusSpartacus 4/20/13 9:38 a.m.
     Re: PID for OS Xbakudd 4/22/13 6:39 a.m.
     PID 1.2 releasedMark Levin 5/6/13 8:49 p.m.
           Re: PID 1.2 releasedGodot 5/6/13 10:47 p.m.
                 Re: PID 1.2 releasedHopper 5/7/13 10:31 a.m.
           Re: PID 1.2 releasedukimalefu 5/7/13 1:45 a.m.

[ Post a Reply | Message Index | Read Prev Msg | Read Next Msg ]
Pre-2004 Posts

 

 

Your Name:
Your E-Mail Address:
Subject:
Message:

If you'd like to include a link to another page with your message,
please provide both the URL address and the title of the page:

Optional Link URL:
Optional Link Title:

If necessary, enter your password below:

Password:
 

 

Problems? Suggestions? Comments? Email maintainer@bungie.org

Marathon's Story Forum is maintained with WebBBS 5.12.