A MOLEK-SYNTEZ solitaire solver written in python

molek-solitaire-solver.py

from copy import deepcopy
from random import shuffle
from queue import PriorityQueue
import time

import _pickle as cPickle

class Card():
    TEXT2NUM = {
        "6": 6, "7": 7, "8": 8, "9": 9, "0": 10,
        "V": 11, "D": 12, "K": 13, "T": 14
    }
    NUM2TEXT = {v: k for k, v in TEXT2NUM.items()}
    CARD_LIST = list(TEXT2NUM.keys())

    def __init__(self, number=None):
        if number:
            # todo(komori): range check
            self.number = number

    @staticmethod
    def from_str(text):
        # todo(komori): error handle
        return Card(Card.TEXT2NUM[text])

    def goes_on(self, other):
        return self.number + 1 == other.number

    def __str__(self):
        # todo(komori): error handle
        return Card.NUM2TEXT[self.number]

    def __eq__(self, other):
        return isinstance(other, Card) and self.number == other.number

    def __lt__(self, other):
        return isinstance(other, Card) and self.number < other.number

    def __hash__(self):
        return hash(str(self))


def gen_deck():
    for card_text in Card.CARD_LIST:
        for _ in range(4):
            yield Card.from_str(card_text)


class Board():
    def __init__(self, deck=None):
        self.move_num = 0
        self.pile_illegal = [False] * 6

        if deck is None:
            deck = list(gen_deck())
            shuffle(deck)

        assert len(deck) == 36

        # todo(komori): use constants
        self.piles = [deck[i:i+6] for i in range(0, 36, 6)]
        self.pile_fixed = [self.isfix(i) for i in range(6)]

    def __str__(self):
        piles_mod = deepcopy(self.piles)
        largest_size = max(map(len, piles_mod)) + 1
        for stack, illegal in zip(piles_mod, self.pile_illegal):
            stack.extend([' '] * (largest_size - len(stack)))
            if illegal:
                stack.append('!')

        piles_s = '\n'.join(
            [' '.join(map(str, r)) for r in zip(*piles_mod) ]
        )

        return piles_s

    def __eq__(self, other):
        if not isinstance(other, Board):
            return False

        return self.piles == other.piles and self.pile_illegal == other.pile_illegal

    def __lt__(self, other):
        return (self.piles, other.pile_illegal) < (self.piles, other.pile_illegal)

    def __hash__(self):
        h_val = 0
        shift = 0
        for i in self.pile_illegal:
            h_val ^= (1 if i else 0) << shift
            shift += 1

        for pile in self.sorted_piles:
            h_val ^= hash(tuple(pile)) << shift
            shift += 1

        return h_val

    def isfix(self, idx):
        if len(self.piles[idx]) != 9:
            return False

        prev = None
        for card in self.piles[idx]:
            if not prev or card.goes_on(prev):
                prev = card
            else:
                return False

        return True

    @property
    def sorted_piles(self):
        return sorted(self.piles)

    @property
    def cleared(self):
        return sum(self.pile_fixed) == 4

    def legal_moves(self):
        for idx, pile in enumerate(self.piles):
            if not pile or self.pile_fixed[idx]:
                continue

            prev = None
            for idy, card in reversed(list(enumerate(pile))):
                if prev and not prev.goes_on(card):
                    break

                prev = card
                for dst_idx, dst_pile in enumerate(self.piles):
                    if dst_idx == idx or self.pile_fixed[dst_idx] or self.pile_illegal[dst_idx]:
                        continue

                    if not dst_pile or card.goes_on(dst_pile[-1]):
                        # new_b = deepcopy(self)
                        new_b = cPickle.loads(cPickle.dumps(self, -1))
                        new_b.piles[dst_idx].extend(new_b.piles[idx][idy:])
                        new_b.piles[idx] = new_b.piles[idx][:idy]
                        new_b.pile_illegal[idx] = False
                        new_b.pile_fixed[dst_idx] = new_b.isfix(dst_idx)
                        new_b.move_num += 1
                        yield new_b
                    elif idy == len(pile) - 1 and not self.pile_illegal[idx]:
                        # new_b = deepcopy(self)
                        new_b = cPickle.loads(cPickle.dumps(self, -1))
                        new_b.piles[dst_idx].append(new_b.piles[idx].pop())
                        new_b.pile_illegal[idx] = False
                        new_b.pile_illegal[dst_idx] = True
                        new_b.move_num += 1
                        yield new_b

    def score(self):
        # todo(komori): reconsider calculation
        # s_val = 8 - 2 * sum(self.pile_fixed)
        s_val = 8*1*4 + 4*(8-1) - 8 *  sum(self.pile_fixed) + 0.1 * self.move_num
        s_val += 5 * sum(self.pile_illegal)

        for pile in self.piles:
            prev = None
            for card in pile:
                if prev and not prev.goes_on(card):
                    s_val -= 1
                prev = card

            if pile:
                s_val += 1
                if pile[0].number < 11:
                    s_val += 2

        return s_val


def solve(board, verbose=True):
    start = time.time()

    seen = set()
    seen.add(board)
    prev = dict()
    queue = PriorityQueue()
    queue.put((board.score(), board))

    finished = None

    last_time = None
    num_states = 0
    lowest_score = board.score()
    while not queue.empty() and not finished:
        s, curr_b = queue.get()

        if verbose:
            if last_time == None or time.time() - last_time > 1:
                print("States explorered: {}\t".format(num_states)
                    + "Lowest Score: {:.2f}\t".format(lowest_score)
                    + "Current Score: {:.2f}\t".format(s)
                    + "Elapsed time: {:.2f}s".format(time.time() - start)
                )
                last_time = time.time()
        num_states += 1

        for next_b in curr_b.legal_moves():
            if next_b not in seen:
                lowest_score = min(lowest_score, next_b.score())
                seen.add(next_b)
                prev[next_b] = curr_b
                if next_b.cleared:
                    finished = next_b
                    break

                queue.put((next_b.score(), next_b))

    if verbose:
        if finished:
            print("Solution found")
            curr_b = finished
            trace_back = []
            while curr_b in prev:
                trace_back.append(curr_b)
                curr_b = prev[curr_b]

            for i,board in enumerate(reversed(trace_back)):
                print("==={}===".format(i))
                print(board)

    print(finished)


if __name__ == "__main__":
    STAGE = (
        "7T0T88"
        "76V6VV"
        "96996K"
        "8T0TDK"
        "779D0D"
        "8VK0DK"
    )
    deck = [Card.from_str(c) for c in STAGE]
    solve(Board(deck))