From 89468c83af1885922bdb4a4d7658f6a04cb6f953 Mon Sep 17 00:00:00 2001
From: vg <vgm+dev@devys.org>
Date: Tue, 19 May 2020 23:34:26 +0200
Subject: try to switch to new algorithm for speeding up solver

---
 solver.py | 74 ++++++++++++++++++++++++++++++++++++++-------------------------
 1 file changed, 45 insertions(+), 29 deletions(-)

diff --git a/solver.py b/solver.py
index df62f64..a03b267 100755
--- a/solver.py
+++ b/solver.py
@@ -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__)
-- 
cgit v1.2.3