aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorvg <vgm+dev@devys.org>2020-05-20 00:25:01 +0200
committervg <vgm+dev@devys.org>2020-05-20 00:25:01 +0200
commitd24d78848bd0ed13c1f771dbd5ad5e85e573f09e (patch)
treea143d84105e3b240d042d4dfa640601f94049405
parent89468c83af1885922bdb4a4d7658f6a04cb6f953 (diff)
downloadkana_quest_solver-d24d78848bd0ed13c1f771dbd5ad5e85e573f09e.tar.gz
kana_quest_solver-d24d78848bd0ed13c1f771dbd5ad5e85e573f09e.tar.bz2
kana_quest_solver-d24d78848bd0ed13c1f771dbd5ad5e85e573f09e.zip
optimize speed
-rwxr-xr-xsolver.py41
1 files 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: