Creating an interactive cryptogram solver (Part II)


Execute Interactive Solver

In Part I of this series we started creating the framework for our solver by creating the Cipher and Aristocrat classes. You are probably thinking “This is a series about interactive solvers but this is all code!” Well, the classes inheriting from Cipher will be the ones doing all the work in our solver. In this part of the series we will finally create the CipherSolver class that will work with the Cipher classes to interactively get the work done. So lets just jump right into the code so we can finally get to our first working solver, the AristocratSolver class!

Disclaimer: I just wanted to give you a heads up before you get into this part of the series. This interactive solver does not use the mouse for interaction. Commands or actions are typed into the program and the program will execute those actions. In the future I may create a new series of articles that describe a fully graphical (uses the mouse) version of the interactive solver. This series of articles is intended to help you create a simple and powerful interactive solver that can be used on any computer that can run Python. This means that it will work on Windows, Mac, Linux and most other major operating systems.

Note: We are going to be adding code to our existing files so I will not post the entire file contents like I did in Part I. I’ll just let you know what has changed and where to put it.

The CipherSolver Class

The CipherSolver class is going to be our base class for all Solvers. It will allow us to easy extend the functionality to fit whatever cipher type we are working on. We are going to need to import a few libraries for this class so lets add the following code to the top of “cipher.py”:

Contents of cipher.py (Place at the top of the file)

import types
import re

This just imports the “types” and “re” libraries so we can use them later in the code. At the bottom of the file we are going to create our CipherSolver class.

Contents of cipher.py (Place at the bottom of the file)

class CipherSolver:
  def __init__(self):
    self.cipher = Cipher()
    self.prompt = ">"
    self.shortcuts = {"d":"display"}

  def display(self):
    print self.cipher.text

  def solve(self):
    while True:
      try:
        raw_line = raw_input(self.prompt + " ")
        line = re.findall(''[^']*'|"[^"]*"|S+', raw_line)
        line = [item[1:-1] if item[0] in ''"' else item for item in line]
        print ""
        cmd = line.pop(0)
        attr = None
        if cmd in self.shortcuts:
          cmd = self.shortcuts[cmd]
        if hasattr(self, cmd):
          attr = getattr(self, cmd)
        elif hasattr(self.cipher, cmd):
          attr = getattr(self.cipher, cmd)
        if attr  None:
          if type(attr) == types.MethodType:
            retvalue = attr(*line)
          else:
            retvalue = attr
          if retvalue != None:
            print retvalue
        else:
          print "Unknown command: ", cmd
        print ""
      except KeyboardInterrupt:
        print "Exiting Solver"
        break
      except Exception, e:
        print "Error: ", e

There is a lot going on here so lets break it into chunks smaller chunks.

  def __init__(self):
    self.cipher = Cipher()
    self.prompt = ">"
    self.shortcuts = {"d":"display"}

  def display(self):
    print self.cipher.text

In the Initialization section we create a variable that will hold an instance of our Cipher class or one of its descendants, like the Aristocrat class. The solver will interact with this object to do all of the encrypting, decrypting, analyzing, etc. The self.shortcuts property contains a dictionary that holds shortcuts or abbreviations for actions that we want to take place. We’ll get to how these are used and why they are important later, but for now know that we can use “d” instead of typing “display” in our solver. Classes based on the CipherSolver class can add to this dictionary to add their own shortcuts. The CipherSolver.display method simply prints out the contents of the Cipher.text. The other classes can override the display method to display in a different way that works better for their specific cipher types.

The CipherSolver.solve method is the most important part of the CipherSolver class because it essentially is the entire interactive solving mechanism. It is a bit complex and lengthy so we are also going to break it into chunks.

Before we get into that, why don’t we go over how the solver will work so you have a basis for what the code is doing. The solver will perform actions that the user enters at its prompt. In the example below, lines that start with “>” are the prompt where the user enters the actions. Once the user presses enter, the solver will read through the action and arguments that the user has typed in and find the appropriate method in the solver class or the cipher class. Lets look at an example using the “sandbox.py”:

Contents of sandbox.py

from cipher import CipherSolver
solver = CipherSolver()
solver.cipher.text = 'This is a test of the emergency broadcast system.'
solver.solve()
python sandbox.py
> display

This is a test of the emergency broadcast system.

> d

This is a test of the emergency broadcast system.

>

When we execute “sandbox.py” we immediately get a “>” prompt to work with. In the example, the user typed “display” which prints out the contents of the Cipher.text. Notice that the user then types “d” and presses enter which gives the same results. This comes from the CipherSolver.shortcuts property that we talked about earlier. It is just an easy way to execute frequently used actions.

Alright, so now back to the CipherSolver.solve method. The solve method is just a giant loop. It continues to prompt the user for more actions until you kill it (Ctrl+C).

  def solve(self):
    while True:
      try:
        raw_line = raw_input(self.prompt + " ")
        line = re.findall(''[^']*'|"[^"]*"|S+', raw_line)
        line = [item[1:-1] if item[0] in ''"' else item for item in line]

Lines 33 takes the users input and runs it through a regular expression to break it apart into a list by splitting it at the spaces. If you want an argument that has spaces, just surround it in quotes. Line 34 just removes any beginning and ending quotes that may have been surrounding the arguments. Lets execute those lines by themselves in python so you can see line for line what it is doing.

>>> import re
>>> raw_line = raw_input("> ")
> command argument "quoted argument" "single quoted argument"
>>> line = re.findall(''[^']*'|"[^"]*"|S+', raw_line)
>>> print line
['command', 'argument', '"quoted argument"', '"single quoted argument"']
>>> line = [item[1:-1] if item[0] in ''"' else item for item in line]
>>> print line
['command', 'argument', 'quoted argument', 'single quoted argument']

So in the end, line will be a list of all the input split into little chunks that we can use. The first item in the list will always be the action or command that will be executed. The rest of the items will be arguments passed into the action methods that are called.

        cmd = line.pop(0)
        attr = None
        if cmd in self.shortcuts:
          cmd = self.shortcuts[cmd]

Here we pop off the first item in the list and set it to the cmd variable. We then check to see if the cmd is in the CipherSolver.shortcuts dictionary. If it is, we use that to lookup which real command will be executed (ie: “d” will change to “display”). Now that we know what command we need to run we go on:

        if hasattr(self, cmd):
          attr = getattr(self, cmd)
        elif hasattr(self.cipher, cmd):
          attr = getattr(self.cipher, cmd)

Python has a great function that will let you know if an object has an attribute or method with a specific name. We use that to see if a method or attribute with name of the entered command exists in the CipherSolver class first. If not found, we check in the attached Cipher class. If it is found in one of these places, then we use the getattr method to get a variable that represents the found method or attribute.

        if attr  None:
          if type(attr) == types.MethodType:
            retvalue = attr(*line)
          else:
            retvalue = attr
          if retvalue != None:
            print retvalue

If the method or attribute was found, then the attr variable will point it. If it is not found, then attr will be None. If attr is a method, we execute that method and pass in the rest of the user inputted contents from earlier. Python allows you to pass in a list to a method as arguments to that method if you place an asterisk in front of a list variable. For example, if we input “command argument1 argument2” then the following method would be called: command(argument1,argument2). If the attr variable is pointing to an attribute then we just display the contents of that attribute. That means if we want to see what is in the Cipher.text property we can just type “text” in the solver.

The rest of the code in “cipher.py” is just error trapping and displaying. We are almost to where we can do some actual solving. Just a little more to go. For now, lets create a new file called “shared.py” that will contain any shared functions that we want available for all our solver classes to use. Right now we’ll only have one function in there but we’ll add more as we progress.

Contents of shared.py

#Breaks the text into lines with a maxium length of maxlen
def breaklines(text, maxlen):
  if maxlen <= 0:
      return text
  textlen = len(text)
  pos = 0
  output = ""
  while pos < textlen:
    chunk = text[pos:pos+maxlen]
    if (pos+maxlen+1 <= textlen) and (text[pos+maxlen+1]  ""):
      tpos = chunk.rfind(" ")
      if tpos  -1:
        chunk = text[pos:pos+tpos]

    output += chunk + "n"
    pos += len(chunk)
    if (pos < textlen) and (text[pos] == " "):
      pos += 1
  return output.strip("n ")

The breaklines functions will break apart text into lines based on the maximum length passed into the function. We’ll use this a lot when displaying text to the screen which may be too long to display normally. Now, we are finally get to create the AristocratSolver class!

The AristocratSolver Class

Just like the we did before with “cipher.py” we will be adding a few import statements to the top of “aristocrat.py”.

Contents of aristocrat.py (Place at the top of the file on line 4)

import shared

Previously, we did not give the Aristocrat class a good way of changing the plaintext and ciphertext keys. Lets add another method to the Aristocrat class at the bottom of the file.

Contents of aristocrat.py (Place at the bottom of the file within the Aristocrat class)

  def set(self, ct, pt = "-"):
    ct = ct.upper()
    pt = pt.lower()
    if pt == "-":
      pt = "-" * len(ct)
    for index in range(len(ct)):
      ctindex = self.ctkey.index(ct[index])
      self.ptkey = self.ptkey[:ctindex] + pt[index] + self.ptkey[ctindex+1:]

This function can take any number of ciphertext characters and sets the plaintext key values to the values passed in. For example: set(“ABC”,”def”) would change the plaintext key for “A” to “d”, “B” to “e”, and “C” to “f”. So the ciphertext key would be “ABC” while the plaintext key would be “def”. This allows us to pass in full words like “GJEG” could be “that”. This will speed up solving a lot because you don’t have to pick individual characters if you know a whole word.

Contents of aristocrat.py (Place at the bottom of the file below the Aristocrat class)

class AristocratSolver(CipherSolver):
  def __init__(self):
    CipherSolver.__init__(self)
    self.cipher = Aristocrat()
    self.maxlinelen = 70
    self.shortcuts['s'] = "set"

  def display(self):
    data = ""
    ct = shared.breaklines(Cipher.encrypt(self.cipher), self.maxlinelen).split("n")
    pt = shared.breaklines(self.cipher.decrypt(), self.maxlinelen).split("n")

    for index in range(len(ct)):
      data += ct[index] + "n"
      data += pt[index] + "nn"
    print data.strip("n")

  def set(self, ct, pt = "-"):
    self.cipher.set(ct,pt)
    self.display()
  def __init__(self):
    CipherSolver.__init__(self)
    self.cipher = Aristocrat()
    self.maxlinelen = 70
    self.shortcuts['s'] = "set"

The initialization function calls the CipherSolver‘s initialization function so we inherit all its properties. We then override the CipherSolver.cipher property with a new Aristocrat instance. We add a new shortcut to the CipherSolver.shortcuts list for the “set” command. So we can just type “s” to speed up solving.

  def display(self):
    data = ""
    ct = shared.breaklines(Cipher.encrypt(self.cipher), self.maxlinelen).split("n")
    pt = shared.breaklines(self.cipher.decrypt(), self.maxlinelen).split("n")

    for index in range(len(ct)):
      data += ct[index] + "n"
      data += pt[index] + "nn"
    print data.strip("n")

We override the CipherSolver.display method with something more useful for Aristocrats. The AristocratSolver.display method will display the ciphertext on one line and the decrypted plaintext below it. It will also break the lines up based on the Aristocrat.maxlinelen property.

  def set(self, ct, pt = "-"):
    self.cipher.set(ct,pt)
    self.display()

The last piece of the AristocratSolver class is the set method. We want to create another set method because when solving we want to display the changes every time we set a new plaintext key value. Finally, lets see this thing in action! Change “sandbox.py” to the following and then execute it:

Contents of sandbox.py

from aristocrat import AristocratSolver
solver = AristocratSolver()
solver.cipher.text = 'GSRH RH Z GVHG LU GSV VNVITVMXB YILZWXZHG HBHGVN.'
solver.solve()
python sandbox.py
> d

GSRH RH Z GVHG LU GSV VNVITVMXB YILZWXZHG HBHGVN.
---- -- - ---- -- --- --------- --------- ------.

> s VNVITVMXB emergency

GSRH RH Z GVHG LU GSV VNVITVMXB YILZWXZHG HBHGVN.
---- -- - -e-- -- --e emergency -r---c--- -y--em.

>

Here we typed “d” to display the current state of the con. Then we typed “s VNVITVMXB emergency”. We could have typed “s V e”, “s N m” etc. but typing it all at once saves us a lot of time. As you can see, we used the shortcuts instead of typing out “display” and “set”. We can add as many shortcuts as we want. Each solver class can have it’s own shortcuts that are tailored to the specific solving needs of that class.

We have not created a fully working interactive cryptogram solver for Aristocrats! We could solve the entire con with this right now!

GSRH RH Z GVHG LU GSV VNVITVMXB YILZWXZHG HBHGVN.
this is a test of the emergency broadcast system.

In Part III we will extend our existing classes by adding more functionality like frequency counting and key displaying to help us in our solving efforts. We’ll also add support for Patristocrats!

Complete Source Code

You can download the complete source code to Part II at: Creating an interactive cryptogram solver (Part II – Source).

Related Posts:

Creating an interactive cryptogram solver (Introduction)
Creating an interactive cryptogram solver (Part I)
Creating an interactive cryptogram solver (Part III)

Advertisements

5 thoughts on “Creating an interactive cryptogram solver (Part II)”

  1. Then we typed “s VNVITVMXB emergency”.

    This is a bit of a disappointment! I don’t really want to type the ciphertext — I’d much rather point with my mouse at a cipher letter and then type the plain letter, à la mode photon’s Patstat. Less work and, for my book, more intuitive.

    1. Anchises,

      I fully understand your disappointment. I originally started writing a fully graphical (uses the mouse) version but it was a lot more complicated and was not easily extended to support other con types because you would have to write a lot of different graphical user based code for each con type. The current method of interactive solving is also platform independent, meaning that it can run on Windows, Linux, Mac and anything else that Python supports (This was important to me because I have a Mac at home, Windows PC at work, and use a Linux netbook as my main solving computer). I have even got it to run on a Pocket PC (with slight modifications). In the future I may look into making it more graphical. My biggest problem with the mouse based interaction is that it seems to slow me down. I can quickly type “s a b” to change all the a’s to b’s faster than I can click a letter then type the plaintext character. That may just be me though. Thanks for reading.

      Code Penguin

  2. I’m testing CipherSolver, but have run into a problem.

    I get the prompt but then receive

    Error: pop from empty list
    >

    I see no discrepancy in the code, and since I’m fairly new to Python, I’m at a loss.

    1. Anapest,

      When you received the prompt, did you type anything in or just press enter? There isn’t a default action if you just press enter without typing (I will have to fix that in the next post) so it tries to process the blank input. Try typing “d” (without the quotes) and then pressing enter. Please, let me know if this is the issue, I will definitely address it in the next post. Sorry about that.

      Code Penguin

  3. Code Penguin,

    Thanks for the explanation — I also have a Mac and a PC, and can see the logic of your approach. And I agree that the mouse vs.keyboard debate is an old one, and at the end of the day one man’s meat is another man’s poison!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s