From fc45306d601aa9d44311ef683a7ffc9422ae0952 Mon Sep 17 00:00:00 2001
From: vg <vgm+dev@devys.org>
Date: Mon, 27 Apr 2020 18:43:55 +0200
Subject: first commit

---
 .gitignore      |   1 +
 solver.py       | 526 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 test_level.yaml |  10 ++
 3 files changed, 537 insertions(+)
 create mode 100644 .gitignore
 create mode 100755 solver.py
 create mode 100644 test_level.yaml

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],
+]
-- 
cgit v1.2.3