CareerCup

def combinations(string, result='', index=0):
    if index >= len(string):
        print result
        return

    combinations(string, result + string[index].lower(), index+1)
    combinations(string, result + string[index].upper(), index+1)


if __name__ == '__main__':
    combinations('abc')

Assuming * means 0 or more characters, every time you encounter a *, you have 1 of 3 decisions to make:
1. Consume 1 character from the input, but continue matching for * (c*w matches caaaw)
2. Consume 1 character from the input and consume the * and continue (c*w matches caw)
3. Consume the * and continue (c*w matches cw)

def match(haystack, needle):
    if not haystack and not needle:
        return True
    elif not haystack or not needle:
        return False
    elif needle[0] == '*':
        return match(haystack[1:], needle) or \
               match(haystack[1:], needle[1:]) or \
               match(haystack, needle[1:])
    elif needle[0] == haystack[0]:
        return match(haystack[1:], needle[1:])
    else:
       return False

NUM_LIST = ["0", "1", "6", "8", "9"]
UPSIDE_DOWN = {
    "0" : "0",
    "1" : "1",
    "6" : "9",
    "8" : "8",
    "9" : "6"
}

def get180(digits):
    """
    Return numbers with specified digits that look the same upside down
    """
    if digits == 0:
        return ['']

    if digits == 1:
        return filter(lambda x: UPSIDE_DOWN[x] == x, NUM_LIST)

    middle_list = get180(digits - 2)
    result_list = []
    for number in NUM_LIST:
        for middle in middle_list:
            result_list.append(number + middle + UPSIDE_DOWN[number])
    return result_list

DICTIONARY = sorted(["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"], key=lambda x:len(x), reverse=True)
USED = [False for j in range(len(DICTIONARY))]


def find_min_breaks(string, words=()):
    if string == '':
        return words

    min_result = None
    for index, dict_word in enumerate(DICTIONARY):
        if not USED[index] and string.startswith(dict_word):
            USED[index] = True
            result = find_min_breaks(string[len(dict_word):], words + (dict_word,))
            if result and (min_result is None or len(result) < len(min_result)):
                min_result = result
            USED[index] = False
    return min_result

def sum_of_squares(number):
    SQUARES = set()

    i = 1
    while i * i < number:
        square = i * i
        if (number - square) in SQUARES:
            return square, number - square
        SQUARES.add(square)
        i += 1
    return None, None

def is_sorted(array, ordering):
    INDEX = {}
    for index, char in enumerate(ordering):
        INDEX[char] = index

    BASE = len(ordering) # Base of the number system !
    previous_score = 0

    for word in array:
        score = 0
        for char in word:
            score = score * BASE + INDEX[char]
        if score < previous_score:
            return False
        else:
            previous_score = score
    return True

def is_sorted(array, ordering):
    INDEX = {}

    for index, char in enumerate(ordering):
        INDEX[char] = index

    for i in range(len(array) - 1):
        word1 = array[i]
        word2 = array[i + 1]

        index = 0
        while index < len(word1) and index < len(word2):
            if INDEX[word1[index]] < INDEX[word2[index]]:
                break
            elif INDEX[word1[index]] > INDEX[word2[index]]:
                return False
            else:
                index += 1
        else:
            if len(word1) > len(word2):
                return False

    return True


if __name__ == '__main__':
    print is_sorted(['cc', 'cb', 'bb', 'ac'], ['c', 'b', 'a'])
    print is_sorted(['cc', 'cb', 'bb', 'ac'], ['b', 'c', 'a'])
    print is_sorted(['ccc', 'ccc', 'aaab', 'aaa'], ['b', 'c', 'a'])
    print is_sorted(['ccc', 'ccc', 'aaa', 'aaab'], ['b', 'c', 'a'])

def check_surrounded(black_positions, white_positions):
    """
        black_positions is a list of positions: [(row1, col1), (row2, col2), ...]
        white_positions is a list of positions: [(row1, col1), (row2, col2), ...]
    """         
    POSITIONS = {}                  
                                
    for position in black_positions:
        POSITIONS[position] = 'B'
    for position in white_positions:
        POSITIONS[position] = 'B'
                                
    for row, col in white_positions:
        if (row - 1, col) not in POSITIONS or \
           (row + 1, col) not in POSITIONS or \
           (row, col + 1) not in POSITIONS or \
           (row, col - 1) not in POSITIONS:
            return False
                                
    return True

def shorten(color):
    color = int(color, 16)
    lower = (color / 0x11) * 0x11
    higher = ((color / 0x11) + 1) * 0x11

    if (color - lower) < (higher - color):
        return hex(lower)[3]
    else:
        return hex(higher)[3]

def nearest_short_color(long_color):
    red = shorten(long_color[1:3])
    green = shorten(long_color[3:5])
    blue = shorten(long_color[5:7])

    return '#{}{}{}'.format(red, green, blue)


if __name__ == '__main__':
    print nearest_short_color('#09f166')