from copy import copy, deepcopy

def ToUpper(s):
    return s.upper()


## ----------------------------------------------------------------------------
##-Point
class Point:
    def __init__(self, r=0, c=0):
        self.row = r
        self.col = c

    def __str__(self):
        return f'({self.row},{self.col})'


## ----------------------------------------------------------------------------
##-Span
class Spans:

    spans = []

    def __init__(self, p, l, v):
        self.point = p
        self.len = l
        self.vert = v
    
    def GetPoint(self, i):
        assert(i >= 0 and i < self.len)
        if self.vert:
            return Point(self.point.row + i, self.point.col)
        else:
            return Point(self.point.row, self.point.col + i)
    
    def __str__(self):
        return f'[{self.point} len={self.len} vert={self.vert}]'


## ----------------------------------------------------------------------------
##-Words
class Words:

    def __init__(self):
        self.word = []


## ----------------------------------------------------------------------------
##-Library
class Library:

    def __init__(self):
        self.words_ = Words()  # master vector of word
        self.counts_ = {}
        self.word_map_ = {}  # hash table

    # Returns NULL if can't find any matches to the given pattern
    def FindWord(self, s):
        return [key for key, values in self.word_map_.items() if s in values]

    def IsWord(self, s):
        return s in self.word_map_

    def ComputeStats(self):
        for i in range(18):
            self.counts_[i] = []
        for s in self.words_:
            _len = len(s.word)
            if _len <= 18:
                self.counts_[_len-1].append(_len)

    def PrintStats(self):
        print("Here are the counts of each word length")
        for k,v in self.counts_.items():
            if k != 0:
                print(f"[{k}] {len(v)}")

    def GetWord(self, i):
        assert (i >= 0 and i < len(self.words_))
        return self.words_[i]

    def CreatePatternHash(self, w):
        len_w = len(w)
        num_patterns = 1 << len_w
        self.word_map_[w] = []
        for i in range(num_patterns):
            tmp = list(w)
            for j in range(len_w):
                if ((i >> j) & 1):
                    tmp[j] = "-"
            self.word_map_[w].append("".join(tmp))

    def ReadFromFile(self, filename, max_size):
        with open(filename, 'r') as f:
            for line in f:
                line = ToUpper(line.rstrip())
                len_w = len(line)
                if len_w <= max_size:
                    self.words_.word.append(line)
                    self.CreatePatternHash(line)
        print(f"Read {len(self.words_.word)} words from file '{filename}'")

    def DebugBuckets(self):
        for i, (k,v) in enumerate(self.word_map_.items()):
            print(f"[{i}] {len(v)}")

lib = Library()

## ----------------------------------------------------------------------------
##-Attr
class Attr:

    has_letters = False
    has_blanks = False
    
    def __init__(self):
        pass

    def is_empty():
        return (Attr.has_blanks and not Attr.has_letters)

    def is_partial():
        return (Attr.has_blanks and Attr.has_letters)

    def is_full():
        return (not Attr.has_blanks and Attr.has_letters)


## ----------------------------------------------------------------------------
##-Grid
class Grid:

    def __init__(self, n):
        self.name = n
        self.lines = []
        self.sp = Spans.spans

    def rows(self):
        return len(self.lines)

    def cols(self):
        if self.lines == []:
            return 0
        else:
            return len(self.lines[0])
    
    def max_size(self):
        return max(self.rows(), self.cols())

    # Returns character value of the box at point 'p'
    # 'p' must be in bounds
    def box(self, p):
        assert self.in_bounds(p), p
        return self.lines[p.row][p.col]

    def write_box(self, p, c):
        assert self.in_bounds(p), p
        self.lines[p.row][p.col] = c

    # Returns True if the point p is a '.' "block" in the grid
    # 'p' must be in bounds
    def is_block(self, p):
        return self.box(p) == '.'

    def is_blank(self, p):
        return self.box(p) == '-'

    def is_letter(self, p):
        c = self.box(p)
        return c >= 'A' and c <= 'Z'

    def in_bounds(self, p):
        return p.row >= 0 and p.row < self.rows() and p.col >= 0 and p.col < self.cols()

    # Fills in attributes of the string
    def GetString(self, sp, attr):
        len_ = sp.len
        temp = [] 
        for i in range(len_):
            p = sp.GetPoint(i)
            c = self.box(p)
            if c == '-':
                attr.has_blanks = True
            elif c >= 'A' and c <= 'Z':
                attr.has_letters = True
            temp.append(c)
        return ''.join(temp)

    def WriteString(self, sp, s):
        len_ = sp.len
        assert(len(s) == len_)
        new_str = []
        for i in range(len_):
            p = sp.GetPoint(i)
            self.write_box(p, s[i])

    # Next increments the point across the grid, one box at a time
    # Returns True if point is still in bounds
    def Next(self, p, vert):
        if vert:
            p.row += 1
            if p.row >= self.rows():
                p.row = 0
                p.col += 1
        else:
            p.col += 1
            if p.col >= self.cols():
                p.col = 0
                p.row += 1        
        return self.in_bounds(p)

    # NextStopAtWrap is like "Next" except it returns False at every wrap
    # Returns True if we stay in the same line
    def NextStopAtWrap(self, p, vert):
        wrap = False
        if vert:
            p.row += 1
            if p.row >= self.rows():
                p.row = 0
                p.col += 1
                wrap = True
        else:
            p.col += 1
            if p.col >= self.cols():
                p.col = 0
                p.row += 1
                wrap = True        
        return not wrap

    def FillSpans_(self, vert):
        p = Point()
        while (self.in_bounds(p)):
            while (self.in_bounds(p) and self.is_block(p)):
                self.Next(p, vert)
            if not self.in_bounds(p):
                return
            startp = copy(p)

            len_ = 0
            keep_going = True
            while (keep_going and not self.is_block(p)):
                keep_going = self.NextStopAtWrap(p, vert)
                len_ += 1
            self.sp.append(Spans(startp, len_, vert))
    
    def FillSpans(self):
        self.FillSpans_(vert=False)  # horiz
        self.FillSpans_(vert=True)  # vert

    def LoadFromFile(self, filename):
        with open(filename, 'r') as f:
            for line in f:
                if not line.startswith('#'):
                    self.lines.append(list(line.rstrip()))

    def Check(self):
        for s in self.lines:
            assert len(s) == self.cols()

    def Print(self):
        print(f"Grid: {self.name} "
              f"(rows={self.rows()},"
              f" cols={self.cols()},"
              f" max_size={self.max_size()})")
        for s in self.lines:
            print(f"  {''.join(s)}")

    def PrintSpans(self):
        print(f"Spans:")
        for span in self.sp:
            print(f"  {span} {self.GetString(span, Attr())}")

## ----------------------------------------------------------------------------
##-Slot
class Slot:

    slots = []

    def __init__(self, s, p):
        self.span = s
        self.pattern = p
 
    def __str__(self):
        return f"{self.span} '{self.pattern}'"


## ----------------------------------------------------------------------------
##-Solver
class Solver:

    def __init__(self):
        pass

    def ExistsInSet(self, set_, s):
        return s in set_

    def AddToSet(self, set_, s):
        assert(not self.ExistsInSet(set_, s))
        set_.add(s)
    
    def Solve(self, grid):
        print(f"Solving this grid")
        grid.Print()
        self.Loop(grid, 0)

    def Loop(self, grid, depth):
        depth += 1

        empty_slots = []
        partial_slots = []  # these are the ones we want to work on
        full_slots = [] 
        for s in grid.sp:
            attr = Attr
            temp = grid.GetString(s, attr)
            if attr.is_empty():
                empty_slots.append(Slot(s, temp))
            elif attr.is_partial():
                partial_slots.append(Slot(s, temp))
            elif attr.is_full():
                full_slots.append(Slot(s, temp))
            Attr.has_letters = False
            Attr.has_blanks = False
        num_empty = len(empty_slots)
        num_partial = len(partial_slots)
        num_full = len(full_slots)

        # need to check that all words so far are valid!
        for slot in full_slots:
            if not lib.IsWord(slot.pattern):
                return

        # need to check that all words are unique! no duplicates allowed.
        my_set = set()
        for slot in full_slots:
          if self.ExistsInSet(my_set, slot.pattern):
              return
          self.AddToSet(my_set, slot.pattern)

        if (num_partial == 0 and num_empty == 0):
            print("SOLUTION!!")
            grid.Print()
            return

        assert(num_partial > 0)
        self.CommitSlot(grid, partial_slots[0], depth)

    def CommitSlot(self, grid, slot, depth):
        grid = deepcopy(grid)
 
        words = lib.FindWord(slot.pattern)
        if words:
            for w in words:
                grid.WriteString(slot.span, w)
                self.Loop(grid, depth)

## ----------------------------------------------------------------------------
if __name__ == "__main__":
    grid = Grid("MY GRID")
    grid.LoadFromFile('test')
    grid.Check()
    grid.FillSpans()
    grid.PrintSpans()

    lib.ReadFromFile("top_12000.txt", grid.max_size())
    
    solver = Solver()
    solver.Solve(grid)