structures.py

from typing import List, Dict, Optional
import sys


# STRUCTURES POUR SAT ET 3-SAT

class Literal:

    def __init__(self, variable: int, negated: bool = False):
        """
        Args:
            variable (int): Le numéro de la variable (doit être > 0)
            negated (bool): True pour ¬x_i, False pour x_i
        """

        if variable <= 0: # vérifier que le numéro de variable est strictement positif
            raise ValueError("Le numéro de variable doit être strictement positif")
        
        self.variable = variable # numéro de la variable
        self.negated = negated # True si négatif, False sinon
    
    def evaluate(self, assignment: Dict[int, bool]) -> Optional[bool]:
        """
        #evaluate : évaluer le littéral avec une affectation donnée.

        Args:
            assignment: Dictionnaire qui contient les variables dont on a assigné une valeur booléenne
                       Ex: {1: True, 2: False, 3: True}
        """
        if self.variable not in assignment: # si la variable n'est pas assignée,
            return None # retourner None (indéterminé)
        
        value = assignment[self.variable] # obtenir la valeur assignée à la variable
        return not value if self.negated else value # retourner la valeur en tenant compte de la négation
    
    def __str__(self) -> str:
        """
        litteral representation of a given littéral
        
        Returns:
            str: "¬x_i" si négatif, "x_i" sinon
        """
        if self.negated:
            return f"¬x{self.variable}"
        else:
            return f"x{self.variable}"


class Clause:#

    # aka la disjonction de littéraux (bel or)
    
    def __init__(self, literals: List[Literal]):
        # Args: list of literals
        if not literals: # vérifier que la clause n'est pas vide
            raise ValueError("Une clause doit contenir au moins un littéral")
        
        self.literals = literals # liste des littéraux dans la clause
    
    def evaluate(self, assignment: Dict[int, bool]) -> Optional[bool]:
        """
        Args:
            assignment: Dictionnaire qui contient les variables assignées
                       Ex: {1: True, 2: False, 3: True}
        """
        has_unknown = False
        
        for literal in self.literals: # boucler sur chaque littéral dans la clause
            result = literal.evaluate(assignment) # évaluer le littéral avec l'affectation donnée
            
            if result is True: # si le littéral est évalué à True
                return True # la clause est satisfaite
            
            if result is None: #    si le littéral est indéterminé
                has_unknown = True # il y a au moins un littéral indéterminé
        
        return None if has_unknown else False # retourner None si indéterminé, sinon False
    
    def __str__(self) -> str:
        """
        litteral representation of a given clause
        
        Returns:
            str: "(l1 ∨ l2 ∨ ... ∨ lk)"
        """
        return "(" + " ∨ ".join(str(lit) for lit in self.literals) + ")"


class SATInstance:
    
    def __init__(self, num_variables: int, clauses: List[Clause]):
        """      
        Args:
                num_variables (int): Nombre total de variables distinctes
            clauses (List[Clause]): Liste des clauses de la formule
        """
        if num_variables <= 0: # vérifier que le nombre de variables est strictement positif
            raise ValueError("Le nombre de variables doit être strictement positif")
        
        if not clauses: # vérifier que l'instance SAT n'est pas vide
            raise ValueError("Une instance SAT doit contenir au moins une clause")
        
        self.num_variables = num_variables # nombre total de variables distinctes
        self.clauses = clauses # liste des clauses de la formule
    
    def evaluate(self, assignment: Dict[int, bool]) -> Optional[bool]:
        """
        Args:
            assignment: Dictionnaire qui contient les variables assignées
                       Ex: {1: True, 2: False, 3: True}
        """
        has_unknown = False #   indique si au moins une clause est indéterminée
        
        for clause in self.clauses: # boucler sur chaque clause dans l'instance SAT
            result = clause.evaluate(assignment) # évaluer la clause avec l'affectation donnée  
            
            if result is False:
                return False
            
            if result is None:
                has_unknown = True # il y a au moins une clause indéterminée
        
        return None if has_unknown else True # retourner None si indéterminé, sinon True
    
    def __str__(self) -> str:
        """
        litteral representation of a given SAT.
        
        Returns:
            str: "C1 ∧ C2 ∧ ... ∧ Cm"
        """
        return " ∧ ".join(str(clause) for clause in self.clauses)

# STRUCTURES POUR SUBSETSUM
class SubsetSumInstance:
    
    def __init__(self, elements: List[int], target: int):
        """
        Args:
            elements (List[int]): Liste des entiers de l'ensemble S
            target (int): Valeur cible T
        """
        if not elements: # vérifier que l'ensemble n'est pas vide
            raise ValueError("L'ensemble S doit contenir au moins un élément")
        
        self.elements = elements # liste des entiers de l'ensemble S
        self.target = target # valeur cible T
        self.n = len(elements) # nombre d'éléments dans l'ensemble S
    
    def evaluate(self, selection: List[bool]) -> Optional[bool]:
        """
        Args:
            selection (List[bool]): Tableau de sélection des éléments
                                   selection[i] = True si elements[i] ∈ S'
                                   Ex: [False, True, False, True]
        """
        if len(selection) != self.n: # vérifier que la taille du tableau de sélection est correcte
            return None
        
        somme = 0
        for i in range(self.n): # boucler sur chaque élément dans l'ensemble
            if selection[i]: # si l'élément est sélectionné
                somme += self.elements[i] # l'ajouter à la somme
        
        return somme == self.target # retourner True si la somme = target, sinon False
    
    def compute_sum(self, selection: List[bool]) -> Optional[int]:
        # Args: selection (List[bool]): Tableau de sélection
        if len(selection) != self.n: # vérifier que la taille du tableau de sélection est correcte
            return None
        
        somme = 0 # initialiser la somme à 0
        for i in range(self.n): # boucler sur chaque élément dans l'ensemble
            if selection[i]:# si l'élément est sélectionné
                somme += self.elements[i] # l'ajouter à la somme
        
        return somme # retourner la somme des éléments sélectionnés
    
    def get_selected_elements(self, selection: List[bool]) -> Optional[List[int]]:
        # Args: selection (List[bool]): Tableau de sélection
        if len(selection) != self.n: # vérifier que la taille du tableau de sélection est correcte
            return None
        
        return [self.elements[i] for i in range(self.n) if selection[i]] # retourner la liste des éléments sélectionnés
    
    def __str__(self) -> str:
        """
        litteral representation of a given instance.
        
        Returns:
            str: "S = {e₁, e₂, ..., eₙ}, T = target"
        """
        return f"S = {{{', '.join(map(str, self.elements))}}}, T = {self.target}"