davidbau.com

A Coding Puzzle

If you are in the mood for a programming puzzle, read on.

Mirror Cipher

This weekend, Anthony and I played with ciphers in python.

The python interactive terminal is a good place to play with one-line programs. We just ran "python" without any arguments, and then Anthony and I took turns running commands. If you have python, you can follow along.

Here is a simple substitution cipher we made:

alph  = 'abcdefghijklmnopqrstuvwxyz'
ralph = 'zyxwvutsrqponmlkjihgfedcba'
def code(word): return ''.join([ralph[alph.find(letter)] for letter in word])

This cipher replaces every letter with its opposite: it swaps a with z; b with y; and so on. So you get:

>>> code('monster')
'nlmhgvi'
>>> code ('nlmhgvi')
'monster'

Because each letter is replaced by its mirror opposite, applying the same encryption on the ciphertext gives you the plaintext back out. Anthony had great fun encoding different secret messages.

An Unbreakable Code

After we showed our secret code program to Mom, she understood the cipher right away. And she proved she was able to decode the ciphertext, without any machine assistance. That Mom - she is a smart one.

The first rule of secret codes is that if Mom can read a code, it is not hard enough.

So Anthony got an idea for making the cipher harder. Here is what he did:

>>> ralph = 'qazwsxedcrfvtgbyhnujmikolp'
>>> code('monster')
'tbgujsn'

Now, instead of replacing every letter with its opposite, he replaced every letter with a "random" letter. (Can you see how he picked his random letters?)

But then when he tried to decipher his code, the old trick of re-encoding the ciphertext did not work.

>>> code('tbgujsn')
'jaemrug'

What to do now?

I wanted Anthony to learn how to reverse the roles of "ralph" and "alph" to write a secret decoder function. That would have been educational!

But he had other plans.

Trying Harder

Instead of decoding in a rational way, he decided to try repeating his encryption of 'jaemrug' again to see if anything better would come out the second time. All he got was another jumble of letters 'rqstnme'.

But he still didn't give up. He wanted to try harder. He did it again and again several times:

>>> code('monster')
'tbgujsn'
>>> code('tbgujsn')
'jaemrug'
>>> code('jaemrug')
'rqstnme'
>>> code('rqstnme')
'nhujgts'
>>> code('nhujgts')
'gdmreju'
>>> code('gdmreju')
'ewtnsrm'
>>> code('ewtnsrm')
'skjgunt'
>>> code('skjgunt')
'ufremgj'
>>> code('ufremgj')
'mxnster'

Suddenly he struck gold.

"Dad! Look at that, 'mxnster' is almost right!" His crazy idea worked.

Things were not perfect, but surely this almost-monster result could be no mere coincidence.

Encircling the Solution

Anthony had discovered something neat. To save us from manually encrypting things over and over again, I wrote this short program for him:

def reps(word):
   c, cipher = 1, code(word)
   while cipher != word:
     c, cipher = c + 1, code(cipher)
     print cipher
   print c

When we typed in reps('monster'), the program reencrypted the word 90 times, and then came back to exactly the same word 'monster'. No mistakes this time.

Anthony was so excited he ran to tell his his mom about his new discovery. Mom was impressed. "That shouldn't happen," she said.

But, of course, it does happen.

The first rule of mathematics is that if it surprises Mom, it must be good math.

Why did encrypting the word 90 times return to the same text? Mom imagined that even though it was believable you might return to the original text by encrypting over and over, it should have taken a very long time. 90 repetitions did not seem very long. Was it because Anthony had accidentally chosen a special key? It seemed that if Anthony's "ralph" key had been different, he might have taken a different number of encryptions to return to the plaintext.

The Puzzle

So here is the puzzle.

• Try to find a "ralph" key with the most possible reps before returning plaintext.
• How many repetitions will it take?
• Was Anthony's key unusual?
• Is there a magic number of reps that decodes anything, for any "ralph"?

Posted by David at September 25, 2006 10:17 AM