367 lines
9.8 KiB
Python
367 lines
9.8 KiB
Python
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) |