2018-04-04
a python code shippet

a python code snippet

CONFEDERATION_COUNT = 6


class Domain(object):
    """Domain of Variables
    
    i.e. domain of which group a country can belong to in this assignment
    Use Bit-operation to implement rather than list
    Class Attributes:
        size: An integer indicating the size of domains
    Instance Attributes:
        remained: An integer indicating how many value remained in the domain
        last_change: An integer indicating the search step where the domain changed most recently,
            which can be used to backjump to avoid unnecessary steps
    """

    @classmethod
    def init(cls, size):
        cls.size = size
        cls.__full_domain = (1 << size) - 1  # A integer indicating what's value in domain when it's full

    def __init__(self):
        self.__val = Domain.__full_domain  # A integer indicating the values in domain
        self.remained = Domain.size
        self.last_change = -1

    def set_val(self, val):
        """Sets a value for domain, i.e. selects a value and deletes all others"""
        self.__val = 1 << val
        self.remained = 1

    def retrieve(self, val, remained):
        """Retrieves domain to what it is before running AC-3 alg and searching deeper"""
        self.__val = val
        self.remained = remained

    def get_values(self, bits=False):
        """Gets values which are still in domain
        
        :param bits: A boolean indicating whether return in bits format or list
        :return: The values, in format of a integer or a list of integer
        """
        if bits:
            return self.__val
        values_list = []
        for i in range(Domain.size):
            if (1 << i) & self.__val > 0:
                values_list.append(i)
        return values_list

    def revise(self, other_domain, assigned_step):
        """Revise domain in the process of AC-3 alg
        
        :param other_domain: A class domain indicating a domain which has constraint with this domain
        :param assigned_step: A integer indicating the step of our MAC searching alg
        :return: A bool, True if the domain is revised, False if not
        """
        revised = False
        other_val = other_domain.get_values(True)
        list_val = self.get_values()
        for i in list_val:
            # Checks if value i is consistent with the other domain using Bit-operation
            if Domain.__full_domain - (1 << i) & other_val == 0:
                revised = True
                self.__val -= (1 << i)  # Revises domain actually
                self.remained -= 1
                self.last_change = assigned_step  # Record the step of MAC alg
        return revised

    def reduce(self, val, assigned_step):
        """Reduce a value in domain if the domain has that value
        
        :param val: An integer indicating the value to be reduced
        :param assigned_step: A integer indicating the step of our MAC searching alg
        """
        if self.__val & (1 << val) == 0:
            return
        self.__val -= (1 << val)
        self.remained -= 1
        self.last_change = assigned_step


class Variable:
    """A class describing and recording the info of each variable
    
    Class Attributes:
        count: An integer indicating how many variables totally
        dict: A dict connecting a variable's name and its number(in order of being created)
    Instance Attributes:
        name: A string indicating the name of the variable
        domain: A instance of class Domain indicating the info of this variable's domain
        belong_uefa: A bool, True if the country that variable represent belongs to UEFA confederation, False if not
        constraint: A list of integer indicating which variables have constraints with this variable
        assigned: A bool, True if this variable if assigned, False if not
    """

    count = 0
    dict = {}

    def __init__(self, name):
        self.name = name
        self.domain = Domain()
        self.belong_uefa = False
        self.constraint = []
        self.assigned = False
        Variable.dict[name] = Variable.count
        Variable.count += 1

    def assign(self, val):
        """Assigns the value 'val' to this variable"""
        self.assigned = True
        self.domain.set_val(val)


def print_result(variables=None, no_solution=True):
    """Prints result to 'output.txt' file and exit"""
    with open('output.txt', 'w') as output_file:
        if no_solution:
            print >> output_file, 'No'
        else:
            print >> output_file, 'Yes'
            groups = [[] for i in range(Domain.size)]
            for var_itr in variables:
                groups[var_itr.domain.get_values()[0]].append(var_itr.name)
            for group in groups:
                if len(group) == 0:
                    str_out = 'None'
                else:
                    str_out = group[0]
                    for j in range(1, len(group)):
                        str_out = str_out + ',' + group[j]
                print >> output_file, str_out
    exit()


def generate_constraint_queue(variables, related_var=-1):
    """Generates a queue recording pairs of variables with binary constraint
    
    :param variables: A list of instances Variable indicating all variables in this problem
    :param related_var: An integer indicating the variable that is considered to update this queue, -1 if all variables
    :return: A list of [integer, integer] indicating the constraint queue which will be used in AC-3 alg
    """
    constraint_queue = []
    if related_var == -1:
        for i in range(Variable.count):
            constraint_queue.extend(generate_constraint_queue(variables, i))
    else:
        for i in variables[related_var].constraint:
            if not variables[i].assigned:  # Only considers unassigned variables
                constraint_queue.append([i, related_var])
    return constraint_queue


def ac3(variables, constraint_queue, assigned_step=-1):
    """AC-3 alg to reduce the domains of each variable
    
    :param variables: A list of instances Variable indicating all variables in this problem
    :param constraint_queue: A list of [integer, integer] recording the info of pairs of variables with 2-constraint
    :param assigned_step: A integer indicating the step of our MAC searching alg
    :return: False if no solution, else True
    """
    while len(constraint_queue) > 0:
        constraint = constraint_queue.pop(0)
        variable = variables[constraint[0]]
        if variable.domain.revise(variables[constraint[1]].domain, assigned_step):
            if variable.domain.get_values(True) == 0:  # Empty domain -> no solution
                return False
            for i in variable.constraint:
                if i != constraint[1] and not variables[i].assigned:
                    constraint_queue.append([i, constraint[0]])
    return True


def mac(variables, assigned, group_uefa_cnt):
    """MAC(Maintaining Arc Consistency) alg for search
    
    In each step, chooses a unassigned variable using MRV(Minimum-remaining-values) heuristic,
    and deals with UEFA situation(no more than 1 UEFA countries in one group), and then runs 
    AC-3 alg to reduce domain of unassigned variables and check if no solution, and then backjumps
    to the most recent step causing the change of the current variable's domain
    :param variables: A list of instances Variable indicating all variables in this problem
    :param assigned: An integer indicating how many variables have been assigned
    :param group_uefa_cnt: A list of integer indicating how many countries in UEFA have been assigned to a group
    :return: An integer indicating which assigned step should be backjumped to
    """
    if assigned == Variable.count:  # Every variable has been assigned -> solution
        print_result(variables, False)

    # Chooses a unassigned variable using MRV
    variable_idx = 0  # the index of the variable with minimum remaining value in domain
    min_remained = Domain.size + 1
    for i in range(Variable.count):
        var_itr = variables[i]
        if not var_itr.assigned and min_remained > var_itr.domain.remained:
            min_remained = var_itr.domain.remained
            variable_idx = i
    variable = variables[variable_idx]  # The variable to be assigned
    val_list = variable.domain.get_values()
    if min_remained == 1:
        val = val_list[0]
        variable.assign(val)
        if variable.belong_uefa:  # Deals with UEFA situations
            group_uefa_cnt[val] += 1
            if group_uefa_cnt[val] == 2:
                conflict = False
                for var_itr in variables:
                    if not var_itr.assigned and var_itr.belong_uefa:
                        var_itr.domain.reduce(val, assigned)
                        if var_itr.domain.remained == 0:
                            conflict = True
                            break
                if conflict:
                    group_uefa_cnt[val] -= 1
                    variable.assigned = False
                    if variable.domain.last_change != -1:  # If the most recent change is not initialization
                        return variable.domain.last_change
                    else:
                        return assigned - 1
        tmp = mac(variables, assigned + 1, group_uefa_cnt)
        if variable.belong_uefa:
            group_uefa_cnt[val] -= 1
        variable.assigned = False
        if tmp < assigned:
            return tmp
        if variable.domain.last_change != -1:  # If the most recent change is not initialization
            return variable.domain.last_change
        else:
            return assigned - 1

    # Backups domain if variable has more than 1 remaining values
    backup_val = [var_itr.domain.get_values(True) for var_itr in variables]
    backup_remained = [var_itr.domain.remained for var_itr in variables]
    constraining_cnt = [0] * min_remained
    for i in xrange(min_remained):
        # print assigned, variable_idx, min_remained, val_list, i
        tmp = 1 << val_list[i]
        for j in variable.constraint:
            if tmp & variables[j].domain.get_values(True) > 0:
                constraining_cnt[i] += 1
    for i in xrange(min_remained):
        for j in xrange(i):
            if constraining_cnt[i] < constraining_cnt[j]:
                val_list[i], val_list[j] = val_list[j], val_list[i]
                constraining_cnt[i], constraining_cnt[j] = constraining_cnt[j], constraining_cnt[i]

    # Attempts to assign each valid variable
    for val in val_list:
        variable.assign(val)
        if variable.belong_uefa:  # Deals with UEFA situations
            group_uefa_cnt[val] += 1
            if group_uefa_cnt[val] == 2:
                conflict = False
                for var_itr in variables:
                    if not var_itr.assigned and var_itr.belong_uefa:
                        var_itr.domain.reduce(val, assigned)
                        if var_itr.domain.remained == 0:
                            conflict = True
                            break
                if conflict:
                    group_uefa_cnt[val] -= 1
                    continue
        if ac3(variables, generate_constraint_queue(variables, variable_idx)):
            tmp = mac(variables, assigned+1, group_uefa_cnt)
            if tmp < assigned:
                if variable.belong_uefa:
                    group_uefa_cnt[val] -= 1
                variable.assigned = False
                return tmp
        if variable.belong_uefa:
            group_uefa_cnt[val] -= 1
        # Retrieves from backups if more than one remaining value
        for i in range(Variable.count):
            variables[i].domain.retrieve(backup_val[i], backup_remained[i])
    variable.assigned = False  # Cancels assignment
    if variable.domain.last_change != -1:  # If the most recent change is not initialization
        return variable.domain.last_change
    else:
        return assigned - 1


def main():
    with open('input.txt') as input_file:  # Gets input and init all info needed for solving this problem
        Domain.init(int(input_file.readline()))
        pot_count = int(input_file.readline())
        variables = []
        pot_countries = [input_file.readline().replace('\n', '').replace('\r', '').split(',') for i in range(pot_count)]
        for pot_itr in range(pot_count):
            for i in pot_countries[pot_itr]:
                variables.append(Variable(i))
        constraint_table = [[0 for i in range(Variable.count)] for j in range(Variable.count)]
        cons1_table = [[0 for i in range(Variable.count)] for j in range(Variable.count)]
        tmp_cnt = 0
        for pot_itr in range(pot_count):
            for i in range(len(pot_countries[pot_itr])):
                for j in range(len(pot_countries[pot_itr])):
                    if i != j:
                        constraint_table[i+tmp_cnt][j+tmp_cnt] = 1
                        cons1_table[i+tmp_cnt][j+tmp_cnt] = 1
            tmp_cnt += len(pot_countries[pot_itr])
        for con_itr in range(CONFEDERATION_COUNT):
            tmp_str = input_file.readline().replace('\n', '').replace('\r', '')
            confederation_name = tmp_str.split(':')[0]
            country_name = tmp_str.split(':')[1].split(',')
            # Checks if obviously no solution
            if confederation_name == 'UEFA':
                if len(country_name) > 2 * Domain.size:
                    print_result()
            elif len(country_name) > Domain.size:
                print_result()

            if country_name[0] == 'None':
                continue
            for i in range(len(country_name)):
                if confederation_name == 'UEFA':
                    variables[Variable.dict[country_name[i]]].belong_uefa = True
                else:
                    for j in range(len(country_name)):
                        if i != j:
                            constraint_table[Variable.dict[country_name[i]]][Variable.dict[country_name[j]]] = 1
        for i in range(Variable.count):
            for j in range(Variable.count):
                if constraint_table[i][j] == 1:
                    variables[i].constraint.append(j)
    # Chooses a pot with most country
    # Tie breaks by choosing a pot with most constraints except constraints created by the same pot
    # Inits by assigning value to each variable in this pot
    max_pot_cnt = 0
    sum_cons = 0
    tmp_cnt = 0
    tmp_rec = 0
    for i in range(pot_count):
        if len(pot_countries[i]) > max_pot_cnt:
            max_pot_cnt = len(pot_countries[i])
            if max_pot_cnt > Domain.size:  # Obviously no solution
                print_result()
            sum_cons = 0
            tmp_rec = tmp_cnt
            for j in range(max_pot_cnt):
                sum_cons += sum(constraint_table[tmp_cnt+j]) - sum(cons1_table[tmp_cnt+j])
        elif len(pot_countries[i]) == max_pot_cnt:
            tmp_sum = 0
            for j in range(max_pot_cnt):
                tmp_sum += sum(constraint_table[tmp_cnt+j]) - sum(cons1_table[tmp_cnt+j])
            if tmp_sum > sum_cons:
                sum_cons = tmp_sum
                tmp_rec = tmp_cnt
        tmp_cnt += len(pot_countries[i])

    # Inits the info about how many UEFA countries in a group
    group_uefa_cnt = [0 for i in range(Domain.size)]
    for i in range(max_pot_cnt):
        variables[tmp_rec+i].assign(i)
        if variables[tmp_rec+i].belong_uefa:
            group_uefa_cnt[i] = 1

    if not ac3(variables, generate_constraint_queue(variables)):
        print_result()
    mac(variables, max_pot_cnt, group_uefa_cnt)
    print_result()


if __name__ == '__main__':
    main()