Розбір пазла з регулярними виразами від Linkedin

Всі ми з дитинства знаємо про кросвордах. Їх різновидів людство напридумывало досить багато. І одна з таких різновидів передбачає використання регулярних виразів, замість питань на ерудицію. Посилання на один з таких кросвордів потрапила мені в руки, і я з ентузіазмом взявся його розгадувати.

кросворд

У цій замітці я б хотів розібрати даний кросворд по пунктах. Стаття може бути корисна тим, хто вже знайомий і використовує у справі регулярні вирази, але відчуває проблеми з нетривіальними завданнями. У будь-якому випадку, я рекомендую спробувати його пройти самостійно, т. к. він не складний. Ну а якщо такі речі, як негативна ретроспективна перевірка, частину вашого робочого арсеналу, то нічого нового ви тут не знайдете.

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

З чого почнемо?
Як і в звичайних кросвордах, найпростіше почати з самого простого вираження. В даному випадку це
R+D
. Очевидно. що 4-ту клітку буде займати символ
D
, а перші три не інакше як три
R
поспіль.
+
після
R
можна описати так:
R
має зустрітися 1 або більше разів.

RRRD

Рядок була позначена зеленим кольором, отже, наше
RRRD
задовольнило регулярному виразу
^R+D$
. Йдемо далі.

[LINKED]*IN
Це регулярний вираз можна стисло описати так: Рядок закінчується на
IN
, а перед цим у ній міститься довільна мішанина з наступного словника:
L
,
I
,
N
,
K
,
E
,
D
. Вбиваємо очевидне
IN
:

IN

Заодно відзначаємо той факт, що
D
R+D
відмінно вписується в цей словник. Одна клітина залишилася незаповненою, до неї ми повернемося пізніше.

[^WORK]*ING?
Звертаємо увагу на те, що рядок повинен закінчитись на
ING
або
IN
. Тобто по суті ми маємо двома варіантами.
?
перед
G
говорить нам про те, що
G
може бути, а може і не існувати. Дивимося в словник з
[LINKED]*IN
, і не знаходимо в ньому символу
G
. Залишається тільки варіант з
IN
:

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
:

RINE

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

C{0}N[NECT]*
Пішла в хід перша хитрість. Дивимося на
{0}
, де замість
0
могли б бути "1", "1,3", "5" та інші варіанти, які регулюють можливе кількість повторень. Але у нас 0. Тобто символу
C
просто немає. Ігноруємо його.

За ним слідує
N
, тому його і вписуємо:

N

.(LN|K|D)*
Метасимвол точка спочатку регулярного виразу говорить нам про те, що на цій позиції може розташовуватися будь-який символ (є нюанси щодо символу переносу рядка, але вони не стосуються даного кросворду). Вже вбитая
R
цілком годиться.

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

L

[^WORK]*ING?
Словник
[^WORK]
починається з символу
^
, тобто він містить у собі список символів, які НЕ повинні зустрітися на даній позиції.
(LN|K|D)
містить два однобуквенных варіанти, це
K
та
D
. Символ
K
ми виключаємо, т. к. він входить у наш словник заперечення. Залишається тільки
D
:

D

Фінішна пряма ([MBERS]*)\1
На цьому регулярному виразі я сів у калюжу. Мені не вистачило знань. Власне саме це і спонукало мене написати цю замітку.

Що ми маємо? У нас є група, яка містить словник
[MBERS]
, який може повторюватися скільки завгодно разів. У першій клітинці ми вже маємо символ
R
, який є в словнику.

Символ
\1
говорить нам про те, що перша група у регулярному виразі повинна продублироваться з цієї позиції без змін. Між групою і
\1
нічого немає, виходить, що наші 4 клітини повинні містити всі собі одну і ту ж дво-буквену групу двічі поспіль. Наприклад:
RRRR
,
SRSR
або
RSRS
.

З чого випливає те, що саме нам відомий перший символ, то стало бути відомий і 3-ий:

RR

Залишився останній штрих. З
C{0}N[NECT]*
ми знаємо, що 4-а комірка повинна вписуватися в словники
[NECT]
та
[MBERS]
. Єдине перетин ― символ
E
. 4-ая осередок знайдено. Отже, знайдена і 2-а, т. е. кросворд вирішено:

success

Linkedin вітає нас:
Congratulations! Only 12% of people who attempt this puzzle solve it
. Вважаю, що 12% взяті зі стелі.

Посилання


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.