Решение задач с помощью словарей
Словари в 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