diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rwxr-xr-x | solver.py | 526 | ||||
| -rw-r--r-- | test_level.yaml | 10 |
3 files changed, 537 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..bee8a64 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +__pycache__ diff --git a/solver.py b/solver.py new file mode 100755 index 0000000..7a5ce13 --- /dev/null +++ b/solver.py @@ -0,0 +1,526 @@ +#!/usr/bin/env python3 +# Copyright 2020 vg +# SPDX-License-Identifier: MIT + +''' +Usage: solver.py -h|--help + solver.py [-P] YAML_GRID + + +Options: + -h, --help Display this help message + -P Display solution without parents +''' + +import copy +import zlib + +import docopt +import yaml + + +class Kana: + + def __init__(self, type_name, kana=None): + self.type_name = type_name + self.kana = kana + + #print(type_name) + #print(kana) + assert type_name in ('void', 'norm', 'empt', 'froz', 'rock', 'myst') + if type_name in ('norm', 'rock', 'froz', 'myst'): + assert kana[0] in ('k', 's', 'n') + assert kana[1] in ('a', 'i', 'u', 'e', 'o') + + def __repr__(self): + return "%s(%s)" % (self.type_name, self.kana) + + def __eq__(self, other): + return self.type_name == other.type_name and self.kana == other.kana + +kana_void = Kana("void") + + + + +def is_swappable(kana1, kana2): + table_ok = { + "norm": ("norm", "empt", "froz"), + "froz": ("norm", "empt"), + } + if kana1.type_name in table_ok: + if kana2.type_name in table_ok[kana1.type_name]: + return True + elif kana2.type_name in table_ok: + if kana1.type_name in table_ok[kana2.type_name]: + return True + return False + + +def test_is_swappable(): + assert is_swappable(Kana("norm"), Kana("norm")) + assert is_swappable(Kana("froz"), Kana("norm")) + assert is_swappable(Kana("norm"), Kana("empt")) + assert is_swappable(Kana("empt"), Kana("froz")) + assert not is_swappable(Kana("norm"), Kana("rock")) + assert not is_swappable(Kana("froz"), Kana("froz")) + assert not is_swappable(Kana("empt"), Kana("empt")) + + + +class KanaGrid: + + def __init__(self, size, grid, action_count=0, score=0, parent=None): + + self.width = size[0] + self.height = size[1] + self.grid = grid + self.action_count = action_count + self.score = score + self.parent = None + + def copy(self): + return KanaGrid( + (self.width, self.height), + copy.copy(self.grid), + action_count=self.action_count, + score=self.score, + parent=self.parent, + ) + + def action(self, pos, action_type): + kana = self.get_kana(pos) + if action_type == "reveal": + if kana.type_name == "myst": + new_grid = self.copy() + new_grid.action_count += 1 + new_grid.set_kana(pos, Kana("norm", kana.kana)) + return new_grid + elif action_type in ("up", "right", "down", "left"): + if action_type == "up": + pos_dest = (pos[0], pos[1]-1) + elif action_type == "right": + pos_dest = (pos[0]+1, pos[1]) + elif action_type == "down": + pos_dest = (pos[0], pos[1]+1) + elif action_type == "left": + pos_dest = (pos[0]-1, pos[1]) + kana_dest = self.get_kana(pos_dest) + if is_swappable(kana, kana_dest): + new_grid = self.copy() + new_grid.action_count += 1 + new_grid.swap_kana(pos, pos_dest) + return new_grid + + def __repr__(self): + self.update_score() + return ( + ('KanaGrid (cnt: %d, score:%d): \n ' % (self.action_count, self.score)) + + '\n '.join(repr_grid(self.grid, (self.width, self.height)).splitlines()) + ) + + + def __eq__(self, other): + return ( + self.width == other.width + and self.height == other.height + and self.grid == other.grid + and self.action_count == other.action_count + ) + + + def update_score(self): + chain_length = 0 + kana_iter = iter(self.grid) + valid_types_for_chain = ("froz", "norm", "rock") + for y in range(self.height): + for x in range(self.width): + kana = next(kana_iter) + + if kana.type_name not in valid_types_for_chain: + continue + + kana_checks = [ + self.get_kana((x, y-1)), + self.get_kana((x+1, y)), + self.get_kana((x, y+1)), + self.get_kana((x-1, y)), + ] + + for kana_check in kana_checks: + if kana_check == kana_void: + continue + elif kana_check.type_name == "empt": + continue + elif kana_check.type_name == "myst": # don't care as brutforce + continue + elif kana_check.type_name in valid_types_for_chain: + if is_kana_compatible(kana, kana_check): + chain_length += 1 + + self.score = chain_length / 2 + 1 + + + + 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')) + + def get_kana(self, pos): + if pos[0] < 0 or pos[0] >= self.width: + return kana_void + elif pos[1] < 0 or pos[1] >= self.height: + return kana_void + + return self.grid[pos[0]+pos[1]*self.width] + + def set_kana(self, pos, kana): + if pos[0] < 0 or pos[0] >= self.width: + return + elif pos[1] < 0 or pos[1] >= self.height: + return + self.grid[pos[0]+pos[1]*self.width] = kana + + def swap_kana(self, pos1, pos2): + kana_dst = self.get_kana(pos2) + + if kana_dst.type_name == "froz": + pos_tmp = pos1 + pos1 = pos2 + pos2 = pos_tmp + kana_dst = self.get_kana(pos2) + + # important + kana_src = self.get_kana(pos1) + pos_src = pos1 + pos_dst = pos2 + vect = (pos2[0] - pos1[0], pos2[1] - pos1[1]) + + while is_swappable(kana_src, kana_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) + + if kana_src.type_name != "froz": + break + + pos_src = pos_dst + pos_dst = (pos_dst[0] + vect[0], pos_dst[1] + vect[1]) + kana_dst = self.get_kana(pos_dst) + + + def load(input_dict): + grid = [] + for serialized_kana in input_dict['grid']: + if serialized_kana[0] == 'void': + grid.append(kana_void) + else: + grid.append(Kana(serialized_kana[0], serialized_kana[1])) + return KanaGrid(input_dict['size'], grid) + + def dump(self, stream): + raise NotImplemented + + + +def test_kana_grid(): + + inital_grid = [ + kana_void , Kana("myst", "su"), kana_void , Kana("myst", "ko"), kana_void , + Kana("froz", "se"), Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "so"), + Kana("froz", "ku"), Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "no"), + kana_void , kana_void , Kana("rock", "ka"), kana_void , kana_void , + ] + initial_grid_size = 5, 4 + chain_target = 7 + + expected_grid = [ + kana_void , Kana("myst", "su"), kana_void , Kana("myst", "ko"), kana_void , + Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "se"), Kana("froz", "so"), + Kana("froz", "ku"), Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "no"), + kana_void , kana_void , Kana("rock", "ka"), kana_void , kana_void , + ] + + kanagrid_orig = KanaGrid(initial_grid_size, initial_grid) + kanagrid_new = kanagrid_orig.action(pos=(0, 1), action_type="right") + + print("kanagrid_orig") + print(kanagrid_orig) + print("kanagrid_new") + print(kanagrid_new) + print("expected_grid") + display_grid(expected_grid, initial_grid_size) + + assert kanagrid_new.grid == expected_grid + + + + + + + +def repr_grid(grid, grid_size): + lines = [] + kana_iter = iter(grid) + for y in range(grid_size[1]): + line = "" + for x in range(grid_size[0]): + kana = next(kana_iter) + if kana.type_name == "void": + line += " " + elif kana.type_name == "empt": + line += "| |" + elif kana.type_name == "myst": + line += "| ?? |" + elif kana.type_name in ("froz", "norm", "rock"): + line += "| %s |" % kana.kana + lines.append(line) + return '\n'.join(lines) + + +def display_grid(grid, grid_size): + print(repr_grid(grid, grid_size)) + + +def is_kana_compatible(kana1, kana2): + if kana1.kana[0] == kana2.kana[0] or kana1.kana[1] == kana2.kana[1]: + return True + return False + + + +def generate_possible_grids(kanagrid): + for y in range(kanagrid.height): + for x in range(kanagrid.width): + for action_type in ("reveal", "up", "right", "down", "left"): + new_grid = kanagrid.action((x, y), action_type) + #if new_grid and new_grid.grid != kanagrid.grid: + # yield (x, y), action_type, new_grid + if new_grid is not None: + yield (x, y), action_type, new_grid # debug test + + + +class Node: + + def __init__(self, grid, parent=None, pos=None, action_type=None): + + self.grid = grid + self.parent = parent + self.action_type = action_type + self.pos = pos + self.children = [] + + def append(self, node): + self.children.append(node) + + def __repr__(self): + + return '(%s, %s, %s, %s, [%s])' % ( + id(self.parent), + self.grid.action_count, + self.pos, + self.action_type, + len(self.children)) + + #if not self.children: + # return repr(self.grid) + + #return ('Node(%d): ' % self.children[0].grid.action_count) + repr(self.children) + + +def make_actions(node, taboos={}, max_action=100, debug=False): + for pos, action_type, new_grid in generate_possible_grids(node.grid): + + #id_grid = id(new_grid.grid) + #if id_grid in taboos: + # best_count = taboos[id_grid] + # if new_grid.action_count >= best_count: + # continue + + #taboos[id_grid] = new_grid.action_count + + #node_test = node + #while node_test: + # if new_grid.grid == node_test.grid.grid: + # continue + # node_test = node_test.parent + + new_node = Node(new_grid, parent=node, pos=pos, action_type=action_type) + node.append(new_node) + + if debug: + #print() + #print("pos %s, action: %s" % (pos, action_type)) + print(new_grid) + + #if score(new_grid.grid) % 2: + #print(node, new_grid) + + if new_grid.action_count < max_action: + make_actions(new_node, taboos=taboos, max_action=max_action, debug=debug) + + +def generate_all_possible_grids(grid, grids, 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: + continue + grids[grid_hash] = new_grid + new_grid.parent = grid + generate_all_possible_grids(new_grid, grids, max_actions) + + +def node_repr_with_parents(node): + items = [] + while node: + items.append("%s %s" % (str(node), str(node.grid))) + node = node.parent + return '\n'.join(reversed(items)) + + +def repr_grid_with_parents(grid): + items = [] + while grid: + items.append(str(grid)) + grid = grid.parent + 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 fact(n): + if n == 1: + return 1 + return n*fact(n-1) + + +def get_leafs(node): + if not node.children: + return [node] + children_extended = [] + for child in node.children: + children_extended.extend(get_leafs(child)) + return children_extended + + +def main(): + + #tree = KanaTree(root=grid) + + #my_grid = [ + # kana_void , Kana("myst", "su"), kana_void , Kana("myst", "ko"), kana_void , + # Kana("froz", "se"), Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "so"), + # Kana("froz", "ku"), Kana("empt" ), Kana("empt" ), Kana("empt" ), Kana("froz", "no"), + # kana_void , kana_void , Kana("rock", "ka"), kana_void , kana_void , + #] + #my_grid_size = 5, 4 + #chain_target = 7 + #kanagrid = KanaGrid(my_grid_size, my_grid) + + #print(kanagrid) + #root = Node(kanagrid) + + # guided + #node = root + #make_actions(node, max_action=1) + #node = node.children[1] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[1] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[4] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[3] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[4] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[5] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[5] + #print(node.grid) + #make_actions(node, max_action=1) + #node = node.children[0] + #print(node.grid) + #print_score_over(root, 0) + + # action by lvl1 + #make_actions(root, max_action=1) + #children_lvl1 = root.children + #print("%d lvl1 calculated" % len(root.children)) + #for index, child in enumerate(children_lvl1): + # print("calculating child %d" % index) + # #print(node_repr_with_parents(child)) + # make_actions(child, max_action=8) + # print_score_over(root, 6) + # # make space in memory + # child.children = [] + + # action by lvl2 + #make_actions(root, max_action=2) + #children_lvl2 = get_leafs(root) + #print("%d lvl2 calculated" % len(children_lvl2)) + #for index, child in enumerate(children_lvl2): + # print("calculating child %d" % index) + # #print(node_repr_with_parents(child)) + # make_actions(child, max_action=8-2) + # print_score_over(root, 6) + # child.children = [] + + #make_actions(root, max_action=8) + #print_score_over(root, 7) + + #for x, y in ((0,1), (4, 2), (2, 3)): + # print(grid.get_kana((x, y))) + + args = docopt.docopt(__doc__) + with open(args['YAML_GRID'], encoding='utf8') as stream: + input_dict = yaml.safe_load(stream) + kanagrid = KanaGrid.load(input_dict) + target_score = input_dict['target_score'] + max_actions = input_dict['max_actions'] + print('Size %dx%d' % (kanagrid.width, kanagrid.height)) + print('Target score %d' % target_score) + print('Max actions %d' % max_actions) + print('Initial grid:') + print(kanagrid) + + del input_dict + + 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: + print("="*80) + if args['-P']: + print(grid) + else: + print(repr_grid_with_parents(grid)) + + + + + # action by lvl in files + +if __name__ == '__main__': + main() diff --git a/test_level.yaml b/test_level.yaml new file mode 100644 index 0000000..b540b94 --- /dev/null +++ b/test_level.yaml @@ -0,0 +1,10 @@ +# kana quest grid +size: [5, 4] +max_actions: 9 +target_score: 7 +grid: [ + [void, null], [myst, su ], [void, null], [myst, ko ], [void, null], + [froz, se ], [empt, null], [empt, null], [empt, null], [froz, so ], + [froz, ku ], [empt, null], [empt, null], [empt, null], [froz, 'no'], + [void, null], [void, null], [rock, ka ], [void, null], [void, null], +] |