求助实现moves_to_nested_dict函数：计数逻辑错误修正

原函数定义 #

def moves_to_nested_dict(moves: list[list[str]]) -> dict[tuple[str, int], dict]:
    """
    Convert <games> into a nested dictionary representing the sequence of moves
    made in the games.

    Each list in <games> corresponds to one game, with the i'th str being the
    i'th move of the game.

    The nested dictionary's keys are tuples containing the string representing
    the move made on that turn and an integer indicating how many games ended
    immediately after this move. See the docstring example below.

    The values of each nested dictionary are themselves nested dictionaries of
    this structure. An empty dictionary is stored as the value for a move that
    will correspond to a leaf

    Note: to keep the docstring short, we use single letters in place
          of real chess moves, as it has no impact on the logic of how this
          code needs to be implemented, since it should work for arbitary
          strings used to denote moves.


    >>> moves_to_nested_dict([[]])  # empty lists are ignored
    {}
    >>> moves_to_nested_dict([])
    {}
    >>> moves_to_nested_dict([['a'], []])
    {('a', 1): {}}
    >>> d = moves_to_nested_dict([["a", "b", "c"],
    ...                           ["a", "b"], ["d", "e"], ["d", "e"]])
    >>> d
    {('a', 0): {('b', 1): {('c', 1): {}}}, ('d', 0): {('e', 2): {}}}
    >>> d = moves_to_nested_dict([
    ...    ["a", "b", "c"], ["a", "b"], ["d", "e", "a"], ["d", "e"]])
    >>> d
    {('a', 0): {('b', 1): {('c', 1): {}}}, ('d', 0): {('e', 1): {('a', 1): {}}}}
    """

我的实现代码 #

result = {}
for game_moves in moves:
    if len(game_moves) == 0:
        continue
    current_dict = result
    num_ended_games = 0
    for move in game_moves[:-1]:
        key = (move, num_ended_games)
        if key not in current_dict:
            current_dict[key] = {}
        current_dict = current_dict[key]
        num_ended_games = 0
    last_move = game_moves[-1]
    key = (last_move, num_ended_games)
    if key not in current_dict:
        current_dict[key] = {}
    current_dict = current_dict[key]
    num_ended_games += 1
return result

错误情况 #

测试用例：

d = moves_to_nested_dict([["a", "b", "c"], ["a", "b"], ["d", "e"], ["d", "e"]])

预期输出：

{('a', 0): {('b', 1): {('c', 1): {}}}, ('d', 0): {('e', 2): {}}}

实际输出：

{('a', 0): {('b', 0): {('c', 0): {}}}, ('d', 0): {('e', 0): {}}}

问题分析与修正方案 #

你的代码核心问题是计数逻辑未正确关联到字典的键上：num_ended_games变量仅在局部循环中变化，从未更新到已存在的字典键中；且所有非最后一步的move都被硬编码为计数0，最后一步也未累加计数。

正确的思路是：每个层级中，同一个move只能对应一个键（(move, count)），其中count是有多少个游戏在执行该move后直接结束。遍历每个游戏时，需要追踪当前路径，对每一步（包括最后一步）的计数进行更新：

1. 对于游戏中的每一步，先检查当前字典层级中是否已存在以该move为第一个元素的键
2. 如果是最后一步，若该键存在则将计数加1，替换原键；若不存在则创建(move, 1)的键
3. 如果不是最后一步，若该键不存在则创建(move, 0)的键，直接进入对应子字典

修正后的代码：

def moves_to_nested_dict(moves: list[list[str]]) -> dict[tuple[str, int], dict]:
    result = {}
    for game_moves in moves:
        if not game_moves:
            continue
        current_dict = result
        total_steps = len(game_moves)
        for idx, move in enumerate(game_moves):
            is_last_step = (idx == total_steps - 1)
            # 查找当前层级中是否已有该move的键
            existing_key = None
            for key in current_dict:
                if key[0] == move:
                    existing_key = key
                    break
            if existing_key:
                if is_last_step:
                    # 最后一步，计数加1，替换原键
                    old_move, old_count = existing_key
                    new_count = old_count + 1
                    # 取出子字典，删除旧键，添加新键
                    sub_dict = current_dict.pop(existing_key)
                    current_dict[(old_move, new_count)] = sub_dict
                    current_dict = sub_dict
                else:
                    # 非最后一步，直接进入子字典
                    current_dict = current_dict[existing_key]
            else:
                # 不存在该move的键，创建新键
                count = 1 if is_last_step else 0
                current_dict[(move, count)] = {}
                current_dict = current_dict[(move, count)]
    return result

验证结果 #

运行测试用例，输出与预期完全一致：

# 测试用例1
d = moves_to_nested_dict([["a", "b", "c"], ["a", "b"], ["d", "e"], ["d", "e"]])
print(d)
# 输出: {('a', 0): {('b', 1): {('c', 1): {}}}, ('d', 0): {('e', 2): {}}}

# 测试用例2
d = moves_to_nested_dict([["a", "b", "c"], ["a", "b"], ["d", "e", "a"], ["d", "e"]])
print(d)
# 输出: {('a', 0): {('b', 1): {('c', 1): {}}}, ('d', 0): {('e', 1): {('a', 1): {}}}}

内容的提问来源于stack exchange，提问作者kakuro