Michael C. Libby
1/4/2005 1:43:00 AM
[apologies for the long post here]
Script attached. Text contains spoilers of the worst sort.
On Tue, 2005-01-04 at 01:36 +0900, Glenn Parker wrote:
> My apologies, I was not aware of the suggested time constraint.
No need to apologize. I was free to stop any time. :)
> Nobody spent more than a week's worth of spare time on
> it, so it seemed to be within bounds for a weekly quiz. I also think
> the recent tic-tac-toe problem was of comparable difficulty.
Actually, if I weren't incompetent, it would have taken me a lot less
time. I'm just amused that I had an easier time with the optimized
solver than the brute force solver. Brute force is supposed to be
simple, right?
> > Now , thanks to crypto3.txt, I will add to the list of ways to foil
> > solvers: write messages that are nearly unsolvable in the first
> > place. :)
>
> Again, my apologies if that puzzle proved too difficult for some. I
> assure that there is at least one solution. I created these puzzles
> myself to avoid copyright issues, and it's hard to evaluate their
> difficulty. I do know that lots of medium-length words in which no
> letters are re-used makes it harder, and crypto3.txt is a fine example
> of that.
I'm just curious about how fast your Ruby solver was able to give a
useful answer on that one. And on what kind of hardware.
> Sometimes, looking at the problem from a more practical standpoint, a
> complete computer-generated solution is overkill. If you scan through
> your algorithm's partial results, you may get enough insight to finish
> the solution on your own. This is especially true when your algorithm
> is stumbling on a proper noun, e.g. an author's name, that is not in
> your dictionary.
No doubt. Certainly my program did a fairly poor job on all the puzzles,
but in the case of the first two the right answer was obvious to the
human reading it.
Anyway...
My script uses patterns to build test maps for each token in the cipher
text. So if it sees uhixl in the cipher text the pattern is just abcde,
if it sees owwdcd the pattern is abbcdc, etc.
First it reads in the dictionary and stores all of the words in a hash
keyed on word pattern.
Next it reads in the cipher text, figures out the pattern for each
token, gets all the words from the dictionary that match the pattern,
and sorts the list of tokens according to token length (on the
assumption that longer words are more likely to have unique patterns).
Third it sets up an array in which to hold potentially valid maps (all
the maps are held as sets like (ab, cd, ef) which would map the token
ace to bdf) and stocks it with the maps for the first token.
Then it loops over each remaining token, doing a comparison of the
possible maps for that token with the existing set of potentially valid
maps.
For each comparison it figures out how many cipher letters the two sets
of sets have in common. If they have no common letters it performs a
cartesian product of the two sets (which is dangerous when the two sets
are large!), if they have common letters it takes the union of the two
sets where the maps agree on what a mapping is.
Examples: (ab, cd) & (ab, ce) = () because the sets don't agree on
mapping for c. (ab, cd) & (cd, ef) = (ab, cd, ef) because the sets agree
on how to map the characters they have in common.
My script is not very polished, requires the dictionary to be present in
the same directory with the name "dict.txt" and accepts the cryptogram
files as an argument: so `ruby decrypt.rb crypto1.txt` does the magic.
My program output is still somewhat rudimentary, but it gives this for
the first gram, unfortunately it gets excited about the middle name
which it has wrong, but which takes away 'u' for use in its correct
mapping:
denims is one per bent inspiration ninety nine per bent perspiration
t?o?as aqua e?ison
denims is one per cent inspiration ninety nine per cent perspiration
t?o?as aqua e?ison
denims is one per gent inspiration ninety nine per gent perspiration
t?o?as aqua e?ison
denims is one per lent inspiration ninety nine per lent perspiration
t?o?as aqua e?ison
denims is one per vent inspiration ninety nine per vent perspiration
t?o?as aqua e?ison
denims is one per went inspiration ninety nine per went perspiration
t?o?as aqua e?ison
The second gram it got 100%:
the difference between the almost right word and the right word is the difference between the lightning bug and the lightning mark twain
The third gram results in:
migf afwc gf ruffs lsc coisr mantra i elsr is go valise wi?f maf efl
cowls mangle
migf afwh gf ruffs lsh hoisr mantra i elsr is go valise wi?f maf efl
howls mangle
migf afwj gf ruffs lsj joisr mantra i elsr is go valise wi?f maf efl
jowls mangle
migf afwy gf ruffs lsy yoisr mantra i elsr is go valise wi?f maf efl
yowls mangle
Which is perhaps a quote from a Joyce novel. ;)
Glenn, thanks for the challenge. James, thanks for Ruby Quiz. First time
I've tried it but the past weeks have been fun to watch.
-Michael C. Libby, www.andsoforth.com