sprouts.py

import collections
import tkinter as tk


def find_shortest_chains(graph: dict[int, list[int]], must_contain: list[int] | None = None, contain_any: list[list[int]] | None = None) -> list[list[int]]:
    """
    Finds the smallest chain within the game data.
    :param graph: Data for a game of sprouts
    :type graph: list[list[int]]
    :return: The smallest chain within the game data.
    :rtype: list[list[int]]
    """
    
    if must_contain is None:
        must_contain = []
    if contain_any is None:
        contain_any = []

    min_cycle_len = float('inf')
    shortest_cycles = []
    found_cycles_canonical = set()

    for start_node in graph:
        distances = {start_node: 0}
        parents: dict[int, int | None] = {start_node: None}
        queue = collections.deque([start_node])

        while queue:
            u = queue.popleft()
            for v in graph.get(u, []):
                if v not in distances:
                    distances[v] = distances[u] + 1
                    parents[v] = u
                    queue.append(v)
                elif v != parents[u]:
                    cycle_len = distances[u] + distances[v] + 1
                    if cycle_len < min_cycle_len:
                        min_cycle_len = cycle_len
                        shortest_cycles = []
                        found_cycles_canonical = set()

                    if cycle_len == min_cycle_len:
                        path_u = []
                        curr = u
                        while curr is not None:
                            path_u.append(curr)
                            curr = parents[curr]

                        path_v = []
                        curr = v
                        while curr is not None:
                            path_v.append(curr)
                            curr = parents[curr]

                        common_ancestor = None
                        while path_u and path_v and path_u[-1] == path_v[-1]:
                            common_ancestor = path_u.pop()
                            path_v.pop()

                        cycle = path_u + [common_ancestor] + list(reversed(path_v))
                        if must_contain and not all(node in cycle for node in must_contain):
                            continue
                        
                        valid = True
                        for nodes in contain_any:
                            if not any(node in cycle for node in nodes):
                                valid = False
                                break
                            
                        if not valid:
                            continue

                        canonical_form = frozenset(cycle)
                        if canonical_form not in found_cycles_canonical:
                            shortest_cycles.append(cycle)
                            found_cycles_canonical.add(canonical_form)

    return shortest_cycles


def reorder_cycle(cycle: list[int]) -> list[int]:
    future_first = cycle.index(min(cycle))
    return cycle[future_first:] + cycle[:future_first]


def remove_nodes_from_graph(graph: dict[int, list[int]], nodes: list[int]) -> dict[int, list[int]]:
    for node in nodes:
        graph.pop(node)

    for node, connections in graph.items():
        for node_to_remove in nodes:
            if node_to_remove in connections:
                graph[node].remove(node_to_remove)

    return graph


def sprout_game_data_to_sprout_pattern(sprout_game_data: dict[int, list[int]]) -> tuple[list[list[int]], dict[int, list[int]], list[list[int]]] | None:
    """
    cleans up game data to a clean sprout position.
    The end position is saved, but the entire game can't be reconstructed.
    :param sprout_game_data: Data for a game of sprouts
    :type sprout_game_data: list[list[int]]
    :return: A clean sprout position
    :rtype: list[list[int]]
    """
    
    graph = sprout_game_data.copy()
    all_cycles = []
    shortest_cycles = []
    while len(graph) > 0:
        shortest_cycles = find_shortest_chains(graph)
        if not shortest_cycles:
            break
        
        # check that there are no cycles that share one or more nodes with another cycle
        # if there are, remove them from the the list of shortest cycles
        cycles_to_remove = []
        for cycle1 in shortest_cycles:
            for cycle2 in shortest_cycles:
                if cycle1 == cycle2 or cycle1 in cycles_to_remove or cycle2 in cycles_to_remove:
                    continue
                
                if any(node in cycle1 for node in cycle2):
                    cycles_to_remove.append(cycle2)
                    
        shortest_cycles = [cycle for cycle in shortest_cycles if cycle not in cycles_to_remove]

        shortest_cycles = [reorder_cycle(cycle) for cycle in shortest_cycles]
        all_cycles.extend(shortest_cycles)
        for cycle in shortest_cycles:
            graph = remove_nodes_from_graph(graph, cycle)
            
    remaining_nodes = list(graph.keys())
    
    uniting_cycles = find_shortest_chains(
        sprout_game_data,
        must_contain=remaining_nodes,
        contain_any=all_cycles
    )
    uniting_cycle = [reorder_cycle(cycle) for cycle in uniting_cycles]
    if not uniting_cycle:
        print("No uniting cycle found")
        #return
    
    #uniting_cycle = uniting_cycle[0]
    
    print(all_cycles)
    print(remaining_nodes)
    print(uniting_cycle)
    
    '''
    root = tk.Tk()
    root.title('Sprout Game Visualization')
    root.geometry('400x400')
    
    canvas = tk.Canvas(root, width=400, height=400)
    
    root.mainloop()'''

    return shortest_cycles, graph, uniting_cycle


sprout_game_data1 = {
    1: [3, 4, 6],
    2: [3, 5, 7],
    3: [1, 2, 4],
    4: [1, 3, 5],
    5: [2, 4, 6],
    6: [1, 5, 7],
    7: [2, 6]
}
sprout_game_data2 = {
    1: [3, 5],
    2: [4, 6],
    3: [1, 5],
    4: [2, 7],
    5: [1, 3, 6],
    6: [2, 5, 7],
    7: [4, 6]
}
sprout_game_data3 = {
    1: [3, 4, 6],
    2: [3, 4],
    3: [1, 2, 5],
    4: [1, 2, 5],
    5: [3, 4, 6],
    6: [1, 5]
}
sprout_game_data4 = {
    1: [2, 4],
    2: [3, 1],
    3: [4, 2],
    4: [1, 3]
}
sprout_game_data_to_sprout_pattern(sprout_game_data2)