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