Все мы с детства знаем о кроссвордах. Их разновидностей человечество напридумывало довольно много. И одна из таких разновидностей подразумевает использование регулярных выражений, вместо вопросов на эрудицию. Ссылка на один из таких кроссвордов попала мне в руки, и я с энтузиазмом принялся его разгадывать.
![кроссворд](https://habrastorage.org/files/12e/f49/30c/12ef4930c4a54aa9888d38b3e3910a62.png)
В этой заметке я бы хотел разобрать данный кроссворд по пунктам. Статья может быть полезна тем, кто уже знаком и использует в деле регулярные выражения, но испытывает проблемы с нетривиальными задачами. В любом случае, я рекомендую попробовать его пройти самостоятельно, т.к. он не сложный. Ну а если такие вещи, как негативная ретроспективная проверка, часть вашего рабочего арсенала, то ничего нового вы в статье не найдёте.
Обычный кроссворд прямоугольной формы. Описания по бокам являются регулярными выражениями и должны полностью описывать содержимое этих ячеек. Для наглядности авторы опустили символы
Как и в обычных кроссвордах, проще всего начать с самого простого выражения. В данном случае это
![RRRD](https://habrastorage.org/files/b22/548/1ff/b225481ff57a4ee39e1eecce5a7bbc58.png)
Строка была помечена зелёным цветом, следовательно, наше
Сие регулярное выражение можно кратко описать так: Строка заканчивается на
![IN](https://habrastorage.org/files/b45/f90/7d1/b45f907d102748638c6cabad20dc6de9.png)
Заодно отмечаем тот факт, что
Обращаем внимание на то, что строка должна закончиться на
![IN](https://habrastorage.org/files/7dc/2c6/0b7/7dc2c60b712c437dad0eeaa1d84ca148.png)
Пошли примеры посложнее. В данном случае мы располагаем группой
Символ
![RINE](https://habrastorage.org/files/dea/bcb/835/deabcb835e7a4fe2ac8d240b8b2bcf2e.png)
Больше половины паззла уже собрано.
Пошла в ход первая хитрость. Смотрим на
За ним следует
![N](https://habrastorage.org/files/a41/1f2/40d/a411f240db77430682930302294dcf3e.png)
Метасимвол точка вначале регулярного выражения говорит нам о том, что на данной позиции может располагаться любой символ (есть нюансы относительно символа переноса строки, но они не касаются данного кроссворда). Уже вбитая
Далее мы видим группу
![L](https://habrastorage.org/files/fe0/e0e/c2d/fe0e0ec2dcbf48cd8fc94f474c0913f5.png)
Словарь
![D](https://habrastorage.org/files/791/d09/c6f/791d09c6fa2740e8b0a164487fec66e0.png)
На этом регулярном выражении я сел в лужу. Мне не хватило познаний. Собственно именно это и побудило меня написать сию заметку.
Что мы имеем? У нас есть группа, содержащая словарь
Символ
Из чего следует то, что раз нам известен первый символ, то стало быть известен и 3-ий:
![RR](https://habrastorage.org/files/b77/b3f/66c/b77b3f66cd5642a6ad7520a5e8e88d7e.png)
Остался последний штрих. Из
![success](https://habrastorage.org/files/2ea/85a/003/2ea85a00345e401aaf37df0404b1b19b.png)
Linkedin поздравляет нас:
![кроссворд](https://habrastorage.org/files/12e/f49/30c/12ef4930c4a54aa9888d38b3e3910a62.png)
В этой заметке я бы хотел разобрать данный кроссворд по пунктам. Статья может быть полезна тем, кто уже знаком и использует в деле регулярные выражения, но испытывает проблемы с нетривиальными задачами. В любом случае, я рекомендую попробовать его пройти самостоятельно, т.к. он не сложный. Ну а если такие вещи, как негативная ретроспективная проверка, часть вашего рабочего арсенала, то ничего нового вы в статье не найдёте.
Что сие есть?
Обычный кроссворд прямоугольной формы. Описания по бокам являются регулярными выражениями и должны полностью описывать содержимое этих ячеек. Для наглядности авторы опустили символы
^
и $
. Т.е. R+D
необходимо понимать как ^R+D$
. Символ ^
обозначает начало строки, а $
её конец, таким образом, выражение описывает содержимое всех 4 ячеек (строки или колонки) целиком.С чего начнём?
Как и в обычных кроссвордах, проще всего начать с самого простого выражения. В данном случае это
R+D
. Очевидно. что 4-ую клетку будет занимать символ D
, а первые три не иначе как три R
подряд. +
после R
можно описать так: R
должно встретиться 1 или более раз. ![RRRD](https://habrastorage.org/files/b22/548/1ff/b225481ff57a4ee39e1eecce5a7bbc58.png)
Строка была помечена зелёным цветом, следовательно, наше
RRRD
удовлетворило регулярному выражению ^R+D$
. Идём дальше.[LINKED]*IN
Сие регулярное выражение можно кратко описать так: Строка заканчивается на
IN
, а перед этим в ней содержится произвольная мешанина из следующего словаря: L
, I
, N
, K
, E
, D
. Вбиваем очевидное IN
:![IN](https://habrastorage.org/files/b45/f90/7d1/b45f907d102748638c6cabad20dc6de9.png)
Заодно отмечаем тот факт, что
D
из R+D
отлично вписывается в этот словарь. Одна клетка осталась незаполненной, к ней мы вернёмся позже.[^WORK]*ING?
Обращаем внимание на то, что строка должна закончиться на
ING
или же IN
. Т.е. по сути мы располагаем двумя вариантами. ?
перед G
говорит нам о том, что G
может быть, а может и отсутствовать. Смотрим в словарь из [LINKED]*IN
, и не находим в нём символа G
. Остаётся только вариант с IN
:![IN](https://habrastorage.org/files/7dc/2c6/0b7/7dc2c60b712c437dad0eeaa1d84ca148.png)
(ENG|INE|E|R)*
Пошли примеры посложнее. В данном случае мы располагаем группой
(ENG|INE|E|R)
, которая может встретиться сколько угодно раз (см. символ *
). Группа предлагает нам ряд вариантов: ENG
, INE
, E
и R
. Т.е. конечной строкой могли бы быть EEEE
, ERER
, ENGE
, RINE
и т.д. Символ
R
из R+D
у нас уже вписан, в группе он также наличествует. Во второй ячейке у нас уже вписан символ I
, и он присутствует в начале INE
. Следовательно, строка примет вид R
+ INE
= RINE
:![RINE](https://habrastorage.org/files/dea/bcb/835/deabcb835e7a4fe2ac8d240b8b2bcf2e.png)
Больше половины паззла уже собрано.
C{0}N[NECT]*
Пошла в ход первая хитрость. Смотрим на
{0}
, где вместо 0
могли бы быть "1", "1,3", "5" и другие варианты, регулирующие возможное кол-во повторений. Но у нас 0. Т.е. символа C
просто нет. Игнорируем его. За ним следует
N
, посему его и вписываем:![N](https://habrastorage.org/files/a41/1f2/40d/a411f240db77430682930302294dcf3e.png)
.(LN|K|D)*
Метасимвол точка вначале регулярного выражения говорит нам о том, что на данной позиции может располагаться любой символ (есть нюансы относительно символа переноса строки, но они не касаются данного кроссворда). Уже вбитая
R
вполне годится.Далее мы видим группу
(LN|K|D)
, которая может повторяться сколько угодно раз. Примечательное в ней то, что только LN
из неё подходит к нашей 4-ой ячейке. А это в свою очередь позволяет нам смело вписать L
:![L](https://habrastorage.org/files/fe0/e0e/c2d/fe0e0ec2dcbf48cd8fc94f474c0913f5.png)
[^WORK]*ING?
Словарь
[^WORK]
начинается с символа ^
, т.е. он содержит в себе список символов, которые НЕ должны встретиться на данной позиции. (LN|K|D)
содержит два однобуквенных варианта, это K
и D
. Символ K
мы исключаем, т.к. он входит в наш словарь отрицания. Остаётся только D
:![D](https://habrastorage.org/files/791/d09/c6f/791d09c6fa2740e8b0a164487fec66e0.png)
Финишная прямая ([MBERS]*)\1
На этом регулярном выражении я сел в лужу. Мне не хватило познаний. Собственно именно это и побудило меня написать сию заметку.
Что мы имеем? У нас есть группа, содержащая словарь
[MBERS]
, который может повторяться сколь угодно раз. В первой ячейке мы уже имеем символ R
, который есть в словаре. Символ
\1
говорит нам о том, что первая группа в регулярном выражении должна продублироваться по этой позиции без изменений. Между группой и \1
ничего нет, получается, что наши 4 клетки должны содержать все себе одну и ту же дву-буквенную группу дважды подряд. К примеру: RRRR
, SRSR
или RSRS
.Из чего следует то, что раз нам известен первый символ, то стало быть известен и 3-ий:
![RR](https://habrastorage.org/files/b77/b3f/66c/b77b3f66cd5642a6ad7520a5e8e88d7e.png)
Остался последний штрих. Из
C{0}N[NECT]*
мы знаем, что 4-ая ячейка должна вписываться в словари [NECT]
и [MBERS]
. Единственное пересечение ? символ E
. 4-ая ячейка найдена. Следовательно, найдена и 2-ая, т.е. кроссворд решён: ![success](https://habrastorage.org/files/2ea/85a/003/2ea85a00345e401aaf37df0404b1b19b.png)
Linkedin поздравляет нас:
Congratulations! Only 12% of people who attempt this puzzle solve it
. Полагаю, что 12% взяты с потолка.Ссылки
Комментарии (4)
JIghtuse
14.03.2016 19:22+5Спасибо, немного размял мозги. Вспомнился более сложный кроссворд, который некоторое время назад был популярен. Его решал подольше.
https://gregable.com/p/regexp-puzzle.html
Agaspher20
15.03.2016 15:34Было бы лучше конечно ссылку на пазл дать в начале. А тем кто сам не решил уже объяснять.
CAJAX
Для тех, кому одного кроссворда мало, есть https://regexcrossword.com