algo_solution.py

#!/usr/bin/python3
from random import sample

voisines1 = [[1, 2], [0, 2, 4], [0, 1, 3, 5], [2, 4], [1, 3, 5], [2, 4]]
voisines2 = [[1, 2], [0, 2, 4], [0, 1, 5], [2, 4], [1, 5], [2, 4, 3]]
voisines3 = [[1, 2], [0, 2, 4], [0, 1, 5], [2, 5], [1, 5], [2, 4, 3]]
voisines4 = [[1, 2], [0, 2, 4], [0, 1, 5], [2, 4], [1, 5], [2, 4]]

def bad_solution(neightbors, timer=50):
    '''
    Global usage: We will try to generate a graph by traveling our tops and try to add it if:
        * the top is not adjacents to our tops found
    If our solution isn't found we will try again...
    '''
    if timer < 10:
        timer = 10
    # best_graph will contain our best graph found
    best_graph = list()
    for _ in range(timer):
        # adj will contain our adjacents to our points in grap
        adj = list()
        # graph will contain our current solution
        graph = list()
        # indexes will be our indexes list shuffled
        indexes = sample(range(0, len(neightbors)), len(neightbors))
        for j in indexes:
            if j not in adj:
                graph.append(j)
                for neightbor in neightbors[j]:
                    if neightbor not in adj:
                        adj.append(neightbor)
            for k in range(0, len(neightbors)):
                if k not in graph and k not in adj:
                    break
        found = True
        k = 0
        # We will check if every top is in graph or adj, else it means we didn't find a solution
        while k < len(neightbors) and found:
            if k not in graph and k not in adj:
                found = False
            k += 1
        if found and (len(best_graph) == 0 or len(graph) < len(best_graph)):
            best_graph = graph
    print(best_graph)

bad_solution(voisines1)
bad_solution(voisines2)
bad_solution(voisines3)
bad_solution(voisines4)