<commit_before>"""Constraint satisfaction problems.
"""

import pprint
import logging


log = logging.getLogger(__name__)


class CSP(object):
    """Finite-domain constraint satisfaction problem.

    Arguments:
        var_domains: A list with one entry for each variable
            containing a sequence with all the possible values of the
            variable. All the variables must be domain-consistent
            (i.e. there must exist at least one consistent
            configuration in which each value value occurs).
        constraints: A list of tuples with two components each: i) a
            tuple with the indices of the variables involved in the
            constraint, and ii) a function that checks the constraint.
            The constraint functions will receive an indices tuple and
            a values tuple, both containing only the restricted
            variable indices and their values (in the same order
            provided in `constraints`). The function should return
            `True` if the values satisfy the constraint, `False`
            otherwise. The constraints must be normalized (i.e. two
            different constraints shouldn't involve the same set of
            variables).

    All the arguments are available as instance attributes.
    """

    def __init__(self, var_domains, constraints):
        self.var_domains = [list(var_domain) for var_domain in var_domains]
        self.constraints = constraints
        self.is_binary = True
        self._constraints_index = {}
        for var_indices, constraint_fun in constraints:
            if len(var_indices) != 2:
                self.is_binary = False
            key = frozenset(var_indices)
            if key in self._constraints_index:
                raise ValueError("The constraints must be normalized")
            self._constraints_index[key] = var_indices, constraint_fun
        self.reset()

    def solve(self):
        """Find a consistent assignment of the variables.

        Returns:
            A dictionary with the values assigned to the variables if
            a solution was found, `None` otherwise.
        """
        return _backtracking_search({}, self.var_domains,
                                    self._constraints_index)

    # The following are internal methods used to keep track of the
    # assignments and enforce global or local consistency after each
    # variable is assigned when the dialog is being used.

    def reset(self):
        self.assignment = {}
        self.pruned_var_domains = self.var_domains.copy()

    def assign_variable(self, var_index, var_value, consistency="global"):
        if var_index in self.assignment:
            raise ValueError("The variable is already assigned")
        if var_value not in self.pruned_var_domains[var_index]:
            raise ValueError("Invalid assignment in the current state")
        log.debug("assignning variable %d to %r", var_index, var_value)
        log.debug("initial assignment:\n%s", pprint.pformat(self.assignment))
        log.debug("initial domains:\n%s",
                  pprint.pformat(self.pruned_var_domains))
        self.assignment[var_index] = var_value
        self.pruned_var_domains[var_index] = [var_value]
        if len(self.assignment) < len(self.var_domains):
            if consistency == "global":
                self.enforce_global_consistency()
            elif consistency == "local":
                if not self.is_binary:
                    raise ValueError("Local consistency only " +
                                     "implemented for binary CSPs")
                self.enforce_local_consistency()
            # If the domain of a variable was reduced to a single
            # value, set it back in the assignment.
            for var_index, var_values in enumerate(self.pruned_var_domains):
                assert len(var_values) > 0
                if len(var_values) == 1 and var_index not in self.assignment:
                    var_value = self.pruned_var_domains[var_index][0]
                    self.assignment[var_index] = var_value
        log.debug("final assignment:\n%s", pprint.pformat(self.assignment))
        log.debug("final domains:\n%s",
                  pprint.pformat(self.pruned_var_domains))

    def enforce_global_consistency(self):
        # Check that all possible answers to the remaining questions
        # lead to at least one consistent assignment.
        log.debug("enforcing global consistency")
        for var_index in range(len(self.var_domains)):
            if len(self.pruned_var_domains[var_index]) > 1:
                tmp_var_domains = self.pruned_var_domains.copy()
                consistent_values = []
                for var_value in self.pruned_var_domains[var_index]:
                    tmp_var_domains[var_index] = [var_value]
                    solution = _backtracking_search({}, tmp_var_domains,
                                                    self._constraints_index)
                    if solution:
                        consistent_values.append(var_value)
                if (len(consistent_values) <
                        len(self.pruned_var_domains[var_index])):
                    self.pruned_var_domains[var_index] = consistent_values

    def enforce_local_consistency(self):
        # Singleton arc consistency. Based on Figure 2 of Romuald
        # Debruyne and <NAME> (1997). Some practicable
        # filtering techniques for the constraint satisfaction
        # problem, IJCAI'97, 412-417.
        log.debug("enforcing local consistency")
        _arc_consistency_3(self.pruned_var_domains,<commit_msg>Check for local consistency in addition to global<commit_after>"""Constraint satisfaction problems.
"""

import pprint
import logging


log = logging.getLogger(__name__)


class CSP(object):
    """Finite-domain constraint satisfaction problem.

    Arguments:
        var_domains: A list with one entry for each variable
            containing a sequence with all the possible values of the
            variable. All the variables must be domain-consistent
            (i.e. there must exist at least one consistent
            configuration in which each value value occurs).
        constraints: A list of tuples with two components each: i) a
            tuple with the indices of the variables involved in the
            constraint, and ii) a function that checks the constraint.
            The constraint functions will receive an indices tuple and
            a values tuple, both containing only the restricted
            variable indices and their values (in the same order
            provided in `constraints`). The function should return
            `True` if the values satisfy the constraint, `False`
            otherwise. The constraints must be normalized (i.e. two
            different constraints shouldn't involve the same set of
            variables).

    All the arguments are available as instance attributes.
    """

    def __init__(self, var_domains, constraints):
        self.var_domains = [list(var_domain) for var_domain in var_domains]
        self.constraints = constraints
        self.is_binary = True
        self._constraints_index = {}
        for var_indices, constraint_fun in constraints:
            if len(var_indices) != 2:
                self.is_binary = False
            key = frozenset(var_indices)
            if key in self._constraints_index:
                raise ValueError("The constraints must be normalized")
            self._constraints_index[key] = var_indices, constraint_fun
        self.reset()

    def solve(self):
        """Find a consistent assignment of the variables.

        Returns:
            A dictionary with the values assigned to the variables if
            a solution was found, `None` otherwise.
        """
        return _backtracking_search({}, self.var_domains,
                                    self._constraints_index)

    # The following are internal methods used to keep track of the
    # assignments and enforce global or local consistency after each
    # variable is assigned when the dialog is being used.

    def reset(self):
        self.assignment = {}
        self.pruned_var_domains = self.var_domains.copy()

    def assign_variable(self, var_index, var_value, consistency="global"):
        if var_index in self.assignment:
            raise ValueError("The variable is already assigned")
        if var_value not in self.pruned_var_domains[var_index]:
            raise ValueError("Invalid assignment in the current state")
        log.debug("assignning variable %d to %r", var_index, var_value)
        log.debug("initial assignment:\n%s", pprint.pformat(self.assignment))
        log.debug("initial domains:\n%s",
                  pprint.pformat(self.pruned_var_domains))
        self.assignment[var_index] = var_value
        self.pruned_var_domains[var_index] = [var_value]
        if len(self.assignment) < len(self.var_domains):
            if consistency == "global":
                self.enforce_global_consistency()
            elif consistency == "local":
                if not self.is_binary:
                    raise ValueError("Local consistency only " +
                                     "implemented for binary CSPs")
                self.enforce_local_consistency()
            # If the domain of a variable was reduced to a single
            # value, set it back in the assignment.
            for var_index, var_values in enumerate(self.pruned_var_domains):
                assert len(var_values) > 0
                if len(var_values) == 1 and var_index not in self.assignment:
                    var_value = self.pruned_var_domains[var_index][0]
                    self.assignment[var_index] = var_value
        log.debug("final assignment:\n%s", pprint.pformat(self.assignment))
        log.debug("final domains:\n%s",
                  pprint.pformat(self.pruned_var_domains))

    def enforce_global_consistency(self):
        # Check that all possible answers to the remaining questions
        # lead to at least one consistent assignment.
        log.debug("enforcing global consistency")
        _arc_consistency_3(self.pruned_var_domains,
                           self._constraints_index)
        for var_index in range(len(self.var_domains)):
            if len(self.pruned_var_domains[var_index]) > 1:
                consistent_values = []
                for var_value in self.pruned_var_domains[var_index]:
                    tmp_var_domains = self.pruned_var_domains.copy()
                    tmp_var_domains[var_index] = [var_value]
                    if _backtracking_search({}, tmp_var_domains,
                                            self._constraints_index):
                        consistent_values.append(var_value)
                if (len(consistent_values) <
                        len(self.pruned_var_domains[var_index])):
                    self.pruned_var_domains[var_index] = consistent_values
                    _arc_consistency_3(self.pruned_var_domains,
                                       self._constraints_index)

    def enforce_local_consistency(self):
        # Singleton arc consistency. Based on Figure 2 of Romuald
        # Debruyne and <NAME> (1997). Some practicable
        # filtering techniques for the constraint satisfaction
        # problem, IJCAI'97, 412-417.
        log.debug("enforcing local consistency")
        _arc_consistency_3(self.pruned_var_domains,
{'fraction_non_alphanumeric': 0.06907037358818419, 'fraction_numerical': 0.0034752389226759338, 'mean_word_length': 2.1719481950950676, 'pattern_counts': {'":': 4, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1832071', 'n_tokens_mistral': 3003, 'n_tokens_neox': 2799, 'n_words': 902}