aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMarianne Chevrot <blackmoor+git@devys.org>2020-05-20 17:56:17 +0200
committerMarianne Chevrot <blackmoor+git@devys.org>2020-05-20 17:56:17 +0200
commitbc706018b92df380052fe0ab76af533bc8225fa8 (patch)
treec9378c266268ade493d6e971d3b92ea133ccd48f
parent4e959caf03d749f5a5908e074b02cd9cf52606cc (diff)
downloadkana_quest_solver-bc706018b92df380052fe0ab76af533bc8225fa8.tar.gz
kana_quest_solver-bc706018b92df380052fe0ab76af533bc8225fa8.tar.bz2
kana_quest_solver-bc706018b92df380052fe0ab76af533bc8225fa8.zip
speed up thingsHEADmaster
-rw-r--r--.coverage1
-rw-r--r--.gitignore1
-rw-r--r--levels/level_5_slimes/level_5.22.yaml31
-rwxr-xr-xsolver.py60
-rw-r--r--tests_solver/test_solver.py2
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: