diff options
| -rw-r--r-- | .coverage | 1 | ||||
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | levels/level_5_slimes/level_5.22.yaml | 31 | ||||
| -rwxr-xr-x | solver.py | 60 | ||||
| -rw-r--r-- | tests_solver/test_solver.py | 2 |
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 @@ -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∧|| || || | @@ -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: |