Stuck on this function

Question

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): {}}}}
    """

i've been trying to solve this function but i'm kinda stuck. I know how to write the general structure but have no idea how to get the number correctly. Can someone help implement

this is what I've done:

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

and the error messages are

Failed example: d

Expected:

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

Got:

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

Answer 1

You were on the right track with nested for-loops, but

    num_ended_games = 0 ## beginning of loop

        key = (move, num_ended_games)
        if key not in current_dict:

    num_ended_games += 1 ## end of loop

Incrementing num_ended_games at the end of loop without setting it anywhere does not update it in the result dictionary. To change a dictionary key you need to set the old value to the new key and del or .pop the old key. Also, keep in mind that tuples are not mutable in python, so to change one value in a tuple, you need to replace the whole tuple...

Try something like the version of moves_to_nested_dict below. ^{(view example outputs)}

def moves_to_nested_dict(moves: list[list[str]]) -> dict[tuple[str,int], dict]:
    result = {}
    for game_moves in moves:
        cur_dict = result

        for reverse_index, move in enumerate(game_moves, 1-len(game_moves)):
            cur_key = [k for k in cur_dict if k[0]==move]            
            if not cur_key: cur_dict[(cur_key := (move, 0))] = {}
            else: cur_key = cur_key[0]
            
            if not reverse_index: ## <-- reverse_index=0 on last move
                cur_dict[(move, cur_key[1]+1)] = cur_dict.pop(cur_key)
            else: cur_dict = cur_dict[cur_key]
    return result

^{[Using enumerate with start=1-len makes reverse_index count starting from 1-len and ending at 0 - so we can use that to keep track of how many moves are left and when we're on the last move; and the walrus operator (:=) is just a handy way of defining/updating and using a variable in one statement instead of needing an extra line to set it first before using it.]}

---

Btw, this would be much simpler if num_ended_games was a value inside the dictionary so that just move could be used as the key, and you could just use .setdefault instead of needing to check for and sometimes update the key:

def moves_to_nested_dict(moves: list[list[str]]) -> dict[str,dict]:
    result = {}
    for game in moves:
        cur_dict = result
        for move in game: 
            cur_dict = cur_dict.setdefault(move, {'__games_ended__':0}) # (move,{})
        if game: cur_dict['__games_ended__'] = cur_dict.get('__games_ended__',0)+1
    return result

^{[Using <dict>.get(<key>) is safer than <dict>[<key>] when you can't be sure that the key exists.]}

With this version,

moves_to_nested_dict([['a','b'], ['a','b'], ['a','b','c'], ['d','a'], ['a','d']])

would return

{
  'a': {
    '__games_ended__': 0,
    'b': {'__games_ended__': 2, 'c': {'__games_ended__': 1}},
    'd': {'__games_ended__': 1}
  },
  'd': {'__games_ended__': 0, 'a': {'__games_ended__': 1}}
}