Solver for Professor spelet
""" | |
Solver for "Professor Spelet" by dan-spil. | |
Made by Eric Henziger, 2013, hemtillhenziger (at) gmail.com | |
""" | |
def create_card(top, right, bottom, left): | |
""" Takes four tuples, and put them in one tuple making up the card. """ | |
card = (top, right, bottom, left) | |
return card | |
def convert_card(card): | |
""" | |
Convert numerical card data to human readable stuff. | |
I.e. the tuple (1, 2) is converted to ("feet", "green") | |
""" | |
body_part = ("head", "feet") | |
colour = ("blue", "brown", "green", "purple") | |
return ((body_part[card[0][0]], colour[card[0][1]]), | |
(body_part[card[1][0]], colour[card[1][1]]), | |
(body_part[card[2][0]], colour[card[2][1]]), | |
(body_part[card[3][0]], colour[card[3][1]])) | |
def create_deck(): | |
""" | |
Create and return a list of cards, this is a replica of the deck I | |
have at home, a simple way of getting more solutions to the puzzle would | |
be to change the order of the cards in the deck. | |
""" | |
deck = [create_card((1, 2), (0, 1), (0, 3), (1, 2)), | |
create_card((1, 3), (0, 1), (0, 0), (1, 1)), | |
create_card((1, 2), (1, 3), (0, 0), (0, 1)), | |
# These are the only doublette cards: | |
# (Has no significance whatsoever, but cool story bro.) | |
create_card((0, 0), (1, 1), (1, 3), (0, 2)), | |
create_card((0, 0), (1, 1), (1, 3), (0, 2)), | |
create_card((0, 2), (0, 3), (1, 2), (1, 0)), | |
create_card((0, 1), (0, 0), (1, 2), (1, 3)), | |
create_card((1, 1), (0, 1), (0, 0), (1, 0)), | |
create_card((0, 3), (1, 1), (1, 2), (0, 2)), | |
create_card((1, 1), (0, 3), (0, 0), (1, 2)), | |
create_card((0, 0), (0, 3), (1, 1), (1, 2)), | |
create_card((0, 2), (0, 1), (1, 1), (1, 3)), | |
create_card((0, 3), (0, 2), (1, 1), (1, 0)), | |
create_card((0, 1), (0, 3), (1, 2), (1, 0)), | |
create_card((0, 3), (1, 0), (1, 2), (0, 1)), | |
create_card((0, 2), (0, 2), (1, 1), (1, 0)), | |
] | |
return deck | |
def print_human_friendly(deck): | |
""" For every card in a deck, print its human readable representation.""" | |
for card in deck: | |
print(convert_card(card)) | |
return | |
def print_nice_board(board): | |
""" | |
Print the state of a board, only the places on the board that actually | |
has a card put on it will be printed. | |
""" | |
nice_board = [] | |
for row in board: | |
for board_card in row: | |
if board_card: | |
nice_board.append(board_card) | |
print_human_friendly(nice_board) | |
return | |
def rotate(card): | |
"""Rotate the card one step in clockwise direction.""" | |
return card[-1:] + card[:-1] | |
def get_prev_pos(pos): | |
if pos == (0, 0): | |
raise Exception("Can't get a pos before the [0, 0] position") | |
prev_x = pos[1] - 1 | |
# If prev_x is not negative, there's is a position to the left of pos. | |
if prev_x >= 0: | |
return (pos[0], prev_x) | |
# Otherwise we just go up to the last position in the previous row. | |
# DANGER DANGER, that '3' there is ugly hardcoded, what if our board is | |
# larger than 4x4 tiles? | |
return (pos[0] - 1, 3) | |
def get_next_pos(pos): | |
""" | |
Used to answer the question 'Where should we place the next card?' | |
Who would have thought that modulo could be such a nice and handy operator. | |
""" | |
col = (pos[1] + 1) % 4 | |
if col == 0: | |
row = (pos[0] + 1) % 4 | |
else: | |
row = pos[0] | |
return (row, col) | |
def is_pos_earlier(pos1, pos2): | |
""" | |
Return True if pos1 comes before pos2 on the board. | |
(0, 0) is the first position and (3, 3) is the last position. | |
(2, 0) is later than (1, 3)""" | |
if pos1[0] > pos2[0]: | |
return False | |
elif pos1[0] < pos2[0]: | |
return True | |
else: | |
return pos1[1] < pos2[1] | |
def check_neighbours(card, pos): | |
""" | |
If card has no neighbour above or to the left, we return True. | |
We apparently expect board to be like a global variable or someth, | |
that doesn't feel all that jolly good but who cares when the code finally | |
work? Not me! | |
""" | |
ret = True | |
# Check if there's a card above. | |
above_y = pos[0] - 1 | |
if above_y >= 0: | |
# Verify that bodyparts are not the same. | |
ret = card[0][0] != board[above_y][pos[1]][2][0] | |
# Verify that colors are the same. | |
ret = ret and (card[0][1] == board[above_y][pos[1]][2][1]) | |
# If the card above is OK, check the card to the left in the same way. | |
if not ret: | |
return False | |
left_x = pos[1] - 1 | |
if left_x >= 0: | |
ret = ret and (card[3][0] != board[pos[0]][left_x][1][0]) | |
ret = ret and (card[3][1] == board[pos[0]][left_x][1][1]) | |
return ret | |
def remove_blacks(deck, pos, blacklist): | |
""" | |
Check if the blacklist has any cards on the current position. | |
If so, remove them from the deck and eventually return the deck with | |
all blacklisted cards removed. | |
""" | |
for black_card in blacklist.get(pos, []): | |
for i in range(4): # Why not range(3)? ARE YOU WASTING CPU POWA?!?!?! | |
try: | |
deck.remove(black_card) | |
except ValueError: | |
# The card might be rotated, try to remove all possible rotations. | |
black_card = rotate(black_card) | |
print("Tried to remove %s from %s, failed." % (black_card, deck)) | |
return deck | |
def uniques_only(deck): | |
""" | |
Take a deck of cards and return only the unique ones. | |
HINDDSIGHT NOTE:This is a typical example of desperation functions that you | |
implement late at night when your code has bugs that you don't understand | |
how to fix the right way, a good sign that it is time to go to bed. | |
""" | |
removables = [] | |
for i in range(len(deck)): | |
card = deck[i] | |
for j in range(4): | |
if card in deck[i+1:]: | |
removables.append(card) | |
card = rotate(deck[i]) | |
for card in removables: | |
try: | |
deck.remove(card) | |
except ValueError: | |
print("Tried to remove a %s from %s" % (card, deck)) | |
return deck | |
def rm_extra_cards_in_deck(card, deck): | |
""" See the HINDSIGHT NOTE in the docstring of the uniques_only function. """ | |
def count_cards(card, deck): | |
total = 0 | |
for i in range(3): | |
total += deck.count(card) | |
card = rotate(card) | |
return total | |
while count_cards(card, deck) > 1: | |
# Remove some cards | |
for i in range(3): | |
if card in deck: | |
deck.remove(card) | |
break | |
card = rotate(card) | |
return deck | |
if __name__ == "__main__": | |
# A board of 4 * 4 tiles, all empty (None) at the beginning. | |
rows = 4 | |
columns = 4 | |
board = [] | |
for i in range(rows): | |
board.append([None for j in range(columns)]) | |
# This would be nice if it worked, doesn't because of reference things I | |
# don't fully understand. | |
# board = [None * 4] * 4 | |
def card_fits(card, pos): | |
""" | |
If it fits, it sits. | |
http://i2.kym-cdn.com/photos/images/newsfeed/000/292/573/0c2.jpg | |
That is, if the card is okay with its neighbours, return True so | |
whoever made this function call understands that it is okay to put | |
the card on the board. | |
Three lines of code, six lines of comment, well done. | |
""" | |
if check_neighbours(card, pos): | |
return True | |
return False | |
def match_cards(deck, pos, blacklist): | |
""" | |
Try to place any of the cards in the deck, that's not blacklisted | |
on position @pos on the board. | |
""" | |
for card in deck: | |
### Lots of prints that noone cares about. | |
# print("New try for %s:" % (pos,)) | |
# print(card, convert_card(card)) | |
# print("Current look of the board: ") | |
# print_nice_board(board) | |
# print("Available cards in the deck:") | |
# print(len(deck)) | |
# print_human_friendly(deck) | |
# print("Trying to place card", convert_card(card)) | |
# Try each orientation of the card. | |
orig_card = card | |
for i in range(4): | |
if card_fits(card, pos) and (card not in blacklist): | |
# Card matched the board, remove it from the deck. | |
print("The card %s matches on pos %s! :D" % | |
(convert_card(card), (pos,))) | |
board[pos[0]][pos[1]] = card | |
deck.remove(orig_card) | |
return True, deck | |
card = rotate(card) | |
return False, deck | |
def build_board(deck): | |
""" Big function.""" | |
pos = (0, 0) # Our start postition is row 0, column 0. | |
blacklisted_cards = {} # No blacklisted cards to begin with. | |
# Why not have an endless loop? Don't worry, we have EXCEPTIONS to break | |
# us free from this eternal professor filled carousel. | |
while True: | |
# Start every attempt to place a cards by flooding stdout with | |
# info about the deck and blacklisted cards, genious idea. | |
print("This is the complete deck:") | |
print_human_friendly(deck) | |
for key in blacklisted_cards: | |
print("@@@ Currently there are %s bad cards on pos %s: %s" % | |
(len(blacklisted_cards[key]), key, | |
[convert_card(card) for card in blacklisted_cards[key]])) | |
# match_cards will do its best to place a card on the current position | |
# of the board, if successful ret will be set to True and the new_deck | |
# will be the deck we sent in except for the card we placed on the board. | |
# If not ret is set to False, the new_deck will not be any different from | |
# the deck we sent in to match_cards. | |
ret, new_deck = match_cards(deck, pos, blacklisted_cards.get(pos, [])) | |
# Sweet! -1 is the index of the last element of a list, | |
# regardless of it's length. | |
if board[-1][-1]: | |
# If we managed to place a card on the last tile of the board, | |
# we are done, to celebrate we print the current state of the board which | |
# hopefully give us a legit solution to the puzzle and the | |
# raise an exception, best design ever. | |
print_nice_board(board) | |
raise Exception("We made it!!!") | |
if ret: | |
# Great, we placed a card on pos. | |
# The blacklisted cards on "later" positions, if any, | |
# are no longer blacklisted! | |
removable_keys = [] | |
for key in blacklisted_cards: | |
if is_pos_earlier(pos, key): | |
removable_keys.append(key) | |
for key in removable_keys: | |
blacklisted_cards.pop(key) | |
# For the next loop in the while-snurra, we need to update our | |
# deck with a new and improved one. | |
deck = new_deck | |
# Where should we place the next card? | |
pos = get_next_pos(pos) | |
else: | |
# Really bad if we can't even put a card on the first tile, | |
# we may give up on finding a solution. | |
if pos == (0, 0): | |
raise Exception("Failed to put a card on the first position!!!") | |
# We we're unable to find a card matching the current board. | |
# Oh boy, now it's time to back track this mess. | |
prev_pos = get_prev_pos(pos) | |
prev_card = board[prev_pos[0]][prev_pos[1]] | |
# Remove the card from the board and temporarily add it | |
# to the blacklist. | |
board[prev_pos[0]][prev_pos[1]] = None | |
# setdefault on dictionary, very very smexy. | |
# If we don't have blacklisted cards on pos, then we create an | |
# empty list on that pos and add our prev_card to the list. | |
blacklisted_cards.setdefault(prev_pos, []).append(prev_card) | |
# Rotate the card and return it to the deck. | |
card = rotate(prev_card) | |
deck.append(card) | |
# Position is backed on step. | |
pos = prev_pos | |
return | |
def main(): | |
deck = create_deck() | |
# Try to build the board | |
build_board(deck) | |
# Because build_board will throw exceptions, that we don't care to | |
# handle, we will never see this awesome printing in action. | |
print("\n\nWe're all done here boys, lets wrap it up!") | |
if deck: | |
print("Unable to find a complete solution to the puzzle =/") | |
for row in board: | |
lol = ["st", "nd", "rd", "th"] | |
print("\nListing cards in the %s%s row" % | |
(board.index(row) + 1, lol[board.index(row)])) | |
# Iterate over rows. | |
for card in row: | |
if card: | |
print(convert_card(card)) | |
next_card = row.index(card) + 1 | |
if next_card < 4 and row[next_card]: | |
print("Matches the card: ") | |
print(board) | |
main() # Release the code! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment