# Path: simpleai/search/models.py
# class CspProblem(object):
#     def __init__(self, variables, domains, constraints):
#         self.variables = variables
#         self.domains = domains
#         self.constraints = constraints
# 
#         # variable-based constraints dict
#         self.var_contraints = dict([(v, [constraint
#                                          for constraint in constraints
#                                          if v in constraint[0]])
#                                     for v in variables])
# 
#         # calculate degree of each variable
#         self.var_degrees = dict([(v, len(self.var_contraints[v]))
#                                  for v in variables])
# 
# Path: simpleai/search/csp.py
# def _find_conflicts(problem, assignment, variable=None, value=None):
#     '''
#     Find violated constraints on a given assignment, with the possibility
#     of specifying a new variable and value to add to the assignment before
#     checking.
#     '''
#     if variable is not None and value is not None:
#         assignment = deepcopy(assignment)
#         assignment[variable] = value
# 
#     conflicts = []
#     for neighbors, constraint in problem.constraints:
#         # if all the neighbors on the constraint have values, check if conflict
#         if all(n in assignment for n in neighbors):
#             if not _call_constraint(assignment, neighbors, constraint):
#                 conflicts.append((neighbors, constraint))
# 
#     return conflicts
# 
# def _count_conflicts(problem, assignment, variable=None, value=None):
#     '''
#     Count the number of violated constraints on a given assignment.
#     '''
#     return len(_find_conflicts(problem, assignment, variable, value))
# 
# def _most_constrained_variable_chooser(problem, variables, domains):
#     '''
#     Choose the variable that has less available values.
#     '''
#     # the variable with fewer values available
#     return sorted(variables, key=lambda v: len(domains[v]))[0]
# 
# def _highest_degree_variable_chooser(problem, variables, domains):
#     '''
#     Choose the variable that is involved on more constraints.
#     '''
#     # the variable involved in more constraints
#     return sorted(variables, key=lambda v: problem.var_degrees[v], reverse=True)[0]
# 
# def _least_constraining_values_sorter(problem, assignment, variable, domains):
#     '''
#     Sort values based on how many conflicts they generate if assigned.
#     '''
#     # the value that generates less conflicts
#     def update_assignment(value):
#         new_assignment = deepcopy(assignment)
#         new_assignment[variable] = value
#         return new_assignment
# 
#     values = sorted(domains[variable][:],
#                     key=lambda v: _count_conflicts(problem, assignment,
#                                                    variable, v))
#     return values
# 
# def _min_conflicts_value(problem, assignment, variable):
#     '''
#     Return the value generate the less number of conflicts.
#     In case of tie, a random value is selected among this values subset.
#     '''
#     return argmin(problem.domains[variable], lambda x: _count_conflicts(problem, assignment, variable, x))
# 
# def backtrack(problem, variable_heuristic='', value_heuristic='', inference=True):
#     '''
#     Backtracking search.
# 
#     variable_heuristic is the heuristic for variable choosing, can be
#     MOST_CONSTRAINED_VARIABLE, HIGHEST_DEGREE_VARIABLE, or blank for simple
#     ordered choosing.
#     value_heuristic is the heuristic for value choosing, can be
#     LEAST_CONSTRAINING_VALUE or blank for simple ordered choosing.
#     '''
#     assignment = {}
#     domains = deepcopy(problem.domains)
# 
#     if variable_heuristic == MOST_CONSTRAINED_VARIABLE:
#         variable_chooser = _most_constrained_variable_chooser
#     elif variable_heuristic == HIGHEST_DEGREE_VARIABLE:
#         variable_chooser = _highest_degree_variable_chooser
#     else:
#         variable_chooser = _basic_variable_chooser
# 
#     if value_heuristic == LEAST_CONSTRAINING_VALUE:
#         values_sorter = _least_constraining_values_sorter
#     else:
#         values_sorter = _basic_values_sorter
#     return _backtracking(problem,
#                          assignment,
#                          domains,
#                          variable_chooser,
#                          values_sorter,
#                          inference=inference)
# 
# def min_conflicts(problem, initial_assignment=None, iterations_limit=0):
#     """
#     Min conflicts search.
# 
#     initial_assignment the initial assignment, or None to generate a random
#     one.
#     If iterations_limit is specified, the algorithm will end after that
#     number of iterations. Else, it will continue until if finds an assignment
#     that doesn't generate conflicts (a solution).
#     """
#     assignment = {}
#     if initial_assignment:
#         assignment.update(initial_assignment)
#     else:
#         for variable in problem.variables:
#             value = _min_conflicts_value(problem, assignment, variable)
#             assignment[variable] = value
# 
#     iteration = 0
#     run = True
#     while run:
#         conflicts = _find_conflicts(problem, assignment)
# 
#         conflict_variables = [v for v in problem.variables
#                               if any(v in conflict[0] for conflict in conflicts)]
# 
#         if conflict_variables:
#             variable = random.choice(conflict_variables)
#             value = _min_conflicts_value(problem, assignment, variable)
#             assignment[variable] = value
# 
#         iteration += 1
# 
#         if iterations_limit and iteration >= iterations_limit:
#             run = False
#         elif not _count_conflicts(problem, assignment):
#             run = False
# 
#     return assignment


import unittest
from simpleai.search.models import CspProblem
from simpleai.search.csp import (_find_conflicts, _count_conflicts,
                                 _most_constrained_variable_chooser,
                                 _highest_degree_variable_chooser,
                                 _least_constraining_values_sorter,
                                 _min_conflicts_value, backtrack,
                                 min_conflicts)
# coding=utf-8


class TestCsp(unittest.TestCase):
    def setUp(self):
        self.variables = ('A', 'B', 'C')

        self.domains = {
            'A': [1, 2, 3],
            'B': [1, 3, 4],
            'C': [1, 2],
        }

        # a constraint that expects different variables to have different values
        def const_different(variables, values):

# Path: simpleai/search/models.py
# class CspProblem(object):
#     def __init__(self, variables, domains, constraints):
#         self.variables = variables
#         self.domains = domains
#         self.constraints = constraints
# 
#         # variable-based constraints dict
#         self.var_contraints = dict([(v, [constraint
#                                          for constraint in constraints
#                                          if v in constraint[0]])
#                                     for v in variables])
# 
#         # calculate degree of each variable
#         self.var_degrees = dict([(v, len(self.var_contraints[v]))
#                                  for v in variables])
# 
# Path: simpleai/search/csp.py
# def _find_conflicts(problem, assignment, variable=None, value=None):
#     '''
#     Find violated constraints on a given assignment, with the possibility
#     of specifying a new variable and value to add to the assignment before
#     checking.
#     '''
#     if variable is not None and value is not None:
#         assignment = deepcopy(assignment)
#         assignment[variable] = value
# 
#     conflicts = []
#     for neighbors, constraint in problem.constraints:
#         # if all the neighbors on the constraint have values, check if conflict
#         if all(n in assignment for n in neighbors):
#             if not _call_constraint(assignment, neighbors, constraint):
#                 conflicts.append((neighbors, constraint))
# 
#     return conflicts
# 
# def _count_conflicts(problem, assignment, variable=None, value=None):
#     '''
#     Count the number of violated constraints on a given assignment.
#     '''
#     return len(_find_conflicts(problem, assignment, variable, value))
# 
# def _most_constrained_variable_chooser(problem, variables, domains):
#     '''
#     Choose the variable that has less available values.
#     '''
#     # the variable with fewer values available
#     return sorted(variables, key=lambda v: len(domains[v]))[0]
# 
# def _highest_degree_variable_chooser(problem, variables, domains):
#     '''
#     Choose the variable that is involved on more constraints.
#     '''
#     # the variable involved in more constraints
#     return sorted(variables, key=lambda v: problem.var_degrees[v], reverse=True)[0]
# 
# def _least_constraining_values_sorter(problem, assignment, variable, domains):
#     '''
#     Sort values based on how many conflicts they generate if assigned.
#     '''
#     # the value that generates less conflicts
#     def update_assignment(value):
#         new_assignment = deepcopy(assignment)
#         new_assignment[variable] = value
#         return new_assignment
# 
#     values = sorted(domains[variable][:],
#                     key=lambda v: _count_conflicts(problem, assignment,
#                                                    variable, v))
#     return values
# 
# def _min_conflicts_value(problem, assignment, variable):
#     '''
#     Return the value generate the less number of conflicts.
#     In case of tie, a random value is selected among this values subset.
#     '''
#     return argmin(problem.domains[variable], lambda x: _count_conflicts(problem, assignment, variable, x))
# 
# def backtrack(problem, variable_heuristic='', value_heuristic='', inference=True):
#     '''
#     Backtracking search.
# 
#     variable_heuristic is the heuristic for variable choosing, can be
#     MOST_CONSTRAINED_VARIABLE, HIGHEST_DEGREE_VARIABLE, or blank for simple
#     ordered choosing.
#     value_heuristic is the heuristic for value choosing, can be
#     LEAST_CONSTRAINING_VALUE or blank for simple ordered choosing.
#     '''
#     assignment = {}
#     domains = deepcopy(problem.domains)
# 
#     if variable_heuristic == MOST_CONSTRAINED_VARIABLE:
#         variable_chooser = _most_constrained_variable_chooser
#     elif variable_heuristic == HIGHEST_DEGREE_VARIABLE:
#         variable_chooser = _highest_degree_variable_chooser
#     else:
#         variable_chooser = _basic_variable_chooser
# 
#     if value_heuristic == LEAST_CONSTRAINING_VALUE:
#         values_sorter = _least_constraining_values_sorter
#     else:
#         values_sorter = _basic_values_sorter
#     return _backtracking(problem,
#                          assignment,
#                          domains,
#                          variable_chooser,
#                          values_sorter,
#                          inference=inference)
# 
# def min_conflicts(problem, initial_assignment=None, iterations_limit=0):
#     """
#     Min conflicts search.
# 
#     initial_assignment the initial assignment, or None to generate a random
#     one.
#     If iterations_limit is specified, the algorithm will end after that
#     number of iterations. Else, it will continue until if finds an assignment
#     that doesn't generate conflicts (a solution).
#     """
#     assignment = {}
#     if initial_assignment:
#         assignment.update(initial_assignment)
#     else:
#         for variable in problem.variables:
#             value = _min_conflicts_value(problem, assignment, variable)
#             assignment[variable] = value
# 
#     iteration = 0
#     run = True
#     while run:
#         conflicts = _find_conflicts(problem, assignment)
# 
#         conflict_variables = [v for v in problem.variables
#                               if any(v in conflict[0] for conflict in conflicts)]
# 
#         if conflict_variables:
#             variable = random.choice(conflict_variables)
#             value = _min_conflicts_value(problem, assignment, variable)
#             assignment[variable] = value
# 
#         iteration += 1
# 
#         if iterations_limit and iteration >= iterations_limit:
#             run = False
#         elif not _count_conflicts(problem, assignment):
#             run = False
# 
#     return assignment


# Path: tests/search/test_csp.py
import unittest
from simpleai.search.models import CspProblem
from simpleai.search.csp import (_find_conflicts, _count_conflicts,
                                 _most_constrained_variable_chooser,
                                 _highest_degree_variable_chooser,
                                 _least_constraining_values_sorter,
                                 _min_conflicts_value, backtrack,
                                 min_conflicts)

# coding=utf-8


class TestCsp(unittest.TestCase):
    def setUp(self):
        self.variables = ('A', 'B', 'C')

        self.domains = {
            'A': [1, 2, 3],
            'B': [1, 3, 4],
            'C': [1, 2],
        }

        # a constraint that expects different variables to have different values
        def const_different(variables, values):

            return len(values) == len(set(values))  # remove repeated values and count