DISCUSSION CONTAINS SPOILERS

On Sat, 2005-01-01 at 03:27 +0900, Ruby Quiz wrote:
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.grayproductions.net/ruby_quiz/

According to the site: "The only goal we try to follow with the quizzes
is to keep them pretty short (30 minutes to an hour to solve for the
average coder). This is obviously vague, so use you're best judgment.
We're interested in fun little diversions, not a massive time sink."

> Coding a brute force solution is relatively trivial, 

Speak for yourself! :)

Having never written a brute force decryption algorithm I thought I'd
better make sure it was as trivial as everyone says (including myself,
knowing that essentially all it needs to do is iterate over the entirety
of the possible keyspace).

This actually took me a few hours because while in theory I knew what
was required, getting from the vague notion of "test all 25! keys in the
key space" to actual working code was another matter. But I'm glad I
took the time because I am now a lot more familiar with Ruby and the
problem space.

> but there are many opportunities for the clever optimizer.

Yes, there are. Thank the gods, because the brute force solution is
miserably slow on a standard home PC. I got bored watching and never did
make certain that my brute force algorithm actually works on the
cryptograms in the Quiz (I did make sure it could solve shorter grams
with much smaller dict files).

> 	-----
> 	crypto3.txt
> 	-----

This particular cipher text kept two very capable humans busy for over
30 minutes with not even a hint of a solution in sight. My optimized
parser (which actually took about an hour or two to write) worked on it
for three or four hours itself and only spat out gibberish.

-----

I want to thank you for this Quiz, though. Not only have I been reading
Neal Stephenson's excellent book "Cryptonomicon", I'd just been
explaining to my daughter last weekend how encryption was different from
encoding, how encryption worked, and possible techniques to foil
mechanical solvers such as this Quiz will generate.

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. :)

I will post my solution(s) to this Quiz later today or tomorrow. My
optimized method involves using patterns from the cipher text and the
dictionary to create sets of maps for each token and then using Set#& to
join them together when possible to make a set of maps covering the
entire character set of the cipher text. The chief speed differences
seem to be related to the order in which to compare the tokens against
each other.

And I have yet to try something like:

  eval "set[0] & set[1] & set[2] ... & set[n]"

Which would combine them all at once. Hmmmm. Back to emacs...

So... is anyone else giving this a go? What strategies are you using?

 - Michael C. Libby, www.andsoforth.com