basicCryptanalysis.py

#!/usr/bin/env python

'''
  Basic Cryptanalysis
  
    url: https://www.hackerrank.com/challenges/basic-cryptanalysis

    input: space separated input cipher
    output: space separated decoded message

    resource: dictionary.lst dictionary of valid words

  Really basic recursive solution starting from longest word, could
  do a bunch of things like substring analysis and regex wildcard
  matching but this was easy enough.

'''

import copy

def is_valid(dictionary, word, substitutions):

  original_substitutions = copy.deepcopy(substitutions)
  valid = []
  for possible in dictionary[len(word)]:

    success = True
    for orig, sub in zip(word, possible):

      if (orig in substitutions):
        if (substitutions[orig.lower()] != sub.lower()):
          success = False
          break

      substitutions[orig.lower()] = sub.lower()
      substitutions[orig.upper()] = sub.upper()

    if success:
      valid.append(copy.deepcopy(substitutions))

    substitutions = copy.deepcopy(original_substitutions)

  return valid

def recurse_valid(dictionary, words, starts):

  if not words:
    return starts

  results = []
  for start in starts: 
    new_starts = is_valid(dictionary, words[0], start)
    if new_starts:
      results.extend(new_starts)

  return recurse_valid(dictionary, words[1:], results)

def solve(dictionary, cipher_words, substitutions):

  if not cipher_words:
    return substitutions

  longest = max(cipher_words)
  level_words = cipher_words.pop(longest)

  # use the start valid substitutions
  starts = is_valid(dictionary, level_words[0], substitutions)
  result = recurse_valid(dictionary, level_words[1:], starts)

  for v, i in zip(result, xrange(len(result))):
    res = solve(dictionary, cipher_words, v)
    if solve(dictionary, cipher_words, v):
      return res

  return []


if __name__ == '__main__':

  # load the dictionary file
  dictionary = {}
  with open('dictionary.lst') as f:
      
    # process each word and store by length
    for line in f:
  
      # get the length of the word
      word = line.strip()
      length = len(word)

      # add the word to the dictionary by length
      if length not in dictionary:
        dictionary[length] = []
      dictionary[length].append(word)

  # read the input cipher and then store by length
  cipher = raw_input()
  cipher_words = {}
  for cipher_word in cipher.split():
    
    # store the words by length (code could be reused from above)
    length = len(cipher_word)

    # add the word to dictionary by length
    if length not in cipher_words:
      cipher_words[length] = []
    cipher_words[length].append(cipher_word)

  # dictionary of substitutions
  substitutions = {}

  # recursively solve from longest to shortest words
  substitutions = solve(dictionary, cipher_words, substitutions)
  substitutions[' '] = ' '

  # print out the replaced string
  plaintext = ''.join([substitutions[c] for c in cipher])
  print plaintext