MIT 6.0001 PS4：一个使用 Python Class 的简单加解密程序

本文是我对 MIT 6.0001 课程（Introduction to Computer Science and Programming in Python）配套作业 Problem Set 4 的解答。仅供参考。

完整代码：https://github.com/Jed-Z/mit-6.0001-and-6.0002/tree/master/6.0001/6.0001_PS4

本文地址：https://www.jeddd.com/article/mit-python-ps4-class.html

问题描述

详细的要求见原题，从 MIT OCW 下载原题：Problem Set 4 (ZIP) (This file contains: 1 .pdf file, 3 .py files and 2 .txt files.)

求解思路

Part A: Permutations of a string

Part A 主要练习递归。

排列函数

要求用递归的方式求字符串的全排列。递归的本质即是把问题分解为多个相同的、但规模更小的问题，并指定一个停止条件。

在全排列这一问题中，递归步骤是：将字符串的首个字符拿出来，然后将它插入到余下字符的每一排列的所有位置。停止条件是字符串只剩下一个字符。在get_permutations函数中，使用 if-else 语句来区分递归步骤和停止条件。

如何用 Python 实现“将字符插入到字符串”这一功能？我们知道，字符串是不可变类型，因此不能直接改变为字符串的某个字符。可行的方法是，使用切片将一个字符串从希望插入字符的位置切成两半，然后使用+运算符将左半边、新字符、右半边拼接起来，从而实现“插入字符”这一功能。

def get_permutations(sequence):
    if len(sequence) <= 1:  # 停止条件
        return [sequence]
    else:                   # 递归步骤
        permus = []         # 对sequence排列的结果
        for smaller in get_permutations(sequence[1:]):
            for i in range(len(smaller) + 1):
                permus.append(smaller[:i] + sequence[0] + smaller[i:])  #将首字母插入每个位置
        permus.sort()       # 字典序排序
        return permus

在上述代码中，倒数第二行的sort()是为了使输出结果与题目所给样例相同，即使去掉也不会影响排列结果的正确性。

主程序

主程序用来测试get_permutations函数。虽然题目建议测试长度不超过 3 的字符串，但为了使测试更为有意义，我分别选取了长度为 2、3、4 的三个字符串作为测试样例。分别为：

example1 = '12'
example2 = 'abc'
example3 = 'bust'

运行程序，结果如下，均符合预期：

Input: 12
Expected Output: ['12', '21']
Actual Output: ['12', '21']
----------------
Input: abc
Expected Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Actual Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
----------------
Input: bust
Expected Output: ['bstu', 'bsut', 'btsu', 'btus', 'bust', 'buts', 'sbtu', 'sbut', 'stbu', 'stub', 'subt', 'sutb', 'tbsu', 'tbus', 'tsbu', 'tsub', 'tubs', 'tusb', 'ubst', 'ubts', 'usbt', 'ustb', 'utbs', 'utsb']
Actual Output: ['bstu', 'bsut', 'btsu', 'btus', 'bust', 'buts', 'sbtu', 'sbut', 'stbu', 'stub', 'subt', 'sutb', 'tbsu', 'tbus', 'tsbu', 'tsub', 'tubs', 'tusb', 'ubst', 'ubts', 'usbt', 'ustb', 'utbs', 'utsb']

Part B: Cipher Like Caesar

Part B 主要练习类、对象、继承。

Part 1: Message

构造函数

Message 类有两个成员变量，其构造函数如下：

def __init__(self, text):
    self.message_text = text
    self.valid_words = load_words(WORDLIST_FILENAME)

getter

Message 有两个 getter 方法，如下：

def get_message_text(self):
    return self.message_text

def get_valid_words(self):
    return self.valid_words.copy()

注意这两个 getter 的不同之处——get_message_text返回的是字符串，由于字符串本身是不可变类型，因此可以直接返回成员即可；get_valid_words返回的是列表，而列表是可变类型，为了避免在类外意外地修改对象中的成员，必须要返回列表的一份拷贝，所以要显式地使用copy()。在本文档末尾的“总结”处还有更详细的说明。

build_shift_dict

build_shift_dict方法用于根据参数 shift 构造一个由原文到密文的凯撒密码字符映射，大小写字母需要分别处理，该方法返回一个有 52 项的字典。

首先，把 shift 限制在 [0, 26) 内，我采用了取模的方法，使得此方法能够接受不在此范围内的参数而不会出错。注意 Python 中对负数取模的结果符号由除数（而不是被除数）决定，这与 C/C++ 等其他语言不同。

shift %= 26  # shift的取值范围为[0, 26)

使用切片功能构造经 shift 偏移后的字母表，大小写分别处理。

lower_before = string.ascii_lowercase
upper_before = string.ascii_uppercase
lower_after = lower_before[shift:] + lower_before[:shift]
upper_after = upper_before[shift:] + upper_before[:shift]

使用zip函数将原字母表和偏移后的字母表打包成元组，再转换为字符串。大小写分别处理。

lower_dict = dict(zip(lower_before, lower_after))
upper_dict = dict(zip(upper_before, upper_after))

最后合并两个字典并返回。

return dict(**lower_dict, **upper_dict)

apply_shift

apply_shift方法用于将 shift 作用于成员 self.message_text。由于上面build_shift_dict中对 shift 取模了，因此apply_shift中就无需限制 shift 的范围。

apply_shift的细节是，对于字符串中那些特殊字符（大小写字母以外的字符，包括空格、 标点等）不做任何处理，保留原样。使用字典对象的get方法可以实现这一点。如对于一个字符ch，如果shift_dict中存在，则返回shift_dict[ch]；如果不存在，则返回ch本身：shift_dict.get(ch, ch)。再配合列表解析即可构造出一个映射后字符的列表。最后使用空字符串的join方法将其拼接成一个字符串，并返回它。

两行代码搞定：

def apply_shift(self, shift):
    shift_dict = self.build_shift_dict(shift)
    return ''.join([shift_dict.get(ch, ch) for ch in self.get_message_text()])

Part 2: PlaintextMessage

PlaintextMessage 是 Message 的子类。

构造函数

可以显式调用父类的构造函数。根据 Style Guide #7 的规则，编写 PlaintextMessage 的构造函数：

def __init__(self, text, shift):
    Message.__init__(self, text)
    self.shift = shift % 26
    self.encryption_dict = self.build_shift_dict(self.shift)
    self.message_text_encrypted = self.apply_shift(self.shift)

getter

PlaintextMessage 的五个成员变量中有三个是子类新增的，因此需要新定义三个 getter 方法。getter 的原则与前述相同——不可变对象直接返回，可变对象返回一份拷贝。

def get_shift(self):
    return self.shift

def get_encryption_dict(self):
    return self.encryption_dict.copy()

def get_message_text_encrypted(self):
    return self.message_text_encrypted

change_shift

修改 PlaintextMessage 的三个新成员。与构造函数中的代码类似，调用父类的方法：

def change_shift(self, shift):
    self.shift = shift % 26
    self.encryption_dict = self.build_shift_dict(self.shift)
    self.message_text = self.apply_shift(self.shift)

Part 3: CiphertextMessage

构造函数

CiphertextMessage 没有新的成员变量，只需调用父类的构造函数。

def __init__(self, text):
    Message.__init__(self, text)

decrypt_message

decrypt_message方法用蛮力方法尝试 26 种偏移可能（包括 0），找出某一个偏移 shift，使得解码出的原文拥有最多的真实单词。真实单词在文件 words.txt 中，可以用题目已经为我们提供的is_word函数来判断一个字符串是不是真实单词。

由凯撒密码的特点可知，解密用的偏移与加密偏移 shift 之和恰好为 26。

def decrypt_message(self):
    max_count = 0                            # 目前最大有效单词数
    max_decrypted = self.get_message_text()  # 目前有效单词数最多的解密
    max_shift = 0                            # 目前有效单词数最多的偏移
    for shift in range(1, 26):
        count = 0  # 有效单词数
        decrypted = self.apply_shift(26 - shift)
        for word in decrypted.split():
            if is_word(self.get_valid_words(), word):
                count += 1
        if count > max_count:
            max_count = count
            max_decrypted = decrypted
            max_shift = shift

    return max_shift, max_decrypted

Part 4: Testing

在if __name__ == '__main__':后进行测试。

编写多个样例，分别测试 PlaintextMessage 和 CiphertextMessage。

#Example test case (PlaintextMessage)
plaintext = PlaintextMessage('hello', 2)
print('Expected Output: jgnnq')
print('Actual Output:', plaintext.get_message_text_encrypted())
print('-' * 16)

#Example test case (CiphertextMessage)
ciphertext = CiphertextMessage('jgnnq')
print('Expected Output:', (24, 'hello'))
print('Actual Output:', ciphertext.decrypt_message())
print('-' * 16)

# 我的测试，注意shift在[0, 26)之外
plaintext2 = PlaintextMessage('Hello, World!', 30)
print('Expected Output: Lipps, Asvph!')
print('Actual Output:', plaintext2.get_message_text_encrypted())
print('-' * 16)

ciphertext2 = CiphertextMessage('Lipps, Asvph!')
print('Expected Output:', (22, 'Hello, World!'))
print('Actual Output:', ciphertext2.decrypt_message())
print('-' * 16)

以上测试的结果：

Loading word list from file...
   55901 words loaded.
Expected Output: jgnnq
Actual Output: jgnnq
----------------
Loading word list from file...
   55901 words loaded.
Expected Output: (24, 'hello')
Actual Output: (24, 'hello')
----------------
Loading word list from file...
   55901 words loaded.
Expected Output: Lipps, Asvph!
Actual Output: Lipps, Asvph!
----------------
Loading word list from file...
   55901 words loaded.
Expected Output: (22, 'hello')
Actual Output: (22, 'Hello, World!')
----------------

尝试解密 story：

# best shift value and unencrypted story
cipher_story = CiphertextMessage(get_story_string())
print(cipher_story.decrypt_message())

结果：

Loading word list from file...
   55901 words loaded.
(12, 'Jack Florey is a mythical character created on the spur of a moment to help cover an insufficiently planned hack. He has been registered for classes at MIT twice before, but has reportedly never passed aclass. It has been the tradition of the residents of East Campus to become Jack Florey for a few nights each year to educate incoming students in the ways, means, and
ethics of hacking.')

Part C: Substitution Cipher

Part 1: SubMessage

构造函数

SubMessage 类有两个成员变量，其构造函数如下：

def __init__(self, text):
    self.message_text = text
    self.valid_words = load_words(WORDLIST_FILENAME)

getter

getter 的原则与前述相同——不可变对象直接返回，可变对象返回一份拷贝。

def get_message_text(self):
    return self.message_text

def get_valid_words(self):
    return self.valid_words.copy()

build_transpose_dict

需要构造一个含有 52 项的字典，它有四部分组成：

1. 元音小写字母，以 'aeiou' 中的每个字符为键，以参数vowels_permutation的每个字符的小写为值建立字典vowels_lower_dict；
2. 元音大写字母，以 'AEIOU' 中的每个字符为键，以参数vowels_permutation的每个字符的大写为值建立字典vowels_upper_dict；
3. 辅音小写字母，由小写辅音字母构成的字典consonants_lower_dict，键和值相同；
4. 辅音大写字母，由大写辅音字母构成的字典consonants_upper_dict，键和值相同。

最后将以上四部分合并成一个字典并返回。

def build_transpose_dict(self, vowels_permutation):
    vowels_lower_dict = dict(zip(VOWELS_LOWER, vowels_permutation.lower()))
    vowels_upper_dict = dict(zip(VOWELS_UPPER, vowels_permutation.upper()))
    consonants_lower_dict = dict(zip(CONSONANTS_LOWER, CONSONANTS_LOWER))
    consonants_upper_dict = dict(zip(CONSONANTS_UPPER, CONSONANTS_UPPER))
    return dict(**vowels_lower_dict, **vowels_upper_dict, **consonants_lower_dict, **consonants_upper_dict)

apply_transpose

把build_transpose_dict的字典作用于self.message_text上。和 Part B 中的apply_shift函数类似，使用列表解析和字符串的join来完成。

def apply_transpose(self, transpose_dict):
    return ''.join([transpose_dict.get(ch, ch) for ch in self.get_message_text()])

Part 2: EncryptedSubMessage

构造函数

EncryptedSubMessage 没有新的成员变量，只需调用父类的构造函数。

def __init__(self, text):
    SubMessage.__init__(self, text)

decrypt_message

尝试 aeiou的所有排列，将其作为build_transpose_dict的vowels_permutation参数构建解密映射。尝试所有的映射，从中找出使得解密后的字符串含有真实单词数量最多的那个，然后返回解密后的字符串。

def decrypt_message(self):
    max_count = 0                            # 目前最大有效单词数
    max_decrypted = self.get_message_text()  # 目前有效单词数最多的解密
    vowels_permus = get_permutations(VOWELS_LOWER)
    for permu in vowels_permus:
        transpose_dict = self.build_transpose_dict(permu)
        count = 0
        decrypted = self.apply_transpose(transpose_dict)
        for word in decrypted.split():
            if is_word(self.get_valid_words(), word):
                count += 1
        if count > max_count:
            max_count = count
            max_decrypted = decrypted

    return max_decrypted

Part 3: Testing

编写两个测试：

if __name__ == '__main__':

    # Example test case
    message = SubMessage("Hello World!")
    permutation = "eaiuo"
    enc_dict = message.build_transpose_dict(permutation)
    print("Original message:", message.get_message_text(), "Permutation:", permutation)
    print("Expected encryption:", "Hallu Wurld!")
    print("Actual encryption:", message.apply_transpose(enc_dict))
    enc_message = EncryptedSubMessage(message.apply_transpose(enc_dict))
    print("Decrypted message:", enc_message.decrypt_message())
    print('-' * 16)

    # 我的测试
    message2 = SubMessage(
        "Jack Florey is a mythical character created on the spur of a moment to help cover an insufficiently planned hack.")
    permutation2 = 'oiaue'
    enc_dict2 = message2.build_transpose_dict(permutation2)
    print("Original message:", message2.get_message_text(), "Permutation:", permutation2)
    print("Expected encryption:",
        "Jock Fluriy as o mythacol choroctir criotid un thi sper uf o mumint tu hilp cuvir on anseffacaintly plonnid hock.")
    print("Actual encryption:", message2.apply_transpose(enc_dict2))
    enc_message2 = EncryptedSubMessage(message2.apply_transpose(enc_dict2))
    print("Decrypted message:", enc_message2.decrypt_message())

运行结果：

Loading word list from file...
   55901 words loaded.
Original message: Hello World! Permutation: eaiuo
Expected encryption: Hallu Wurld!
Actual encryption: Hallu Wurld!
Loading word list from file...
   55901 words loaded.
Decrypted message: Hello World!
----------------
Loading word list from file...
   55901 words loaded.
Original message: Jack Florey is a mythical character created on the spur of a moment to help cover an insufficiently planned hack. Permutation: oiaue
Expected encryption: Jock Fluriy as o mythacol choroctir criotid un thi sper uf o mumint tu hilp cuvir on anseffacaintly plonnid hock.
Actual encryption: Jock Fluriy as o mythacol choroctir criotid un thi sper uf o mumint tu hilp cuvir on anseffacaintly plonnid hock.
Loading word list from file...
   55901 words loaded.
Decrypted message: Jack Florey is a mythical character created on the spur of a moment to help cover an insufficiently planned hack.

总结

1. Style Guide #7。这是 MIT 6.0001 课程提供的一份代码风格指南，可以在这里下载到。其中第 7 条为“Calling a superclass constructor from a subclass”，即在子类中调用父类的构造函数。根据代码重用的原则，没有必要在子类中重新构造父类，只需要重用父类的__init__即可。具体可以使用Super()，也可以直接使用父类名。我模仿了 Style Guide 中的示例，采用使用父类名称的做法。

2. 类的 getter 和 setter。与其它面向对象编程语言类似，给类添加访问成员变量和修改成员变量的 getter 方法和 setter 方法的重要的，它们体现了“封装”这一特点。不应该在对象外面直接访问成员变量，这种行为破坏了封装。

   另外，需要注意的是，一般情况下 getter 函数需返回不可变对象或可变对象的拷贝。请看以下例子：

   class SampleClass:
       def __init__(self):
           self.simple_list = [1, 2, 3]
           print('Inside __init__, id =', id(self.simple_list))
   
       def get_simple_list(self):
           return self.simple_list
   
   
   sample = SampleClass()
   test_list = sample.get_simple_list()
   print('Outside class,   id =', id(test_list))

运行结果如下：

```
Inside __init__, id = 1945763799560
Outside class,   id = 1945763799560
```

这表明通过`get_simple_list`获得的就是成员变量`simple_list`本身，在对象外部修改`test_list`会导致`sample`对象内的成员随之改变。这一定程度上也破坏了封装，因而是不可取的。正确的方法是在 getter 中返回可变对象的拷贝（使用`copy()`方法）。

3. Python 中的模运算。Python 中的模运算与 C/C++ 等其它语言的不同。Python 使用的是 floor 方式，而 C/C++ 使用的是 truncate 方式。举个例子，在 Python 中，-7 % 3 为 2，而在 C/C++ 中，-7 % 3 为 1。

   在本次实验 Part B 凯撒密码处理 shift 时，Python 的这种模方式反而提供了方便——只要 shift 是个整数，那么 shift % 26 就可以将其范围限制在 [0, 26) 以内。比如，若 shift 为 27，那么取模后变成 1，相当于偏一位；若 shift 为 -1，那么取模后变成 25，相当于偏移二十五位。

4. 语法糖。与 C/C++ 等更底层的语言不同，Python 提供了相当多的内置函数和便捷语法，如果恰当使用，能够显著提高程序可读性，更加符合“Python之禅”。比如 Part B 中的apply_shift，返回将字符串中的每个字符经过字典shift_dict映射的结果，恰当地利用 Python 语法，只用一行代码即可完成此操作：

   return ''.join([shift_dict.get(ch, ch) for ch in self.get_message_text()])

本文地址：https://www.jeddd.com/article/mit-python-ps4-class.html