MIT 6.0001 PS3:用 Python 实现一个单词游戏

请注意,本文编写于 187 天前,最后修改于 148 天前,其中某些信息可能已经过时。

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

问题描述

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

求解思路

在开始之前,先解压 ps3.zip,并直接运行 ps3.py,以确保我们已经准备好所有将会用到的文件。出现下列结果,表示正常:

Loading word list from file...
   83667 words loaded.
play_game not implemented.

Problem 1: Word scores

首先编写get_word_score函数,它接受两个参数,分别是一个字符串 word 代表单词,还有一个非负整数 n 表示手牌的大小。

根据要求,一个单词的分数由两部分的乘积组成,将两个部分分别保存在变量first_componentsecond_component中:

first_component = 0
for c in word.lower():
    first_component += SCRABBLE_LETTER_VALUES[c]
    
second_component = max(1, (7*len(word) - 3*(n-len(word))))

观察到其中first_component的计算过程是对一个字符串中每个字符在字典SCRABBLE_LETTER_VALUES中对应数值的和,因此考虑使用一些称为“语法糖”的技巧来简化这个循环。可以用以下代码来计算first_component

first_component = sum([SCRABBLE_LETTER_VALUES[c] for c in word.lower()])

后面这种方法结合了列表解析与sum函数,只用一行代码就代替了原来的三行代码,更加简洁,而且可读性更高。需要注意的一点是SCRABBLE_LETTER_VALUES中只有小写字母的对应分数,因此在列表解析时需要使用word.lower()来将其转换为小写。

get_word_score的完整代码如下,可以通过 test_ps3.py 中 test_get_word_score()的单元测试。

def get_word_score(word, n):
    first_component = sum([SCRABBLE_LETTER_VALUES[c] for c in word.lower()])
    second_component = max(1, (7*len(word) - 3*(n-len(word))))
    return first_component * second_component

Problem 2: Dealing with hands

在本文档中,“hand”一词译为“手牌”。

题目已经为我们提供了get_frequency_dictdisplay_handdeal_hand三个函数,它们可以直接拿来使用,无需做其他修改(至少目前不需要修改)。

在 Problem 2 中,我们要编写的是update_hand函数,它接受手牌 hand 以及一个单词 word 为参数,返回从 hand 中移除 word 中所有出现的字母的一个新手牌。需要注意的是该函数不会改变传入的参数 hand,而是返回一个新的手牌,因此函数内部需要对 hand 做一份拷贝,即:

new_hand = hand.copy()

在这个函数中,存在一种特殊情况,就是从 hand 中移除某个字母以后,该字母的出现次数变为 0——对于这种情况,我的方案是始终保证手牌中不存在次数为 0 的字母,一旦移除后次数变为 0,立即将该字母从手牌中删除。从字典中删除元素的方法是pop

update_hand的完整代码如下,可以通过 test_ps3.py 中 test_update_hand()的单元测试。

def update_hand(hand, word):
    new_hand = hand.copy()  # 将hand字典拷贝一份
    for letter in word.lower():
        if letter in new_hand:
            new_hand[letter] -= 1  # 递减字母个数
            if new_hand[letter] <= 0:  # 字母个数减至0时将其删除
                new_hand.pop(letter)
    return new_hand

Problem 3. Valid words

is_valid_word函数接受三个参数:单词 word、手牌 hand 和单词列表 word_list,该函数检查两项内容:第一项,检查给定单词是否在 word_list 中存在;第二项,检查该单词是否能由给定手牌的一个子集构造出来。

第一项检查很简单,只需要使用in判断 word 是否在 word_list 中即可。

第二项检查的思路是,首先使用get_frequency_dict获得给定单词 word 中每个字母出现的频数,然后循环地将每个字母的频数与手牌 hand 的频数相比较,如果某一次循环中字母所需要的次数超过了 hand 提供的次数,说明手牌不能组成这个单词;如果循环结束,则说明手牌可以组成这个单词。

基于以上思路编写代码。is_valid_word的完整代码如下,可以通过 test_ps3.py 中 test_is_valid_word()的单元测试。

def is_valid_word(word, hand, word_list):
    if word.lower() not in word_list:  # 单词不在单词列表中
        return False
    compose = get_frequency_dict(word.lower())  # 单词本身所需要的频数字典
    for letter in compose.keys():
        if compose[letter] > hand.get(letter, 0):  # 某一字母所需要的次数超过了hand提供的次数
            return False
    return True

注意:以上代码不是最终版本,在后面的 Problem 中还会修改。

Problem 4. Wildcards

通配符“*”可以代替一个元音字母,元音字母在 ps3.py 文件的开头处(第 12 行)已经给出:

VOWELS = 'aeiou'

为了添加对通配符的支持,我们需要修改一些之前已经编写好的代码,下面一一说明。

修改字母分值字典

根据要求,如果玩家使用了通配符,该通配符不会获得任何得分,但是在计算分数时它占一个字母的位置。所以我们要在字典SCRABBLE_LETTER_VALUES中增加一项'*': 0

修改 deal_hand 函数

该函数生成的手牌必须有且仅有一个通配符。此前,生成的手牌中有$$ \frac{1}{3} $$ 的字母是元音字母,剩下的是辅音字母;修改后,元音字母的个数会减少一个,并增加一个通配符,辅音字母的数量不变。

修改后的deal_hand的完整代码如下:

def deal_hand(n):
    hand={}
    num_vowels = int(math.ceil(n / 3))

    for i in range(num_vowels - 1):  # 通配符代替了一个元音字母
        x = random.choice(VOWELS)
        hand[x] = hand.get(x, 0) + 1
    
    for i in range(num_vowels, n):    
        x = random.choice(CONSONANTS)
        hand[x] = hand.get(x, 0) + 1
    
    hand['*'] = 1  # 一个通配符
    return hand

修改 is_valid_word 函数

如果单词中没有通配符,那么is_valid_word要做的事情和原来一样,见 Problem 3;如果单词中含有一个通配符,那么需要将通配符替换为一个元音字母,然后再检查该单词的有效性。尝试将通配符换成五个元音字母中的一个,如果至少有一个元音字母使单词有效,那么函数返回 True;如果五个元音字母都不能使单词成为有效的,那么返回 False。

修改后的is_valid_word的完整代码如下:[][]

def is_valid_word(word, hand, word_list):
    if '*' not in word:
        if word.lower() not in word_list:  # 单词不在单词列表中
            return False
        compose = get_frequency_dict(word.lower())  # 单词本身所需要的频数字典
        for letter in compose.keys():
            if compose[letter] > hand.get(letter, 0):  # 某一字母所需要的次数超过了hand提供的次数
                return False
        return True

    elif word.count('*') == 1:
        for vowel in VOWELS:
            flag = True
            try_word = word.replace('*', vowel)
            if try_word not in word_list:
                continue
            compose = get_frequency_dict(try_word)
            try_hand = hand.copy()
            try_hand.pop('*')
            try_hand[vowel] = try_hand.get(vowel, 0) + 1
            for letter in compose.keys():
                if try_hand.get(letter, 0) < compose[letter]:
                    flag = False
                    break
            if flag:
                return True
            else:
                continue
        return False

Problem 5. Playing a hand

首先编写calculate_handlen函数,用于计算手牌中所有字母的个数(包括重复次数):

def calculate_handlen(hand):
    return sum(hand.values())

play_hand仅针对一副手牌与用户进行交互。根据 ps3.py 中提供的伪代码,可以轻松地编写出这个函数。完整代码如下:

def play_hand(hand, word_list):
    # Keep track of the total score
    total_score = 0
    
    # As long as there are still letters left in the hand:
    while calculate_handlen(hand) > 0:
        # Display the hand
        print('Current Hand: ', end='')
        display_hand(hand)
        # Ask user for input
        user_input = input('Enter word, or "!!" to indicate that you are finished: ')
        # If the input is two exclamation points:
        if user_input == '!!':
            # End the game (break out of the loop)
            break
            
        # Otherwise (the input is not two exclamation points):
        else:
            # If the word is valid:
            if is_valid_word(user_input, hand, word_list):
                # Tell the user how many points the word earned,
                # and the updated total score
                points = get_word_score(user_input, len(hand))
                total_score += points
                print('"', user_input, '" earned ', points, ' points. Total: ', total_score, ' points', sep='')
            # Otherwise (the word is not valid):
            else:
                # Reject invalid word (print a message)
                print('That is not a valid word. Please choose another word.')
            # update the user's hand by removing the letters of their inputted word
            hand = update_hand(hand, user_input)
            print()  # 空行

    # Game is over (user entered '!!' or ran out of letters),
    # so tell user the total score
    if calculate_handlen(hand) <= 0:  # hand为空
        print('Ran out of letters. ', end='')
    print('Total score:', total_score, 'points')
    # Return the total score as result of function
    return total_score

自己编写测试代码,测试题目附带的 Example #1 和 Example #2,输出结果、每一步的得分和总得分均与样例相同:

if __name__ == '__main__':
    word_list = load_words()

    hand_example1 = {'a':1, 'j':1, 'e':1, 'f':1, '*':1, 'r':1, 'x':1}
    play_hand(hand_example1, word_list)

    hand_example2 = {'a':1, 'c':1, 'f':1, 'i':1, '*':1, 't':1, 'x':1}
    play_hand(hand_example2, word_list)

Problem 6. Playing a game

编写substitute_hand函数,在该函数中,玩家指定一个要替换的字母,然后程序随机选择一个不同的且从未出现过的字母代替这个字母,次数与原字母相同。

def substitute_hand(hand, letter):
    if letter in hand:
        available_letters = string.ascii_lowercase  # 26个小写字母
        available_letters = available_letters.replace(letter, '')  # 删去要替换的原字母
        for exist_letter in hand:
            if hand[exist_letter] > 0:
                available_letters = available_letters.replace(exist_letter, '')  # 删去手牌中已存在的字母
        new_letter = random.choice(available_letters)  # 随机选择一个新字母
        new_hand = hand.copy()
        new_hand[new_letter] = new_hand.pop(letter)
        return new_hand

    else:  # 如果要替换的字母本来就不存在,则直接返回原手牌
        return hand

根据play_game的函数文档(即__doc__)提供的过程编写该函数:

def play_game(word_list):
    substitute_flag = True  # 有一次替换字母的机会
    replay_flag = True  # 有一次重玩的机会

    num_of_hands = int(input('Enter total number of hands: '))
    total_score = 0
    for i in range(num_of_hands):
        hand = deal_hand(HAND_SIZE)
        print('Current hand: ')
        display_hand(hand)
        if substitute_flag and input('Would you like to substitute a letter? ').lower()[0] == 'y':
            substitute_flag = False
            letter_replace = input('Which letter would you like to replace: ')
            hand = substitute_hand(hand, letter_replace)
        hand_score = play_hand(hand,word_list)
        print('Total score for this hand:', hand_score)
        print('----------')
        if replay_flag and input('Would you like to replay the hand? ').lower()[0] == 'y':
            replay_score = play_hand(hand,word_list)
            hand_score = max(hand_score, replay_score)  # 取较大的分数
            replay_flag = False
            print('----------')
        total_score += hand_score
    print('Total score over all hands:', total_score)

play_game中多次要求玩家输入“yes”或“no”,不过为了使得程序更加人性化,我的代码中并不要求玩家的输入和“yes”或“no”精确匹配,而采取了以下方案——用户输入了以大写'Y'或小写'y'开头的字符串均被认为是“yes”,其余情况认为是“no”。

由于玩家只有一次替换字母的机会,因此我用一个变量substitute_flag作为标志,将其初始化为 True 表示“允许替换字母”。类似地,玩家只有一次重玩当前手牌的机会,我用变量replay_flag作为标志,将其初始化为 True 表示“允许重玩”。一旦这些机会被用掉,立即将对应的标志置为 False。

这里用到了一个小技巧,就是使用了“短路逻辑”。以替换字母这一功能为例,注意到玩家进行字母替换有两个条件,一是标志substitute_flag为 True,二是在询问玩家是否要替换字母后玩家输入了'yes',只有这两个条件都满足时才会进行字母替换。然而,如果标志为 False,则根本不需要询问玩家。普通的方法是使用嵌套的 if 语句,我用的方法是使用逻辑与(and)的短路特性,即只有第一项为 True 时才会判断第二项,否则整个表达式直接求值为 False,无需再判断第二项。如下:

if substitute_flag and input('Would you like to substitute a letter? ').lower()[0] == 'y':
    # ...
    # 替换字母的代码,已省略
    # ...

最后,完成 main 函数:

if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

运行测试

大部分的测试工作在各个单元测试中已经完成。

下面的测试是指在编写完整个程序后,以玩家的身份试玩这个单词游戏。由于手牌是随机生成的,因此每次测试几乎都是不可复现的,仅供参考,表示程序可以正常运行:

Loading word list from file...
   83667 words loaded.
Enter total number of hands: 2
Current hand:
u e n w x x *
Would you like to substitute a letter? no
Current Hand: u e n w x x *
Enter word, or "!!" to indicate that you are finished: new
"new" earned 72 points. Total: 72 points

Current Hand: u x x *
Enter word, or "!!" to indicate that you are finished: xu*
That is not a valid word. Please choose another word.

Current Hand: x
Enter word, or "!!" to indicate that you are finished: !!
Total score: 72 points
Total score for this hand: 72
----------
Would you like to replay the hand? no
Current hand:
i e c h v l *
Would you like to substitute a letter? yes
Which letter would you like to replace: v
Current Hand: i e c h l * w
Enter word, or "!!" to indicate that you are finished: h*il
"h*il" earned 114 points. Total: 114 points

Current Hand: e c w
Enter word, or "!!" to indicate that you are finished: cew
That is not a valid word. Please choose another word.

Ran out of letters. Total score: 114 points
Total score for this hand: 114
----------
Would you like to replay the hand? yes
Current Hand: i e c h l * w
Enter word, or "!!" to indicate that you are finished: ch*w
"ch*w" earned 209 points. Total: 209 points

Current Hand: i e l
Enter word, or "!!" to indicate that you are finished: lie
"lie" earned 63 points. Total: 272 points

Ran out of letters. Total score: 272 points
----------
Total score over all hands: 344

以上测试中测试了实现的全部内容,既测试了替换字母,又测试了不替换字母;既测试了重玩手牌,又测试了不重玩;既测试了用“!!”中途退出,又测试了消耗完所有手牌的情况。在重玩手牌的测试中,可以看出该手牌的分数确实是取了两次中较大的那个分数。在输入无效单词的测试中,可以看出尽管单词无效,它仍然消耗手牌。所有测试均与题目中的要求相符,并且符合预期。

这里说明一个非功能性的问题,题目中所给的样例中出现了提示信息前后信息不符的问题,我只采用了其中一种。例如,样例中既有“Please enter a word or '!!' to indicate you are done:”,又有“Enter word, or "!!" to indicate that you are finished:”,二者有一些用词上的区别,我采用了后者。

总结

完成实验本身的要求并不难,因为 MIT6_0001F16_ProblemSet3.pdf 文档中已经给出了充足的提示。在以上要求之外,我还做了一些额外的考虑以增加程序的严谨性和鲁棒性;还使用了一些技巧来使得程序更加简洁;还有一些其他值得注意的方面,现总结如下。

  • 伪代码。在 Problem 5 中,题目为我们提供了需求的伪代码,因而我们可以非常轻松地实现功能。不难发现,写出来的 Python 代码和题目提供的伪代码非常相似。由此也可以感受出 Python 语法和自然语言非常接近,如果程序中的函数和变量命名合理的话,那么整个 Python 程序将会非常接近自然语言。
  • 短路逻辑。短路逻辑几乎存在于所有的编程语言中,这里不再赘述短路逻辑的含义。在代码中恰当地使用短路逻辑,能够使程序变得更加简洁,也可以提高程序的可读性。在 Problem 6 中我就用到了逻辑与的短路特性,从而用一行代码就实现了两层嵌套 if 语句的功能。
  • 语法糖。与 C/C++ 等更底层的语言不同,Python 提供了相当多的内置函数和便捷语法,如果恰当使用,能够显著提高程序可读性,更加符合“Python之禅”。在这次作业中,最明显的例子就是通过组合使用内置函数来代替循环:比如在calculate_handlen函数中只是用了一行代码来对字典中的值求和:

    sum(hand.values())

再比如在get_word_score函数中,使用一行代码来把字典映射作用于字符串上:

sum([SCRABBLE_LETTER_VALUES[c] for c in word.lower()])

类似的例子还有很多,不一一列举。或许这就是人们常说的“人生苦短,我用 Python”的原因之一吧!

  • 比较严格地遵守了 PEP 8 编码规范。如缩进均使用 4 个空格(而不是制表符 Tab)、导入模块使用多行 import、表达式和语句中按规范使用空格等。我使用了 Autopep8 来自动格式化代码。之所以用了“比较严格”这种保守的词汇,是因为在我的代码中,有少数几行地长度超过了 79 个字符,这是不符合 PEP 8 规范的。之所以要违反规范,是因为若截断这些行,将严重降低代码的可读性。

Comments

添加新评论