Solver for Professor spelet

professor.py

"""
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!