Конкурс по программированию на JS: Почтовые фильтры13.11.2015 20:33

Компания Hola снова объявляет конкурс по программированию на JS с солидным призовым фондом:

Первое место: 1500 USD
Второе место: 1000 USD
Третье место: 500 USD
Возможно, мы решим отметить чьё-то чрезвычайно оригинальное решение специальным призом в 350 USD.
Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите такую же сумму, как и он.

Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.

Правила

Некоторые из тех, кто помнит наши предыдущие конкурсы, были недовольны тем, что условия задач были сформулированы нечётко, и от участника требовалось «угадать», что мы имели в виду. На этот раз условие сформулировано предельно однозначно, а в распоряжении участников — эталонная реализация решения. Победит тот, чей код будет самым быстрым при условии прохождения тестов на корректность.

Условия конкурса на английском языке размещены на нашем сайте. Ниже — перевод на русский язык.

Отправляйте решения на challengejs@hola.org.
Решения принимаются до 25 декабря 2015, 23:59:59 UTC.
Победители будут объявлены 8 января 2015.
Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
Для тестирования мы будем использовать Node.js v5.0.0 (стабильная версия на момент публикации).
Ваше решение должно состоять из единственного файла на JS.
Решение должно быть на чистом JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой. Мы приветствуем (но не требуем) отправку оригинала вместе с результатом трансляции (но не вместо).
Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
Мы будем тестировать решения на корректность и производительность. Только решения, прошедшие тестирование на корректность, будут допущены к тестированию на производительность. Победит самое быстрое из корректных решений.
Все работы участников, а также наши тесты на корректность и производительность, будут опубликованы при подведении итогов.
Подводя итоги, мы опубликуем Ваше полное имя (или псевдоним, если Вы подпишетесь им), но не адрес электронной почты.
Запрещается публикация участниками своих решений до окончания конкурса. Нарушители будут дисквалифицированы.
Если условие задачи кажется Вам неоднозначным, проверьте своё понимание условия с помощью нашей эталонной реализации (см. ниже), вместо того, чтобы задавать вопросы по условию. Если Вы обнаружите, что поведение эталонной реализации противоречит условию, пожалуйста, сообщите нам.

Постановка задачи

Вы разрабатываете систему применения фильтров для почтовой системы. Вам нужно написать модуль для Node.js, экспортирующий одну функцию:

filter(messages, rules)

messages — это объект, ставящий в соответствие уникальным идентификаторам сообщений объекты с двумя свойствами: from и to. Каждый такой объект описывает одно электронное письмо.
rules — это массив объектов с тремя свойствами: from (необязательно), to (необязательно) и action (обязательно). Каждый из этих объектов описывает одно правило фильтрования.

Все строковые значения во входных данных непустые и содержат только символы ASCII в диапазоне от 0x20 до 0x7F включительно.

Считается, что письмо удовлетворяет правилу фильтрования, если оба его свойства from и to удовлетворяют маскам, заданным в соответствующих свойствах правила. Маски регистрозависимые; символу * в маске удовлетворяет любое число (0 или более) любых символов, а символу ? — один любой символ. Если свойства from или to отсутствуют в правиле фильтрования, то в качестве значения по умолчанию используется *. Как следствие, если в правиле отсутствуют оба свойства from и to, то ему удовлетворяют все письма.

К каждому письму необходимо применить все правила, которым оно удовлетворяет, в правильном порядке. Функция filter должна вернуть объект, ставящий в соответствие идентификаторам сообщений массивы действий. Для каждого письма такой массив должен содержать значения свойств action всех правил, которым это письмо удовлетворяет, в порядке перечисления правил в массиве rules. Если письмо не удовлетворяет ни одному из правил, пустой массив для этого письма всё равно должен присутствовать в результате.

Пример

Ниже приведён типичный пример корректного вызова функции filter:

filter({
    msg1: {from: 'jack@example.com', to: 'jill@example.org'},
    msg2: {from: 'noreply@spam.com', to: 'jill@example.org'},
    msg3: {from: 'boss@work.com', to: 'jack@example.com'}
}, [
    {from: '*@work.com', action: 'tag work'},
    {from: '*@spam.com', action: 'tag spam'},
    {from: 'jack@example.com', to: 'jill@example.org', action: 'folder jack'},
    {to: 'jill@example.org', action: 'forward to jill@elsewhere.com'}
])

Правильная реализация filter в этом случае вернёт следующее:

{
    msg1: ['folder jack', 'forward to jill@elsewhere.com'],
    msg2: ['tag spam', 'forward to jill@elsewhere.com'],
    msg3: ['tag work']
}

Эталонная реализация

Мы подготовили эталонную реализацию функции filter по адресу http://hola.org/challenge_mail_filter/reference. Для заданных значений аргументов она выдаёт корректный результат. Эта реализация также строго проверяет корректность входных значений (от Вашего решения проверки входных данных не требуется). В спорных случаях вместо того, чтобы задавать нам вопросы по условию задачи, пользуйтесь эталонной реализацией. Если Вы подозреваете, что эталонная реализация выдаёт неверный ответ для тех или иных входных данных, пожалуйста, сообщите нам.

Чтобы не допустить перегрузки нашего сервера, мы ограничили объёмы входных данных 10 правилами и 10 письмами. Ваше решение не должно иметь таких ограничений.

К эталонной реализации по упомянутому выше адресу можно делать HTTP-запросы методом POST с телом запроса типа application/json. Тело должно представлять собой объект с двумя свойствами: messages и rules, — содержащими значения соответствующих аргументов функции filter. Тело ответа, также в формате JSON, будет содержать значение, которое функция должна вернуть. При недопустимых входных данных Вы получите ответ HTTP 400 с описанием ошибки в формате text/plain.

Желаем удачи всем участникам!