From d24d78848bd0ed13c1f771dbd5ad5e85e573f09e Mon Sep 17 00:00:00 2001 From: vg Date: Wed, 20 May 2020 00:25:01 +0200 Subject: optimize speed --- solver.py | 41 +++++++++++++++++++++++++++-------------- 1 file changed, 27 insertions(+), 14 deletions(-) diff --git a/solver.py b/solver.py index a03b267..3663b75 100755 --- a/solver.py +++ b/solver.py @@ -83,22 +83,28 @@ class KanaGrid: self.width = size[0] self.height = size[1] #self.grid = grid - self.grid = numpy.array(grid) + if type(grid) is list: + self.grid = numpy.array(grid) + else: + self.grid = grid self.action_count = action_count self.score = score self.myst_count = myst_count self.parent = parent def copy(self): - return KanaGrid( + new_grid = KanaGrid( (self.width, self.height), - self.grid.copy(), + None, + #self.grid.copy(), #copy.copy(self.grid), action_count=self.action_count, score=self.score, myst_count=self.myst_count, parent=self.parent, ) + new_grid.grid = self.grid.copy() + return new_grid def is_swappable(self, pos1, pos2): kana1 = self.get_kana(pos1) @@ -228,7 +234,7 @@ class KanaGrid: # the bare minimum equal to 1. self.score, self.myst_count = self.longest_chain() - def get_hash(self): + def get_tuple(self): #data = ''.join(( # str(self.width), # str(self.height), @@ -239,9 +245,8 @@ class KanaGrid: #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) + return (self.width, self.height, tuple(self.grid), self.action_count) def get_kana(self, pos): if pos[0] < 0 or pos[0] >= self.width: @@ -395,26 +400,34 @@ 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: # syntax in numpy ? + #if new_grid: # and new_grid.grid != kanagrid.grid: # syntax in numpy ? + #if new_grid and not (new_grid.grid == kanagrid.grid).all(): # and new_grid.grid != kanagrid.grid: # syntax in numpy ? + #if new_grid and not numpy.array_equal(new_grid.grid, kanagrid.grid): + if new_grid: + # better perf to have only new_grid is None check and not + # comparison if move has given same grid as having exact + # same grid is less likely than having action() filter + # useless actions and comparing all grid two times (one + # here and one in the taboos) is more consuming. yield (x, y), action_type, new_grid -def generate_all_possible_grids(grid, grid_hashes, max_actions): +def generate_all_possible_grids(grid, taboos, max_actions): for pos, action_type, new_grid in generate_possible_grids(grid): - grid_hash = new_grid.get_hash() - if grid_hash in grid_hashes: + grid_hash = new_grid.get_tuple() + if grid_hash in taboos: continue - grid_hashes.add(grid_hash) + taboos.add(grid_hash) new_grid.parent = grid if new_grid.action_count >= max_actions: yield new_grid continue - yield from generate_all_possible_grids(new_grid, grid_hashes, max_actions) + yield from generate_all_possible_grids(new_grid, taboos, 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) + taboos = set() + generator = generate_all_possible_grids(kanagrid, taboos=taboos, max_actions=max_actions) for grid in generator: grid.update_score() if grid.score >= target_score and grid.myst_count == 0: -- cgit v1.2.3