Вы не сможете решить эту задачу на собеседовании

Привет, Habr. Хочу поделиться с вами одной интересной задачей, которую многие из нас получали на собеседовании, но, вероятно, даже и не догадывались о том, что решаем ее неправильно.

Прежде всего — немного истории. Работая на должностях тимлида и техлида мне порой приходилось проводить собеседования, соответственно нужно подготовить несколько теоретических вопросов, ну и пару несложных задач, на решение которых не должно было бы уйти больше 2х-3х минут. Если с теорией все просто — мой любимый вопрос это: «чему равен typeof null?», по ответу сразу можно понять, кто сидит перед тобой, джун — просто правильно ответит, а претендент на сеньера, еще и объяснит почему. То с практикой — сложнее. Я долго не мог придумать нормальное задание, не изъезженное, типа fizz-buzz, а что-нибудь свое. Поэтому я на собеседованиях давал задания, которые сам проходил, устраиваясь на текущую работу. О первом из них и пойдет речь.

Текст задачи
Напишите функцию, которая принимает на вход строку, а возвращает эту строку «задом наперед»
function strReverse(str) {};
strReverse(‘Habr’) === ‘rbaH’; // true

Очень простая задача, решений для которой масса, самым оптимальным для себя я долго считал такое решение:

const strReverse = str => str.split(»).reverse().join(»);
Но что-то меня в этом решении смущало всегда, а именно ненадежность «split(»)». И вот после одного из собеседований, я задумался: «Что же такое я могу передать в строке, что сломает мой способ…?». Ответ пришел очень быстро.

О, да, вы уже могли понять о чем я, emoji! Эти чертовы смайлики, их придумал сам дьявол, вы только посмотрите, во что превращается палец вверх, если его перевернуть (нет, не в палец вниз).
Сразу хочу извиниться, редактор разметки убирает emoji из кода, поэтому вставляю картинки.

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

Огонь, работает, супер, но… Подождите ка, с недавних пор мы можем указать цвет для смайла, и что же будет, если мы передадим такой emoji в функцию?
Это фиаско, братан!

Вот тут то я и сел в лужу. Если честно, я пару раз предлагал еще на собеседованиях решить эту задачу, в основном, надеясь что мне предложат то решение, которое сможет это сделать — нет, претенденты разводили руками и не могли мне ничем помочь.
Помог случай, ну или спортивный интерес. Со словами «Хочешь задачку со специальной олимпиады?» я отправил ее моему бывшему коллеге. «Ок, к вечеру попробую сделать» — последовал ответ, и я напрягся… «А что если сделает? А что если реально сможет? Он сможет, а я — нет? Так дела не пойдут!» — так подумал я и начал шерстить интернет. Тут я перейду к теоретической части, которая некоторым из вас может показаться интересной и полезной, а некоторым — повторением пройденного материала.

Что нам нужно знать о Emoji?
Во первых, это — стандарт! Стандарт, который хорошо описан.

Решающим моментом в жизни emoji можно считать день принятия стандарта unicode 8.0 и стандарта emoji 2.0 в нем, тогда и были описаны первые последовательности юникода и последовательности emoji.

Давайте вот тут остановимся чуть подольше и разберем вопрос подробнее.

Согласно первой версии стандарта emoji является представлением одного символа юникода

И так далее

Вторая версия стандарта позволяет нам взять несколько симовлов юникода в определенной последовательности, чтобы получить emoji

Полный список

Это и есть простые последовательности в emoji, но простые они только потому что есть еще и zwj — последовательности.
ZERO WIDTH JOINER (ZWJ) — соединитель с нулевой шириной, это та ситуация, когда между несколькими emoji вставляется специальный символ юникода ZWJ (200D), который «схлопывает» emoji по обе стороны от него и вот что мы получаем в итоге:

Полный список

В последующих стандартах эти последовательности только дополнялись, так что количество комбинаций emoji только росло со временем.

Что ж, с мат частью разобрались, но что же нам делать, чтобы перевернуть строку и при этом сохранить последовательность?

Регулярные выражения.
Если у вас есть проблема и вы захотели решить ее с помощью регулярных выражений, то теперь у вас две проблемы.Углубляясь в изучение стандарта юникода находим отдельный раздел о последовательностях emoji, в котором говорится о том, как должны быть реализованы последовательности, и все оказывается достаточно просто.

Последовательность может быть составлена по следующей формуле
emoji_sequence :=
emoji_core_sequence
| emoji_zwj_sequence
| emoji_tag_sequence

# по пунктам

emoji_core_sequence :=
emoji_character
| emoji_presentation_sequence
| emoji_keycap_sequence
| emoji_modifier_sequence
| emoji_flag_sequence

emoji_presentation_sequence :=
emoji_character emoji_presentation_selector
emoji_presentation_selector := x{FE0F}

emoji_keycap_sequence := [0-9#*] x{FE0F 20E3}

emoji_modifier_sequence :=
emoji_modifier_base emoji_modifier

emoji_modifier_base := p{Emoji_Modifier_Base}
emoji_modifier := p{Emoji_Modifier}
# к этому вернемся чуть позже

emoji_flag_sequence :=
regional_indicator regional_indicator

regional_indicator := p{Regional_Indicator}

emoji_zwj_sequence :=
emoji_zwj_element ( ZWJ emoji_zwj_element )+

emoji_zwj_element :=
emoji_character
| emoji_presentation_sequence
| emoji_modifier_sequence

emoji_tag_sequence :=
tag_base tag_spec tag_term

tag_base :=
emoji_character
| emoji_modifier_sequence
| emoji_presentation_sequence
tag_spec := [x{E0020}-x{E007E}]+
tag_term := x{E007F}

В принципе, этого уже достаточно, чтобы грамотно(нет) составить регулярное выражение, но еще немного слов про юникод.

Unicode Categories
В юникоде определены категории, используя которые мы можем в регулярных выражениях находить, например, все заглавные буквы, или, например, все буквы латинского алфавита. Более подробно со списком можно ознакомиться здесь. Что важно для нас: в стандарте определены категории для emoji: {Emoji}, {Emoji_Presentation}, {Emoji_Modifier}, {Emoji_Modifier_Base}, и казалось бы, все хорошо, давайте использовать, но в реализацию ECMAScript они еще не вошли. Точнее — вошла только одна категория — {Emoji}

Остальные на данный момент находятся на рассмотрении в tc-39 (stage-2 на момент 10.04.2019).

«Что ж, придется писать регулярку» — подумал и примерно через час мой бывший коллега кидает мне ссылку на гитхаб github.com/mathiasbynens/emoji-regex, ну да, на гитхабе всегда найдется то, что ты только собирался написать… А жаль, но речь не об этом… Библиотека реализует и импортирует регулярное выражение для поиска эмоджи, в принципе то что надо! Наконец то можно попробовать написать реализацию нужной нам функции!

const emojiRegex = require(’emoji-regex’);
const regex = emojiRegex();
function stringReverse(string) {

let match;
const emojis = [];
const separator = `unique_separator_${Math.random()}`;
const reversedSeparator = […separator].reverse().join(»);

while (match = regex.exec(string)) {
const emoji = match[0];
emojis.push(emoji);
}

return […string.replace(regex, separator)].reverse().join(»).replace(new RegExp(reversedSeparator, ‘gm’), () => emojis.pop());

}

Подводя небольшой итог
Я обожаю задачи со «специальной» олимпиады, они заставляют меня узнавать что-то новое, каждый раз расширяя границы знаний. Я не понимаю людей, которые говорят: «Я не понимаю, зачем нужно знать, что null >= 0? Мне это не пригодится!». Пригодится, 100% пригодится, в тот момент, когда ты будешь выяснять причину того-или иного явления — ты прокачаешь себя, как программиста и станешь лучше. Не лучше кого-то, а лучше себя, который еще пару часов назад не знал, как решить какую-то задачу.

Спасибо за прочтение, всем спасибо, буду рад любым комментариям.

Необходимый постскриптум:

Все сломала буква u{0415}u{0308}. Это буква ё, состоящая из 2х символов, оказывается в стандарте юникода есть вариант объединения не только emoji, но и просто символов… Но это — совсем другая история.

UPD: Речь идет не о букве «Ё», а о сочетании 2х символов Юникода u{0415}(Е) и u{0308}(«̈), которые идя друг за другом образуют последовательность юникода и мы видим букву «Ё» на экране.

Оставить комментарий