Secret santa: backtracking

backtracking.py

from typing import List, Optional
from players_info import ListOfPlayerInfo


def _backtrack(possible_ids: List[List[int]],
               current_id_chain: List[int]) -> bool:
    """
    Explore all possible paths by iterating over players' possibilities.
    """
    if len(current_id_chain) == len(possible_ids):
        if current_id_chain[0] in possible_ids[current_id_chain[-1]]:
            return True
    else:
        for idx in possible_ids[current_id_chain[-1]]:
            if not idx in current_id_chain:
                current_id_chain.append(idx)
                if _backtrack(possible_ids, current_id_chain):
                    return True
                current_id_chain.pop()
    return False


def solve(players: ListOfPlayerInfo) -> Optional[List[int]]:
    """
    Find a connected path among the players.
    """
    possible_ids = _init_possible_recipients(players)
    possible_ids = _refine_possible_recipients(possible_ids)

    id_chain = [0]
    if not _backtrack(possible_ids, id_chain):
        return None

    print("Solution: {}".format(" -> ".join([players[idx].name for idx in id_chain])))
    return id_chain