Решение задач с помощью словарей
Словари в Python удобно использовать для решения задач, связанных с:
- хранением и обработкой данных о свойствах объекта;
- сопоставлением данных;
- подсчетом;
- выбором подходящих по условию значений – включая регулярные выражения.
В последнем случае словарь эффективно заменяет условные конструкции if – elif – else. В качестве ключей в словарях можно использовать только неизменяемые типы данных – цифры, строки (включая «сырые») и кортежи. Однако в качестве значений можно использовать почти любые типы данных.
Задача 1: Скрабл
В настольной игре Скрабл (Scrabble) каждая буква имеет определенную ценность. В случае с английским алфавитом очки распределяются так:
- A, E, I, O, U, L, N, S, T, R – 1 очко;
- D, G – 2 очка;
- B, C, M, P – 3 очка;
- F, H, V, W, Y – 4 очка;
- K – 5 очков;
- J, X – 8 очков;
- Q, Z – 10 очков.
А русские буквы оцениваются так:
- А, В, Е, И, Н, О, Р, С, Т – 1 очко;
- Д, К, Л, М, П, У – 2 очка;
- Б, Г, Ё, Ь, Я – 3 очка;
- Й, Ы – 4 очка;
- Ж, З, Х, Ц, Ч – 5 очков;
- Ш, Э, Ю – 8 очков;
- Ф, Щ, Ъ – 10 очков.
Напишите программу, которая вычисляет стоимость введенного пользователем слова. Будем считать, что на вход подается только одно слово, которое содержит либо только английские, либо только русские буквы.
Пример ввода:
ноутбук
Пример вывода:
12
Решение:
Сначала напишем функцию isCyrillic(), которая возвращает True, если введенное слово содержит кириллические символы, и False, если буквы – латинские.
Затем создадим словари, где ключами будут очки, а значениями – строки из букв. Метод items() позволяет обращаться к ключам и значениям одновременно – если очередная буква в слове входит в одно из значений, генератор добавит ключ в список, а метод списка sum() подсчитает стоимость всего слова:
import re
def isCyrillic(text):
return bool(re.search('[а-яА-Я]', text))
points_en = {1:'AEIOULNSTR',
2:'DG',
3:'BCMP',
4:'FHVWY',
5:'K',
8:'JZ',
10:'QZ'}
points_ru = {1:'АВЕИНОРСТ',
2:'ДКЛМПУ',
3:'БГЁЬЯ',
4:'ЙЫ',
5:'ЖЗХЦЧ',
8:'ШЭЮ',
10:'ФЩЪ'}
text = input().upper()
if isCyrillic(text):
print(sum([k for i in text for k, v in points_ru.items() if i in v]))
else:
print(sum([k for i in text for k, v in points_en.items() if i in v]))
Хочешь научиться создавать программы и автоматизировать рутинные задачи на Python? На нашем курсе ты не только изучишь синтаксис языка, но и научишься мыслить как программист, решая реальные задачи и создавая полноценные приложения.
Что ты получишь:
- Структурированную программу обучения, подходящую даже для новичков
- Практические задания, позволяющие закрепить теорию
- Поддержку опытных преподавателей
- Возможность создать свой первый проект уже во время обучения
Задача 2: Рюкзак
Турист собирается в поход. Он сможет нести N кг вещей. Но вещей, которые он запланировал уложить в рюкзак, оказалось намного больше. Нужно определить, какие вещи от наиболее тяжелых к самым легким поместятся в рюкзак.
Пример ввода:
10
Пример вывода:
палатка
спальный мешок
удочка
термос
салфетки
жвачка
Решение:
Эту классическую задачу комбинаторной оптимизации удобно решать с помощью словаря, в котором содержатся все вещи. Для сортировки вещей мы воспользуемся методом sorted() и лямбда-функцией в качестве ключа сортировки. Решение выглядит так:
things = {'зажигалка': 20, 'компас': 100, 'фрукты': 500, 'рубашка': 300,
'термос': 1000, 'аптечка': 200, 'куртка': 600, 'бинокль': 400, 'удочка': 1200,
'салфетки': 40, 'бутерброды': 820, 'палатка': 5500, 'спальный мешок': 2250, 'жвачка': 10}
ves = int(input()) * 1000
sorted_things = dict(sorted(things.items(), key=lambda x: -x[1]))
for k, v in sorted_things.items():
if v <= ves:
print(k, sep='/n')
ves -= v
Задача 3. Email-адреса
Данные об email-адресах студентов хранятся в словаре:
emails = {'mgu.edu': ['andrei_serov', 'alexander_pushkin', 'elena_belova', 'kirill_stepanov'],
'gmail.com': ['alena.semyonova', 'ivan.polekhin', 'marina_abrabova'],
'msu.edu': ['sergei.zharkov', 'julia_lyubimova', 'vitaliy.smirnoff'],
'yandex.ru': ['ekaterina_ivanova', 'glebova_nastya'],
'harvard.edu': ['john.doe', 'mark.zuckerberg', 'helen_hunt'],
'mail.ru': ['roman.kolosov', 'ilya_gromov', 'masha.yashkina']}
Нужно дополнить код таким образом, чтобы он вывел все адреса в алфавитном порядке и в формате имя_пользователя@домен.
Решение:
Задача решается с помощью генератора словаря (или списка) и метода sorted() в одну строчку:
print(*sorted({i + '@' + k for k, v in emails.items() for i in v}), sep = '\n')
Задача 4: Права доступа
Вирус повредил систему прав доступа к файлам. Известно, что над каждым файлом можно производить определенные действия:
- запись –
W; - чтение –
R; - запуск –
X.
На вход программе подается:
- число
n– количество файлов; nстрок с именами файлов и допустимыми операциями;- число
m– количество запросов к файлам; mзапросов вида «операция файл».
Для каждого допустимого запроса программа должна возвращать OK, для недопустимого – Access denied.
Пример ввода:
3
python.exe X
book.txt R W
notebook.exe R W X
5
read python.exe
read book.txt
write notebook.exe
execute notebook.exe
write book.txt
Пример вывода:
Access denied
OK
OK
OK
OK
Решение:
Для сопоставления соответствия команд правам доступа создадим словарь rights, для записи введенных имен – словарь names. Конструкция print(('Access denied', 'OK')[comm in names[n]]), которая выводит результат, аналогична print('OK' if comm in names[n] else 'Access denied') и заменяет цикл с условием:
names = {}
rights = {'W': 'write', 'R': 'read', 'X': 'execute'}
for i in range(int(input())):
x = input().split()
names[x[0]] = [rights[i] for i in x[1:]]
for i in range(int(input())):
comm, n = input().split()
print('OK' if comm in names[n] else 'Access denied')
Задача 5: Продажи
Напишите программу, которая подсчитывает количество единиц товаров, приобретенных покупателями онлайн-магазина. На вход программе подается число n – количество записей о покупках, а затем n строк вида «Покупатель Товар Количество». Для каждого покупателя программа должна выводить список покупок.
Пример ввода:
5
Сергей Карандаш 3
Андрей Тетрадь 5
Юлия Линейка 1
Сергей Ручка 2
Юлия Книга 4
Пример вывода:
Андрей:
Тетрадь 5
Сергей:
Карандаш 3
Ручка 2
Юлия:
Книга 4
Линейка 1
Решение:
Проще всего такую задачу решить с помощью метода setdefault() – он позволяет получить значение из словаря по заданному ключу, и автоматически добавляет в словарь отсутствующие там элементы:
sales = {}
for _ in range(int(input())):
name, item, count = input().split()
sales[name][item] = sales.setdefault(name, {}).setdefault(item, 0) + int(count)
for key in sorted(sales):
print(f'{key}:')
for i in sorted(sales[key].items()):
print(*i)
Задача 6: Объединение словарей
В Python предусмотрено объединение словарей:
merged_dict = {**dict1, **dict2}
Однако если в словарях есть одинаковые ключи, ключу в объединенном словаре будет присвоено значение из второго словаря. Напишите программу, которая объединяет два словаря и суммирует значения одинаковых ключей.
Решение:
Воспользуемся методом get() , который принимает второй аргумент – значение по умолчанию, в нашем случае это должен быть 0. Кроме того, применим объединение множеств с помощью оператора |:
dict1 = {'яблоки': 100, 'бананы': 333, 'груши': 200,
'апельсины': 300, 'ананасы': 45, 'лимоны': 98,
'сливы': 76, 'манго': 34, 'виноград': 90, 'лаймы': 230}
dict2 = {'яблоки': 300, 'груши': 200, 'бананы': 400,
'малина': 777, 'ананасы': 12, 'лаймы': 123, 'черника': 111, 'арбузы': 666}
merged_dict = {key: dict1.get(key, 0) + dict2.get(key, 0) for key in set(dict1) | set(dict2)}
print("Объединенный словарь:", merged_dict)
Задача 7: Коты и владельцы
В базе данных ветеринарной клиники информация о пациентах-котах хранится в списке кортежей. Данные о кошках и их владельцах записаны в формате «Кличка животного, Возраст животного, Имя владельца, Фамилия владельца»:
cats = [('Мартин', 5, 'Алексей', 'Егоров'),
('Фродо', 3, 'Анна', 'Самохина'),
('Вася', 4, 'Андрей', 'Белов'),
('Муся', 7, 'Игорь', 'Бероев'),
('Изольда', 2, 'Игорь', 'Бероев'),
('Снейп', 1, 'Марина', 'Апраксина'),
('Лютик', 4, 'Виталий', 'Соломин'),
('Снежок', 3, 'Марина', 'Апраксина'),
('Марта', 5, 'Сергей', 'Колесников'),
('Буся', 12, 'Алена', 'Федорова'),
('Джонни', 10, 'Игорь', 'Андропов'),
('Мурзик', 1,'Даниил', 'Невзоров'),
('Барсик', 2, 'Виталий', 'Соломин'),
('Рыжик', 7, 'Владимир', 'Медведев'),
('Матильда', 8, 'Андрей', 'Белов'),
('Гарфилд', 3, 'Александр', 'Березуев')]
Обнаружилось, что имена некоторых владельцев повторяются, потому что у них несколько кошек. Необходимо оптимизировать хранение данных таким образом, чтобы для каждого владельца при выводе на печать данные о всех его животных отображались в одной строке:
Игорь Бероев: Муся, 7; Изольда, 2
Решение.
Воспользуемся методом словарей setdefault() и методом join() для объединения элементов списков и кортежей с необходимыми разделителями:
result = {}
for cat in cats:
temp = cat[0] + ', ' + str(cat[1])
result.setdefault(cat[2:], []).append(temp)
for k, v in result.items():
print(' '.join(k) + ':', '; '.join(v))
Задача 8: Редкое слово
Напишите программу, которая принимает на вход строку, и выводит слово, которое встречается во фразе реже всего. Если редких слов несколько, нужно вывести то, которое меньше в лексикографическом порядке. Регистр слов не учитывается, знаки препинания в предложениях игнорируются.
Пример ввода:
дом, милый дом, милый.
Пример вывода:
дом
Решение:
Для подсчета символов, слов и т. п. удобно использовать метод get(), а для сортировки – лямбда-функцию, которая обеспечит вывод наименьшего из редких слов:
words = {}
for i in input().split():
i = i.strip('.,!?:;-').lower()
words[i] = words.get(i, 0) + 1
print(min(words.items(), key=lambda x: (x[1], x[0]))[0])
Задача 9: Дубликаты
Напишите программу, которая принимает на вход строку, и отслеживает, сколько раз каждый символ уже встречался. Количество повторов добавляется к символам с помощью постфикса формата _n.
Пример ввода:
a a a b c a a d c d d
Пример вывода:
a a_1 a_2 b c a_3 a_4 d c_1 d_1 d_2
Решение:
Самое компактное решение получается при использовании f-строк и метода get():
sp = input().split()
result = {}
for i in sp:
if i in result:
print(f'{i}_{result[i]}', end=' ')
else:
print(i, end=' ')
result[i] = result.get(i, 0) + 1
Задача 10: Анаграммы
Напишите программу, которая принимает на вход две строки и определяет, являются ли они анаграммами. Знаки препинания, пробелы и регистр при этом игнорируются.
Пример ввода:
Цари, вино и сало.
Лисица и ворона.
Пример вывода:
YES
Решение:
Избавиться от знаков препинания можно несколькими способами – с помощью strip(), replace(), или просто путем добавления в словарь только букв (метод isalpha()) из введенных строк:
def a(word):
result = {}
for i in word.lower():
if i.isalpha():
result[i] = result.get(i, 0) + 1
return result
print("YES" if a(input()) == a(input()) else "NO")
Задача 11: Расшифровка
На вход программе подается:
1. Зашифрованная строка.
2. N – число букв в словаре.
3. N строк, в которых в формате «буква: частота» указывается, сколько раз каждая буква встречается в слове.
Программа выводит расшифрованное слово.
Пример ввода:
?*!*!*
3
b: 1
a: 3
n: 2
Пример вывода:
banana
Решение:
Для сопоставления символов зашифрованного слова с буквами понадобятся два словаря:
my_dict, w = {}, {}
sl = input()
for i in sl:
w[i] = w.get(i, 0) + 1
for _ in range(int(input())):
a, b = input().split(': ')
my_dict[int(b)] = a
for i in sl:
print(my_dict[w[i]], end='')
Задача 12: Запрос
Напишите функцию, которая принимает словарь с параметрами и возвращает строку запроса, сформированную из отсортированных в лексикографическом порядке параметров.
Пример:
Код print(query({'course': 'python', 'lesson': 2, 'challenge': 17})) должен возвращать строку:
challenge=17&course=python&lesson=2
Решение:
Используя метод items(), функцию можно написать так:
def query(params):
return '&'.join(sorted(f'{k}={v}' for k, v in params.items()))
Примечание – в Python есть библиотека urllib для работы с параметрами URL. При использовании этого модуля функция выглядит так:
from urllib.parse import urlencode
def query(params):
sortedpar = dict(sorted(params.items()))
return urlencode(sortedpar)
Другие варианты
Каждую из приведенных выше задач можно решить несколькими способами – с использованием словарей или без них. Генераторы сокращают код в несколько раз, но в то же время усложняют чтение – начинающим, возможно, будет проще использовать обычные циклы.
Комментарии