Решаем задачи и прокачиваем навык работы со словарями, используя методы get(), setdefault(), генераторы словарей и сортировку с помощью лямбда-функций.

Решение задач с помощью словарей

Словари в 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]))     

Задача 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)     

Другие варианты

Каждую из приведенных выше задач можно решить несколькими способами – с использованием словарей или без них. Генераторы сокращают код в несколько раз, но в то же время усложняют чтение – начинающим, возможно, будет проще использовать обычные циклы.

***

Материалы по теме

• 🐍 15 вещей, которые нужно знать о словарях Python
• 🐍 Python и динамическое программирование на примере задачи о рюкзаке
• 🐍 Известная задача с потерянным билетом: реализация на Python