lab07

Lab 7: Словари, ссылочная модель данных и ловля шарика

Лаба: http://cs.mipt.ru/python/lessons/lab7.html.

В качестве ДЗ достаточно решить 3 задачи: две по словарям и одну по задачам с pygame типа ловли шарика.

По некоторым номерам в названии задачи есть ссылка на ресурс Питонтьютор. Если выбор в плане решения падает на такую задачу, рекомендуется перейти по соответствующей ссылке, чтобы посмотреть более полную версию условия (с примерами). (И, кроме условия, можно будет при желании и небольшую теорсправку там же на сайте почитать.)

Если при считывании/записи файла вместо читаемых строк возникают "крокозябры" (или вообще ошибки), то рекомендуется попробовать открывать файл с явным указанием кодировки UTF-8:

input_file = open(file_path, encoding='utf8')
output_file = open(file_path, 'w', encoding='utf8')

Словари

Задача D1 (Переворачивание словаря)

В файле dict.txt описан словарь, отображающий некоторые строковые ключи в числовые значения. Формат описания словаря: на каждой строчке записана пара ключ-значение, между ними отделённая пробелами комбинация символов ->. Например:

key1 -> 1
key2 -> -17.5

Напишите программу, которая считывает словарь из указанного файла и "переворачивает" его, то есть создаёт по нему новый словарь, в котором ключи и значения поменяны местами. Запишите обращённый таким образом словарь в файл "result.txt" в том же формате, в каком был записан во входном файле оригинальный словарь. По примеру выше перевёрнутый словарь получился бы такой:

1 -> key1
-17.5 -> key2

Задача D2 (Сложная функция)

Пусть есть функция $f\colon X \to Y$ и функция $g\colon Y \to Z$, тогда функция $h\colon X \to Z$, $h(x) = g\bigl(f(x)\bigr)$ называется сложной функцией, или композицией функций $f$ и $g$.

В файле f.txt приведены значения функции $f$ в формате x -> y. А в файле g.txt приведены значения функции $g$ в формате y -> z. Гарантируется, что область значений $f$ содержится в области определения $g$.

Запишите в файле "result.txt" значения композиции функций $f$ и $g$ в том же формате, причём чтобы строчки файла были ещё упорядочены по аргументу $x$.

Пример:

# f.txt
3 -> 9
1 -> 1
5 -> 25

# g.txt
1 -> -1
25 -> 23
9 -> 7

# result.txt
1 -> -1
3 -> 7
5 -> 23

Задача D3 (Комплементарная цепочка)

ДНК и РНК — это соответственно двойная и одинарная цепочки нуклеотидов. Причём в ДНК встречаются только азотистые основания ATGC, а в РНК — AUGC.

По РНК можно получить комплементарную ей ДНК по следующему правилу. Каждому азотистому основанию из РНК соответсвует основание для первой цепочки ДНК: A → T, U → A, G → C, C → G; вторая же цепочка ДНК строится комплементарной первой: A → T, T → A, G → C, C → G.

Напишите программу, которая принимает со входа строчку нуклеотидов, составляющую молекулу РНК, и выводит на экран две цепочки нуклеотидов соответствующей ей по правилу комплементарности молекулы ДНК.

Пример (источник):

# Вход
GUGCAUCUGACUCCUGAGGAGAAG

# Выход
CACGTAGACTGAGGACTCCTCTTC
GTGCATCTGACTCCTGAGGAGAAG

Задача D4 (TF–IDF)

В одной из прошлых задач рассматривался сюжет об определении тематики текста. Это можно сделать с помощью простого подсчёта частот слов (ведь слово, которое чаще встречается, скорее всего, и определяет то, о чём говорится в тексте). Однако до этого лучше было сделать предобработку текста: убрать часто встречающиеся неинформативные слова и уменьшить "вариативность" (убрать разные формы одного и того же слова или вообще перевести все однокоренные слова в одно). Пример текста до и после предложенной в упомянутой задаче предобработки:

# Исходный текст
Муравьи живут семьями в гнёздах, называемых муравейниками, которые устраивают в почве, древесине, под камнями; некоторые сооружают муравейники из мелких растительных частиц и т. п. Существуют паразитические виды, которые обитают в гнёздах других муравьёв, муравьи-«рабовладельцы», содержащие в своих гнёздах «рабов» — муравьёв других видов. Ряд видов приспособился к обитанию в жилищах человека. Некоторые виды ценятся за регулирование численности насекомых-вредителей, другие могут считаться вредителями.

# Самые частые слова:
# в, гнёздах, других, которые

---

# Предобработанный текст
муравь семьям гнёзд называем муравейникам устраив почв древесин камням некотор сооруж муравейник мелк растительн част существ паразитическ обит гнёзд муравь муравь рабовладельц содержащ гнёзд муравь приспособилс обитан жилищ некотор ценятс регулирован численност насеком вредител считатьс вредителям

# Самые частые слова:
# муравь, гнёзд, некотор

Видно, что в некотором смысле стало лучше, однако "непонятные" слова всё равно остались...

В данной задаче предлагается применить ещё одну "хитрость", чтобы отсеять неинформативные слова ("в", "другие", "которые" и т.д.) Хитрость основана на наблюдении, что неинформативные слова общей лексики часто встречаются как в пределах одного интересуемого текста, так и вообще во всех текстах. Таким образом, если слово встречается во многих текстах (документах) — то оно, скорее всего, неинформативное и ничего по сути не сообщает. Поэтому, когда после предобработки определяем частоты слов (term frequency, или TF), чтобы определить тему, можно ввести дополнительный множитель, обратно пропорциональный частоте встречаемости слова в разных документах (inverse document frequency, или IDF). Это позволит "переместить на задний план" все оставшиеся после предобработки непонятные слова. Описанная идея по "коррекции частот" называется TF–IDF. Почитать про это подробнее (и посмотреть на конкретные формулы подсчёта) можно, например, на Википедии: TF–IDF (рус.) и TF–IDF (англ.; более полная статья).

Итого, задание (наконец): с помощью обратных частот слов в документах (IDF), посчитанных по коллекции из предобработанных "сырых" текстов прошлого задания и текста из примера выше, выведите для каждого документа этой коллекции 5 слов с самым большим значением TF–IDF.

Пример:

# Предобработанный текст
муравь семьям гнёзд называем муравейникам устраив почв древесин камням некотор сооруж муравейник мелк растительн част существ паразитическ обит гнёзд муравь муравь рабовладельц содержащ гнёзд муравь приспособилс обитан жилищ некотор ценятс регулирован численност насеком вредител считатьс вредителям

# Слова по убыванию TF–IDF:
# гнёзд, муравь (снова эти два), семьям, древесин, рабовладельц

Задача D5 (Словарь)

В файле words.txt даны некоторые английские слова, а в файле definitions.txt — их определения по словарю Collins COBUILD. Проблема в том, что порядок слов и порядок определений в указанных файлах никак не соотносится, и не понятно, какому слову какое определение соответствует. Помогите это исправить! Напишите программу, которая бы составила словарь, где ключом является слово, а значением — его определение. Словарь надо сохранить в файле с именем "result.txt" так же построчно в формате слово -> определение:

word1 -> definition1
word2 -> definition2

P.S. Не обязательно (но приветствуется), если слова, как и в любом нормальном словаре, будут идти по алфавиту.

Задача D6 (Полиглот)

Маша понимает, что она учится на Физтехе, а не в каком-то лингвистическом институте, но ничего с собой поделать не может: ей нравится изучать языки, и раз есть возможность заниматься и английским, и китайским, то она решила попробовать учить сразу оба языка. И вроде бы всё ничего, справляется (как Маша всё успевает — загадка). Однако иногда, в особенно загруженные недели, ей приходится по-настоящему тяжело. И прошедшая неделя как раз была не из простых... Не вдаваясь в дальнейшие подробности описания всех пережитых Машей "приключений", перейдём к сути задачи.

В файле rus_eng_messed.txt приведён список новых слов, которые Маша узнала по английскому, с русскими переводами, а в файле rus_zho_messed.txt — те же слова, но на китайском (которые Маша подсмотрела интереса ради), тоже с русскими переводами. Но получилось так, что слова в указанных файлах оказались перепутаны, то есть иногда сначала может идти слово на русском, потом его перевод на английский или китайский, а иногда наоборот: слово на иностранном, а потом аналог на русском. Помогите Маше навести порядок в записях! Получите два словаря (для английского и китайского), так чтобы ключами были русские слова, а значениями — иностранные. Запишите эти словари в файлы "rus_eng.txt" (для английского) и "rus_zho.txt" (для китайского). Также Маша просит составить для неё ещё один словарь, англо-китайский (зачем он ей, Маша не уточнила): в котором ключи — это слова на английском, а значения — на китайском. Сохраните этот словарь в файл "eng_zho.txt". Формат файлов с результатами: каждая строчка вида слово -> перевод.

Пример:

# Вход (rus_eng_messed.txt)
мама -> mother
father -> папа

# Вход (rus_zho_messed.txt)
妈妈 (māma) -> мама
爸爸 (bàba) -> папа

# Выход (rus_eng.txt)
мама -> mother
папа -> father

# Выход (rus_zho.txt)
мама -> 妈妈 (māma)
папа -> 爸爸 (bàba)

# Выход (eng_zho.txt)
mother -> 妈妈 (māma)
father -> 爸爸 (bàba)

Задача D7 (Что посмотреть?)

По части фильмов Маша практически всеядна: готова смотреть любые жанры; и новые, и старые фильмы. Однако не любой фильм Маша готова будет смотреть спонтанно. (Например, если в какой-то день у неё пары до вечера, то Маша вряд ли будет готова просто так взять и в тот же вечер посмотреть, скажем, "Братьев Карамазовых".) Маша любит иногда выбрать фильм заранее, чтобы можно было "настроиться" на просмотр. Но как вообще выбирать фильм? По каким критериям, где искать? Определённого алгоритма у Маши нет, и в этот раз она решила провести такой эксперимент: узнать в начале недели у одногруппников, какой бы они фильм рекомендовали ей посмотреть, выбрать фильм из предложенных, и в конце недели устроить просмотр. Опрос Маша уже провела. Теперь вы должны помочь ей сделать выбор!

В файле movie_recommendations.txt представлены рекомендации фильмов от Машиных коллег по учёбе. Каждая строчка имеет вид: имя одногруппника/одногруппницы - название рекомендуемого фильма (год выхода фильма). В файле movies_seen_or_not.txt содержится информация о том, какие фильмы Маша уже смотрела: напротив названий таких фильмов стоит слово seen, иначе написано no.

А в файле classmate_ratings.txt указаны "рейтинги доверия", которые Маша присвоила знакомым. Если Маша полностью доверяет мнению человека, то у него стоит рейтинг 1.0, если же доверия человеку почти нет, то стоит 0.1 или вообще 0.0 (либо просто не особо знакомы с человеком; либо знакомы, просто по части кино доверия нет; либо, кто знает, есть какие-то ещё причины не доверять...)

Для того, чтобы по рекомендациям выбрать фильм, Маша предлагает для каждой картины посчитать числовой показатель по следующей формуле:

$$ s(m) = \sum_{i \in R_m} r_i $$

То есть показатель s(m) (от movie score) для данного фильма m равен сумме рейтингов доверия $r$ одногруппников $R_m$, которые порекомендовали Маше данный фильм к просмотру. Таким образом, чем больше "надёжных" одногруппников порекомендуют фильм m, тем выше получится оценка s(m).

Помогите Маше! Напишите программу, которая бы по всем упомянутым входным данным посчитала оценки s(m). Результат запишите в файл "movie_ratings.txt" в формате movie - s(movie) так, чтобы 1) фильмы были расположены по убыванию значения s(m) и 2) среди фильмов не было бы тех, которые Маша уже смотрела (такие фильмы просто не надо включать в итоговый файл).

Пример:

# Вход (movie_recommendations.txt)
Classmate1 - Movie1 (2021)
Classmate2 - Movie2 (2022)
Classmate3 - Movie3 (2023)

# Вход (movies_seen_or_not.txt)
Movie1 (2021) - seen
Movie2 (2022) - no
Movie3 (2023) - no

# Вход (classmate_ratings.txt)
Classmate1 - 1.0
Classmate2 - 0.9
Classmate3 - 0.1

# Выход (movie_ratings.txt)
Movie2 (2022) - 0.9
Movie3 (2023) - 0.1

Задача D8 (Алиса в Стране чудес)

В файле route.txt построчно по парам приведены места пребывания Алисы во время её путешествия по Стране чудес: откуда -> куда. Но строчки расположены в хаотичном порядке. Напишите программу, которая бы выводила на экран связный последовательный маршрут Алисы: место_1 -> место_2 -> ... -> место_n.

Пример:

# Вход (route.txt)
D -> E
A -> B
C -> D
B -> C

# Выход
A -> B -> C -> D -> E

Задача D9 (Словарь ближайшего соседа)

Напишите программу, которая может принимать от пользователя запросы двух видов (k и v числа):

• add k, v — добавить в словарь значение v по ключу k; вывести v на экран
• get k — достать из словаря значение v по ключу k; вывести v на экран

Таким образом, программа должна работать просто как словарь. С единственным отличием: если при запросе get k ключа k в словаре ещё нет, то программа должна вернуть значение, соответствующее ближайшему k ключу, уже хранящемуся в словаре (идея т.н. метода ближайшего соседа). Если в словаре будет два равноудалённых от k ключа (один меньше, другой больше), то как результат get k надо вернуть среднее арифметическое их значений.

Пример:

# Запущена программа, принимает запросы
add 1, 2  # 2
add 3, 8  # 8
get 1     # 2
get 0     # 2
get 2     # 5

Задача D10 (Словарь синонимов)

https://pythontutor.ru/lessons/dicts/problems/synonym_dictionary/

Вам дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны.

Для слова из словаря, записанного в последней строке, определите его синоним.

Пример:

# Вход
3
Hello Hi
Bye Goodbye
List Array
Goodbye

# Выход
Bye

Задача D11 (Права доступа)

https://pythontutor.ru/lessons/dicts/problems/permissions/

В файловую систему одного суперкомпьютера проник вирус, который сломал контроль за правами доступа к файлам. Для каждого файла известно, с какими действиями можно к нему обращаться:

• запись W
• чтение R
• запуск X

В первой строке содержится число N — количество файлов содержащихся в данной файловой системе. В следующих N строчках содержатся имена файлов и допустимых с ними операций, разделенные пробелами. Далее указано чиcло M — количество запросов к файлам. В последних M строках указан запрос вида Операция Файл. К одному и тому же файлу может быть применено любое колличество запросов.

Вам требуется восстановить контроль над правами доступа к файлам: ваша программа для каждого запроса должна будет возвращать OK, если над файлом выполняется допустимая операция, или же Access denied, если операция недопустима.

Пример:

# Вход
4
helloworld.exe R X
pinglog W R
nya R
goodluck X W R
5
read nya
write helloworld.exe
execute nya
read pinglog
write pinglog

# Выход
OK
Access denied
Access denied
OK
OK

Задача D12 (Страны и города)

https://pythontutor.ru/lessons/dicts/problems/countries_and_cities/

Дан список стран и городов каждой страны. Затем даны названия городов. Для каждого города укажите, в какой стране он находится.

Пример:

# Вход
2
Brazil São_Paulo Rio_de_Janeiro Salvador Olinda
Japan Tokyo Kyoto Fukuoka
3
Kyoto
São_Paulo
Salvador

# Выход
Japan
Brazil
Brazil

События Pygame (продолжение)

Каждая задача — продолжение одной из задач по прошлой лабе. Таким образом, предполагается, что каждый продолжит работать над задачей, выбранной ранее.

Во всех задачах можно предлагать и свои модификации — но тогда надо это заранее обсудить с преподавателем.

Задача Ev1 (Поймай шарик)

Предыдущее задание.

Упражнение из лабы.

Предлагается в качестве задачи на дом сделать следующие несколько пунктов упражнения:

• Добавить второй тип мишени со своей формой и своим специфическим характером движения.
• Выдавать за эти мишени другое количество очков.
• Сделать таблицу лучших игроков, автоматически сохраняющуюся в файл (видимо, предполагается перед началом игры как-то спросить имя у игрока?)

("Читабельный код", про который также говорилось в упражнении, предполагается по умолчанию.)

Задача Ev2 (Тараканьи бега)

Предыдущее задание.

Надо реализовать любые три модификации из предложенных:

• Добавьте новый тип таракана со своей формой и цветом.
• Если во время бега кликать левой кнопкой мыши по таракану, то он начинает бежать быстрее (чем больше раз кликнул, тем быстрее побежал).
• Добавьте сохранение результатов забега в файл: после пересечения последним тараканом финиша в тектовый файл для каждого таракана записывается его номер (номер дорожки) и время.
• Если во время бега кликнуть левой кнопкой мыши перед тараканом, то появляется "замедляющая ловушка": статичная точка, которая снижает скорость таракана, пока он находится на ней (как только таракан проходит ловушку, скорость возвращается к исходному значению).
• Сделайте так, чтобы кнопка старта была и кнопкой паузы (если нажать ещё раз, забег ставится на паузу, нажать ещё раз — продолжается и т.д.)
• Добавьте "глупых" тараканов: они бегут в другую сторону, и надо несколько раз кликнуть по ним мышью, чтобы они развернулись.
• Добавьте "целевого" таракана: это личный таракан игрока (и самый медленный из всех), и потому в интересах игрока попытаться сделать так, чтобы именно этот таракан пришёл к финишу первым.

Задача Ev3 (Круги на воде)

Предыдущее задание.

Надо реализовать любые три модификации из предложенных:

• Добавьте "угасание" кругов со временем: по мере того, как они, расходясь, становятся больше, они также и "истончаются", так что вообще могут полностью исчезнуть, не дойдя до границы.
• Добавьте взаимодействие между кругами: более маленький считается более "сильным" и потому в месте контакта перекрывает большой.
• Если быстро несколько раз кликнуть мышью по воде, то возникает "сильный" круг: он изначально толще, чем обычные круги (можно думать об этом так, что "сильный" круг возникает словно в результате падения в воду более большого камня).
• Если кликнуть мышью на область около границы, то возникает "волна": горизонтальная, если кликнуть около верхней или нижней границы (и вертикальная, если кликнуть около правой или левой). Волна движется по полю в противоположную сторону (если возникла снизу, то идёт наверх и т.п.)
• Добавьте на поверхность воды лилии с лягушками: лягушка неподвижно сидит на кувшинке, а если по ней несколько раз кликнуть мышкой ("надоесть" лягушке), то она спрыгивает с кувшинки в случайном направлении, уплывает, а в месте падения на воду возникает круг.
• Добавьте лодочку: пусть иногда с какой-то границы на воду приходит лодочка, они идёт ровно по прямой, и оставляет за собой круги (с каким-то интервалом).
• Добавьте кнопку, включающую дождь: если на неё нажать, то вся поверхность воды начинает покрываться маленькими быстро исчезающими кругами (словно капли дождя падают на воду). Нажать ещё раз — дождь прекращается и вода постепенно успокаивается (все возникшие маленькие круги исчезают, новых не появляется).

Задача Ev4 (Листья)

Предыдущее задание.

Надо реализовать любые три модификации из предложенных:

• Сделайте так, чтобы листья были разноцветными (придерживайтесь осенней гаммы).
• Реализуйте одновременное опадение нескольких листьев: теперь вместо одного могут начать опадать одновременно несколько. Пока эта группа листьев падает, новые не отваливаются (так же, как раньше при падении только одного листа).
• Реализуйте независимое опадание листьев: то есть одновременно могут падать два и более листьев, а также в процессе падения одного листа может начать опадать новый. (Описанная модификация исключает предыдущую, то есть либо эта, либо та.)
• Добавьте кнопки усиления и ослабления ветра: по мере нажимания на кнопку усиления опадание становится всё активнее. Нажатие на кнопку ослабления ветра "нейтрализует" одно нажатие на кнопку усиления (например, если три раза усилить и один раз ослабить, то ветер будет дуть с двукратным усилением).
• Сделайте так, чтобы листья могли опадать под углом. Предлагается следующая идея: пусть постоянно словно дует ветер, и листья в данный момент падают по ветру. Иногда направление ветра случайно меняется, и одновременно с этим меняется и направление падения листьев.
• Пусть при клике по ветке левой кнопкой мыши с неё спадает один лист.
• Если при падении листа нажать по нему мышкой и удерживать, то он перестаёт падать (словно "прижимаем" его к экрану).
• Если при падении листа зажать по нему левой кнопкой мыши, то его можно передвинуть в любое место экрана. Как только отжать мышь — лист продолжает падать (из того места, куда его переместили).

Задача Ev5 (Brick Clicker, или "Интересные картинки")

Предыдущее задание.

Надо реализовать любые три модификации из предложенных:

• Если промазать и кликнуть мимо активного блока, то он "тускнеет" (снова становится неактивным).
• Блок становится активным только на некоторое время: если не успеть по нему нажать, то он гаснет, и открыть его на данном шаге уже не получится. Время активности варьируется случайным образом в некоторых пределах.
• Одновременно могут загораться несколько блоков (ограниченное число).
• Одновременно могут загораться несколько блоков, при этом: если успеть кликнуть по всем, они все открываются, если же допустить ошибку (промазать или не уложиться по времени — в зависимости от того, какие модификации были реализованы до этого), то они все тускнеют и ничего на данном шаге не открывается.
• Периодически по полю на большой скорости проносится "магическая открывающая лупа": это светлый непрозрачный круг, который врывается на поле в случайном месте границы и пересекает его по прямой. Если успеть по нему кликнуть, то исчезают все блоки, находящиеся в момент клика под лупой (надеюсь, примерно понятно 😅). То есть это возможность за один раз открыть больше одного блока (но возможность не простая, потому что лупа должна двигаться достаточно быстро, и появляется внезапно).
• На вход программе можно подать свою картинку (это доработка не по части pygame, более "техническая") — и тогда игра будет идти с ней.
• В программе должна быть возможность задать "степень гранулярности", то есть как много вообще должно быть блоков: много — долгая и "дразнящая" игра, или мало — более динамичная и простая (это тоже доработка не по части pygame).
• Добавить блок – "убийцу прогресса": это такой активный блок, который загорается красным (случается редко). Если по такому блоку не успеть кликнуть вовремя или промазать (в зависимости от того, какие модификации были реализованы до этого), то все открытые до этого блоки возвращаются обратно и вся картинка снова закрывается.

Задача Ev6 (Свободная)

Предыдущее задание.

Свяжитесь с преподавателем, если решали такую задачу — надо будет придумывать варианты модификаций в специальном порядке 😅