Конкурс з програмування на PHP: Класифікатор слів

Компанія Hola оголошує початок весняного конкурсу з програмування! Призовий фонд збільшено:

  1. Перше місце: 3000 USD.
  2. Друге місце: 2000 USD.
  3. Третє місце: 1000 USD.
  4. Можливо, ми вирішимо відзначити чиїсь надзвичайно оригінальні рішення двома спеціальними призами в 400 USD.
  5. Якщо Ви відправите комусь посилання на цей конкурс, поставивши наша адреса 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 Кіб з BAT-файлом, тобто обмеження застосовується до суми розмірів цих двох файлів. Ви також можете вказати, що Ваш файл даних стиснутий за допомогою 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 Кіб. Ми опублікуємо вміст Вашого архіву, але не будемо його тестувати. Воно також допоможе нам визначити, кого нагородити спеціальними призами за оригінальність.

Якщо у Вас не виходить відправити рішення, напишіть, будь ласка, коментар або лист.

Бажаємо удачі всім учасникам!

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

0 коментарів

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