speed up thingsHEADmaster

5 files changed, 45 insertions, 50 deletions

diff --git a/.coverage b/.coverage
deleted file mode 100644
index 6686567..0000000
--- a/.coverage
+++ /dev/null
@@ -1 +0,0 @@
-!coverage.py: This is a private format, don't read it directly!{"lines":{"/home/storage/Games/kana_quest/kana_quest_solver/solver.py":[5,17,18,20,21,23,25,27,29,45,48,51,30,31,35,38,54,56,58,69,79,108,143,150,173,192,195,204,212,219,246,255,258,265,274,308,312,320,329,339,347,357,366,391,39,42,43,61,62,63,64,65,66,67,46,80,205,207,210,81,83,84,85,86,87,88,82,90,91,93,94,95,96,92,98,99,100,105,106,109,110,111,112,70,71,72,73,74,75,76,113,114,213,215,217,115,267,268,269,49,270,266,40,116,118,119,120,121,117,123,124,125,126,127,128,129,130,131,132,134,135,136,137,138,139,140,220,222,228,229,230,231,233,236,237,239,242,243,244,141,259,193,174,175,176,177,178,144,145,146,147,148,179,181,182,151,152,154,155,156,157,159,160,161,162,158,164,165,167,208,168,171,183,184,185,186,187,188,169,313,315,317,206,316,170,166,180,189,261,262,276,277,278,279,280,281,282,283,284,275,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,304,305,260,309,101,102,103,240,104,247,248,249,252,250,253,358,359,330,321,322,323,324,325,326,331,196,197,198,199,200,202,332,334,335,336,223,224,225,226,333,360,361,362,363]}}
\ No newline at end of file
diff --git a/.gitignore b/.gitignore
index d87335f..5cca022 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,3 +2,4 @@ __pycache__
 *.pyc
 *.swp
 *.cache
+.coverage
diff --git a/levels/level_5_slimes/level_5.22.yaml b/levels/level_5_slimes/level_5.22.yaml
new file mode 100644
index 0000000..8969f35
--- /dev/null
+++ b/levels/level_5_slimes/level_5.22.yaml
@@ -0,0 +1,31 @@
+# kana quest grid level 5.22
+size: [7, 4]
+max_actions: 19
+#max_actions: 22
+target_score: 9
+grid: [
+  [ar_d, ki  ], [ar_d, null], [void, null], [slim, u   ], [slim, o   ], [void, null], [void, null],
+  [ar_u, null], [norm, null], [norm, null], [norm, null], [norm, null], [norm, null], [ar_l, si  ],
+  [norm, null], [ar_d, null], [norm, null], [norm, null], [norm, null], [norm, null], [ar_l, nu  ],
+  [ar_u, null], [ar_u, sa  ], [ar_u, 'no'], [ar_u, he  ], [ar_u, ku  ], [froz, ho  ], [froz, ka  ],
+]
+# The kana 'no' need to be protected else the program convert it into False...
+
+# Too big to be run completly, some solutions:
+#KanaGrid (cnt: 19, score: 9):
+#  |∧  ∧||∨  ∨|      |~ u~|
+#  |    ||∧sa∧||<so<||    ||    ||    ||    |
+#  |∨ki∨||[ka]||∧no∧||<nu<||∧ku∧||    ||    |
+#  |∧  ∧||∨  ∨||[ho]||∧he∧||    ||    ||    |
+#================================================================================
+#KanaGrid (cnt: 19, score: 9):
+#  |∧  ∧||∨  ∨|      |~ u~|
+#  |[ka]||∧sa∧||<so<||    ||    ||    ||    |
+#  |∨ki∨||    ||∧no∧||<nu<||∧ku∧||    ||    |
+#  |∧  ∧||∨  ∨||[ho]||∧he∧||    ||    ||    |
+#================================================================================
+#KanaGrid (cnt: 19, score: 9):
+#  |∨ki∨||[ka]|      |~ u~|
+#  |∧  ∧||∧sa∧||<so<||    ||    ||    ||    |
+#  |    ||∨  ∨||∧no∧||<nu<||∧ku∧||    ||    |
+#  |∧  ∧||∨  ∨||[ho]||∧he∧||    ||    ||    |
diff --git a/solver.py b/solver.py
index 8735f79..11ecce0 100755
--- a/solver.py
+++ b/solver.py
@@ -14,15 +14,13 @@ Options:
   --print        Display only the original (unresolved) grid
 '''
 
-#import copy
+import copy
 import os
 import pickle
 import time
-#import zlib
 
 import docopt
 import yaml
-import numpy
 
 class Kana:
 
@@ -82,11 +80,7 @@ class KanaGrid:
 
         self.width = size[0]
         self.height = size[1]
-        #self.grid = grid
-        if type(grid) is list:
-            self.grid = numpy.array(grid)
-        else:
-            self.grid = grid
+        self.grid = copy.copy(grid)
         self.action_count = action_count
         self.score = score
         self.myst_count = myst_count
@@ -95,15 +89,12 @@ class KanaGrid:
     def copy(self):
         new_grid = KanaGrid(
                 (self.width, self.height),
-                None,
-                #self.grid.copy(),
-                #copy.copy(self.grid),
+                grid=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):
@@ -234,19 +225,8 @@ class KanaGrid:
             # the bare minimum equal to 1.
             self.score, self.myst_count = self.longest_chain()
 
-    def get_tuple(self):
-        #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)
-        #print(f'my_tuple: {my_tuple}, hash {hash(my_tuple)}')
-        return (self.width, self.height, tuple(self.grid), self.action_count)
+    def get_grid_hashable(self):
+        return tuple(self.grid)
 
     def get_kana(self, pos):
         if pos[0] < 0 or pos[0] >= self.width:
@@ -279,8 +259,6 @@ class KanaGrid:
         vect = (pos2[0] - pos1[0], pos2[1] - pos1[1])
 
         while self.is_swappable(pos_src, pos_dst):
-            #print("swap between src %s (%s) dst %s (%s)"
-            #      % (kana_src, pos_src, kana_dst, pos_dst))
             self.set_kana(pos_src, kana_dst)
             self.set_kana(pos_dst, kana_src)
 
@@ -400,9 +378,6 @@ 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 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
@@ -412,22 +387,22 @@ def generate_possible_grids(kanagrid):
                     yield (x, y), action_type, new_grid
 
 
-def generate_all_possible_grids(grid, taboos, max_actions):
+def generate_all_possible_grids(grid, bests, max_actions):
     for pos, action_type, new_grid in generate_possible_grids(grid):
-        grid_hash = new_grid.get_tuple()
-        if grid_hash in taboos:
+        key = new_grid.get_grid_hashable()
+        if key in bests and bests[key].action_count <= new_grid.action_count:
             continue
-        taboos.add(grid_hash)
+        bests[key] = new_grid
         new_grid.parent = grid
         if new_grid.action_count >= max_actions:
             yield new_grid
             continue
-        yield from generate_all_possible_grids(new_grid, taboos, max_actions)
+        yield from generate_all_possible_grids(new_grid, bests, max_actions)
 
 
 def search_all_solution(kanagrid, target_score, max_actions):
-    taboos = set()
-    generator = generate_all_possible_grids(kanagrid, taboos=taboos, max_actions=max_actions)
+    bests = {}
+    generator = generate_all_possible_grids(kanagrid, bests=bests, max_actions=max_actions)
     for grid in generator:
         grid.update_score()
         if grid.score >= target_score and grid.myst_count == 0:
@@ -448,16 +423,6 @@ def repr_grid_with_parents(grid):
     return '\n'.join(reversed(items))
 
 
-#def print_score_over(node, target_score):
-#    node.grid.update_score()
-#    if node.grid.score >= target_score:
-#        print("="*80)
-#        print(node_repr_with_parents(node))
-#        return
-#    for child in node.children:
-#        print_score_over(child, target_score)
-
-
 def main():
 
     args = docopt.docopt(__doc__)
@@ -516,6 +481,5 @@ def main():
     print(f'time taken to calculate: {hours:02d}:{minutes:02d}:{seconds:02d}')
 
 
-
 if __name__ == '__main__':
     main()
diff --git a/tests_solver/test_solver.py b/tests_solver/test_solver.py
index 808804e..a1a0e67 100644
--- a/tests_solver/test_solver.py
+++ b/tests_solver/test_solver.py
@@ -15,7 +15,6 @@ def test_is_swappable():
             [Kana("froz", "su"), Kana("norm", "su")],
             [Kana("norm", "su"), Kana("norm"      )],
             [Kana("norm"      ), Kana("froz", "su")],
-            [Kana("norm"      ), Kana("norm"      )],
     ]
 
     for swappable_grid in swappable_grids:
@@ -26,6 +25,7 @@ def test_is_swappable():
     not_swappable_grids = [
             [Kana("norm", "su"), Kana("rock", "su")],
             [Kana("froz", "su"), Kana("froz", "su")],
+            [Kana("norm"      ), Kana("norm"      )],
     ]
 
     for not_swappable_grid in not_swappable_grids: