创建一个字典列表，其中每个字典都包含另一个字典作为值

Question

我正在使用Python编写一个算法，用于玩this游戏。

游戏中瓷砖的当前状态是以字典形式表示的：

{
    <tile_id>: {
                'counters': <number of counters on tile or None>,
                'player': <player id of the player who holds the tile or None>,
                'neighbours': <list of ids of neighbouring tile>
               },
               ...
}

我有另一个字典，存储所有“满”的瓷砖（即具有比其邻居少一个计数器且player为我自己的瓷砖）。这个名为full_tiles的字典与上面的board字典形式相同。

我现在正在尝试创建一个列表chains，其中列表中的每个元素都是我的至少与一个其他满瓷砖相邻的满瓷砖的字典（即一系列满瓷砖）。因此，这将是我在棋盘上所有单独链的列表。

以下是我目前的代码：

for tile_id, tile in full_tiles.items(): #iterates through all full tiles
    current_tile = {tile_id : tile}      #temporarily stores current tile
    if not chains:                       #if chains list is empty
        chains.append(current_tile)      #begin list
    else:                                #if list is not empty
        for index, chain in enumerate(chains):            #iterate though list of chains
            if not (current_tile in chain):               #if current tile is not in current chain
                for tile_id2, tile2 in chain.items():     #iterate through tiles in current chain
                    for neighbour in tile2["neighbours"]: #iterate through each neighbour of current tile
                                                          #neighbour is in the form of tile_id
                        if neighbour in chain:            #if current tile's neighbour is in chain
                            chain[tile_id] = tile         #add tile to chain

由于代码只能在模拟游戏的应用程序中运行，因此对我来说很难测试、调试和检查其是否正常工作。如您所见，这个代码块中有许多嵌套循环，很难跟进。此刻我无法集中思维，无法确定这个混乱的代码是否会按照我的期望正常运行。

在我写这篇文章时，我刚刚意识到——在代码的第7行——我只检查当前图块是否不在当前链中，因此会有相交的链，这当然会是一团糟。我需要首先检查当前图块是否不在任何链中，而不仅仅是一个链。

除了这个错误之外，我的代码能否实现我想要的目标？或者您能否推荐一种更简单、更整洁的方法？（一定有！）

如果我没有提供关于如何运行代码或需要进一步解释的任何信息（例如board字典的内容），请告诉我。

提前感谢您的任何帮助。

编辑：不幸的是，由于时间限制，我必须完成这个项目，而且这是我第一次使用Python工作，目前我缺乏使用下面给出的资源来优化我的解决方案所需的语言知识。这是我的最终非常丑陋和混乱的解决方案，最终可以正常工作，并且在代码处理的小数据集上效率不太低。

for x in range(0, len(my_hexplode_chains) - 1):
    match_found = False
    for y in range(x + 1, len(my_hexplode_chains)):
        for tile_id_x, tile_x in my_hexplode_chains[x].items():             #compare each chain in list
            for tile_id_y, tile_y in my_hexplode_chains[y].items():         #to every other chain
                for neighbour in tile_x["neighbours"]:                      #if tiles in different lists
                    if neighbour == tile_id_y:                              #are neighbours
                        match_found = True
                        my_hexplode_chains[x].update(my_hexplode_chains[y]) #append one chain to the other
                        del my_hexplode_chains[y]                           #delete appended chain
                if match_found:                                             #continue loop at next chain
                    break                                                   #very ugly way to do this
            if match_found:
                break
        if match_found:
            break
    if match_found:
        break

- KOB

---

这是一个图问题。在Python中，图最容易表示为节点和邻接列表对的字典。你可以很简单地使用推导式来完成这个任务。 - erip

@erip 很不幸，我对Python完全是新手，只是为了完成这个挑战才开始学习它。我真的不太理解你所推荐的内容，但我现在会去研究一下。谢谢。 - KOB

绝对不是不幸的。 :) 很高兴看到你在学习！这是关于推导式的一个相当不错的描述。如果你熟悉数学中的集合构建符号，那么它与那个类似。 - erip

文档中还有一个非常好的图形实现描述。不过，你需要进行一些修改。你可能想要实现一个Tile类，并将其映射到一个Tile列表。 - erip

@mabe02 是的，我当时时间很紧，而且这是我第一次使用Python。我对这种语言及其数据结构的理解还不足以从erip提供的源代码中得出解决方案。我的最终解决方案与我在问题中提供的方法类似。它是一段非常丑陋和混乱的代码，但它完美地工作，并且效率并不是特别低下。你为什么问这个？ - KOB

Answer 1

这个优化怎么样？

def find_match (my_hexplode_chains):

    x =  0
    len_chain = len(my_hexplode_chains)
    while x <= len_chain:
        y = x + 1
        for tile_id_x, tile_x in my_hexplode_chains[x].items():
            for tile_id_y, tile_y in my_hexplode_chains[y].items():
                if tile_id_y in tile_x["neighbours"]:
                    my_hexplode_chains[x].update(my_hexplode_chains[y])
                    del my_hexplode_chains[y]
                    return True
        x += 1
    return False

你可以在游戏中的每个移动之后通过此函数并跟踪输出。

- mabe02

---

这是目前为止最好、最高效的解决方案，但我相信一定有一种使用某些数据结构更少混乱的方式来构建它。 - KOB