__TOC__
Занурення Так як регулярні вирази - це операції з рядками на стероїдах, так само модуль itertools - ітератори на стероїдах. Але спершу я хочу показати вам одну класичну головоломку:
HAWAII + IDAHO + IOWA + OHIO == STATES 510199 + 98153 + 9301 + 3593 == 621246
H = 5 A = 1 W = 0 I = 9 D = 8 O = 3 S = 6 T = 2 E = 4
Такі головоломки називаються математичними ребусами. Букви утворюють якісь слова, але якщо замінити кожну букву цифрою від 0 до 9, числа утворять правильну математичну тотожність. Задача в тому, аби вияснити яка цифра відповідає кожній букві. Всі випадки використання букви замінюються на одну й ту ж цифру, жодна цифра не замінює двох різних букв, і жодне "слово" не може починатись з цифри 0.
В цьому розділі ми розберемо неймовірну програму мовою Python, початково написану Реймондом Геттінґером. Ця програма розв’язує математичні ребуси використовуючи всього 14 рядків коду.
import re import itertools
def solve(puzzle): words = re.findall('[A-Z]+', puzzle.upper()) unique_characters = set(''.join(words)) assert len(unique_characters) <= 10, 'Too many letters' first_letters = {word for word in words} n = len(first_letters) sorted_characters = ''.join(first_letters) + \ ''.join(unique_characters - first_letters) characters = tuple(ord(c) for c in sorted_characters) digits = tuple(ord(c) for c in '0123456789') zero = digits for guess in itertools.permutations(digits, len(characters)): if zero not in guess[:n]: equation = puzzle.translate(dict(zip(characters, guess))) if eval(equation): return equation
if __name__ == '__main__': import sys for puzzle in sys.argv[1:]: print(puzzle) solution = solve(puzzle) if solution: print(solution)
Ви можете запустити програму з командного рядка. Як це виглядатиме в Лінукс продемонстровано нижче. (Пошук розв’язку може зайняти деякий час, тому наберіться терпіння).
you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652
Пошук всіх входжень шаблону Перше що робить наш розв’язувач головоломок - знаходить всі великі латинські літери в умові:
>>> import re >>> re.findall('[0-9]+', '16 2-by-4s in rows of 8') ['16', '2', '4', '8'] Модуль re містить реалізацію регулярних виразів мови Python. Він має вправну функцію findall(), яка отримує регулярний вираз, і рядок, та повертає список зі всіма входженнями шаблону в рядок. В нашому випадку шаблону відповідають послідовності цифр.
>>> re.findall('[A-Z]+', 'SEND + MORE == MONEY') ['SEND', 'MORE', 'MONEY'] Це шаблон якому відповідають послідовності літер. Знову ж таки значенням що повертається - список, кожен елемент якого співставний з регулярним виразом.
А ось ще один приклад, щоб дещо розім’яти ваш мозок:
>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.") [' sixth s', " sheikh's s", " sheep's s"]
Здивовані? Регулярний вираз шукає пробіл, s, найкорошту можливу послідовність довільних символів, знову пробіл, а потім іншу s. Але дивлячись на той рядок я бачу аж п’ять відповідностей:
Theick sheikh's sixth sheep's sick. The sixthheikh's sixth sheep's sick. The sixth sickixth sheep's sick. The sixth sick sheikh'sheep's sick. The sixth sick sheikh's sixthick.
А re.findall() повертає список з трьома співпадіннями. Якщо конкретно, то з першим, третім і п’ятим. Чому б це? Тому що вона не повертає співпадіння які перекриваються. Перше співпадіння перекривається з другим, тому друге пропускається. Наступне третє повертається, але воно перетинається з четвертим, тому четверте пропускається, і насамкінець повертається п’яте. Таким чином отримуємо п’ять співпадінь.
Але це не має жодного відношення до розв’язування ребусів. Я просто подумав що це може бути цікаво.
Пошук унікальних елементів послідовності Множини роблять пошук унікальних елементів тривіальною справою.
>>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick'] >>> set(a_list) {'sixth', 'The', "sheep's", 'sick', "sheik's"}
Отримавши на вхід список елементів, функція set() поверне набір унікальних рядків в списку. Це можна собі уявити як цикл for: беремо перший елемент, додаємо в множину. Потім другий, третій, четвертий, п’ятий... Стоп! П’ятий вже є в множині, тому його пропускаємо. Додаємо ще шостий, і пропускаємо останній. В результаті отримуємо набір унікальних елементів списку. Для цього список навіть не довелось сортувати.
>>> a_string = 'EAST IS EAST' >>> set(a_string) {'A', ' ', 'E', 'I', 'S', 'T'} Така ж техніка працює з рядками, тому що рядки - просто послідовності символів.
>>> words = ['SEND', 'MORE', 'MONEY'] >>> ''.join(words) 'SENDMOREMONEY'
<code>.join(a_list)</code> склеює список рядків a_list в один рядок.
>>> set(''.join(words)) {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
Цей код повертає множину унікальних символів в усіх рядках списку.
Розв’язувач ребусів використовує такий підхід при побудові множини всіх символів головоломки:
unique_characters = set(''.join(words)) Цей набір пізніше використовується щоб присвоювати символам числові значення, в процесі перебору розв’язків.
Пересвідчення (assert) Як і багато інших мов, Python містить інструкцію assert. Вона працює так:
>>> assert 1 + 1 == 2
Після інструкції assert іде довільний вираз мови Python. В цьому випадку твердження 1 + 1 == 2 істинне, тому інструкція assert нічого не робить.
>>> assert 1 + 1 == 3 Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError
Тим не менш, якщо вираз приймає хибне значення в булевому контексті, assert згенерує виняток AssertionError
>>> assert 2 + 2 == 5, "Only for very large values of 2" Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError: Only for very large values of 2
Також ви можете додати після виразу пояснення того що сталось для інших людей.
Коротше кажучи, рядок коду: assert len(unique_characters) <= 10, 'Too many letters'
... є еквівалентним оцьому:
if len(unique_characters) > 10: raise AssertionError('Too many letters')
Розв’язувач ребусів використовує таке пересвідчення, щоб не почати розв’язувати головоломку, яка містить більше десяти різних символів. Бо так як цифр всього десять головоломка що має більше символів не може мати розв’язку.
Генераторні вирази Генераторні вирази - це як генераторні функції тільки без функцій.
>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'} >>> gen = (ord(c) for c in unique_characters)
Генераторний вираз схожий на анонімну функцію що генерує значення. Він схожий на списковий вираз, але замість квадратних дужок використовує круглі.
>>> gen <generator object <genexpr> at 0x00BADC10>
Генераторний вираз повертає ітератор.
>>> next(gen) 69 >>> next(gen) 68
Виклик функції next повертає наступне значення переданого їй ітератора.
>>> tuple(ord(c) for c in unique_characters) (69, 68, 77, 79, 78, 83, 82, 89)
За бажанням ви можете здійснити ітерацію крізь всі значення, та повернути список, кортеж, чи множину, передаючи генераторний вираз як аргумент у функції list(), tuple() чи set(). В цьому випадку вам навіть не потрібна зайва пара дужок - просто передайте "голий" вираз ord(c) for c in unique_characters в функцію tuple(), і Python сам здогадається що це генераторний вираз.
Ось інший спосіб досягнути того ж, використовуючи генераторну функцію:
def ord_map(a_string): for c in a_string: yield ord(c)
gen = ord_map(unique_characters)
Генераторний вираз набагато компактніший, хоча є функціонально еквівалентним.
Перебір перестановок... Спосіб для лінивих! Перш за все - що перестановки взагалі таке? Перестановки - це таке математичне поняття. (Взагалі то, існує кілька означень, залежно від того який розділ математики вам потрібен. Тут я розглядаю комбінаторику, але якщо це для вас взагалі нічого не означає - не хвилюйтесь. Як завжди - вікіпедія це ваша помічниця).
Ідея полягає в тому, що ви берете послідовність якихось об’єктів (чисел, рядків чи навіть танцюючих ведмедів) і перебираєте всі можливі способи утворити з неї менші послідовності. Ці менші послідовності повинні бути однакової, проте довільної довжини - від одного до кількості елементів в початковій послідовності. (Примітка: англійське слово permutations в українській комбінаторній термінології означає два поняття: розміщення та перестановки. Перестановки - це розміщення довжини n, де n - довжина початкової послідовності, тому надалі напевне краще буде перекладати термін permutations як розміщення. Не знаю.) Також - два однакові розміщення не повинні повторюватись. Математики кажуть: "давайте знайдемо всі розміщення з трьох елементів по два", що означає: давайте знайдемо всі різні послідовності довжини 2, з трьох можливих елементів.
>>> import itertools
Модуль itertools містить багато цікавих речей, і в тому числі функцію permutations(), яка робить за нас всю важку роботу з генерації розміщень.
>>> perms = itertools.permutations([1, 2, 3], 2)
Функція permutations() приймає на вхід послідовність (в даному випадку список з трьох чисел), і число - розмір розміщень які ми будемо генерувати. Функція повертає ітератор, який можна використовувати в циклах for, чи інших місцях де потрібні послідовності. Тут я перевірю всі значення ітератора вручну.
>>> next(perms) (1, 2) >>> next(perms) (1, 3) >>> next(perms) (2, 1) >>> next(perms) (2, 3) >>> next(perms) (3, 1) >>> next(perms) (3, 2)
Зауважте що розміщення впорядковані. (2, 1) - це інша не те саме розміщення що й (1, 2).
>>> next(perms) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration
І це всі розміщення з елементів [1, 2, 3] взятих поодинці. Такі пари як (1, 1) не з’являються, бо вони містять повторення, тому не є правильними розміщеннями. Коли ітерації закінчуються ітератор генерує виняток StopIteration
Функція permutations() приймає не тільки списки. Вона може приймати довільні послідовності - навіть рядки.
>>> import itertools >>> perms = itertools.permutations('ABC', 3)
Рядок - це всього лиш послідовність символів. При генеруванні перестановок рядок 'ABC' еквівалентний списку ['A', 'B', 'C']
>>> next(perms) ('A', 'B', 'C') >>> next(perms) ('A', 'C', 'B') >>> next(perms) ('B', 'A', 'C') >>> next(perms) ('B', 'C', 'A') >>> next(perms) ('C', 'A', 'B') >>> next(perms) ('C', 'B', 'A') >>> next(perms) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration
Перше розміщення (тут прийнятний і термін перестановка) з елементів ['A', 'B', 'C'], взятих по три штуки - ('A', 'B', 'C'). Решта п’ять - ці ж три елементи які розміщуються у всіх мислимих порядках.
>>> list(itertools.permutations('ABC', 3)) [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
Так як функція permutations() завжди повертає ітератор, то найпростіший спосіб її зневадження - передати цей ітератор функції list(), щоб отримати всі перестановки одразу.
Інші веселі речі з модуля itertools >>> import itertools >>> list(itertools.product('ABC', '123')) [('A', '1'), ('A', '2'), ('A', '3'), ('B', '1'), ('B', '2'), ('B', '3'), ('C', '1'), ('C', '2'), ('C', '3')]
itertools.product() повертає ітератор що генерує декартовий добуток двох послідовностей.
>>> list(itertools.combinations('ABC', 2)) [('A', 'B'), ('A', 'C'), ('B', 'C')]