日拱一卒，伯克利教你CS，为了让你学会面向对象，老师用心良苦

TechFlow-承志

发布于 2022-09-21 12:00:39

5330

发布于 2022-09-21 12:00:39

文章被收录于专栏：TechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，日拱一卒，我是梁唐。

前两天五一节的时候肝完了伯克利CS61A这门公开课的实验4，做完之后感触颇多。为了让学生们学好CS，伯克利的老师真的是拼了。

实验的内容既保证了高质量，干货满满。又尽量降低难度，让大一刚刚接触CS的学生也能尽快上手。并且还保证了练习过程当中的趣味性，哪怕我不是伯克利的学生，也能深深体会到老师的用心。更要命的是，这样的课程居然是完全免费的！注意是完全免费，所以让我每一次都忍不住安利。

课程链接：https://www.bilibili.com/video/BV16W411W76H

实验原始文档：https://inst.eecs.berkeley.edu//~cs61a/sp18/lab/lab04/#required-questions

在这一次的实验当中，我们要练习一下数据抽象。数据抽象是面向对象的基础，本质上是对程序中虚拟的实体做一定的抽象，用若干函数来进行表达实体的各种行为，从而对代码和逻辑进行高度封装，让代码可读性以及使用变得更加简易。

从这点上来说，面向对象只是一种设计思想，类只是这种思想的承载方式。本次实验为了降低难度，使用了易于理解的函数来阐述这个思想，对于新手来说更加的友好。

可能看我的描述还是有些抽象，不过没有关系，只要用心做完实验的题目，相信大家一定可以理解到其中的精髓。

好了，废话不多说，让我们开始今天的实验吧。

Required Questions

Lists Practice

Q1: List Indexing

对于下列给定的list来说，它们当中的哪一位等于7？比如对于x = [7]来说，答案应该是x[0]。你可以使用python解释器来辅助你进行实验。

使用ok命令来回答问题：python3 ok -q indexing -u

一共有6道题：

>>> x = [1, 3, [5, 7], 9]
______

>>> x = [[7]]
______

>>> x = [3, 2, 1, [9, 8, 7]]
______

>>> x = [[3, [5, 7], 9]]
______

>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
______

>>> lst[3][0]
______

这六道题都不难，但注意要写出完整的索引。

Q2: WWPD: Lists?

读程序给出Python的运行结果，试着凭借肉眼得出答案。

使用ok命令来答题：python3 ok -q lists -u

一共有7题。

>>> [x*x for x in range(5)]
______

>>> [n for n in range(10) if n % 2 == 0]
______

>>> ones = [1 for i in ["hi", "bye", "you"]]
>>> ones + [str(i) for i in [6, 3, 8, 4]]
______

>>> [i+5 for i in [n for n in range(1,4)]]
______

>>> [i**2 for i in range(10) if i < 3]
______

>>> lst = ['hi' for i in [1, 2, 3]]
>>> print(lst)
______

>>> lst + [i for i in ['1', '2', '3']]
______

难度不大，可能有一两题稍微有些绕，实在觉得困难可以在Python中亲自运行一下。

Q3: If This Not That

定义函数if_this_not_that，它接收一个int的list，i_list以及一个int this。对于每一个中的元素，如果元素大于this，那么打印它，否则输出'that'。

代码框架：

def if_this_not_that(i_list, this):
    """Define a function which takes a list of integers `i_list` and an integer
    `this`. For each element in `i_list`, print the element if it is larger
    than `this`; otherwise, print the word "that".

    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
    that
    that
    that
    4
    5
    """
    "*** YOUR CODE HERE ***"

使用ok命令来进行测试：python3 ok -q if_this_not_that

答案

没有难度。

def if_this_not_that(i_list, this):
    for i in i_list:
        if i > this:
            print(i)
        else:
            print('that')

City Data Abstraction

现在我们有一个数据类型来抽象城市，一个城市对象拥有城市名称以及它的经度和纬度。

我们的ADT有一个构造函数：

make_city(name, lat, lon)：通过给定的名称、经度和纬度创建城市对象。

对于每一个城市，我们也有一些选择器：

get_name(city)：返回城市的名称
get_lat(city) ：返回城市的纬度
get_lon(city)：返回城市的经度

下面提供一些例子，我们是如何创建城市以及使用它们的经纬度的：

>>> berkeley = make_city('Berkeley', 122, 37)
>>> get_name(berkeley)
'Berkeley'
>>> get_lat(berkeley)
122
>>> new_york = make_city('New York City', 74, 40)
>>> get_lon(new_york)
40

注意，我们不需要知道这些函数是如何实现的。我们可以假设其他人按照上文中的说明替我们开发好了这些函数。

Q4: Distance

现在我们要开发distance函数，它用来计算两个城市对象之间的距离。

两个坐标点(x1, y1)和(x2, y2)之间的距离是

\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

。我们已经导入了sqrt函数，使用一个城市的经纬度作为它的坐标，你需要使用上文中提供的选择器来获取城市的经纬度信息。

代码框架：

from math import sqrt
def distance(city1, city2):
    """
    >>> city1 = make_city('city1', 0, 1)
    >>> city2 = make_city('city2', 0, 2)
    >>> distance(city1, city2)
    1.0
    >>> city3 = make_city('city3', 6.5, 12)
    >>> city4 = make_city('city4', 2.5, 15)
    >>> distance(city3, city4)
    5.0
    """
    "*** YOUR CODE HERE ***"

使用ok命令来进行测试：python3 ok -q distance

答案

根据题意调用对应的函数获取经纬度信息，之后套用距离公式即可。

from math import sqrt
def distance(city1, city2):
    x1, y1 = get_lon(city1), get_lat(city1)
    x2, y2 = get_lon(city2), get_lat(city2)
    return sqrt((x1 - x2)**2 + (y1 - y2)**2)

Q5: Closer city

接着，实现closer_city函数，它接收一个经纬度和两个城市，返回距离给定经纬度更近的城市。

你只能使用上文中介绍的选择器和构造函数，以及你刚刚开发的distance函数。

所有的选择器和构造函数可以在utils.py中找到，如果你好奇它是怎么实现的，可以去阅读源码。然而，数据抽象的目的是为了在不需要了解实现原理仅仅需要交互方式以及数据类型的前提下进行使用。

提示：可以创建一个临时的城市

代码框架：

def closer_city(lat, lon, city1, city2):
    """
    Returns the name of either city1 or city2, whichever is closest to
    coordinate (lat, lon).

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    """
    "*** YOUR CODE HERE ***"

使用ok来进行测试：python3 ok -q closer_city

答案

实现的时候会发现distance函数传入的参数是两个城市，而非一个城市和一个坐标。所以我们需要使用lat, lon创建一个临时的城市，再计算这个临时城市和city1和city2的距离，选择距离更小的那个进行返回。

注意，最后只需要返回城市的名称，而不需要返回城市对象。

def closer_city(lat, lon, city1, city2):
    temp_city = make_city('tmp', lat, lon)
    dis1, dis2 = distance(temp_city, city1), distance(temp_city, city2)
    ret = city1 if dis1 <= dis2 else city2
    return get_name(ret)

Q6: Don't violate the abstraction barrier!

不要逾越数据抽象的限制！

当我们使用ADT创建函数的时候，我们需要尽可能地使用构造函数和选择器，而不是猜测ADT的实现。依靠数据抽象底层的实现来完成逻辑是违反数据抽象的规范的，永远别这样做！

有可能你刚刚distance和closer_city的实现已经违反了规范，试着移除lab04.py中下列几行代码的注释来进行检查：

# make_city = lambda name, lat, lon: [lon, [lat], name]
# get_name = lambda city: city[2]
# get_lat = lambda city: city[1][0]
# get_lon = lambda city: city[0]

这些语句改变了city ADT的实现。抽象天然的屏障可以保证当ADT中实现方式改变的时候，只要上游使用构造函数、选择器的方式正确，不会影响它们的结果。

现在，试着重新跑一下你刚刚distance和closer_city的测试：

python3 ok -q distance
python3 ok -q closer_city

如果你遵守了规范，使用了构造函数和选择器，那么你的测试依然可以通过。

如果你去掉注释了之后无法通过了，那么你需要替换掉违反了规范的部分。比如说手动使用了新的list对象来创建了city。使用合适的选择器和构造函数。

在我们继续实验之前，确保你能理解测试依然能够通过的原因，并且你的函数能够通过刚才的两个测试。

Optional Questions

More Lists Practice

Q7: Flatten

编写函数flatten，它接收一个list（可能有多层）将它展开，如：

提示，你可以使用python内置的type函数来检查一个对象是不是list，例如：

代码框架：

def flatten(lst):
    """Returns a flattened version of lst.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]      # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    """
    "*** YOUR CODE HERE ***"

使用ok来进行测试：python3 ok -q flatten

答案

由于输入的lst可能有多层，并且我们无法判断究竟有几层，所以可以考虑使用递归。

递归的逻辑也很简单，如果当前的lst是一个整数，直接返回只包含它的list。即[lst]。

如果是一个list，那么进行遍历，将当中的每一个元素使用flatten展开。将这些展开之后的元素全部合并返回。

def flatten(lst):
    if type(lst) == int:
        return [lst]
    ret = []
    for l in lst:
        ret += flatten(l)
    return ret

Q8: Merge

编写一个函数merge它读入两个有序list lst1和lst2，返回一个新的list，它包含着两个list中的所有元素

代码框架：

def merge(lst1, lst2):
    """Merges two sorted lists.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"

使用ok来测试代码：

python3 ok -q merge

答案

归并问题，之前的文章当中写过好几次了。

由于两个list长度不一，所以在对比两个数组元素大小之前，需要先判断数组是否还有剩余的元素。一个比较简单的做法是在进行归并之前，先向两个list中插入一个极大的int作为标兵。只要数组当中没有超过标兵的值，就可以保证标兵一定不会被弹出，从而就不需要再判断数组是否还有剩余元素。

def merge(lst1, lst2):
    n, m = len(lst1), len(lst2)
    lst1.append(sys.maxsize)
    lst2.append(sys.maxsize)
    i, j = 0, 0
    ret = []
    while i < n or j < m:
        if lst1[i] <= lst2[j]:
           ret.append(lst1[i])
           i += 1
        else:
            ret.append(lst2[j])
            j += 1 
    return ret

Connect N

在这个章节末尾，你将要开发一个属于你的connect N游戏（常见的是connect 4）。

你可能也许知道，connect N是一个双人游戏，两个玩家轮流从上方选择一列放入棋子。放入的棋子会落到该列的最下方的格子，已经满了的列不能再放入棋子。

当有一个玩家的N个棋子连成一条线时获胜，无论是横着、竖着还是对角线连线都行。有玩家获胜或者所有格子都填满时游戏结束，下面是一个Connect 4的棋盘：（原图挂了，重新找的图）

Building Connect N

让我们为玩家X和O创建对战区域。

在这个实验当中，我们将会将棋盘表示成二维list。我们将会以矩阵的形式展示棋盘，比如list的值是：

[['-', '-', '-', '-'], ['O', 'O', 'O', 'X'], ['X', 'X', 'X', 'O']]

展示出来会是：

二维list中的数字代表了什么？二维list中的元素又代表了什么？在我们开始创建棋盘之前，先试着思考一下。

注意，list是从下标0开始的，行和列都是从0开始的：

Q9: Creating an empty board

在我们的游戏中，我们将要使用数据抽象，所以让我们先来完成构造函数。

我们将空格子表示成'-'，在文件lab04_extra.py中，将我们的代码填充完整。

首先实现函数create_row，它将会以我们的数据抽象类型返回一个棋盘中的空行。

这个函数只能有一行包含return的代码。

提示：你可以使用list comprehension语法

代码框架：

def create_row(size):
    """Returns a single, empty row with the given size. Each empty spot is
    represented by the string '-'.

    >>> create_row(5)
    ['-', '-', '-', '-', '-']
    """
    "*** YOUR CODE HERE ***"

使用ok来进行测试：python3 ok -q create_row

接着使用create_row来实现create_board，它将会返回一个特定维度的棋盘。这个函数也只包含一行带return的语句。

代码框架：

def create_board(rows, columns):
    """Returns a board with the given dimensions.

    >>> create_board(3, 5)
    [['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]
    """
    "*** YOUR CODE HERE ***"

使用ok来进行测试：python3 ok -q create_board

答案

Python创建list的基本用法，没有难度。

def create_row(size):
    return ['-' for _ in range(size)]

def create_board(rows, columns):
    return [create_row(columns) for _ in range(rows)]

Q10: Updating the board

在游戏的过程当中，棋盘将会一直变化。我们需要让我们的表示棋盘的数据也随之改变。为了完成这点，我们需要在每次游戏状态改变时创建新的board来代表。实现replace_elem函数，它接收一个list以及一个索引和一个元素。函数会返回一个新的数组，传入的元素会摆放在新数组的索引处，其余值和原数组相同。

这个函数同样只有一行带return的代码。

代码框架：

def replace_elem(lst, index, elem):
    """Create and return a new list whose elements are the same as those in
    LST except at index INDEX, which should contain element ELEM instead.

    >>> old = [1, 2, 3, 4, 5, 6, 7]
    >>> new = replace_elem(old, 2, 8)
    >>> new
    [1, 2, 8, 4, 5, 6, 7]
    >>> new is old   # check that replace_elem outputs a new list
    False
    """
    assert index >= 0 and index < len(lst), 'Index is out of bounds'
    "*** YOUR CODE HERE ***"

使用ok进行测试：python3 ok -q replace_elem

答案

题目中了，我们要返回一个新的数组。从测试样例当中我们也可以看出这一点。

所以我们不能直接在旧的list上修改，而要创建一个新的。由于其余元素需要和老的一样，我们可以使用切片将旧的数组索引之前和索引之后的片段筛选出来再进行拼接。

def replace_elem(lst, index, elem):
    assert index >= 0 and index < len(lst), 'Index is out of bounds'
    "*** YOUR CODE HERE ***"
    return lst[:index] + [elem] + lst[index+1: ]

Q11: Manipulating pieces

现在，我们的棋盘就完成了，当我们来开发一些选择器。

首先，我们需要能在给定位置时找到该位置对应的棋子（'-', 'X', 'O')，实现get_piece函数来实现。

注意：因为get_piece是一个选择器，它允许打破数据抽象的限制。这意味着它可以知道棋盘是以嵌套list的方式实现的，可以使用列表更新操作来更新它。这可以帮助我们将所有函数的内部实现从程序员和其他用户的代码当中抽象出来

这个函数也只能包含一行带返回的语句

代码框架：

def get_piece(board, row, column):
    """Returns the piece at location (row, column) in the board.

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> board = put_piece(board, rows, 0, 'X')[1] # Puts piece "X" in column 0 of board and updates board
    >>> board = put_piece(board, rows, 0, 'O')[1] # Puts piece "O" in column 0 of board and updates board
    >>> get_piece(board, 1, 0)
    'X'
    >>> get_piece(board, 1, 1)
    '-'
    """
    "*** YOUR CODE HERE ***"

现在，我们棋盘上所有的点都是空的。所有get_piece函数并没有用，让我们来做一些改动。

继续实现put_piece函数，它将给定用户的棋子放入指定的列中。put_piece将会返回2元tuple，包含(<row index>, <new board>)。

第一个元素是棋子放入的行，或者是-1表示该列已经满了。第二个元素是放入该棋子之后的新棋盘，如果要放入的列已经满了，那么则返回之前的棋盘。

假设给定的列在棋盘上，记住你可以使用get_piece来获取棋盘上的棋子。max_rows参数可以帮助我们判断我们的棋子将会放入哪一行。

提示：你可能会需要调用replace_elem函数两次来创建新的棋盘

代码框架：

def put_piece(board, max_rows, column, player):
    """Puts PLAYER's piece in the bottommost empty spot in the given column of
    the board. Returns a tuple of two elements:

        1. The index of the row the piece ends up in, or -1 if the column
           is full.
        2. The new board

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> row, new_board = put_piece(board, rows, 0, 'X')
    >>> row
    1
    >>> row, new_board = put_piece(new_board, rows, 0, 'O')
    >>> row
    0
    >>> row, new_board = put_piece(new_board, rows, 0, 'X')
    >>> row
    -1
    """
    "*** YOUR CODE HERE ***"

使用ok命令进行测试：

python3 ok -q get_piece
python3 ok -q put_piece

答案

get_piece的代码很简单，就是一个二维数组的索引。

put_piece有一个小坑，就是row是从max_row-1开始递减的，而非从0开始递增的。这个有点反直觉。

def get_piece(board, row, column):
    return board[row][column]

def put_piece(board, max_rows, column, player):
    row = max_rows - 1
    while get_piece(board, row, column) != '-' and row >= 0:
        row -= 1
    if row < 0:
        return -1, board
    board[row] = replace_elem(board[row], column, player)
    return row, board

You are now crossing the abstraction barrier!!!

你现在已经完成了构造函数以及选择器，还完成了一些修改数据类型的方法。从现在开始，你再也不用把棋盘当成是一个list来看待了。相反，相信你的抽象涉及，使用你刚刚开发的方法。

Q12: Making a move

让我们首先来实现一个函数让玩家可以在游戏里采取行动。这个和put_piece函数不同，put_piece假设玩家给的是一个有效的列序号。make_move只有在确定给定的列是有效的，才会摆放棋子。它返回一个二元tuple（row索引，棋盘）。

如果行动是有效的，在列上摆放一颗棋子，并且返回棋子的行号和一个新棋盘（你是否已经完成了一个能派上用场的函数？）。如果行动是无效的，make_move将会返回-1，以及原先的棋盘，什么都不改变。

参数max_rows和max_cols描述了棋盘的范围，可能会在判断行动是否有效时有用。

代码框架：

def make_move(board, max_rows, max_cols, col, player):
    """Put player's piece in column COL of the board, if it is a valid move.
    Return a tuple of two values:

        1. If the move is valid, make_move returns the index of the row the
           piece is placed in. Otherwise, it returns -1.
        2. The updated board

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> row, board = make_move(board, rows, columns, 0, 'X')
    >>> row
    1
    >>> get_piece(board, 1, 0)
    'X'
    >>> row, board = make_move(board, rows, columns, 0, 'O')
    >>> row
    0
    >>> row, board = make_move(board, rows, columns, 0, 'X')
    >>> row
    -1
    >>> row, board = make_move(board, rows, columns, -4, '0')
    >>> row
    -1
    """
    "*** YOUR CODE HERE ***"

使用ok来进行测试：python3 ok -q make_move

答案

整体逻辑和刚才put_piece几乎一样，只不过我们需要先判断传入的col是否是合法的。

只有0 <= col <= max_cols才是合法的，不在区间里就直接返回-1, board。

如果col合法，直接返回put_piece的结果即可。

def make_move(board, max_rows, max_cols, col, player):
    if col < 0 or col >= max_cols:
        return -1, board
    row, board = put_piece(board, max_rows, col, player)
    return row, board

Q13: Printing and viewing the board

如果我们可以看到棋盘是不是效果会更好呢？让我们来实现一个函数来搞定它。

函数print_board读入一个棋盘以及棋盘的维度，然后将它目前的状态打印出来。

我们希望我们的棋盘看起来不错，在这种情况下，使用string要比list更好。所以我们将要把['X', 'X', 'O', '-']这样的一行打印成'X X O -'，用空格来分隔其中的棋子。

记住，你可以使用+操作符来拼接字符串，比如'hel' + 'lo' = 'hello'

记住我们需要遵守抽象规范，你必须在假设你不知道棋盘是一个嵌套list的情况下实现。所以我们需要使用我们刚刚开发的选择器来完成它

提示：你可能已经发现了，在有些测试样例中无法通过。这是因为你在行尾输出了多余的空格。strip()函数可以解决这个问题，它能够移除行首和行尾多余的空格，比如：

代码框架：

def print_board(board, max_rows, max_cols):
    """Prints the board. Row 0 is at the top, and column 0 at the far left.

    >>> rows, columns = 2, 2
    >>> board = create_board(rows, columns)
    >>> print_board(board, rows, columns)
    - -
    - -
    >>> new_board = make_move(board, rows, columns, 0, 'X')[1]
    >>> print_board(new_board, rows, columns)
    - -
    X -
    """
    "*** YOUR CODE HERE ***"

使用ok进行测试：python3 ok -q print_board

答案

题目要求我们不能把board当做是二维数组，这就要求我们使用刚刚开发的get_piece来获取board当中的内容。

board中的内容本身就是字符串，所以我们只需要用一个额外的字符串将每一行获取的内容拼接起来再输出即可。注意使用strip来去除掉首尾多余的空格。

def print_board(board, max_rows, max_cols):
    for i in range(max_rows):
        output = ''
        for j in range(max_cols):
            output += get_piece(board, i, j) + ' '
        print(output.strip())

现在这个游戏已经可以运行了，你可以亲自尝试一下。进入lab04文件夹之后运行以下命令：

Q14: Checking for victory

是不是很有趣呢？但目前为止我们还没有考虑获胜，这是我们最后需要为Connect N游戏开发的功能——检查是否获胜。

首先，让我们实现两个helper函数check_win_row和check_win_col，分别检查给定的用户在水平和竖直是否获胜。

因为我们要在每轮游戏之后检查获胜，所以只需要检查最近行动的玩家是否获胜即可。check_win_row和check_win_col都仅仅需要检查一个特定的玩家，它是以参数的形式传入的。记住num_connect告诉你多少相连的棋子能够触发获胜。max_rows和max_cols的定义和上面一样。

和print_board一样，你需要遵守抽象类型。

代码框架：

def check_win_row(board, max_rows, max_cols, num_connect, row, player):
    """ Returns True if the given player has a horizontal win
    in the given row, and otherwise False.

    >>> rows, columns, num_connect = 4, 4, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'O')
    False
    >>> board = make_move(board, rows, columns, 2, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'X')
    False
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win_row(board, rows, columns, num_connect, 3, 'X')
    True
    >>> check_win_row(board, rows, columns, 4, 3, 'X')    # A win depends on the value of num_connect
    False
    >>> check_win_row(board, rows, columns, num_connect, 3, 'O')   # We only detect wins for the given player
    False
    """
    "*** YOUR CODE HERE ***"

使用ok进行测试：python3 ok -q check_win_row

答案

判断给定row是否有超过num_connect个连续位置等于player，注意由于要判断连续，如果遇到一个不相等的，需要将count置为0

def check_win_row(board, max_rows, max_cols, num_connect, row, player):
    cnt = 0
    for i in range(max_cols):
        if get_piece(board, row, i) == player:
            cnt += 1
        else:
            cnt = 0
        if cnt >= num_connect:
            return True
    return False

代码框架：

def check_win_column(board, max_rows, max_cols, num_connect, col, player):
    """ Returns True if the given player has a vertical win in the given column,
    and otherwise False.

    >>> rows, columns, num_connect = 5, 5, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 0, 'X')
    False
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 1, 'O')
    False
    >>> board = make_move(board, rows, columns, 2, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> check_win_column(board, rows, columns, num_connect, 1, 'O')
    True
    >>> check_win_column(board, rows, columns, 4, 1, 'O')
    False
    >>> check_win_column(board, rows, columns, num_connect, 1, 'X')
    False
    """
    "*** YOUR CODE HERE ***"

使用ok进行测试：python3 ok -q check_win_column

答案

column同理，只不过调换一下坐标的顺序而已。

def check_win_column(board, max_rows, max_cols, num_connect, col, player):
    cnt = 0
    for i in range(max_rows):
        if get_piece(board, i, col) == player:
            cnt += 1
        else:
            cnt = 0
        if cnt >= num_connect:
            return True
    return False

Q15: Winning!

最后，让我们实现一个方法来检查所有的获胜可能。实现check_win，让它能够在任何方向获胜都返回True，无论横向、纵向或对角线。

你需要使用刚刚开发的函数，check_win_row和check_win_column，以及现成的check_win_diagonal(board, max_rows, max_cols, num_connect, row, col, player)。

代码框架如下：

def check_win(board, max_rows, max_cols, num_connect, row, col, player):
    """Returns True if the given player has any kind of win after placing a
    piece at (row, col), and False otherwise.

    >>> rows, columns, num_connect = 2, 2, 2
    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'O')
    False
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    True

    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 0, 'O')[1]
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
    True
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    False

    >>> board = create_board(rows, columns)
    >>> board = make_move(board, rows, columns, 0, 'X')[1]
    >>> board = make_move(board, rows, columns, 1, 'O')[1]
    >>> board = make_move(board, rows, columns, 1, 'X')[1]
    >>> check_win(board, rows, columns, num_connect, 0, 0, 'X')
    False
    >>> check_win(board, rows, columns, num_connect, 1, 0, 'X')
    True
    """
    diagonal_win = check_win_diagonal(board, max_rows, max_cols, num_connect,
                                      row, col, player)
    "*** YOUR CODE HERE ***"

使用ok测试代码：python3 ok -q check_win

答案

逻辑很简单，调用一下这三个判断获胜的函数，只要有一个为True，返回True，否则返回False。

def check_win(board, max_rows, max_cols, num_connect, row, col, player):
    diagonal_win = check_win_diagonal(board, max_rows, max_cols, num_connect,
                                      row, col, player)
    "*** YOUR CODE HERE ***"
    if check_win_row(board, max_rows, max_cols, num_connect, row, player) or check_win_column(board, max_rows, max_cols, num_connect, col, player) or diagonal_win:
        return True
    return False

恭喜，你已经开发好了专属的Connect N游戏！有没有觉得你边上的兄弟很适合来一局呢？和之前一样，在终端里运行命令来运行游戏：

我们为你开发了play函数，如果你好奇的话，你可以看下它的实现。

就像你看到的一样，正是由于合适的数据抽象，play函数变得无比简单。注意到，我们只是使用了你开发的make_move, print_board, check_win就执行了游戏，而甚至不需要知道棋盘和棋子是如何实现的。

我把play的代码贴过来了，大家可以亲自感受一下，的确非常简洁：

def play(board, max_rows, max_cols, num_connect):
    max_turns = max_rows * max_cols
    playing = True
    print("Player 'X' starts")
    who = 'X'
    turns = 0

    while True:
        turns += 1
        if turns > max_turns:
            print("No more moves. It's a tie!")
            sys.exit()

        while True:
            try:
                col_index = int(input('Which column, player {}? '.format(who)))
            except ValueError as e:
                print('Invalid input. Please try again.')
                continue

            row_index, board = make_move(board, max_rows, max_cols, col_index, who)

            if row_index != -1:
                break

            print("Oops, you can't put a piece there")

        print_board(board, max_rows, max_cols)

        if check_win(board, max_rows, max_cols, num_connect, row_index, col_index, who):
            print("Player {} wins!".format(who))
            sys.exit()

        who = other(who)

到这里这次的实验就算是做完了，这个量还是挺大的，但相信大家只要能耐心做完，一定收获满满。

技术和实力的进步，其实就是在一次次这样一点点进步下积累的，加油！

喜欢本文的话不要忘记三连~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯云测试服务

游戏

编程算法

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

腾讯云测试服务

游戏

编程算法