❗️Задача для конкурса в честь дня программиста

Условие:

Даны две строки s и f (начальная и конечная) и словарь D (набор слов).

Нужно определить, можно ли преобразовать s в f, используя только слова из словаря D. При этом каждое преобразование должно менять только один символ, а длина слова должна оставаться неизменной. Если преобразование возможно, нужно найти кратчайшую последовательность таких преобразований и вернуть ее длину. Если преобразование невозможно, вернуть "Преобразование невозможно".

Пример ввода 1:

    D = ["cat", "cot", "dot", "dog", "bat", "dag"]
    s = "cat"
    t = "dog"

Вывод:
Минимальное количество шагов для преобразования 'cat' в 'dog': 3

Пример ввода 2:

    D = ["cat", "cot", "bat"]
    s = "cat"
    t = "dog"

Вывод:
Минимальное количество шагов для преобразования 'cat' в 'dog': Преобразование невозможно

😈 Осторожно — Regex! 3 эпических сбоя, вызванных регулярками

Регулярные выражения — мощный, гибкий и многофункциональный инструмент для обработки текста и валидации данных. С их помощью можно решать сложные задачи буквально одной строкой кода. Однако неправильно составленное регулярное выражение может превратиться в настоящую бомбу замедленного действия, готовую взорваться при определенных входных данных. Последствия могут быть сложноустранимыми, а иногда катастрофическими — как в этих реальных кейсах.

1️⃣ Сбой Stack Overflow

В 2016 году Stack Overflow испытал 34-минутный перебой в работе. Причиной стало регулярное выражение, используемое для обработки пользовательского ввода:

^[\s\u200c]+|[\s\u200c]+$

Это выражение должно было находить пробелы в начале и конце строки. Проблема возникла, когда какой-то пользователь запостил комментарий, содержащий около 20 000 последовательных пробелов. Механизм обработки регулярных выражений начал проверять каждый пробел. Когда после 20 000-го пробела встретился другой символ, движок начал откатываться назад, пытаясь найти соответствие, начиная со второго пробела, третьего и так далее.

Это привело к катастрофическому возврату (catastrophic backtracking) — ошибке, которая возникает, когда движок регулярных выражений тратит чрезмерное количество времени на попытки найти соответствие шаблону, перебирая различные комбинации. Количество проверок начало лавинообразно увеличиваться и быстро достигло 199 990 000 — это вызвало значительную задержку и в итоге сбой системы.

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

2️⃣ Сбой Cloudflare

2 июля 2019 года произошел крупный сбой в работе платформы Cloudflare. Один из инженеров написал регулярное выражение, которое привело к действительно катастрофическому возврату — вызвало экстремальную перегрузку всей инфраструктуры. Использование процессоров выросло до 100%, а большинство сайтов, подключенных к Cloudflare, замедлились до крайности или вовсе оказались недоступными.

Коварная регулярка выглядела так:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

Самую большую опасность в этом выражении представляет .*(?:.*=.*) — группа без захвата, которая может привести к чрезмерному использованию процессора при обработке определенных шаблонов. Эта конструкция вызвала серьезные проблемы с производительностью и в конечном итоге привела к массовому сбою.

3️⃣ Глобальный сбой Windows/CrowdStrike

19 июля 2024 года произошел самый массовый сбой в истории — из строя вышли около 8,5 млн Windows-компьютеров с ПО CrowdStrike. Причиной сбоя стало несоответствие между ожидаемым количеством входных параметров (21) и фактическим количеством параметров (20), которые были переданы в интерпретатор контента (этот компонент отвечает за обработку содержимого с использованием регулярных выражений). Когда система получила ввод с 21 параметром, интерпретатор контента попытался считать данные за пределами выделенной памяти, что и привело к сбою системы.

📨 Материал взят из нашей еженедельной email-рассылки, посвященной бэкенду. Подпишитесь, чтобы быть в числе первых, кто получит дайджест.