Google Galaxy Nexus Challenge 1

puzzle_1.py

# The semaphore alphabet.
# The first character represents number of flags held straight up, and so on, going clockwise.
# Info taken from: http://en.wikipedia.org/wiki/Flag_semaphore
alpha = {
    '00002000': ' ',
    '10100000': '#',
    '00001100': 'A',
    '00001010': 'B',
    '00001001': 'C',
    '10001000': 'D',
    '01001000': 'E',
    '00101000': 'F',
    '00011000': 'G',
    '00000110': 'H',
    '00000101': 'I',
    '10100000': 'J',
    '10000100': 'K',
    '01000100': 'L',
    '00100100': 'M',
    '00010100': 'N',
    '00000011': 'O',
    '10000010': 'P',
    '01000010': 'Q',
    '00100010': 'R',
    '00010010': 'S',
    '10000001': 'T',
    '01000001': 'U',
    '10010000': 'V',
    '01100000': 'W',
    '01010000': 'X',
    '00100001': 'Y',
    '00110000': 'Z',
}

# The signalling androids, as provided by Google.
# Interpreted in the same way as the alphabet above.
# As seen on: http://www.google.com/nexus/challenge3/01sdfpogiue.html
puzzle = [
    '11101211',
    '20002101',
    '10100000',
    '10001123',
    '02002301',
    '01102512',
]

def match(android, symbol):
    new_signal = ''
    for i, j in zip(android, symbol):
        if int(i) - int(j) < 0:
            return None
        new_signal += str(int(i) - int(j))
    return new_signal

def possible_matches(android, mapping, stack=''):
    for symbol, letter in mapping.items():
        m = match(android, symbol)
        if m == '00000000':
            yield stack+letter
        elif m:
            for i in possible_matches(m, mapping, stack+letter):
                yield i

for android in puzzle:
    results = set()
    for result in possible_matches(android, alpha):
        result = reduce(str.__add__, sorted(result))
        results.add(result)
    print results