#!/usr/bin/python # Alberto Maria Segre, Sriram V. Pemmaraju, and Jamie Moore # # Copyright 2013, The University of Iowa. All rights reserved. # Permission is hereby given to use and reproduce this software # for non-profit educational purposes only. # # This is the solution to Project 1, Stage 2. # # Helper Function to expand a string into a list. This will allow the program # to change the contents of a string which are otherwise not mutable. def expand(string): L = [] for ch in string: L.append(ch) return L # Helper function to collapse a list of characters into a single string. This # will allow the program reverse the effects of expand. def collapse(L): returnStr = "" for ch in L: returnStr += ch return returnStr # This function reverses the text. It returns a new string that is a copy of # the input string, but in reverse order. def flip(string): returnStr = "" for ch in string: returnStr = ch + returnStr return returnStr # This function returns a new string tha is a copy of the input string, but # with all characters in the target string removed. def flush (string, target): # Call helper function to make the string mutable by converting it to a list string = expand(string) i = 0 while i < len(string): if string[i] in target: del string[i] # You only need to increment i if nothing was deleted. else: i += 1 # Call helper function to turn the character list back into a string. string = collapse(string) return string # Helper function that checks if a list and string have the same characters def isMatch(listSegment, s1): i = 0 match = True while i < len(listSegment): if listSegment[i] != s1[i]: match = False i += 1 return match # This function returns a new string that is a copy of the input string, but # with every occurance of the substring s1 replaced with the substring s2. def swap(string, s1, s2): i = 0 # Call helper function to make the string mutable by converting it to a list string = expand(string) while i < len(string): if string[i] == s1[0]: listSegment = string[i:i+len(s1)] # Call helper function to determine if there is a word match # starting at i ith s1. if isMatch(listSegment, s1): j = 0 # If it matches delete each letter from the list while j < len(s1): del string[i] j += 1 # Replace the with s2 for ch in s2: string.insert(i, ch) i += 1 else: i += 1 else: i += 1 # Call helper function to turn the character list back into a string. string = collapse(string) return string # This function returns a new string that is a copy of the input string, but # with multiple consecutive ocurrances of character c reduced to a single # charcter c. def trim(string, c): i = 0 # Call expand helper method created above. # This creates a list of characters. string = expand(string) while True: if string[i] == c: while string[i] == string[i+1]: #delete duplicate character del string[i+1] i += 1 if i == len(string): break # Call collapse helper function to reverse the expand method and return # string to a string type. string = collapse(string) return string # The function performs an ASCII shift. # Takes a string and an integer n and shifts each character in # the string by n. The function pays attention to the fact that characters # have to be shifted within the range 32 through 126. def shift(string, n): newstring = "" i = 0 while i < len(string): newstring = newstring + chr(((ord(string[i])+n-32)%95)+32) i = i+1 #print newstring return newstring # Extracts a number starting at location j in the given string. # Returns the number as a string. This function is useful in parsing # the instruction. def getNumber(string, j): number = "" while string[j] >= "0" and string[j] <= "9": number = number + string[j] j = j + 1 # Watch out for the end of string if j == len(string): break return number # Extracts a string of characters starting at location j in the given string. # The value n represents the number of characters to get from the string. # Returns the characters as a string. This function is useful in parsing the # instructions d and s. def getCharacters(string, j, n): characters = "" i = 0 while i < n: characters = characters + string[j+i] i += 1 return characters # Checks if a given line contains only blanks. If so returns True; otherwise # returns False. def isBlank(string): i = 0 while i < len(string): if string[i] != " ": return False i = i + 1 return True # Parses the instruction character by character and returns a # list of integers that correspond to the sequence of shifts to be # performed def parse(instruction): instList = [] # Parse the instruction character-by-character looking for instructions i = 0 while i < len(instruction): # shift up found if instruction[i] == "+": n = "+" + getNumber(instruction, i+1) instList.append(n) i = i + len(n) # shift down found elif instruction[i] == "-": n = "-" + getNumber(instruction, i+1) instList.append(n) i = i + len(n) # flip (aka reverse) command found elif instruction[i] == "r": instList.append("r") i += 1 # flush command found elif instruction[i] == "d": #check if the character after d is a number or a character nextChar = instruction[i+1] if nextChar >= "0" and nextChar <= "9": n = getNumber(instruction, i+1) chars = getCharacters(instruction, i+len(n)+2, int(n)) instList.append("d"+chars) i = i + len(chars) + len(n) + 2 else: instList.append("d"+nextChar) i = i + 2 # swap command found elif instruction[i] == "s": sList = [] nextChar = instruction[i+1] if nextChar >= "0" and nextChar <= "9": # Get first number and character set n = getNumber(instruction, i+1) chars = getCharacters(instruction, i+len(n)+2, int(n)) #print chars i = i + len(chars) + len(n) + 2 sList = ["s", chars] # Get second number and character set n = getNumber(instruction, i+1) chars = getCharacters(instruction, i+len(n)+2, int(n)) i = i + len(chars) + len(n) + 2 sList.append(chars) instList.append(sList) else: # The is for the single character version: s sList = ["s", instruction[i+1], instruction[i+2]] instList.append(sList) i = i + 3 # trim command found elif instruction[i] == "x": instList.append("x"+instruction[i+1]) i += 2 return instList # The function that "drives" the entire decryption process def driver(filename): f = open(filename, "r") # repeat while there are more instructions instructions = f.readline()[:-1] while instructions: # parse the current line of instruction print instructions instList = parse(instructions) # repeat while there are more lines to decrypt ciphertext = f.readline()[:-1].strip() while ciphertext: # Apply each instruction to the ciphertext i = 0 while i < len(instList): # The first character of each command in the instList represents # the type of instruction it is. This section determines that # and calls the proper function. # + or - : shift() # r : flip() # d : flush() # s : swap() # x : trim() if (instList[i][0] == "+") or (instList[i][0] == "-"): ciphertext = shift(ciphertext, int(instList[i])) elif instList[i][0] == "r": ciphertext = flip(ciphertext) elif instList[i][0] == "d": target = instList[i][1:] ciphertext = flush(ciphertext, target) elif instList[i][0] == "s": # The command for 's' is actually the first command that # isn't stored as a string. It is stored as a sub-list. # This design decision ensured that 's' only had to be # parsed once. Still... the first element of that sublist # is a string "s". s1 = instList[i][1] s2 = instList[i][2] ciphertext = swap(ciphertext, s1, s2) elif instList[i][0] == "x": c = instList[i][1] ciphertext = trim(ciphertext, c) i = i+1 print ciphertext # Read the next line of the ciphertext ciphertext = f.readline()[:-1] # If the line contains only blanks, then it is time to # break and look for the next instruction line if isBlank(ciphertext): break # Read the next instruction line instructions = f.readline()[:-1] print "" f.close()