diff options
| -rwxr-xr-x | solver.py | 74 |
1 files changed, 45 insertions, 29 deletions
@@ -22,6 +22,7 @@ import zlib import docopt import yaml +import numpy class Kana: @@ -64,6 +65,10 @@ class Kana: def __eq__(self, other): return self.type_name == other.type_name and self.kana == other.kana + def __hash__(self): + #print(f'hash of Kana({self}): {hash((self.type_name, self.kana))}') + return hash((self.type_name, self.kana)) + kana_void = Kana.create('void') @@ -77,7 +82,8 @@ class KanaGrid: self.width = size[0] self.height = size[1] - self.grid = grid + #self.grid = grid + self.grid = numpy.array(grid) self.action_count = action_count self.score = score self.myst_count = myst_count @@ -86,7 +92,8 @@ class KanaGrid: def copy(self): return KanaGrid( (self.width, self.height), - copy.copy(self.grid), + self.grid.copy(), + #copy.copy(self.grid), action_count=self.action_count, score=self.score, myst_count=self.myst_count, @@ -222,13 +229,19 @@ class KanaGrid: self.score, self.myst_count = self.longest_chain() def get_hash(self): - data = ''.join(( - str(self.width), - str(self.height), - str(self.grid), - str(self.action_count), - )) - return zlib.crc32(data.encode('utf8')) + #data = ''.join(( + # str(self.width), + # str(self.height), + # str(self.grid), + # str(self.action_count), + # )) + #return zlib.crc32(data.encode('utf8')) + #return hash((self.width, self.height, str(self.grid), self.action_count)) + #my_tuple = (self.width, self.height, str(self.grid.all()), self.action_count) + #my_tuple = (self.width, self.height, str(self.grid.all()), self.action_count) + my_tuple = (self.width, self.height, tuple(self.grid), self.action_count) + #print(f'my_tuple: {my_tuple}, hash {hash(my_tuple)}') + return hash(my_tuple) def get_kana(self, pos): if pos[0] < 0 or pos[0] >= self.width: @@ -382,18 +395,36 @@ def generate_possible_grids(kanagrid): for x in range(kanagrid.width): for action_type in KanaGrid.actions: new_grid = kanagrid.action((x, y), action_type) - if new_grid and new_grid.grid != kanagrid.grid: + if new_grid: # and new_grid.grid != kanagrid.grid: # syntax in numpy ? yield (x, y), action_type, new_grid -def generate_all_possible_grids(grid, grids, max_actions): +def generate_all_possible_grids(grid, grid_hashes, max_actions): for pos, action_type, new_grid in generate_possible_grids(grid): grid_hash = new_grid.get_hash() - if grid_hash in grids or new_grid.action_count > max_actions: + if grid_hash in grid_hashes: continue - grids[grid_hash] = new_grid + grid_hashes.add(grid_hash) new_grid.parent = grid - generate_all_possible_grids(new_grid, grids, max_actions) + if new_grid.action_count >= max_actions: + yield new_grid + continue + yield from generate_all_possible_grids(new_grid, grid_hashes, max_actions) + + +def search_all_solution(kanagrid, target_score, max_actions): + grid_hashes = set() + generator = generate_all_possible_grids(kanagrid, grid_hashes=grid_hashes, max_actions=max_actions) + for grid in generator: + grid.update_score() + if grid.score >= target_score and grid.myst_count == 0: + yield grid + + +def get_solutions_from_cache(cache): + for solution in cache['solutions']: + kanagrid = KanaGrid.load_reversed_parents(solution) + yield kanagrid def repr_grid_with_parents(grid): @@ -414,21 +445,6 @@ def print_score_over(node, target_score): print_score_over(child, target_score) -def search_all_solution(kanagrid, target_score, max_actions): - grids = {} - generate_all_possible_grids(kanagrid, grids=grids, max_actions=max_actions) - for grid in grids.values(): - grid.update_score() - if grid.score >= target_score and grid.myst_count == 0: - yield grid - - -def get_solutions_from_cache(cache): - for solution in cache['solutions']: - kanagrid = KanaGrid.load_reversed_parents(solution) - yield kanagrid - - def main(): args = docopt.docopt(__doc__) |