# coding=utf-8
import random
from copy import deepcopy, copy
from itertools import product
from simpleai.search.utils import argmin

MOST_CONSTRAINED_VARIABLE = 'mcv'
HIGHEST_DEGREE_VARIABLE = 'degree'
LEAST_CONSTRAINING_VALUE = 'lvc'


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 _basic_variable_chooser(problem, variables, domains):
    '''
    Choose the next variable in order.
    '''
    return variables[0]


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 _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 _call_constraint(assignment, neighbors, constraint):
    variables, values = zip(*[(n, assignment[n])
                              for n in neighbors])
    return constraint(variables, values)


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 _basic_values_sorter(problem, assignment, variable, domains):
    '''
    Sort values in the same original order.
    '''
    return domains[variable][:]


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 _backtracking(problem, assignment, domains, variable_chooser, values_sorter, inference=True):
    '''
    Internal recursive backtracking algorithm.
    '''
    from simpleai.search.arc import arc_consistency_3
    if len(assignment) == len(problem.variables):
        return assignment

    pending = [v for v in problem.variables
               if v not in assignment]
    variable = variable_chooser(problem, pending, domains)

    values = values_sorter(problem, assignment, variable, domains)