Задача 1. Анонимное письмо
В классических детективах герои часто получают анонимные послания, текст которых набран вырезанными из журнала (газеты) буквами и знаками препинания. Напишите программу, которая определит, достаточно ли в журнале символов для составления анонимного письма.
Решение
Брутфорсный подход – подсчитать для каждой буквы алфавита и
каждого знака препинания, сколько раз они встречаются в письме и в журнале.
Если какой-то символ встречается в письме реже, чем в журнале, программа
возвращает True, в противном
случае – False. Это очень медленное решение,
поскольку программа перебирает все символы из набора, включая те, которые не
встретятся ей ни в письме, ни в тексте журнала. Кроме того, программа выполнит
множество итераций – по числу символов в наборе – над каждым символом письма и
текста.
Более оптимальное решение – однократный проход по тексту
письма с сохранением информации о количестве вхождений каждого символа в виде
хеш-таблицы. В этой хеш-таблице ключами являются входы символов, а значениями –
количество вхождений каждого символа. Затем выполняется проход по тексту
журнала: для каждого символа c надо проверить, есть ли он в хеш-таблице. Если есть, то значение счетчика вхождений уменьшается на
1, а если после этого значение счетчика становится равным 0, то символ
удаляется из хеш-таблицы. Если после обработки всего текста журнала хеш-таблица
оказывается пустой, то это означает, что все символы встречались в журнале
столько же раз, сколько и в письме, и программы вернет True. Если же после
обработки всего журнала хеш-таблица не пуста, то результатом работы программы
будет False, поскольку в этом случае найдутся символы, которые в письме встречаются
чаще, чем в журнале.
Вариант 1
import collections
def letter_from_magazine(letter_text, magazine_text):
# подсчитываем частоту вхождений каждого символа письма
char_frequency_for_letter = collections.Counter(letter_text)
# проверяем, можно ли составить письмо из текста журнала
for c in magazine_text:
if c in char_frequency_for_letter:
char_frequency_for_letter[c] -= 1
if char_frequency_for_letter[c] == 0:
del char_frequency_for_letter[c]
if not char_frequency_for_letter:
# все символы письма есть в журнальном тексте
return True
return False
Вариант 2
import collections
def letter_from_magazine_pythonic(letter_text, magazine_text):
return not collections.Counter(letter_text) - collections.Counter(magazine_text)
Пример использования
letter_text = '''Сегодня в полночь в старом саду... Оставь миллион долларов в колодце.
Внимание - если жизнь кота тебе дорога, держи все в секрете!'''
magazine_text = '''Сегодня компания Microsoft представила новую,
загадочную версию Windows в полночь. Эта версия была разработана в условиях
строжайшей секретности под кодовым названием "Старый колодец".
Только избранные сотрудники имели доступ к тестированию этой системы в старом саду с яблонями.
Руководство компании утверждает, что новая Windows содержит уникальные возможности,
которые позволят пользователям работать эффективно и безопасно.
Особое внимание уделено защите личной информации.
Однако подробности держатся в секрете. Тем, кто хочет получить доступ к этой системе,
придется доказать свою надежность и умение хранить тайны. В противном случае конкуренты могут похитить интеллектуальную собственность Microsoft и навредить компании!
По неподтвержденным данным, новая Windows содержит упоминания о "миллионе долларов" и "кошачьем счастье". Что это значит - пока неясно. Но руководство компании призывает всех хранить тайну и не раскрывать детали этого проекта. Только так новая операционка сможет увидеть свет и принести пользу.'''
print(letter_from_magazine(letter_text, magazine_text))
print(letter_from_magazine_pythonic(letter_text, magazine_text))
Вывод:
True
True
Задача 2. Кэш для операций над ISBN номерами
Международный стандартный книжный номер (ISBN) – это уникальный идентификатор книжных изданий, необходимый для операций с книгой в торговых сетях и учетном ПО. В современных ISBN используется 13 цифр, но в этой задаче мы рассматриваем 10-значные ISBN старого образца – они действовали до 2007 года.
10-значные ISBN представляют собой строку, где первые 9 символов – цифры, а последний символ – контрольный. Контрольный символ представляет собой сумму первых 9 цифр по модулю 11, причем 10 обозначается символом X. Создайте кэш для поиска цен на книги, представленные в системе с помощью ISBN. Вам нужно реализовать методы поиска, вставки и удаления. Для вытеснения кэша используйте политику наименьшего числа использованных записей (LRU). Если ISBN уже присутствует, метод вставки не должен изменять цену, но должен обновить эту запись как последнюю использованную. Поиск также должен обновить эту запись как последнюю использованную.
Решение
Для быстрого поиска идеально подходят хеш-таблицы, где в качестве ключей используются ISBN. Вместе с каждым ключом мы будем хранить значение – цену и время последнего обращения к этому ключу. Такой подход дает время поиска O(1). Вставка в кэш тоже занимает O(1), пока кэш не заполнится. Как только кэш заполняется, для добавления новой записи нам нужно найти запись с наименьшим временем последнего обращения (LRU), которая будет вытеснена и освободит место для новой записи. Поиск этой записи занимает O(n) времени, где n – размер кэша.
Чтобы улучшить производительность, можно использовать ленивую сборку мусора. Допустим, мы хотим, чтобы размер кэша был n. Мы не удаляем записи из хеш-таблицы, пока она не вырастет до 2n записей. На этом этапе мы пробегаем по всей хеш-таблице и находим медианный возраст элементов. Затем мы отбрасываем все элементы младше медианы. Время удаления в худшем случае становится O(n), но это происходит не чаще чем раз в n операций. Недостаток этого подхода – для некоторых запросов временная сложность может достичь O(n), если кэш полностью заполнен. Это происходит потому, что при удалении элементов из кэша могут возникнуть коллизии, и придется искать другое место для хранения элемента, что может потребовать дополнительного времени.
Альтернативное решение – поддержка отдельной очереди с ключами. В этом случае в хеш-таблице для каждого ключа мы будем хранить ссылку на его место в очереди. Каждый раз, когда мы ищем ISBN и находим его в хеш-таблице, номер перемещается в начало очереди. Для этого нужна реализация очереди на основе связного списка, чтобы можно было перемещать элементы из середины в начало. Когда длина очереди превышает n, при добавлении нового элемента в кэш, элемент в конце очереди удаляется из кэша, т.е. из очереди и хеш-таблицы.
Код решения
import collections
class LRUCache:
def __init__(self, capacity):
self.isbn_price_table = collections.OrderedDict()
self.capacity = capacity
def lookup(self, isbn):
if isbn not in self.isbn_price_table:
return -1
price = self.isbn_price_table.pop(isbn)
self.isbn_price_table[isbn] = price
return price
def insert(self, isbn, price):
# вставляем значение для ключа,
# только если ключ уже существует, не обновляя существующие
if isbn in self.isbn_price_table:
price = self.isbn_price_table.pop(isbn)
elif len(self.isbn_price_table) >= self.capacity:
self.isbn_price_table.popitem(last=False)
self.isbn_price_table[isbn] = price
def erase(self, isbn):
return self.isbn_price_table.pop(isbn, None) is not None
Пример использования
cache = LRUCache(3) # создаем кэш с емкостью 3
cache.insert('978-3-16-148410-0', 785.55) # вставляем книгу с ISBN 978-3-16-148410-0 и ценой 785.55
cache.insert('978-3-16-148411-7', 322.99)
cache.insert('978-3-16-148412-4', 417.99)
price = cache.lookup('978-3-16-148410-0') # ищем цену книги с ISBN 978-3-16-148410-0
print(price)
cache.erase('978-3-16-148410-0') # удаляем книгу с ISBN 978-3-16-148410-0
for isbn, price in cache.isbn_price_table.items():
print(f'ISBN: {isbn}, Цена: {price} руб')
Вывод:
785.55
ISBN: 978-3-16-148411-7, Цена: 322.99 руб
ISBN: 978-3-16-148412-4, Цена: 417.99 руб
Задача 3. Гипотеза Коллатца
Гипотеза Коллатца (или гипотеза 3n+1) – это нерешенная математическая проблема из области теории чисел.
Суть гипотезы
Любое число при выполнении определенных манипуляций с ним рано или поздно сводится к единице:
- Берем любое натуральное число n. Если оно четное, делим его на 2. Если нечетное – умножаем на 3 и прибавляем 1.
- Повторяем эту операцию с полученным числом до тех пор, пока в результате не получится 1.
Гипотеза до сих пор не доказана математически для всех значений n, хотя компьютерные расчеты подтверждают, что она верна для очень больших значений n.
Напишите программу для проверки первых n чисел на соответствие гипотезе Коллатца.
Решение
Идея решения состоит в том, чтобы пройти через все числа и для каждого из них последовательно применять правила до тех пор, пока не получим единицу.
Это означает, что для проверки гипотезы к каждому числу нужно применять процесс Коллатца (если число четное, нужно разделить его на 2; если число нечетное, надо умножить его на 3 и прибавить 1) до тех пор, пока мы не достигнем числа 1. Если в процессе попадается число, которое уже встречалось ранее в последовательности, это означает циклическую последовательность, и нужно вернуть False. Если последовательность стремится к бесконечности, функция также должна вернуть False.
Код решения
def test_collatz_conjecture(n):
verified_numbers = set() # для сохранения нечетных чисел, проверенных на сходимость к 1
# начинаем с 3, гипотеза тривиально выполняется для 1.
for i in range(3, n + 1):
sequence = set()
test_i = i
while test_i >= i:
if test_i in sequence:
return False
sequence.add(test_i)
if test_i % 2:
if test_i in verified_numbers:
break # число уже проверено на сходимость к 1
verified_numbers.add(test_i)
test_i = 3 * test_i + 1
else:
test_i //= 2
return True
print(test_collatz_conjecture(int(input())))
Задача 4. Решатель судоку
Судоку – популярная логическая головоломка, которая заключается в заполнении сетки 9x9 цифрами так, чтобы в каждой строке, столбце и сетке 3x3 были использованы все цифры от 1 до 9. Игровое поле судоку, по сути, представляет собой латинский квадрат 9-го порядка.
Напишите программу, которая получает частично заполненную сетку судоку и дополняет ее цифрами от 1 до 9 так, чтобы получилась корректная матрица судоку.
Решение
Несмотря на то что матрица имеет фиксированный размер, заполнение методом перебора займет слишком много времени. Судоку обычно решают с помощью одного из этих двух подходов:
Воспользуемся первым вариантом – его также называют алгоритмом обратного поиска и алгоритмом обратного отслеживания:
- Функция
place_number()проверяет, можно ли поместить число n в ячейку с координатами (y, x) в матрице судоку. Она проверяет, не встречается ли это число уже в той же строке, столбце или 3x3 подматрице. Если число можно поместить, функция возвращаетTrue, в противном случаеFalse.
- Функция
solve_sudoku()рекурсивно проходит по каждой ячейке и пытается поместить в нее числа от 1 до 9. Если число можно поместить и после этого сетка может быть решена, функция возвращает заполненную матрицу. Если число нельзя поместить, функция возвращаетNone, что вызывает откат к предыдущей ячейке.
Код решения
def place_number(y, x, n, challenge):
for i in range(9):
if challenge[y][i] == n:
return False
for i in range(9):
if challenge[i][x] == n:
return False
x0 = (x // 3) * 3
y0 = (y // 3) * 3
for i in range(3):
for j in range(3):
if challenge[y0 + i][x0 + j] == n:
return False
return True
def solve_sudoku(challenge):
for y in range(9):
for x in range(9):
if challenge[y][x] == 0:
for n in range(1, 10):
if place_number(y, x, n, challenge):
challenge[y][x] = n
if solve_sudoku(challenge):
return challenge
challenge[y][x] = 0
return None
return challenge
challenge = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
[5, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 7, 0, 0, 0, 0, 3, 1],
[0, 0, 3, 0, 1, 0, 0, 8, 0],
[9, 0, 0, 8, 6, 3, 0, 0, 5],
[0, 5, 0, 0, 9, 0, 6, 0, 0],
[1, 3, 0, 0, 0, 0, 2, 5, 0],
[0, 0, 0, 0, 0, 0, 0, 7, 4],
[0, 0, 5, 2, 0, 6, 3, 0, 0]]
for row in solve_sudoku(challenge):
print(*row)
Вывод:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Задача 5. Интервалы занятости
Временные промежутки, в течение которых пользователь занят, выполняя определенные задачи, представлены в его расписании в виде отдельных временных интервалов. В каждый интервал может входить несколько задач. Например:
- С 8 до 15 – работа (с 8 до 10 написание кода, с 10 до 12 совещание и т.д.)
- С 18 до 22 – личные дела (с 18 до 19 ужин, с 19 до 21 просмотр сериалов и т.п.)
- С 23 до 7 часов – сон.
Напишите программу, которая добавляет в список дел новые задачи и обновляет интервалы занятости, отсортированные по времени старта. Например, если в приведенное выше расписание добавить новую задачу с интервалами (17, 20), обновленные промежутки занятости будут иметь вид: (8, 15), (17, 22), (23, 7).
Решение
Брутфорсный подход – найти наименьшее значение старта и наибольшее значение финиша в наборе, состоящем из существующих интервалов и новой задачи. Затем каждое целое число между этими двумя значениями проверяется на принадлежность к интервалу. Время выполнения этого алгоритма составляет O(Dn), где D – разница между двумя крайними значениями, а n –количество интервалов. Обратите внимание, что D может быть значительно больше, чем n. Если занятость измеряется, например, секундами, промежуток занятости охватывает 5 лет, массив состоит из ([0, 1], [157766399, 157766400]), а добавляемый интервал охватывает [10, 20] – брутфорсный алгоритм будет перебирать все целые числа от 0 до 157 766 400.
Более оптимальное решение состоит из 3 этапов:
- Сначала обрабатываем интервалы, которые находятся перед новой задачей – они сразу добавляются в результат.
- Когда сталкиваемся с промежутком, который пересекается с интервалом новой задачи – вычисляем объединение существующего промежутка и нового интервала. Проходим через последующие интервалы и добавляем их в результат, если они пересекаются с формируемым интервалом.
- И наконец, обрабатываем интервалы, которые расположены после новой задачи. Поскольку ни один из этих интервалов не может пересекаться с новой задачей, мы просто добавляем эти интервалы в результат.
Код решения
from collections import namedtuple
Interval = namedtuple('Interval', ('start', 'finish'))
def add_interval(busy_intervals, new_task):
i, result = 0, []
# обрабатываем интервалы до новой задачи
while (i < len(busy_intervals) and new_task.start > busy_intervals[i].finish):
result.append(busy_intervals[i])
i += 1
# обрабатываем интервалы, которые пересекаются с новой задачей
while (i < len(busy_intervals) and new_task.finish >= busy_intervals[i].start):
# если [a, b] и [c, d] пересекаются, объединенный интервал равен [min(a, c), max(b, d)].
new_task = Interval(
min(new_task.start, busy_intervals[i].start),
max(new_task.finish, busy_intervals[i].finish))
i += 1
# обрабатываем интервалы после новой задачи
return result + [new_task] + busy_intervals[i:]
Пример использования
busy_intervals = [Interval(7, 13), Interval(12, 15), Interval(14, 19), Interval(23, 7)]
new_task = Interval(17, 21)
result = add_interval(busy_intervals, new_task)
for interval in result:
print(interval)
Вывод:
Interval(start=7, finish=13)
Interval(start=12, finish=15)
Interval(start=14, finish=21)
Interval(start=23, finish=7)
Материалы по теме
- 🐍💼 Подготовка к собеседованию по Python: решаем 5 интересных задач
- 6 алгоритмов решения задач по спортивному программированию
- 🐍🧩 Обработка вложенных списков и матриц в Python: 5 задач с решениями для совершенствования навыков
Комментарии