Основная часть
|
После завершения работы над каждым вопросом фиксируй изменения (делай коммит): Так же не возбраняется в любое время проталкивать изменения на GitHub: |
Вопрос 1: Ищи жёлуди
Белки ждут твоей помощи! Деревьев много, а на каких из них есть жёлуди — неясно. Определи функцию acorn_finder, которая принимает дерево и возвращает True, если в нём есть хотя бы один узел со значением 'жёлудь', а в противном случае — False.
def acorn_finder(t):
"""Возвращает True, если t содержит узел со значением 'жёлудь', иначе False.
>>> scrat = tree('жёлудь')
>>> acorn_finder(scrat)
True
>>> sproul = tree('roots', [tree('ветвь1', [tree('лист'), tree('жёлудь')]), tree('ветвь2')])
>>> acorn_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> acorn_finder(numbers)
False
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 2: Подрезка листьев
Определи функцию prune_leaves, которая для заданного дерева t и тапла значений vals создаёт новую версию дерева t без листьев со значениями из vals. Не пытайся удалять узлы с ветвями или листья со значениями, не входящими в vals. Возвращай None, если подрезка листьев «съела» всё дерево.
def prune_leaves(t, vals):
"""Возвращает изменённую копию t, в которой все листья со значениями, равными
элементам списка vals, удаляются. Возвращает None, если от дерева ничего не осталось.
>>> t = tree(2)
>>> print(prune_leaves(t, (1, 2)))
None
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
>>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
1
2
3
5
6
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 3: Память
Напиши функцию, принимающую число n и возвращающую функцию одного аргумента. Эта функция принимает ещё одну функцию — правило обновления n. При обновлении n выводится его новое значение.
def memory(n):
"""
>>> f = memory(10)
>>> f(lambda x: x * 2)
20
>>> f(lambda x: x - 7)
13
>>> f(lambda x: x > 5)
True
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Дополнительная часть
Шекспир и словари
Теперь настало время решать задачу аппроксимации всего корпуса текстов Шекспира! Для этого тебе придётся узнать, что такое биграмная модель языка. Если кратко, то вот идея: выбираешь какое-то слово, например «The», затем ищешь во всех текстах Шекспира предложения, где встречается слово «The» и запоминаешь всевозможные следующие за ним слова. Теперь представь, что это повторяется для каждого слова.
Тебе должно быть уже понятно, как построить целое предложение. Пусть оно начинается со слова «The», из списка следующих слов случайно выбирай какое-нибудь слово, например, «cat». Теперь смотри на список продолжений слова «cat» и опять случайно выбирай из него элемент. Продолжай, и продолжай, и продолжай эти операции, пока не встретится точка («.»). Вуаля, псевдо-предложение псевдо-Шескпира готово!
Объект, содержащий всю информацию по продолжениям слов хоть и называется «таблица последователей» (successor table), но в реальности является словарём. Ключи словаря — слова, значения — списки возможных продолжений.
Вопрос 4: Таблица последователей
Вот неполное определение функции build_successors_table. На входе — список слов (из текстов Шекспира), на выходе — таблица последователей. Короче, смотри на доктесты.
|
В представленом коде два пропуска |
def build_successors_table(tokens):
"""Возвращает словарь: ключи — слова; значения — списки последующих следующих слов.
>>> text = ['We', 'came', 'to', 'investigate', ',', 'catch', 'bad', 'guys', 'and', 'to', 'eat', 'pie', '.']
>>> table = build_successors_table(text)
>>> sorted(table)
[',', '.', 'We', 'and', 'bad', 'came', 'catch', 'eat', 'guys', 'investigate', 'pie', 'to']
>>> table['to']
['investigate', 'eat']
>>> table['pie']
['.']
>>> table['.']
['We']
"""
table = {}
prev = '.'
for word in tokens:
if prev not in table:
"*** ТВОЙ КОД ЗДЕСЬ ***"
"*** ТВОЙ КОД ЗДЕСЬ ***"
prev = word
return tableВопрос 5: Построение фразы
Настало время сгенерировать текст! Пусть задано начальное слово. Нужно выбрать из таблицы последователей successor table продолжение, потом продолжение для него и так до точки.
Для выбора случайного элемента из списка нужно использовать функцию choice(your_list) из модуля random.
|
Допиши функцию construct_sent.
def construct_sent(word, table):
"""Печатает случайную фразу начиная со слова word, составляя её по table.
>>> table = {'Wow': ['!'], 'Sentences': ['are'], 'are': ['cool'], 'cool': ['.']}
>>> construct_sent('Wow', table)
'Wow!'
>>> construct_sent('Sentences', table)
'Sentences are cool.'
"""
import random
result = ''
while word not in ['.', '!', '?']:
"*** ТВОЙ КОД ЗДЕСЬ ***"
return result.strip() + wordТеперь всё вместе
Класс! Попробуй теперь подсунуть твоим функциям настоящие данные. Следующий фрагмент кода уже присутствует в файле-заготовке, он позволяет получить список всех слов из текстов Шекспира.
def shakespeare_tokens(path='shakespeare.txt', url='http://composingprograms.com/shakespeare.txt'):
"""Возвращает слова пьес Шекспира списком."""
import os
from urllib.request import urlopen
if os.path.exists(path):
return open('shakespeare.txt', encoding='ascii').read().split()
else:
shakespeare = urlopen(url)
return shakespeare.read().decode(encoding='ascii').split()Теперь раскомментируй две строки, которые построят successor table из текста Шекспира.
# Раскомментируй две следующие строки
# tokens = shakespeare_tokens()
# table = build_successors_table(tokens)Попробуй создавать предложения.
>>> construct_sent('The', table)
'The perilous narrow gate , my gold.'Все предложения начинаются с «The». Немного усложнив код, можно получать совсем случайные фразы.
def random_sent():
import random
return construct_sent(random.choice(table['.']), table)
Поиграть с кодом как всегда можно в интерактивной сессии (флаг -i).
|
Вопрос 6: Выращивание листов
Определи функцию sprout_leaves, которая принимает дерево t и список значений vals. Функция должна вернуть новое дерево, идентичное исходному, за исключением того, что в листьях исходного дерева должны появиться новые ветви (в соответствии со списком vals).
Например, пусть дано дерево t = tree(1, [tree(2), tree(3, [tree(4)])]):
1
/ \
2 3
|
4Если к нему применить sprout_leaves(t, [5, 6]), то получится:
1
/ \
2 3
/ \ |
5 6 4
/ \
5 6Вперёд!
def sprout_leaves(t, vals):
"""Наращивает новые листы, содержащие данные из vals на каждый лист
исходного дерева t и возвращает результирующее дерево.
>>> t1 = tree(1, [tree(2), tree(3)])
>>> print_tree(t1)
1
2
3
>>> new1 = sprout_leaves(t1, [4, 5])
>>> print_tree(new1)
1
2
4
5
3
4
5
>>> t2 = tree(1, [tree(2, [tree(3)])])
>>> print_tree(t2)
1
2
3
>>> new2 = sprout_leaves(t2, [6, 1, 2])
>>> print_tree(new2)
1
2
3
6
1
2
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 7: Сложение деревьев
Определи функцию add_trees, которая принимает два дерева и возвращает новое дерево, в котором значения каждого узла, топологически совпадающего в обоих деревьев, равно сумме соответствующих значений. Если узел присутствует в одном дереве, но отсутствует в другом, то в результирующем дереве он должен быть.
Рассмотри возможность использования функции zip для обхода по двум последовательностям одновременно.
|
| Если эта задача кажется сложнее предыдущих, то так оно и есть! Это довольно сложная задача, но её можно сделать! Поговори об этой задаче с коллегами или поспрашивай преподавателей. |
def add_trees(t1, t2):
"""
>>> numbers = tree(1,
... [tree(2,
... [tree(3),
... tree(4)]),
... tree(5,
... [tree(6,
... [tree(7)]),
... tree(8)])])
>>> print_tree(add_trees(numbers, numbers))
2
4
6
8
10
12
14
16
>>> print_tree(add_trees(tree(2), tree(3, [tree(4), tree(5)])))
5
4
5
>>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
4
6
4
>>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
tree(2, [tree(3, [tree(4)]), tree(5)])))
4
6
8
5
5
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"