Все мы с детства знаем о кроссвордах. Их разновидностей человечество напридумывало довольно много. И одна из таких разновидностей подразумевает использование регулярных выражений, вместо вопросов на эрудицию. Ссылка на один из таких кроссвордов попала мне в руки, и я с энтузиазмом принялся его разгадывать.



В этой заметке я бы хотел разобрать данный кроссворд по пунктам. Статья может быть полезна тем, кто уже знаком и использует в деле регулярные выражения, но испытывает проблемы с нетривиальными задачами. В любом случае, я рекомендую попробовать его пройти самостоятельно, т.к. он не сложный. Ну а если такие вещи, как негативная ретроспективная проверка, часть вашего рабочего арсенала, то ничего нового вы в статье не найдёте.

Что сие есть?

Обычный кроссворд прямоугольной формы. Описания по бокам являются регулярными выражениями и должны полностью описывать содержимое этих ячеек. Для наглядности авторы опустили символы ^ и $. Т.е. R+D необходимо понимать как ^R+D$. Символ ^ обозначает начало строки, а $ её конец, таким образом, выражение описывает содержимое всех 4 ячеек (строки или колонки) целиком.

С чего начнём?

Как и в обычных кроссвордах, проще всего начать с самого простого выражения. В данном случае это R+D. Очевидно. что 4-ую клетку будет занимать символ D, а первые три не иначе как три R подряд. + после R можно описать так: R должно встретиться 1 или более раз.



Строка была помечена зелёным цветом, следовательно, наше RRRD удовлетворило регулярному выражению ^R+D$. Идём дальше.

[LINKED]*IN

Сие регулярное выражение можно кратко описать так: Строка заканчивается на IN, а перед этим в ней содержится произвольная мешанина из следующего словаря: L, I, N, K, E, D. Вбиваем очевидное IN:



Заодно отмечаем тот факт, что D из R+D отлично вписывается в этот словарь. Одна клетка осталась незаполненной, к ней мы вернёмся позже.

[^WORK]*ING?

Обращаем внимание на то, что строка должна закончиться на ING или же IN. Т.е. по сути мы располагаем двумя вариантами. ? перед G говорит нам о том, что G может быть, а может и отсутствовать. Смотрим в словарь из [LINKED]*IN, и не находим в нём символа G. Остаётся только вариант с IN:

(ENG|INE|E|R)*

Пошли примеры посложнее. В данном случае мы располагаем группой (ENG|INE|E|R), которая может встретиться сколько угодно раз (см. символ *). Группа предлагает нам ряд вариантов: ENG, INE, E и R. Т.е. конечной строкой могли бы быть EEEE, ERER, ENGE, RINE и т.д.

Символ R из R+D у нас уже вписан, в группе он также наличествует. Во второй ячейке у нас уже вписан символ I, и он присутствует в начале INE. Следовательно, строка примет вид R + INE = RINE:



Больше половины паззла уже собрано.

C{0}N[NECT]*

Пошла в ход первая хитрость. Смотрим на {0}, где вместо 0 могли бы быть "1", "1,3", "5" и другие варианты, регулирующие возможное кол-во повторений. Но у нас 0. Т.е. символа C просто нет. Игнорируем его.

За ним следует N, посему его и вписываем:

.(LN|K|D)*

Метасимвол точка вначале регулярного выражения говорит нам о том, что на данной позиции может располагаться любой символ (есть нюансы относительно символа переноса строки, но они не касаются данного кроссворда). Уже вбитая R вполне годится.

Далее мы видим группу (LN|K|D), которая может повторяться сколько угодно раз. Примечательное в ней то, что только LN из неё подходит к нашей 4-ой ячейке. А это в свою очередь позволяет нам смело вписать L:

[^WORK]*ING?

Словарь [^WORK] начинается с символа ^, т.е. он содержит в себе список символов, которые НЕ должны встретиться на данной позиции. (LN|K|D) содержит два однобуквенных варианта, это K и D. Символ K мы исключаем, т.к. он входит в наш словарь отрицания. Остаётся только D:

Финишная прямая ([MBERS]*)\1

На этом регулярном выражении я сел в лужу. Мне не хватило познаний. Собственно именно это и побудило меня написать сию заметку.

Что мы имеем? У нас есть группа, содержащая словарь [MBERS], который может повторяться сколь угодно раз. В первой ячейке мы уже имеем символ R, который есть в словаре.

Символ \1 говорит нам о том, что первая группа в регулярном выражении должна продублироваться по этой позиции без изменений. Между группой и \1 ничего нет, получается, что наши 4 клетки должны содержать все себе одну и ту же дву-буквенную группу дважды подряд. К примеру: RRRR, SRSR или RSRS.

Из чего следует то, что раз нам известен первый символ, то стало быть известен и 3-ий:



Остался последний штрих. Из C{0}N[NECT]* мы знаем, что 4-ая ячейка должна вписываться в словари [NECT] и [MBERS]. Единственное пересечение ? символ E. 4-ая ячейка найдена. Следовательно, найдена и 2-ая, т.е. кроссворд решён:



Linkedin поздравляет нас: Congratulations! Only 12% of people who attempt this puzzle solve it. Полагаю, что 12% взяты с потолка.

Ссылки

• Википедия
• Пазл
• Сайт посвящённый таким кроссвордам (#комментарий от CAJAX)