Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A MOLEK-SYNTEZ solitaire solver written in python
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment