Reseni obecneho algebrogramu - neoptimalizovano (Jirka Vejrazka)

algebrogram.py

from itertools import permutations
from collections import deque

try:
    import psyco
    psyco.full()
except ImportError:
    pass

#gram = ['AA', 'AA', 'BB']

#gram = ['AMY', 'KEN', 'ALEX'] 

gram = [
     'JAN',
    'DNES',
    'NEVI',
     'ZDA',
      'SE',
    'JEDE',
   'JEDNA',
   'JIZDA',
   'ZNOVA'
]

def feed_lists(g, ltrs, nonz, qcheck):
    '''naplni seznam vsech pismen, ktere se vyskytuji v algebrogramu,
    soucasne vytvori seznam tech, ktere nesmi byt nula
    a take vyrobi verzi pro rychly test zalozeny na souctu jednotek
    '''
    for word in g:
        for char in word:
            if char not in ltrs:
                ltrs.append(char)
        if word[0] not in nonz:
            nonz.append(word[0])
        qcheck.append(word[-1])

def get_number(chars, char_map):
    '''prevede znaky na cisla podle mapovani, vraci int()
    >>> get_numbers('ABC', 'ABCDEFGHIJ')
    12  # 012 
    >>> get_numbers('CAJE', 'ABCDEFGHIJ')
    3194 
    '''
    assert len(char_map) == 10
    chars = list(chars)
    chars.reverse()
    multiplier = 1
    res = 0
    for char in chars:
        if char == '.':
            continue
        num = char_map.index(char)
        res += num * multiplier
        multiplier *= 10
    return res

def matches(item_list, lastonly=False):
    '''zjisti, zda je soucet polozek v seznamu roven posledni polozce, ktera
    se souctu "neucastni"

    lastonly = True kontroluje pouze jestli souhlasi jednotky (po modulo 10)

    >>> matches([1, 1, 1, 1, 4])
    True
    >>> matches([9, 8, 17])
    True
    >>> matches([1, 2, 9])
    False
    >>> matches([8, 7, 5])
    False
    >>> matches([8, 7, 5], lastonly=True)
    True  # 15 ... ->  5 
    '''
    assert len(item_list) > 1 
    items = item_list[:-1]
    sum_total = item_list[-1]
    tmp = 0
    for i in items:
        tmp += i
    if tmp == sum_total:
        return True
    if lastonly and tmp % 10 == sum_total:
        return True
    return False

def convert_to_numbers(item_list, char_mapping):
    '''prevede kazdou polozku listu na cisla'''
    return [get_number(x, char_mapping) for x in item_list]

def printout(gram_, char_mapping):
    '''vytiskne vysledek pro zadane mapovani znaku na cisla'''
    for entry in gram[:-1]:
        print '%10s' % get_number(entry, char_mapping)
    print '-' * 10
    print '%10s' % get_number(gram_[-1], char_mapping)
    print

if __name__ == '__main__':
    letters, nonzero, qch_list = [], [], []
    feed_lists(gram, letters, nonzero, qch_list)

    # hack pro algebrogram majici mene nez 10 pimen
    while len(letters) < 10:
        letters.append('.')
    solutions = set()

    queue = deque(letters)
    for x in letters:
        queue.rotate()
        first_char = queue[0]
        if first_char in nonzero:
            continue  # jedno z "cisel"  v algebrogramu by zacalo nulou
        for permutation in permutations(list(queue)[1:]):
            candidate = first_char + ''.join(permutation)
            if candidate in solutions:  # hack
                continue
            if not matches(convert_to_numbers(qch_list, candidate), 
                           lastonly=True):
                # scitani na urovni jednotek nefunguje, preskocime
                continue
            if matches(convert_to_numbers(gram, candidate)):
                # cele to vyslo, vytiskni
                printout(gram, candidate)
                solutions.add(candidate)  # hack