Home > python > Python Challenge #1

Python Challenge #1

This exercise is from http://www.pythonchallenge.com.

Challenge

We have the following encoded text:

g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj.

And the following hint to decode it: “K -> M, O -> Q, E -> G”.

First try to solve it yourself. My solution is below.


 

Solution #1

The hint suggests that we should shift right every character by two positions, so ‘A’ becomes ‘C’, ‘B’ becomes ‘D’, etc. However, if we look at the encoded text, we can see that some characters shouldn’t be moved (‘.‘, ‘(‘, and ‘)‘). That is, we only need to deal with characters from the ranges ‘a’..’z’ and ‘A’..’Z’.

The difficulty is with the last two characters, ‘Y‘ and ‘Z‘ (and the lower-case equivalents). ‘Y‘ should become ‘A‘, and ‘Z‘ must become ‘B‘, that is the range must be circular. Imagine the numbers between 0 and 25. The shifting should work the following way: 0 => 2, 1 => 3, ..., 24 => 0, 25 => 1. That is: (N+2) mod 26, where N is the current number and 26 is the number of elements. For instance, if N=24, then (24+2) mod 26 is 0. So using the modulo we can get a circular list.

In the ASCII table, the character code of ‘A‘ is 65, ‘B‘ is 66, …, ‘Z‘ is 90. The idea is the following: if we meet an upper-case letter, subtract 65 from its ASCII code. This way the letter is projected to the range 0..25. Do as explained in the previous paragraph, then add 65 to put it back in the original 65..90 range. Lower-case letters are in the range 97..122, so in these cases you subtract 97.

There are two important Python functions that we need here: ord() and chr(). Examples: ord('A') returns 65, i.e. the ASCII code of the specified letter. chr(65) returns ‘A‘, i.e. the letter with the specified ASCII value.

Now let’s see the script:

#!/usr/bin/env python

text = """
g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw
rfgq rcvr gq qm jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj.
"""

letters = ord('Z') - ord('A') + 1   # 26, i.e. the number of alphabetical letters
offset = 2                          # according to the decoding hint

result = []                 # a "stringbuffer"
for c in text:
    if c.isalpha():                 # if it's an alphabetical char.
        if c.isupper():             # if uppercase
            backtozero = ord('A')
        else:                       # if lowercase
            backtozero = ord('a')

        shifted = chr(((( ord(c) - backtozero ) + offset) % letters) + backtozero)
        result.append(shifted)
    else:
        result.append(c)    # if not an alphabetical char., just add it

print ''.join(result)

Of course, this problem could be solved in lots of different ways. Here is another solution using a translation table:

Solution #2

#!/usr/bin/env python

text = """
g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr amknsrcpq ypc dmp. bmgle gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw
rfgq rcvr gq qm jmle. sqgle qrpgle.kyicrpylq() gq pcamkkclbcb. lmu ynnjw ml rfc spj.
"""

table1 = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
table2 = list('cdefghijklmnopqrstuvwxyzabCDEFGHIJKLMNOPQRSTUVWXYZAB')

result = []                 # a "stringbuffer"
for c in text:
    try:
        pos = table1.index(c)    # raises ValueError if the value is not present
        result.append(table2[pos])
    except ValueError:
        result.append(c)

print ''.join(result)

Here table2 is the translation table of table1, i.e. if you take an element from table1 at position i, you can decode it by taking the ith element from table2. Using the list() function they are converted from string to list. We do it because we want to use the index() function later.

Then we iterate through the characters of the encoded text. We take a letter c, look up its position in table1, then take its decoded version from table2. If the character is not present in table1 then we get an exception. In this case we have nothing to do, just add c to the result.

Notes

This kind of encryption is also called as Caesar cipher. The method is named after Julius Caesar, who used it to communicate with his generals.

About these ads
Categories: python Tags: , , , ,
  1. Dave
    November 8, 2012 at 16:12 | #1

    Interesting approaches, how about this:

    def recode(cypher):
        intab = ''
        for char in map(chr, range(121, 123)):
            intab += char
        for char in map(chr, range(97, 121)):
            intab += char
    
        outtab = ''
        for char in map(chr, range(97, 123)):
            outtab += char
    
        print(cypher.translate(dict((ord(x), y) for (x, y) in zip(intab, outtab))))
    
    • November 8, 2012 at 16:23 | #2

      For intab and outtab I would use a stringbuffer. Strings are immutable in Python thus you make a new string in each iteration.

      sb = []
      loop:
          sb.append(something)
      #
      result = ''.join(sb)
      
  1. No trackbacks yet.
You must be logged in to post a comment.
Follow

Get every new post delivered to your Inbox.

Join 63 other followers

%d bloggers like this: