Конкурс по программированию на JS: Классификатор слов
Компания Hola объявляет начало весеннего конкурса по программированию! Призовой фонд увеличен:
- Первое место: 3000 USD.
- Второе место: 2000 USD.
- Третье место: 1000 USD.
- Возможно, мы решим отметить чьи-то чрезвычайно оригинальные решения двумя специальными призами в 400 USD.
- Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя).
Мы ищем талантливых программистов, поэтому авторы интересных решений будут приглашены на собеседования.
Правила
На этот раз мы решили попробовать что-то новенькое: для разнообразия, этот конкурс — не на производительность кода.
Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.
- Отправляйте решения с помощью этой формы. По электронной почте решения не принимаются.
- Решения принимаются до 27 мая 2016, 23:59:59 UTC.
- Предварительные результаты будут опубликованы 3 июня 2016, а окончательное объявление победителей — 10 июня 2016.
- Можно отправлять решения многократно, но от каждого участника будет рассмотрено только самое последнее решение, отправленное до окончания срока приёма работ.
- Для тестирования мы будем использовать Node.js v6.0.0 (текущая версия на момент публикации). Можно использовать любые возможности языка, поддерживаемые интерпретатором в стандартной конфигурации.
- Весь код решения должен находиться в единственном файла на JS.
- Решение должно быть на JS. Если Вы предпочитаете CoffeeScript или подобные языки, необходимо оттранслировать решение в JS перед отправкой.
- Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.
- Ваш JS-файл должен быть не больше 64 КиБ.
- Вы можете предоставить один дополнительный файл данных для своей программы (см. ниже). Если Вы предоставляете такой файл, то он делит квоту в 64 КиБ с JS-файлом.
- Если Ваш JS-файл или дополнительный файл данных — продукт генерации, минификации и/или компиляции с других языков вроде CoffeeScript, пожалуйста, приложите архив с исходниками, а также, желательно, описанием подхода. Содержимое этого архива будет опубликовано, но мы не будем его тестировать.
- Нам нужно знать Ваше полное имя, но если Вы хотите, мы опубликуем вместо него псевдоним. Мы сохраним Ваш адрес электронной почты в тайне.
- Запрещается публикация участниками своих решений до окончания конкурса. Нарушители будут дисквалифицированы.
- Задавайте вопросы по условию задачи в комментариях к этой публикации или по электронной почте.
Постановка задачи
Вам нужно написать программу, которая отличает слова английского языка от последовательностей символов, не являющихся словами. В этой задаче мы считаем словами английского языка те и только те строки, которые встречаются в списке words.txt, прилагаемом к условию. Членство в списке регистронезависимое. Казалось бы, это просто — нужно только проверить, встречается ли строка в словаре — если бы не ограничение на размер решения в 64 КиБ.
Едва ли возможно написать программу, которая укладывалась бы в ограничение и всегда давала бы верные ответы. Но этого и не требуется. Мы измерим, как часто Ваша программа будет отвечать правильно, и победит программа, дающая наибольший процент правильных ответов.
API
Ваш JS-файл должен быть модулем для Node.js, экспортирующим две функции:
init(data)
Необязательно. Если функция экспортирована, она будет вызвана один раз для инициализации модуля. В качестве аргумента data будет передано содержимое дополнительного файла данных (в виде Buffer), если Вы его предоставили, или undefined в противном случае.
test(word)
Эта функция должна возвращать true, если она классифицирует word как слово английского языка, и false в противном случае. Эту функцию можно вызывать многократно для различных слов.
Вместе с программой Вы можете предоставить дополнительный файл данных. Если Вы это сделаете, то тестовая система прочитает этот файл в Buffer и передаст Вашей функции init. Файл данных делит квоту в 64 КиБ с JS-файлом, то есть ограничение применяется к сумме размеров этих двух файлов. Вы также можете указать, что Ваш файл данных сжат с помощью gzip. Если Вы отметите соответствующую опцию в форме отправки решения, то содержимое файла данных будет обработано функцией zlib.gunzipSync перед тем, как попасть в функцию init. Этот вариант удобен тем, что Вам не нужно ни внедрять в код на JS двоичные данные, ни писать самостоятельно стандартный алгоритм распаковки. При этом, конечно, ограничение по размеру касается сжатых данных; после распаковки их размер вполне может превысить 64 КиБ.
Тестирование
Мы будем тестировать Вашу программу на большом количестве слов. Некоторые из них будут реальными словами из предоставленного словаря, а некоторые — генерированными не-словами с различной степенью сходства с настоящими словами, от шума вроде dknwertwi до почти-слов вроде sonicative. Мы будем использовать в тестах только ASCII-строки, содержащие латинские буквы нижнего регистра, а также символы ' и -.
В отличие от предыдущих соревнований, Вы можете заранее увидеть наши тесты по адресу hola.org/challenges/word_classifier/testcase. При каждой загрузке Вы получите редирект на адрес, содержащий случайное число. Это число — начальное значение для детерминистического генератора псевдослучайных чисел. С каждым конкретным начальным значением Вы всегда получите один и тот же набор тестов, а, варьируя начальное значение, можете получить множество разных тестов. Генератор возвращает JSON-объект, ключами которого являются 100 различных слов, а значениями — true или false в зависимости от того, встречается ли слово в словаре (хотя последнее Вы легко можете проверить самостоятельно). С помощью генератора тестов Вы можете сами измерить процент правильных ответов, которые даёт Ваша программа, или сравнить разные версии решения между собой. Мы оставляем за собой право ограничивать частоту запросов к генератору тестов.
Наша тестовая система загрузит Ваш модуль один раз. Затем, если модуль экспортирует функцию init, тестовая система её вызовет. Если Вы предоставили дополнительный файл данных, он будет загружен в Buffer, распакован при необходимости, и передан функции init в качестве аргумента data. После этого тестовая система вызовет функцию test много раз для разных слов и подсчитает число правильных ответов. Значения, которые возвращает функция, будут приведены к булевым.
Мы будем генерировать тесты тем же генератором, который описан выше. Мы сгенерируем некоторое количество блоков по 100 слов. Решения всех участников получат одни и те же наборы тестов. Мы возьмём столько блоков по 100 слов, сколько потребуется для того, чтобы с уверенностью различить между результатами тройки призёров. Вместе с результатами конкурса мы опубликуем начальные значения псевдослучайного генератора, которые мы использовали для тестирования, и исходный код генератора тестов.
Отправка решения
Для отправки решений пользуйтесь формой. Мы не принимаем решения по электронной почте.
Мы ожидаем, что многие решения будут содержать генерированный, минифицированый, сжатый код или данные, и поэтому просим отправить нам также и исходники решения. Если код или данные — результат генерации, приложите, пожалуйста, генератор. Если код минифицирован или сжат, включите оригинал, а также программу для сжатия, если это не публичный модуль. Если код скомпилирован из другого языка вроде CoffeeScript, включите оригинал на этом языке. Мы также просим Вас по возможности включить файл README с кратким описанием Вашего подхода к решению (на английском языке). Не включайте, пожалуйста, словарь из условия задачи — он у нас уже есть. Всё это упакуйте, пожалуйста, в tar.gz или zip, и отправьте нам вместе с решением. Размер этого архива не учитывается при проверке ограничения на размер решения в 64 КиБ. Мы опубликуем содержимое Вашего архива, но не будем его тестировать. Оно также поможет нам определить, кого наградить специальными призами за оригинальность.
Если у Вас не получается отправить решение, напишите, пожалуйста, комментарий или письмо.
Желаем удачи всем участникам!
