Все мы с детства знаем о кроссвордах. Их разновидностей человечество напридумывало довольно много. И одна из таких разновидностей подразумевает использование регулярных выражений, вместо вопросов на эрудицию. Ссылка на один из таких кроссвордов попала мне в руки, и я с энтузиазмом принялся его разгадывать.
В этой заметке я бы хотел разобрать данный кроссворд по пунктам. Статья может быть полезна тем, кто уже знаком и использует в деле регулярные выражения, но испытывает проблемы с нетривиальными задачами. В любом случае, я рекомендую попробовать его пройти самостоятельно, т.к. он не сложный. Ну а если такие вещи, как негативная ретроспективная проверка, часть вашего рабочего арсенала, то ничего нового вы в статье не найдёте.
Что сие есть?
Обычный кроссворд прямоугольной формы. Описания по бокам являются регулярными выражениями и должны полностью описывать содержимое этих ячеек. Для наглядности авторы опустили символы ^
и $
. Т.е. 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% взяты с потолка.
Ссылки
ссылка на оригинал статьи https://habrahabr.ru/post/279199/
Добавить комментарий