Праздник Игоря

Начал читать книгу «Экспертные системы: принципы разработки и программирование». Книга массивная, много букв. В конце первой главы дается криптоарифметическая задачка donald+gerald = robert при условии, что d = 5. Взял листик бумаги и ручку, минут 5–10 ушло на решение. В книге дают задание написать программу, решающую эту задачу. Начал придумывать как бы я написал эту программу. В голову пришло решение «в лоб», используя перебор.

Собрал в кулак свою лень, создал питоновский файл и начал писать. Далее будет код с краткими вкраплениями моих комментариев: # у меня стоит питон 2.5 этой функции там еще нет, но в питоне 2.6 она уже есть # эта функция перемешивает массив чисел создавая все возможные комбинации, и добавляя в итератор def permutations(iterable, r=None): # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC # permutations(range(3)) --> 012 021 102 120 201 210 pool = tuple(iterable) n = len(pool) r = n if r is None else r indices = range(n) cycles = range(n, n-r, -1) yield tuple(pool[i] for i in indices[:r]) while n: for i in reversed(range(r)): cycles[i] -= 1 if cycles[i] == 0: indices[i:] = indices[i+1:] + indices[i:i+1] cycles[i] = n - i else: j = cycles[i] indices[i], indices[-j] = indices[-j], indices[i] yield tuple(pool[i] for i in indices[:r]) break else: return import time #декоратор для замера времени def print_timing(func): def wrapper(*arg): t1 = time.time() res = func(*arg) t2 = time.time() print '%s took %0.3f s' % (func.func_name, (t2-t1)) return res return wrapper class Resolver(object): #хардкодом инициализирую все что нужно item1 = "donald" item2 = "gerald" result = "robert" known_elem = {"d": 5} # создаю массив уникальных букв, собранных из 3 слов, вероятно есть более красивый способ на питоне написать такой код (по мере своего развития в питоне буду такой код писать) def get_letters_array(self): result = [] s = self.item1+self.item2+ self.result arr = list(s) for letter in arr: if not letter in result and not letter in self.known_elem: result.append(letter) return result #по порядку создаем хеш где каждой букве соответствует число из массива (и тут питон не идеален) def get_letters_numbers(self, letters_array, numbers): result = {} i = 0 for letter in letters_array: result[letter]= numbers[i] i+=1 return result #строка преобразуется в числовое значение например "donald" => в число def get_number(self, letters_numbers, _str): result = [] for s in list(_str): if s in self.known_elem: result.append(str(self.known_elem[s])) continue result.append(str(letters_numbers[s])) return int("".join(result)) #создаем массив цифр для подстановок, если уже есть известный элемент удаляем его для сокращения количества итераций def get_initial_numbers(self): arr = range(0, 10) if self.known_elem.values()[0] in arr: arr.remove(self.known_elem.values()[0] ) return arr #проверяем чтоб число не начиналось с 0 def firstNumberIs0(self, letters_numbers): return (letters_numbers[self.item1[0]]==0 or letters_numbers[self.item2[0]]==0 or letters_numbers[self.result[0]]==0) #тут все начинается @print_timing def resolve(self): letters_array = self.get_letters_array(); current_iterantion = 0 initial_numbers = self.get_initial_numbers() for numbers in permutations(initial_numbers): letters_numbers = self.get_letters_numbers(letters_array, numbers) item1 = self.get_number(letters_numbers, self.item1) item2 = self.get_number(letters_numbers, self.item2) result = self.get_number(letters_numbers, self.result) if item1 + item2 ==result: print "result found on %s iteration: %s + %s = %s" % (current_iterantion, item1, item2, result) break current_iterantion+=1 return if __name__ == '__main__': Resolver().resolve()

Результаты:
donald+gerald = robert если известно, что d = 5 :
result found on 103487 iteration: 526485 + 197485 = 723970
resolve took 9.399 s
если ничего не известно — подольше:
result found on 1917887 iteration: 526485 + 197485 = 723970
resolve took 183.831 s

Нашел еще задачку: send+more = money
result found on 2787378 iteration: 9567 + 1085 = 10652
resolve took 265.016 s

Сделал для себя несколько выводов. Метод перебора, довольно таки дубовый и медленный. В следующий раз хочу попробовать что-то быстрое, может генетический алгортим. Понял, что нужно углубить знания в питоне для более эффективного написания кода.

Комментарии(1)