From bc706018b92df380052fe0ab76af533bc8225fa8 Mon Sep 17 00:00:00 2001 From: Marianne Chevrot Date: Wed, 20 May 2020 17:56:17 +0200 Subject: speed up things --- .coverage | 1 - .gitignore | 1 + levels/level_5_slimes/level_5.22.yaml | 31 ++++++++++++++++++ solver.py | 60 +++++++---------------------------- tests_solver/test_solver.py | 2 +- 5 files changed, 45 insertions(+), 50 deletions(-) delete mode 100644 .coverage create mode 100644 levels/level_5_slimes/level_5.22.yaml 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∧||= 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: -- cgit v1.2.3