## Packages utilisés

- tqdm
- operator
- copy
- random
- numpy

# Pizza Gate

solution globale : `python ficher.py --input-file a_example`

from tqdm import tqdm
from operator import attrgetter
import numpy as np
import copy

class Pizza():
    
    def __init__(self, pizza_id, num_ingredients, list_ingredients):
        self.pizza_id = pizza_id
        self.num_ingredients = num_ingredients
        self.list_ingredients = list_ingredients
        
    def __repr__(self):
        representation = "Pizza:"
        representation += "\n  id : \t"+str(self.pizza_id)
        representation += "\n  num : \t"+str(self.num_ingredients)
        representation += "\n  ing : \t"+str(self.list_ingredients)
        return representation
    
    @classmethod
    def from_line(cls, line, line_id):
        line_data = line.split()
        num_ingredients = int(line_data[0])
        list_ingredients = line_data[1:]
        return cls(line_id, num_ingredients, list_ingredients)

class PizzaProblem():
    def __init__(self, num_pizzas, num_t2, num_t3, num_t4):
        self.num_pizzas = int(num_pizzas)
        self.num_t2 = int(num_t2)
        self.num_t3 = int(num_t3)
        self.num_t4 = int(num_t4)
    
    def __repr__(self):
        representation = "Problem:"
        representation += "\npizzas:\t"+str(self.num_pizzas)
        representation += "\nnum T2:\t"+str(self.num_t2)
        representation += "\nnum T3:\t"+str(self.num_t3)
        representation += "\nnum T4:\t"+str(self.num_t4)
        return representation

def get_data(input_file):
    frigo = []
    with open(input_file, "r") as file:

        problem_data = file.readline()

        pizza_gate = PizzaProblem(*problem_data.split())

        for idx, line in enumerate(file):
            pizza_eclatax = Pizza.from_line(line, idx)
            frigo.append(pizza_eclatax)
    return frigo, pizza_gate

def sort_by_max_ingredients(pizza_list):
    from operator import  attrgetter
    pizza_list.sort(reverse=True, key=attrgetter("num_ingredients") )
    
    return pizza_list

def sort_by_max_compat(chosen_pizzas, pizza_list):
    pizza_list.sort(reverse=True, key=lambda x: pizza_compatibility(chosen_pizzas, x) )
    
    return pizza_list

def pizza_compatibility(pizza_list, challenger_pizza):
    
    # Get ingredient of challenger_pizza
    challenger_ingr = challenger_pizza.list_ingredients
    
    # Check if already existing pizza is list or Pizza
    if type(pizza_list) == list :
        existing_ingr = []
        for piz in pizza_list:
            existing_ingr += piz.list_ingredients
    elif isinstance(pizza_list,Pizza):
        existing_ingr = pizza_list.list_ingredients
        
    # Remove duplicates
    existing_ingr = set(existing_ingr)
    challenger_ingr = set(challenger_ingr)
    
    improvement = (len(challenger_ingr) - len(challenger_ingr.intersection(existing_ingr)))/len(challenger_ingr)
        
    return improvement
    
def mon_heuristique_eclatee(pizza_list, problem_class):
    
    print("la magie opère ici")
    solution = []
    sorted_pizza = sort_by_max_ingredients(pizza_list)
    
    for num_team, team_size in zip([problem_class.num_t4, problem_class.num_t3, problem_class.num_t2],[4,3,2]):
        print("===== team of",team_size)
        print("===== ",num_team,"to process")

        for team in tqdm(range(num_team)):

            tempo_pizza_sol = []
            if len(sorted_pizza) == 0: break
            best_pizza = sorted_pizza.pop(0)
            tempo_pizza_sol.append(best_pizza)
            
            for remaning_pizza in range(team_size-1):
                # Get best pizza
                if len(sorted_pizza) == 0: break

                best_pizza = max(sorted_pizza, key=lambda x: pizza_compatibility(tempo_pizza_sol,x))
                # remove best pizza from list
                sorted_pizza.pop(sorted_pizza.index(best_pizza))
                tempo_pizza_sol.append(best_pizza)
                
            solution.append(str(team_size)+' '+' '.join([str(x.pizza_id) for x in tempo_pizza_sol]))
    return solution



def consolidate_results(solution):
    definitive_solution = []
    shipped_pizzas = 0
    for idx, sol in enumerate(solution):
        data = sol.split()
        if int(data[0]) == len(data[1:]):
            definitive_solution.append(sol)
            shipped_pizzas += int(data[0])
            
    return definitive_solution, shipped_pizzas     

def format_resutlts(solution, input_file):
    with open('./outputs/'+input_file.split('/')[-1]+'.out','w') as file:
        file.write(str(len(solution)))
        for sol in solution:
            file.write('\n'+sol)
        file.write('\n')


if __name__ == "__main__":

    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument("--input-file", type=str)
    args = parser.parse_args()

    print(args.input_file.split('/')[2])
    frigo, pizza_gate = get_data(args.input_file)
    pizza_solution = mon_heuristique_eclatee(frigo, pizza_gate)
    definitive_pizza_solution, shipped_piz = consolidate_results(pizza_solution)
    print(shipped_piz,"pizzas shipped over",pizza_gate.num_pizzas)
    format_resutlts(definitive_pizza_solution, args.input_file)

## Recherche locale par voisinage

1/ on charge une solution precédente (dans un dossier 'output_best')
2/ on iter. de manière à créer des voisinages de solutions et de repartir des meilleurs solutions trouvées

from source import *

# ex = "a_example"
ex = "b_little_bit_of_everything.in"
# ex = "c_many_ingredients.in"
# ex = "d_many_pizzas.in"
# ex = "e_many_teams.in"

filename = f'input/{ex}'
load_best = True

# load data
frigo, pizza_gate = get_data(filename)

# load best solution
if load_best:
    filename_best = f"outputs_best/{ex.split('.')[0]}.out"
    init_solution = load_best_to_start(filename_best)
    print('> best solution loaded !') 
else:
    init_solution = [[], [], []]


# search 
nb_voisins = 5
nb_iterations = 1000
size_tabu_list = nb_iterations
perturbation = 100
nb_iter_without_improv = 50

actual_solution = deepcopy(init_solution)
best_solution = deepcopy(init_solution)
best_score = get_score(actual_solution, frigo)
print(f'> initial score : {best_score}')

tabu_list = [actual_solution]
count_iter_no_imp = 0

for i in range(nb_iterations):
    print(f"Iter: {i}")
    list_voisins = []
    nb_try = 0
    while len(list_voisins) < nb_voisins and nb_try < 10:
        v = Voisin(actual_solution, frigo, pizza_gate, perturbation=perturbation)
        if v.solution in tabu_list:
            nb_try += 1
        else:
            list_voisins.append(v)
            # tabu_list = [v.solution] + tabu_list[:size_tabu_list-1]
            nb_try = 0 
    if not list_voisins:
        print(f"\t> empty neighborhood !")
        break
    best_v = list_voisins[np.argmax([v.score for v in list_voisins])]   
    actual_solution = deepcopy(best_v.solution)
    tabu_list = [actual_solution] + tabu_list[:size_tabu_list-1]

    if best_v.score > best_score:
        best_solution = deepcopy(actual_solution)
        best_score = best_v.score
        count_iter_no_imp=0
        print(f"\t> New best score: {best_v.score} (iter: {i})")

        # export best solution 
        export=[]
        for i,t in enumerate(best_solution):
            for d in t:
                export.append(str(i+2)+' '+' '.join(d))
        definitive_pizza_solution, shipped_piz = consolidate_results(export)
        format_resutlts(definitive_pizza_solution, ex)
        
    else:
        count_iter_no_imp+=1

    if count_iter_no_imp == nb_iter_without_improv:
        actual_solution = deepcopy(best_solution)
        count_iter_no_imp = 0
        print(f'\t> restart from best')

print(f'> final best score : {best_score}')

Code qui complète le Pizza Gate 2 rue :

def load_best_to_start(filename_best):
    with open(filename_best, "r") as f:
        best = f.read().split('\n')[1:]
    dico_best = {'2':[], '3':[], '4':[]}
    for k in dico_best:
        dico_best[k] = [set(x.split(' ')[1:]) for x in best if x.split(' ')[0] == k]
    pizza_solution = [dico_best[k] for k in dico_best]
    return pizza_solution

def get_score(solution, frigo):
    score = 0
    for deliveries in solution:
        for delivery in deliveries:
            ingredients = set().union(*[frigo[int(x)].list_ingredients for x in delivery])
            score += len(ingredients) * len(ingredients)
    return score

class Voisin():
    def __init__(self, actual_solution, frigo, pizza_gate, perturbation=1):
        
        # budgets 
        self.num_available_t2 = pizza_gate.num_t2 - len(actual_solution[0])
        self.num_available_t3 = pizza_gate.num_t3 - len(actual_solution[1])
        self.num_available_t4 = pizza_gate.num_t4 - len(actual_solution[2])

        # pizzas dispo
        set_pizza_used = set().union(*[set().union(*x) for x in actual_solution])
        set_pizza_all = set([str(i) for i in range(pizza_gate.num_pizzas)])
        self.set_pizza_dispo = set_pizza_all - set_pizza_used
        
        # frigo
        self.nouveau_frigo = [x for x in frigo if str(x.pizza_id) in self.set_pizza_dispo]
        
        # create
        self.solution = deepcopy(actual_solution)
        self.frigo = frigo
        self.create(perturbation=perturbation)
        
        # score
        self.score = get_score(self.solution, self.frigo)
    
    def create(self, perturbation):
        for _ in range(perturbation):
            if sum([len(x) for x in self.solution]) == 0: break
            # deteriorate solution
            j = random.choice([i for i,k in enumerate(self.solution) if k])
            if j == 0:
                self.num_available_t2 += 1
            elif j == 1:
                self.num_available_t3 += 1
            elif j == 2:
                self.num_available_t4 += 1

            s = [get_score([[i]], self.frigo) for i in self.solution[j]]
            p = self.solution[j][np.argmin(s)]
            # p = random.choice(self.solution[j])

            self.solution[j].remove(p)
            self.set_pizza_dispo = self.set_pizza_dispo.union(p)
            
            # maj frigo
            self.nouveau_frigo = [x for x in self.frigo if str(x.pizza_id) in self.set_pizza_dispo]

        # reconstruct new solution
        new_deliveries = self.mon_heuristique_eclatee_2_rue()
        for d in new_deliveries:
            self.solution[d[0]-2].append(d[1])
            if d[0] == 2:
                self.num_available_t2 -= 1
            elif d[0] == 3:
                self.num_available_t3 -= 1
            elif d[0] == 4:
                self.num_available_t4 -= 1

    def mon_heuristique_eclatee_2_rue(self):
        out = []
        sorted_pizza = sort_by_max_ingredients(self.nouveau_frigo)

        list_teams_available = [self.num_available_t4, 
                                self.num_available_t3, 
                                self.num_available_t2]
        list_teams_size = [4,3,2]
        
        c = list(zip(list_teams_available, list_teams_size))
        random.shuffle(c)
        list_teams_available, list_teams_size = zip(*c)
        
        for num_team, team_size in zip(list_teams_available, list_teams_size):
            if len(self.nouveau_frigo) >= team_size:
                for _ in range(num_team):
                    tempo_pizza_sol = []
                    if len(sorted_pizza) == 0: break
                    best_pizza = sorted_pizza.pop(0)
                    tempo_pizza_sol.append(best_pizza)

                    for _ in range(team_size-1):
                        # Get best pizza
                        if len(sorted_pizza) == 0: break
                        best_pizza = max(sorted_pizza, key=lambda x: pizza_compatibility(tempo_pizza_sol,x))

                        # remove best pizza from list
                        sorted_pizza.pop(sorted_pizza.index(best_pizza))
                        tempo_pizza_sol.append(best_pizza)

                    out.append([team_size, set([str(x.pizza_id) for x in tempo_pizza_sol])])
        return out

## Modification Pizza Gate : ajout _limit_ingredients_ et _limit_pizzas_ à `mon_heuristique_eclatee()`

1/ _limit_ingredients_ permet de limiter le nombre d'ingredients considérés sur chaque pizza lors de `pizza_compatibility()`
2/ _limit_pizzas_ permet de limiter le nombre de pizza à checker

def pizza_compatibility(pizza_list, challenger_pizza, limit_ingredients):

    # Get ingredient of challenger_pizza
    challenger_ingr = challenger_pizza.list_ingredients
    
    # Check if already existing pizza is list or Pizza
    if type(pizza_list) == list :
        existing_ingr = []
        for piz in pizza_list:
            existing_ingr += piz.list_ingredients[:limit_ingredients]
    elif isinstance(pizza_list,Pizza):
        existing_ingr = pizza_list.list_ingredients[:limit_ingredients]

    # Remove duplicates
    existing_ingr = set(existing_ingr)
    challenger_ingr = set(challenger_ingr)
    
    improvement = (len(challenger_ingr) - len(challenger_ingr.intersection(existing_ingr)))/len(challenger_ingr)
    return improvement

def mon_heuristique_eclatee(pizza_list, problem_class, limit_ingredients=None, limit_pizzas = None):

    if not limit_pizzas:
        limit_pizzas = problem_class.num_pizzas
    if not limit_ingredients:
        limit_ingredients = int(1e10)
    
    print("la magie opère ici")
    solution = [] 
    sorted_pizza = sort_by_max_ingredients(pizza_list)

    for num_team, team_size in zip([problem_class.num_t4, problem_class.num_t3, problem_class.num_t2],[4,3,2]):
        print("===== team of",team_size)
        print("===== ",num_team,"to process")

        for team in tqdm(range(num_team)):

            tempo_pizza_sol = []
            if len(sorted_pizza) == 0: break
            best_pizza = sorted_pizza.pop(0)
            tempo_pizza_sol.append(best_pizza)
            
            for remaning_pizza in range(team_size-1):
                # Get best pizza
                if len(sorted_pizza) == 0: break

                best_pizza = max(sorted_pizza[:limit_pizzas], key=lambda x: pizza_compatibility(tempo_pizza_sol,x, limit_ingredients))
                # remove best pizza from list
                sorted_pizza.pop(sorted_pizza.index(best_pizza))
                tempo_pizza_sol.append(best_pizza)
                
            solution.append(str(team_size)+' '+' '.join([str(x.pizza_id) for x in tempo_pizza_sol]))
    return solution