import sys

from crossword import *


class CrosswordCreator():

    def __init__(self, crossword):
        """
        Create new CSP crossword generate.
        """
        self.crossword = crossword
        self.domains = {
            var: self.crossword.words.copy()
            for var in self.crossword.variables
        }

    def letter_grid(self, assignment):
        """
        Return 2D array representing a given assignment.
        """
        letters = [
            [None for _ in range(self.crossword.width)]
            for _ in range(self.crossword.height)
        ]
        for variable, word in assignment.items():
            direction = variable.direction
            for k in range(len(word)):
                i = variable.i + (k if direction == Variable.DOWN else 0)
                j = variable.j + (k if direction == Variable.ACROSS else 0)
                letters[i][j] = word[k]
        return letters

    def print(self, assignment):
        """
        Print crossword assignment to the terminal.
        """
        letters = self.letter_grid(assignment)
        for i in range(self.crossword.height):
            for j in range(self.crossword.width):
                if self.crossword.structure[i][j]:
                    print(letters[i][j] or " ", end="")
                else:
                    print("█", end="")
            print()

    def save(self, assignment, filename):
        """
        Save crossword assignment to an image file.
        """
        from PIL import Image, ImageDraw, ImageFont
        cell_size = 100
        cell_border = 2
        interior_size = cell_size - 2 * cell_border
        letters = self.letter_grid(assignment)

        # Create a blank canvas
        img = Image.new(
            "RGBA",
            (self.crossword.width * cell_size,
             self.crossword.height * cell_size),
            "black"
        )
        font = ImageFont.truetype("assets/fonts/OpenSans-Regular.ttf", 80)
        draw = ImageDraw.Draw(img)

        for i in range(self.crossword.height):
            for j in range(self.crossword.width):

                rect = [
                    (j * cell_size + cell_border,
                     i * cell_size + cell_border),
                    ((j + 1) * cell_size - cell_border,
                     (i + 1) * cell_size - cell_border)
                ]
                if self.crossword.structure[i][j]:
                    draw.rectangle(rect, fill="white")
                    if letters[i][j]:
                        w, h = draw.textsize(letters[i][j], font=font)
                        draw.text(
                            (rect[0][0] + ((interior_size - w) / 2),
                             rect[0][1] + ((interior_size - h) / 2) - 10),
                            letters[i][j], fill="black", font=font
                        )

        img.save(filename)

    def solve(self):
        """
        Enforce node and arc consistency, and then solve the CSP.
        """
        self.enforce_node_consistency()
        self.ac3()
        return self.backtrack(dict())

    def enforce_node_consistency(self):
        """
        Update `self.domains` such that each variable is node-consistent.
        (Remove any values that are inconsistent with a variable's unary
         constraints; in this case, the length of the word.)
        """
        for variable in self.domains:
            for word in self.domains[variable].copy():
                if len(word) != variable.length:
                    self.domains[variable].remove(word)

    def revise(self, x, y):
        """
        Make variable `x` arc consistent with variable `y`.
        To do so, remove values from `self.domains[x]` for which there is no
        possible corresponding value for `y` in `self.domains[y]`.

        Return True if a revision was made to the domain of `x`; return
        False if no revision was made.
        """
        revised = False

        # check if the words overlap, if not, return
        overlap = self.crossword.overlaps[x, y]
        if overlap is None:
            return revised

        # return of values in x where a y can exist
        for var_x in self.domains[x].copy():
            consistent = False
            for var_y in self.domains[y]:
                if var_x[overlap[0]] == var_y[overlap[1]]:
                    consistent = True
            if consistent is False:  # doesn't satisfy constraint for (X,Y)
                self.domains[x].remove(var_x)
                revised = True
        return revised

    def ac3(self, arcs=None):
        """
        Update `self.domains` such that each variable is arc consistent.
        If `arcs` is None, begin with initial list of all arcs in the problem.
        Otherwise, use `arcs` as the initial list of arcs to make consistent.

        Return True if arc consistency is enforced and no domains are empty;
        return False if one or more domains end up empty.
        """
        # for structure0.txt:
        #   14D
        #   /
        #  /
        # 01A     41A
        #  \    /
        #   \  /
        #    01D

        # Output of neighbors method is basically the arc for each node
        if arcs is None:
            queue = []
            for variable in self.crossword.variables:
                for neighbor in self.crossword.neighbors(variable):
                    queue.append((variable, neighbor))
        else:
            queue = arcs

        while queue:
            # pop the last time item
            popped_item = queue.pop()
            x, y = popped_item[0], popped_item[1]
            if self.revise(x, y):
                if len(self.domains[x]) == 0:
                    return False
                for z in (self.crossword.neighbors(x)):
                    queue.append((z, x))

        return True

    def assignment_complete(self, assignment):
        """
        Return True if `assignment` is complete (i.e., assigns a value to each
        crossword variable); return False otherwise.
        """
        for variable in self.crossword.variables:
            if variable not in assignment.keys():
                return False
        return True

    def consistent(self, assignment):
        """
        Return True if `assignment` is consistent (i.e., words fit in crossword
        puz
        zle without conflicting characters); return False otherwise.
        """
        # unary constraints
        # 1. Length of the word
        for item in assignment.items():
            if item[0].length != len(item[1]):
                return False

        # binary constraints
        # 1. Overlap Letters
        for item in assignment.items():
            for neighbor in self.crossword.neighbors(item[0]):  # Only care about neighbors
                overlap = self.crossword.overlaps[item[0], neighbor]
                if (overlap is not None) and (neighbor in assignment) and \
                        (item[1][overlap[0]] != assignment[neighbor][overlap[1]]):
                    return False
        # 2. word is not repeated
        # Credit to Denis on stackoverflow for this incredibly clean approach
        # https://stackoverflow.com/questions/1541797/how-do-i-check-if-there-are-duplicates-in-a-flat-list
        if len(assignment.values()) != len(set(assignment.values())):
            return False

        return True

    def order_domain_values(self, var, assignment):
        """
        Return a list of values in the domain of `var`, in order by
        the number of values they rule out for neighboring variables.
        The first value in the list, for example, should be the one
        that rules out the fewest values among the neighbors of `var`.
        """
        # Need to keep track # of elimination in neighbor for each variable, in a dictionary
        # https://www.python.org/dev/peps/pep-0274/
        eliminations = {value: 0 for value in self.domains[var]}

        for value in self.domains[var]:
            for neighbor in self.crossword.neighbors(var):
                # Note that any variable present in assignment already has a value, and therefore
                # shouldn’t be counted when computing the number of values ruled out for neighboring
                # unassigned variables.
                # For domain values that eliminate the same number of possible choices for neighboring
                # variables, any ordering is acceptable.
                # Recall that you can access self.crossword.overlaps to get the overlap, if any, between two variables.
                overlap = self.crossword.overlaps[var, neighbor]
                if (overlap is not None) and (neighbor not in assignment):
                    for neighbor_value in self.domains[neighbor]:
                        if value[overlap[0]] != neighbor_value[overlap[1]]:
                            eliminations[value] = eliminations[value] + 1

        # https://docs.python.org/3/howto/sorting.html
        sorted_values = sorted(eliminations, key=lambda x: x[1])
        return sorted_values

    def select_unassigned_variable(self, assignment):
        """
        Return an unassigned variable not already part of `assignment`.
        Choose the variable with the minimum number of remaining values
        in its domain. If there is a tie, choose the variable with the highest
        degree. If there is a tie, any of the tied variables are acceptable
        return values.
        """
        unassigned_variables = []
        for variable in self.crossword.variables:
            if variable not in assignment:
                unassigned_variables.append(variable)

        # You should return the variable with the fewest
        # number of remaining values in its domain
        remaining_values = {unassigned_variable: len(self.domains[unassigned_variable]) for
                            unassigned_variable in unassigned_variables}
        sorted_remaining_values = sorted(remaining_values.items(), key=lambda x: x[1])
        # If there is a tie between variables, you should choose
        # among whichever among those variables has the largest degree (has the most neighbors).
        # If there is a tie in both cases, you may choose arbitrarily among tied variables.

        # finding duplicate values
        # from dictionary
        # using a naive approach
        # credit https://www.geeksforgeeks.org/python-find-keys-with-duplicate-values-in-dictionary/
        rev_dict = {}
        for key, value in sorted_remaining_values:
            rev_dict.setdefault(value, set()).add(key)
        result = [key for key, values in rev_dict.items()
                  if len(values) > 1]

        # If there is a tie between variables, you should choose
        # among whichever among those variables has the largest degree (has the most neighbors).
        # If there is a tie in both cases, you may choose arbitrarily among tied variables.
        if result is None:
            return sorted_remaining_values[0][0]
        else:
            degrees = {unassigned_variable: len(self.crossword.neighbors(unassigned_variable)) for
                       unassigned_variable in unassigned_variables}
            sorted_remaining_values = sorted(degrees.items(), key=lambda x: x[1])
            return sorted_remaining_values[0][0]

    def backtrack(self, assignment):
        """
        Using Backtracking Search, take as input a partial assignment for the
        crossword and return a complete assignment if possible to do so.

        `assignment` is a mapping from variables (keys) to words (values).

        If no assignment is possible, return None.
        """
        # Check if assignment is complete
        if len(assignment) == len(self.crossword.variables):
            return assignment

        # Try a new variable
        var = self.select_unassigned_variable(assignment)
        for value in self.order_domain_values(var, assignment):
            new_assignment = assignment.copy()
            new_assignment[var] = value
            if self.consistent(new_assignment):
                result = self.backtrack(new_assignment)
                if result is not None:
                    return result
        return None


def main():

    # Check usage
    if len(sys.argv) not in [3, 4]:
        sys.exit("Usage: python generate.py structure words [output]")

    # Parse command-line arguments
    structure = sys.argv[1]
    words = sys.argv[2]
    output = sys.argv[3] if len(sys.argv) == 4 else None

    # Generate crossword
    crossword = Crossword(structure, words)
    creator = CrosswordCreator(crossword)
    assignment = creator.solve()

    # Print result
    if assignment is None:
        print("No solution.")
    else:
        creator.print(assignment)
        if output:
            creator.save(assignment, output)


if __name__ == "__main__":
    main()
