from time import time
from threading import Thread
class _rec_tree:
def __init__(self, value=None, base=None, depth=0):
self.base = base
self.value = value
self.children = []
self.depth = depth
def _add_branch(self, value):
new_tree = _rec_tree(value=value, base=self, depth=self.depth + 1)
self.children.append(new_tree)
return new_tree
def __repr__(self):
if self.value != None:
if self.children:
ret = "{}>\t".format(self.value)
else:
ret = "{}".format(self.value)
else:
ret = ""
for n, child in enumerate(self.children):
if n != 0:
ret += "\t" * (self.depth) * 1
if n != len(self.children) - 1:
ret += str(child) + "\n"
else:
ret += str(child)
return ret
[docs]class Solver:
[docs] def __init__(self, CalcularPosibles, basecase):
self.CalcularPosibles = CalcularPosibles
self.basecase = basecase
self._tree = _rec_tree()
self.current_node = self._tree
self._solutions, self._time, self._found_all = None, None, None
@property
def solutions(self):
if not self._time:
self.solve()
return self._solutions
@property
def time(self):
if not self._time:
self.solve()
return self._time
@property
def found_all(self):
if not self._time:
self.solve()
return self._found_all
@property
def tree(self):
if not self._time:
self.solve()
return self._tree
[docs] def solve(self, num_answers=1, max_time=0, threading=False):
parcial = []
answers = []
time_start = time()
if not threading:
limit = self._recursive_solve(parcial, answers, num_answers if num_answers != 0 else float('inf'), max_time,
time_start)
else:
limit = self._threaded_recursive_solve(parcial, answers, num_answers if num_answers != 0 else float('inf'),
max_time, time_start)
found_all = False if (limit and len(answers) < num_answers) else True
self._solutions, self._time, self._found_all = answers, time() - time_start, found_all
return self._solutions
def _threaded_recursive_solve(self, parcial, answers, num_answers, max_time, time_start):
for elem in self.CalcularPosibles(parcial):
thread = Thread(target=self._recursive_solve,
args=(parcial, answers, num_answers, max_time, time_start, True))
thread.start()
def _recursive_solve(self, parcial, answers, num_answers, max_time, time_start, threaded=False):
def _add(posible):
parcial.append(posible)
self.current_node = self.current_node._add_branch(posible)
def _remove():
parcial.pop()
self.current_node = self.current_node.base
if max_time and time() - time_start > max_time:
return True
if self.basecase(parcial):
answers.append(list(parcial))
return False if len(answers) < num_answers else True
elif threaded and len(answers) >= num_answers:
return True
else:
posibles = self.CalcularPosibles(parcial)
p = 0
solved = False
while not solved and len(posibles):
posible = posibles.pop()
_add(posible)
solved = self._recursive_solve(parcial, answers, num_answers, max_time, time_start)
_remove()
p += 1
return solved