path: root/solver.py

#!/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 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 __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 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


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 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 main():

    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)


if __name__ == '__main__':
    main()