secret_santa.py

import random


class PersonNode:
    def __init__(self, name=None, eligible_nodes=None, exclusions=None):
        self.name = name
        self.eligible_nodes = eligible_nodes if eligible_nodes is not None else []
        self.exclusions = exclusions if exclusions is not None else set()


def pretty_print(nodes):
    for i, node in enumerate(nodes):
        print(f"{node.name} has drawn {nodes[(i + 1) % len(nodes)].name}'s name")


def create_graph_nodes(name_list):
    nodes = []
    for person in name_list:
        nodes.append(
            PersonNode(name=person["name"], exclusions=set(person["exclusions"]))
        )

    for node in nodes:
        node.eligible_nodes = [
            person
            for person in nodes.copy()
            if person.name != node.name and person.name not in node.exclusions
        ]

    return nodes


def draw_names(name_list):
    nodes = create_graph_nodes(name_list)
    start = random.choice(nodes)

    result = None
    visited = set()

    def traverse(cur, path=[]):
        visited.add(cur)
        path.append(cur)

        nonlocal result
        if result != None:
            return

        if len(path) == len(nodes) and start in cur.eligible_nodes:
            result = path[:]
            return

        for node in cur.eligible_nodes:
            if node not in visited:
                traverse(node, path)
                path.pop()
                visited.remove(node)

    traverse(start)
    pretty_print(result)


example_list = [
    {"name": "Todd", "exclusions": ["Keith", "Irina", "Sheena"]},
    {"name": "Keith", "exclusions": ["Todd", "Phoebe"]},
    {"name": "Phoebe", "exclusions": ["Ash"]},
    {"name": "Kurt", "exclusions": ["Travis"]},
    {"name": "Irina", "exclusions": ["John", "Kurt"]},
    {"name": "John", "exclusions": ["Irina", "Clarence"]},
    {"name": "Clarence", "exclusions": ["Stephanie", "Travis"]},
    {"name": "Travis", "exclusions": ["Todd", "Clarence"]},
    {"name": "Ash", "exclusions": ["Irina", "Keith", "Todd"]},
    {"name": "Helga", "exclusions": ["Irina", "John"]},
    {"name": "Stephanie", "exclusions": ["Keith"]},
    {"name": "Sheena", "exclusions": ["John"]},
]

draw_names(example_list)