Python:典当竞赛

Question

另一天，另一个国际象棋相关的CodeFights问题。

棋子竞赛是一个两个人玩的游戏，在一个普通的8×8棋盘上玩。第一个玩家有一个白色的棋子，第二个是黑色的棋子。最初，棋子被放置在棋盘的某处，这样第一排和第八排就不会被占据。玩家轮流采取行动。白色典当向上移动，黑色棋子向下移动。允许采取下列行动：

• 一个单元格在允许的方向上垂直移动。
• 两个单元格在相同的垂直方向上移动，如果该棋子站在第二行(对于白卒)或第七格(对于黑卒)行。注意，即使两格移动，一个棋子也不能跳过对手的棋子。
• 捕获向允许的方向移动一个单元格，向左或向右移动一个单元格。

游戏的目的是到达第一排(黑色典当)或第八排(白色棋子)，或者抓住对手的棋子。鉴于最初的位置和轮到谁，决定谁将赢得或宣布它是平局(即，这是不可能的任何球员赢)。假设玩家发挥得最好。保证white ≠ black。示例

• 对于white = "e2"、black = "e7"和toMove = 'w'，输出应该是pawnRace(white, black, toMove) = "draw"。
• 对于white = "e3"、black = "d7"和toMove = 'b'，输出应该是pawnRace(white, black, toMove) = "black"。
• 对于white = "a7"、black = "h2"和toMove = 'w'，输出应该是pawnRace(white, black, toMove) = "white"。

码

def pawnRace(white, black, to_move):
    winner = {'w': 'white',
              'b': 'black'}

    _to_piece = lambda piece: [ord(piece[0])-ord('a'), int(piece[1])]
    white_file, white_rank = _to_piece(white)
    black_file, black_rank = _to_piece(black)

    # if on the same file and black is on a higher rank,
    # they'll bump and will not be able to pass eachother
    if(white_file == black_file and black_rank > white_rank):
        return 'draw'

    def can_capture(black_rank, black_file, white_rank, white_file):
        """return True if a piece can be captured"""
        return abs(black_file - white_file) == 1 and \
               abs(white_rank - black_rank) == 1 and \
               white_rank < black_rank

    while True:
        # if piece can capture: return winner
        if can_capture(black_rank, black_file, white_rank, white_file):
            return winner[to_move]

        # else move
        if to_move == 'w':
            if white_rank != 2 or \
               can_capture(black_rank, black_file, white_rank + 2, white_file):
                white_rank += 1
            else:
                white_rank += 2

        if to_move == 'b':
            if black_rank != 7 or \
               can_capture(black_rank - 2, black_file, white_rank, white_file):
                black_rank -= 1
            else:
                black_rank -= 2

        # if piece is on promotion square: return winner
        if white_rank == 8 or black_rank == 1:
            return winner[to_move]

        to_move = 'w' if to_move == 'b' else 'b'

Notes

这个挑战错过了前进的一步

这一次，我真的尽了最大的努力，让所有的代码评审人员都很难批评我的方法，让它在保持简单的同时也能读懂。然而，和往常一样，我想知道我是如何做到的，因此我觉得有必要在这里发布它。

你对我的实现有什么改变或改进吗？

Answer 1

这段代码相当清晰--变量的名字很好，而且很明显，算法也相当透明。在低层次重构方面，我没有什么可建议的：

使板高成为声明的常量

值8出现在几个地方(其中一个地方伪装为7 )。这使得它很难概括到不同大小的棋盘。

我确实有一个改进算法的建议：

降低了问题复杂度

事实证明，我们不需要关心每个片段所包含的实际文件--只是文件之间的关系。另外，我们只关心旋转的次数，所以也许我们不需要模拟每一个动作。有三种可能性：

1. 棋子至少由一个空文件分开:游戏是一个直接的比赛，每个回合都没有阻碍棋子向前移动的障碍。获胜的次数取决于覆盖的最短距离(减去1，如果可能有2平方移动的话)。
2. 棋子在同一个文件中:如果棋子不需要互相传递(即白人的等级高于黑人的等级)，那么这是一个直接的种族--见上文。否则，游戏就会被抽签。
3. 碎片在相邻的文件上:如果棋子不需要互相传递，那么就像以前一样是一个直接的竞赛。否则，就有机会通过抓捕赢得比赛--对于第一个玩家来说，如果棋子开始有一个奇怪的距离，那么第二个玩家就有机会赢，如果他们的距离是偶数的话。再次，2平方第一步增加了一个复杂的。例如，如果双方都能为第一步选择一个或两个方块，这可能会给第二个玩家带来优势。

一旦您确定玩家是否需要移动两个方块作为第一步(如果允许的话)，那么游戏结束的次数是一个代数表达式(即O(1)时间)，并且没有必要单独模拟每个回合。如果你想把它扩展到更大的棋盘(例如1e9x1e9棋盘)，这个观察可能会很有帮助。

Answer 2

这段代码的长度似乎是必要的两倍。编辑:看起来比必要的长。(我向下滚动，看着最后一个满是代码的窗口。)

等级2和7的特例是对称的，或者，在1到6之间，即1到7之间，切换到零原点。

您的API是按白色和黑色组织的。我建议从球员和对手的角度来组织它。然后，您的函数在返回之前只需要考虑一个操作，每次移动都要执行两个函数调用。

标识符_to_piece()似乎更好地命名为_to_coords()，或者至少是_from_piece()。感谢您称它为助手，而不是公共API的一部分，这很好。

编辑:把游戏想象成只有一个“玩家”(你的功能)坐在一张桌子上，每一轮棋盘旋转180°，玩家被告知当前的颜色为0/1，W/B。现在，两个if to_move == 'w'子句被埋在一个make_move()助手中。如果选择将播放机to_move = 'w' if to_move == 'b' else 'b'作为数字索引，则可能会将其简化为to_move = 1 - to_move。输出使用'wb'[to_move]。

xxxxx_rank += 1或+= 2的条件可以隐藏在助手中，因此您可以通过move_amount()无条件地递增。if white_rank == 8 or black_rank == 1:只需测试球员是否达到最后一名，而不用担心对手。而且，can_capture()是一个非常好的助手，但是一旦它只需要考虑球员向前移动，它就会变得更简单。