algo.py

from collections import Counter
from itertools import combinations
from pprint import pprint


def get_famous_point(data):
    list_of_points = [point for inner_list in data for point in inner_list]
    return Counter(list_of_points).most_common()[0][0]


def get_green_list_of_lists(point, data):
    green_list_of_lists = [inner_list for inner_list in data if point in inner_list]
    return green_list_of_lists


def convert_green_list_of_lists_to_set(green_list_of_lists):
    set_of_green_points = list(set([point for inner_list in green_list_of_lists for point in inner_list]))
    return set_of_green_points


def check_unique_green(set_of_green_points, red_list_of_lists_with_green):
    green_unique_list_of_lists = []

    for inner_list in red_list_of_lists_with_green:
        counter = 0

        if len(inner_list) == 1:
            if inner_list[0] not in set_of_green_points:
                counter = 1
        else:
            for point in set_of_green_points:
                if point in inner_list:
                    counter += 1

        if counter == 1:
            green_unique_list_of_lists.append(inner_list)

    return green_unique_list_of_lists


def update_lists(green_unique_list_of_lists, green_list_of_lists, red_list_of_lists):
    for _list in green_unique_list_of_lists:
        green_list_of_lists.append(_list)
        red_list_of_lists.remove(_list)

    for inner_list in list(red_list_of_lists):
        if not has_red_point(inner_list, green_list_of_lists):
            red_list_of_lists.remove(inner_list)

    return green_list_of_lists, red_list_of_lists


def has_red_point(check_list, g_list_of_lists):
    for point in check_list:
        if point not in convert_green_list_of_lists_to_set(g_list_of_lists):
            return True
    else:
        return False


def get_all_combinations(list_of_lists):
    tmp = []
    for r_list in list_of_lists:
        if len(r_list):
            _tmp = [list(combination) for combination in combinations(r_list, len(r_list)-1)]
            if _tmp not in tmp:
                    tmp.extend(_tmp)

    return tmp


def remove_duplicate(list_of_lists):
    tmp = []
    for _list in list_of_lists:
        if _list not in tmp:
            tmp.append(_list)
    return tmp



def logic(point, green, red):
    if green:
        set_of_unique_points = convert_green_list_of_lists_to_set(green)
    else:
        set_of_unique_points = [point]

    red_with_green_points = get_green_list_of_lists(point, red)
    g_unique_list_of_lists = check_unique_green(set_of_unique_points, red_with_green_points)
    if len(g_unique_list_of_lists):
        update_lists(g_unique_list_of_lists, green, red)


inputs = [['v', '0', '1'],
          ['v', '1', '2'],
          ['v', '2', '3'],
          ['v', '3', '4'],
          ['v', '4', '0'],
          ['0', '1', 'b'],
          ['0', '5', 'b'],
          ['b', '6', '7'],
          ['b', '7', 'a'],
          ['2', '10', '3'],
          ['1', '9', 'a'],
          ['7', '11']]

# inputs = [['6', '5', '1'],
#           ['5', '3', '1'],
#           ['3', '2', '1'],
#           ['2', '6', '1'],
#           ['4', '3', '2'],
#           ['4', '6', '2'],
#           ['5', '4', '6']]

# inputs = [['3', '6'],
#      ['2', '6'],
#      ['5', '4', '1'],
#      ['2', '1'],
#      ['4', '2'],
#      ['3', '2'],
#      ['3', '4']]
#
# inputs = [
#     ['4', '2'],
#     ['3', '2', '7'],
#     ['3', '4'],
#     ['3', '6'],
#     ['5', '4', '1'],
#     ['2', '1']
# ]

print('### input #### ')
print(inputs)

results = []

while True:
    g_list_of_lists = []
    r_list_of_lists = list(inputs)

    # init
    famous_point = get_famous_point(inputs)
    logic(famous_point, g_list_of_lists, r_list_of_lists)

    while r_list_of_lists:
        has_been_checked = []
        while sorted(has_been_checked) != sorted(convert_green_list_of_lists_to_set(g_list_of_lists)):
            # while r_list_of_lists:
            check_list = convert_green_list_of_lists_to_set(g_list_of_lists)
            for _point in check_list:
                if _point not in has_been_checked:
                    logic(_point, g_list_of_lists, r_list_of_lists)
                    has_been_checked.append(_point)

        tmp = []
        for r_list in r_list_of_lists:
            if len(r_list):
                tmp.extend([list(combination) for combination in combinations(r_list, len(r_list) - 1)])
        r_list_of_lists = tmp

    # print(g_list_of_lists)
    # print('######################')


    r_list_of_lists = [inner_list for inner_list in inputs if inner_list not in g_list_of_lists]
    # print(r_list_of_lists)

    no_way_to_move_to_g = []

    while r_list_of_lists:
        _g_compinations = get_all_combinations(g_list_of_lists)
        _tmp = g_list_of_lists + _g_compinations
        g_list_of_lists_compinations = remove_duplicate(_tmp)

        for r_list in list(r_list_of_lists):
            if len(r_list) <= 2:
                no_way_to_move_to_g.append(r_list)
                r_list_of_lists.remove(r_list)
                break
            g_points = convert_green_list_of_lists_to_set(g_list_of_lists)
            exiting_g_points = []
            for g_point in g_points:
                if g_point in r_list:
                    exiting_g_points.append(g_point)

            if len(exiting_g_points) < 2: # this r_list doesnt have two g points
                no_way_to_move_to_g.append(r_list)
                r_list_of_lists.remove(r_list)

            else:
                for g_vector in [list(combination) for combination in combinations(exiting_g_points, 2)]:
                    if g_vector in inputs:
                        no_way_to_move_to_g.append(r_list)
                        r_list_of_lists.remove(r_list)
                        break
                    else:
                        tmp_r_list_0 = [point for point in r_list if point != g_vector[0]]
                        tmp_r_list_1 = [point for point in r_list if point != g_vector[1]]

                        if (tmp_r_list_0 in g_list_of_lists_compinations) and (tmp_r_list_1 in g_list_of_lists_compinations):
                            g_list_of_lists.append(r_list)
                            r_list_of_lists.remove(r_list)
                            break
                else: # no vector can solve it
                    no_way_to_move_to_g.append(r_list)
                    r_list_of_lists.remove(r_list)



    # print(f'###### cover set number one with famous point {famous_point} ######')
    # print(g_list_of_lists)
    # print('###### no way to convert to green ######')
    # print(no_way_to_move_to_g)

    results.append(
        {"set": g_list_of_lists,
         "famous": famous_point}
    )

    inputs = list(no_way_to_move_to_g)
    if len(no_way_to_move_to_g) == 0:
        break

for index in range(0, len(results)):
    print(f"### cover set number {index+1}: ### ")
    pprint(results[index])