python - "Ticket to Ride"灰色路线的棋盘游戏逻辑

Question

我喜欢玩 Ticket to Ride ，所以我决定尝试用 Python 实现部分游戏逻辑，作为一个辅助编程项目。游戏板本质上是一个加权多重图，因此用 NetworkX 复制了游戏的基本结构。小菜一碟。

我遇到麻烦的一个部分是分析在给定玩家拥有的火车卡 list 的情况下是否可能通过棋盘的特定路径。我认为它本身更像是一个数学问题而不是编程问题，我可能可以拼凑出一种蛮力方法来解决问题，但我认为必须有一种更有效的方法。

对于那些不了解游戏的人:在任何给定时间，每个玩家都有八种颜色之一的多张火车卡，外加一个特殊的“机车”类别作为通配符。这些颜色对应于游戏板上火车线的颜色 (shown here)，灰色线除外，您可以使用任何颜色，只要该段中的所有车厢颜色相同即可。 (有涉及隧道和渡轮的边缘案例，但我们暂时将它们放在一边。)

使用现在的代码，我可以找到两个给定城市之间的所有路径，并返回走那条特定路径需要每种颜色的火车卡数量，除非路径涉及灰色部分。我首先处理非灰色部分，因为它们更直接——要么你有足够的红色/绿色/蓝色卡片用于路径中的每个红色/绿色/蓝色部分，要么你没有。对于灰色，因为您可以选择任何颜色用于每个部分，所以它会更加复杂。

对于只有一个灰色部分的路径，它仍然很容易——要么你有足够的任何一种颜色的卡片来填充它，要么不填充它。但是，对于多个灰色段，可能会遇到这样的情况:为第一个段选择的颜色使得无法完成第二个或第三个段。

举个例子，假设玩家的卡牌库存为 4 红、2 绿、3 蓝，我们想知道他是否可以从巴黎到达维也纳。查看棋盘，很容易看出此卡组合的唯一可能路线是去巴黎 --(3 灰色)--> 苏黎世 --(2 绿色)--> 威尼斯 --(2 灰色)--> Zagrad --(2 灰色)--> 维也纳。我解决这个问题的算法从绿色部分开始，并在那里分配两张绿卡。然后需要决定如何使用剩下的4张红卡和3张蓝卡来覆盖长度为3、2、2的灰色段。

答案当然是使用巴黎和苏黎世之间的 3 张蓝卡，威尼斯到扎格勒和萨格勒到维也纳各使用 2 张红卡。但是，对于涉及更多颜色和更多段的不太明显的情况，如何编写解决此问题的通用算法？

我现在的代码如下所示:

def can_afford(path, cards):
    grays = list()
    for segment in path:
        if segment.color == 'Gray':
            grays.append(segment)
        else:
            if cards.get(segment.color, 0) >= segment.weight:
                cards[segment.color] -= segment.weight
            else:
                return False
    for gray in grays:
        # Halp!
        pass
    return True

(“重量”是火车车厢的长度。)

我觉得这里潜伏着一个非常微不足道的解决方案，我无法确定。有什么想法吗？

Answer 1

正如 Daniel Brückner 所说，找到一种方法将卡片颜色分配给灰色段的问题对应于 bin packing problem ，彩色卡片组对应垃圾箱，灰色部分对应待包装的元素。

现在，装箱问题是NP-hard , 但在这种情况下这不是灾难，因为问题可以在 pseudo-polynomial time 中解决。 (也就是说，时间是容器大小的多项式)使用 dynamic programming ，这对您的应用程序来说应该足够好了，其中垃圾箱的大小受游戏中卡片数量的限制。这是装箱的示例实现，使用 @functools.lru_cache decorator记住它:

从 functools 导入 lru_cache

@lru_cache(maxsize=None)
def packing(bins, objects):
    """Return a packing of objects into bins, or None if impossible. Both
    arguments are tuples of numbers, and the packing is returned in
    the form of a list giving the bin number for each object.

    >>> packing((4,5,6), (6,5,4))
    [2, 1, 0]
    >>> packing((4,5,6), (1,1,2,4,5))
    [0, 0, 0, 1, 2]

    """
    if not objects:
        return []
    o = objects[0]
    rest = objects[1:]
    for i, b in enumerate(bins):
        if o <= b:
            p = packing(bins[:i] + (b - o,) + bins[i+1:], rest)
            if p is not None:
                return [i] + p
    return None

这可用于确定是否可以在 Ticket to Ride 中遵循路径:

def can_afford(path, cards):
    """Return True if path can be followed using cards, False if not.
    cards might be updated, so pass a copy if you don't want that to
    happen.

    """
    grays = []
    for segment in path:
        c, w = segment.color, segment.weight
        if c == 'Gray':
            grays.append(w)
        elif cards.get(c, 0) >= w:
            cards[c] -= w
        else:
            return False
    return packing(tuple(cards.values()), tuple(grays)) is not None

请注意，如果您制作了卡片 collection.Counter , 那么你可以只写 cards[c] 而不是 cards.get(c, 0)。