#!/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 with parents [DEFAULT is 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: valid_types_for_chain = ("froz", "norm", "rock") 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 generate_valid_pos_for_chain(self): for y in range(self.height): for x in range(self.width): kana = self.get_kana((x, y)) if kana.type_name in self.valid_types_for_chain: yield (x, y) def populate_chain(self, pos1, chain_positions): if pos1 in chain_positions: return kana1 = self.get_kana(pos1) chain_positions.add(pos1) pos2_list = [ (pos1[0], pos1[1]-1), # up (pos1[0]+1, pos1[1]), # right (pos1[0], pos1[1]+1), # down (pos1[0]-1, pos1[1]), # left ] for pos2 in pos2_list: if pos2 in chain_positions: continue kana2 = self.get_kana(pos2) if kana2.type_name in self.valid_types_for_chain: if is_kana_compatible(kana1, kana2): self.populate_chain(pos2, chain_positions) def longest_chain(self): already_evaluated_pos = set() highest_length = 0 highest_length_chain = 0 for pos in self.generate_valid_pos_for_chain(): if pos in already_evaluated_pos: continue chain = set() self.populate_chain(pos, chain) already_evaluated_pos = already_evaluated_pos.union(chain) if highest_length < len(chain): highest_length = len(chain) highest_length_chain = chain return highest_length #, highest_length_chain # easy to add if needed def update_score(self): self.score = self.longest_chain() 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(repr_grid_with_parents(grid)) else: print(grid) # action by lvl in files if __name__ == '__main__': main()