Конкурс по программированию на JS: Классификатор слов

    Компания 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 КиБ.

    Едва ли возможно написать программу, которая укладывалась бы в ограничение и всегда давала бы верные ответы. Но 100% правильных ответов и не требуется. Мы измерим, как часто Ваша программа будет отвечать правильно, и победит программа, дающая наибольший процент правильных ответов.

    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 КиБ. Мы опубликуем содержимое Вашего архива, но не будем его тестировать. Оно также поможет нам определить, кого наградить специальными призами за оригинальность.

    Если у Вас не получается отправить решение, напишите, пожалуйста, комментарий или письмо.

    Желаем удачи всем участникам!
    Hola
    47,00
    Компания
    Поделиться публикацией

    Комментарии 620

      –2
      В чём сложность конкурса скачать файл и найти в нём слово?
        +3
        Ваша программа не может ничего скачать, поскольку правилами запрещена загрузка любых модулей, с помощью которых это можно было бы сделать.
          +7
          Если программа без require сможет скачать файл, то автор будет вполне достоин спецприза :)
            –5
            Для программы — фигня вопрос(решение по конкурсу не проходит, т.к. нельзя вмешиваться в тестовую систему). Для модуля — пока не придумал.

            node index.js <words.txt для локального файла

            что-нибудь в духе

            lynx -dump https://github.com/hola/challenge_word_classifier/raw/master/words.txt>words.txt
            node index.js <words.txt

            для удаленного файла.

            Считывание:
            var stdin = process.openStdin();
            var result=[];
            var t="";
            var word=«aaa»;

            stdin.addListener(«data», function(d) {
            t+=d.toString();
            });
            stdin.addListener(«end», function(d) {
            result=t.split('\n');
            var a=result.findIndex((x)=>x.toLowerCase()===word)===-1;
            console.log('Result: ', a);
            });

            –2
            Ок, а где брать словарь? Реализовывать http (ну хоть сокеты доступны)?
              +2
              Нет, сокеты недоступны.
                +3
                Сокеты без require тоже недоступны. Надо угадывать, похоже слово на английское или нет.
                  –4
                  написано, что модули нельзя загружать, но не написано, что нельзя загружать словарь по урлу, если я правильно понял. — верно?
                    +5
                    чтоб загрузить словарь нужен модуль http ну или tcp.
            +4
            Вы статью читали?

            > Казалось бы, это просто — нужно только проверить, встречается ли строка в словаре — если бы не ограничение на размер решения в 64 КиБ.

            Файл размером 6+ МБ. С собой тащить все данные не получится.

            > Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js.

            Загрузить их откуда-то тоже не получится (ну а как это сделать без модуля http?), да и это явно противоречит духу правил.
              –9
              написано, что модули нельзя загружать, но не написано, что нельзя загружать словарь по урлу, если я правильно понял.
                +1
                А как Вы загрузите словарь по урлу?
                  –6
                  Всё очень зависит от накладываемых ограничений и ОС.
                    +1
                    Покажите пример хотя бы для какой-нибудь одной ОС.
                      –7
                      Не хочу, чтобы это наталкивало на какие-то мысли :)
                        +6
                        Мы всё равно дисквалифицируем всех, кто придумает, как обмануть тестовую систему.
                          +1
                          А может лучше за это премию дать?
                            +7
                            Одно другому не мешает. Мы вполне можем дать премию за оригинальный подход, и при этом дисквалифицировать из основного зачёта.
                  +1
                  Как ни странно, соглашусь. Вроде как, это очевидно по «духу» правил, но явно не упомянуто.
                  feldgendler, я думаю, стоит в явном виде написать, что нельзя работать с сетью и файловой системой (если вы почитаете правила ACM и подобных соревнований — там это явно написано).
                    0
                    В ICPC нет запрета на использование стандартных библиотек.
                      0
                      Да, но тут вопрос в том, что считать стандартной библиотекой js.
                      Можно ли считать модули, входящие в поставку node стандартной библиотекой JS (не node)? В браузере то их нет :)
                      Так что вопрос неочевидный…
                        +3
                        «Нельзя загружать никаких модулей, даже тех, что входят в стандартный комплект Node.js».
                0
                И ещё хотел спросить, на какой ОС (семействе ОС) будет тестирование?
                  0
                  Ubuntu. Но в отличие от предыдущего конкурса, здесь это не имеет значения, так как нас не интересует оптимизация по производительности. Не могу придумать, как операционная система могла бы повлиять на подход к решению этой задачи.
                    –3
                    Раз нельзя загружать стандартные модули, то значит можно пользоваться тем, что уже загружено в глобальном пространстве. Из этого можно что-то состряпать.
                      +2
                      Желаю удачи. Как сказал выше dottedmag, успешное решение такого типа тянет на специальный приз. Имейте в виду, что обходной способ загрузить какой-либо модуль без использования require запрещён так же, как и require.

                      Задача, тем не менее, не об этом.
                        +1
                        Да отрубите тестовую машину от интернета, да и делов.
                          0
                          Я не собираюсь загружать node модули.
                    0
                    Ну как отфильтровать действительно случайные последовательности — более-менее понятно.
                    А вот как бороться с «почти словами» с 1-2 опечатками — пока даже идей никаких нет.
                      +1
                      Сходство слов с английскими варьируется по плавной шкале. Ваше решение может успешно отсеивать совершенный шум, менее успешно слова с невысокой степенью подобия, совсем плохо — слова с высокой степенью подобия. Чем точнее распознаватель, тем больше шансов на победу.
                      +1
                      А будет только победитель или можно будет посмотреть на каком месте моё решение?
                        +3
                        Будет таблица результатов для всех участников.
                        +3
                        1. Я правильно понимаю, что задача сводится к написанию алгоритма который сможет ответить есть ли данная последовательность символов в предоставленном словаре, без учета регистра, пробелов или спец символов, т.е. только [a-zA-Z\-]?

                        2. Я правильно понимаю, Что даже если слово правильное и английское, но его нету в словаре который предоставили — оно считать, что слово не английское?
                          0
                          Да и да.

                          В test будут подаваться только слова вида [a-zA-Z'-]+, не нужно отфильтровывать пробелы и спецсимволы.
                            +1
                            Спасибо вам за: https://simple.wikipedia.org/wiki/Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch

                            3. Т.е. я правильно понимаю то что регистр слов не важен?
                            4. Там есть все буквы английского словаря как слова с одной буквой. Это тоже считаем что это слово? Например «Z»?
                              +1
                              Ответы на это написаны в условии.
                                –2
                                Т.е. я правильно понимаю что ответы да и да?
                            0
                            Зачем подавать в тестах слова с дефисом, если в словаре нет ни одного слова с дефисом?
                              +2
                              Это была ошибка в условии, исправлено. Дефисов не будет.
                          +14
                          … дающая наибольший процент правильных ответов.

                          а вдруг повезет
                          function main(){
                            return Math.random() > 0.5
                          }
                          
                          module.exports = {
                            init: function(data){
                              // м-м-м бинарничек
                              console.log('бдыщь')
                            },
                            test: main
                          }
                          
                          

                          не, ну а че б и нет? :)
                            +2
                            50% — это baseline, да.
                              0
                              почти

                              Math.random
                              var n = 1000000;
                              new Array(n).join('1').split('').reduce(function(memo){
                                memo += new Array(100).join('1').split('').map(function(){ return Math.random() > 0.5;}).filter(function(item){ return item;}).length / 100;
                                return memo;
                              }, 0) / n;
                              // 0.4949049399999358
                              



                              вот только не понял почему map по undefined не отрабатывает:
                              (new Array(10).join('1').split('')).map(function(){ return true})
                              // [true, true, true, true, true, true, true, true, true]
                              
                              (new Array(10)).map(function(){ return true})
                              // [undefined × 10]
                              
                                +1
                                потому что
                                map calls a provided callback function once for each element in an array, in order, and constructs a new array from the results. callback is invoked only for indexes of the array which have assigned values; it is not invoked for indexes which have been deleted or which have never been assigned values.
                                © mdc
                                  0
                                  да спасибо уже нашел
                                  callbackfn should be a function that accepts three arguments. map calls callbackfn once for each element in the array, in ascending order, and constructs a new Array from the results. callbackfn is called only for elements of the array which actually exist; it is not called for missing elements of the array.

                                  http://www.ecma-international.org/ecma-262/6.0/index.html#sec-array.prototype.map
                                  0
                                  Array.from(new Array(10))

                                  Array.from(new Array(10)).map((el, ind) => el = ind+1)
                                  // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

                                    0

                                    Зачем извращаться, при том через протокол итераторов, если есть


                                    Array(10).fill()

                                    ?


                                    Учите стандартную библиотеку языка.

                                      0
                                      Если говорить о nodejs то все гуд!
                                      Но fill не во всех браузерах реализован…
                                        +1

                                        А Array.from и стрелки из комментария выше реализованы во всех браузерах? :) Тема ориентированна на ноду, но и в браузерах уже почти все используют полифилы и транспайлеры.

                                  0
                                  Простите за оффтоп,

                                  Боюсь на сто тестов статистики не хватит чтобы набить 50%.

                                  Тем более что мы имеем две вероятности — того тест в словаре, и того что рандом выдаст >0.5. Поправьте если ошибаюсь, но тогда baseline 25% при условии случайного выбора «слово» — «не слово» для теста.
                                    0
                                    Программа, всегда возвращающая false, наберёт 50%. Чтобы сделать хуже, чем 50%, нужно специально постараться.
                                      0
                                      Да, Вы совершенно правы.
                                      Впрочем, человек в начале треда постарался и сделал 25% с рандомом :)

                                      Интересно, сколько будет подано решений с return false — return true?
                                        +1

                                        50% он сделал. Не усложняйте рассуждения сверх меры :-)

                                          0
                                          А, я забыл добавить совпадения типа «нет в словаре» — «нет в словре». Тогда получаем 50%

                                          Надо придумать простое решение которое будет давать меньше 50% и получить приз за spectacular failure.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              +2
                                              Да, именно что «не очень простое».

                                              Хотя, если получится простое ошибочное, можно к нему добавить инверсию иии… PROFIT!
                                  +1
                                  «Вы дисквалифицированы»
                                    +3
                                    Примечание: это не официальное заявление организаторов конкурса.
                                  +2
                                  Данная задача чисто алгоритмическая — без привязки к конкретному языку реализации алгоритма. Т.е. уровень знания языка она не отражает. Причем для JS — эта задача нетипичная, язык заточен под другие вещи.

                                  Имх., для поиска специалистов именно на JS — не совсем удачная постановка.
                                    +8
                                    Эта задача – для поиска программистов, а не «специалистов на JS».
                                      –2
                                      Тогда зачем привязали к конкретному языку? Если иметь алгоритм — то его можно легко воплотить на любом языке, даже если ты с этим языком ранее не работал. Это касается именно этой задачи.

                                      На практике для большинства проектов нужны кодеры. И нечего стесняться. Кодер — этот тот человек, который сможет качественно написать код по имеющемуся алгоритму. На самом деле кодерство — не такая уж простая задача, как некоторые думают.
                                        +6
                                        К конкретному языку привязали затем, чтобы тестировать всё одной тестовой системой с одним API.
                                          –2
                                          Чтобы тестировать одной тестовой системой, достаточно было сделать выполняемый файл, возвращающий на стандартный вывод результат. Вы отсеяли всех, кто не работает с JS и node.js.
                                            +3

                                            Просто у них есть вакансия лишь для NodeJS программистов. :-)

                                              +2
                                              тут особо не требуется знаний JS. я до этого не работал с node, да и js знаю кое как — поэтому все эксперименты провожу на scala, python и даже (тсссс) C#.
                                              Закодить потом решение в JS особого умения не надо
                                        +1
                                        Заточен? Вы толстый клиент когда-нибудь писали?
                                        +1
                                        Есть ли какие то ограничения по памяти? по времени исполнения?

                                        Т.е. если я напишу магический алгоритм, который генерирует этот словарь в переменную, но в итоге он скушает 1GB и займет 100 секунд. Это будет противоречить правилам?
                                          +5
                                          Гигабайт и 100 секунд – не противоречит. 10 гигабайт и 1000 секунд – тоже не противоречит. Терабайт и неделя – отказать.
                                            0

                                            Вроде бы в правилах данные ограничения не указаны. Стоило бы указать, чисто для проформы. Чтобы как в прошлый раз никто не придрался к вам с претензиями, что его решение несправедливо дисквалифицированно.


                                            Ведь можно, например, найти весь словарь в числе пи, в программе указать лишь смещение, затем в init() рассчитать пи с нужной тончностью и получить 100% надёжность теста. А потом возмущаться, что вы недождались завершения работы init() и отдали приз другому.

                                              +9
                                              Смещение займёт больше, чем словарь.
                                                0
                                                Можно рассчитать смещение смещения и так до тех пор, пока не уложится в ограничения
                                                  +1
                                                  Смещение смещения займёт больше, чем смещение, и так далее.
                                                    +1
                                                    К тому же велика вероятность, что при переборе смещений наступит тепловая смерть вселенной.
                                              +1
                                              Десять гигабайт тоже нельзя, настройки V8 по умолчанию — куча 2 GB.
                                            +3
                                            Как участник предыдущего конкурса, большинство из нововведений решительно одобряю. Появился и определенный детерминизм и возможность предварительно тестировать решение. Единственное, мне кажется, что размер блока в 100 слов несколько маловат — в ходе разработки похоже придется запрашивать десятки блоков для реальной оценки незначительных улучшений в коде.
                                              0
                                              Запросите себе один раз достаточно много блоков и используйте их для тестирования всех своих вариантов.
                                              +1
                                              Что есть 64 КиБ? Первый раз вижу такую аббревиатуру. Вики подсказывает, что это кибибайты и на деле это означает 64000 байт, мне кажется проще именно так и указать в задаче.
                                                +6
                                                Кило — множитель 1000, киби — множитель 1024.
                                                  0
                                                  Ох, совсем старый стал, даже в википедию не могу посмотреть нормально )
                                                  Тем более стоило просто указать просто кол-во байт.
                                                    0
                                                    Однако, здравствуйте. Всю жизнь «килобайт» означал 1024 байта. А кто полагал иначе — считался ламером.
                                                      +3
                                                      Приставки были введены Международной электротехнической комиссией (МЭК) в марте 1999 года. После 1999 года ламеры и эксперты по приставкам поменялись местами.

                                                      https://ru.wikipedia.org/wiki/Двоичные_приставки
                                                      https://habrahabr.ru/post/193256/
                                                    +1
                                                    1 кибибайт = 1024 байта. Дурацкое сокращение КиБ использовано только по той причине, что отличие от десятичного килобайта здесь важно.
                                                      +3
                                                      Мне кажется лучше указать конкретное число, в данном случае 65536 байт. Оно вполне узнаваемо программистами.
                                                    0
                                                    А членство точно регистронезависимое? Непонятно, зачем тогда словарь подается на вход в регистрах…
                                                      0
                                                      Просто это словарь из стороннего источника. Вот он у них такой.
                                                      –1
                                                      > Едва ли возможно написать программу, которая укладывалась бы в ограничение и всегда давала бы верные ответы.
                                                      Ну на JavaScript да.
                                                        +4
                                                        Скорее всего, ни на чём нельзя.
                                                          0
                                                          Не соглашусь, если будет язык программирования в котором ваш словарь будет уже встроен по дефолту, то на нем ваша задача будет решаться парою строк )
                                                            +5
                                                            Или там будет команда «решить эту задачу».
                                                            –1
                                                            Для этих целей был придуман Perl. Не факт, что получится, но код будет существенно компактнее.
                                                              +2
                                                              Факт, что не получится.
                                                              Исходный файл со словами занимает 6906809 Байт, а требуется ужать всё вместе с кодом до 65535, т.е. чуть более чем в 100 раз.
                                                              Что-то мне не верится что из менее чем 1% знаний о исходном наборе данных можно восстановить гарантированно все 100%, какой бы при этом язык не был использован.
                                                                –6
                                                                Задача конкурса — выработать алгоритм классификации выборки приложенного словаря с последующим отнесением слов к словарю или не-словарю. Ещё раз повторю, что для таких вещей статистические либы на C и перл подходят больше.
                                                                Не, если упиться смузи, можно мокап на JS сразу лепить, потом отладить.
                                                          +4
                                                          Допускается ли использование каких-либо open-source библиотек при условии что их код будет включен в файл решения и общий размер будет удовлетворять ограничению в 64КиБ?
                                                            +2
                                                            Да, если это позволяет их лицензия.
                                                            +2
                                                            На данный момент ни в словаре, ни в тестах, символ "-" не встречается. Может так случится, что данные потом поменяются?
                                                              0
                                                              Спасибо, Вы нашли ошибку в условии задачи! Убрал упоминание символа -.
                                                                +1
                                                                Правильно ли я понимаю, что файл words.txt зафиксирован и изменяться от текущего состояния на этапе проверки решений не будет?
                                                                  0
                                                                  Правильно.
                                                              +1
                                                              Можно ли отправить несколько решений?
                                                                0
                                                                Учитывается только последнее решение, отправленное каждым участником. Если у Вас есть несколько вариантов, Вы сами можете протестировать их с помощью генератора тестов и определить, какой лучше.
                                                                  0
                                                                  А что насчёт символа "-"? Я не нашёл его в words.txt — можно ли все слова с ним считать неправильными?
                                                                  UPD — надо обновлять страницу :(
                                                                    0
                                                                    Это была ошибка в условии. Убрали из условия упоминание этого символа, в тестах его не будет.
                                                                0
                                                                Решения типа прошерстить все доступные ресурсы (файловая систем, интернет, итд) на предмет слов/текстов в принципе могут быть приняты? Или это гарантированная дисквалификация?
                                                                  0
                                                                  Эти решения невозможны, так как для доступа к интернету и файловой системе нужно загружать модули.
                                                                  +1
                                                                  отличает слова английского языка


                                                                  tsktsk
                                                                  stddmp
                                                                  bkbndr
                                                                  Очень замечательные слова.

                                                                  weltschmerzes
                                                                  Очень английское
                                                                    +1
                                                                    Еще перлы
                                                                    llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch
                                                                    llanfairpwllgwyngyll
                                                                      +2
                                                                      Это названия деревни в Британии.
                                                                        +5
                                                                        +1
                                                                        Да, в этом словаре много дикостей, в том числе аббревиатуры. Тем не менее, по определению в этой задаче английское слово — это слово из этого списка.
                                                                          0
                                                                          Тогда тот кто первый обучит нейронную сеть на этом словаре и умудрится поместить результат её обучения в 64Кб(gzip) — тот и молодца!
                                                                        +1

                                                                        Как генерируются тестовые примеры? Поровну и тех и тех? Для каждого пункта с равной вероятностью выбирается взять слово из словаря или сгенерировать рандом? Или как ещё?

                                                                          0
                                                                          Слов и не-слов примерно поровну, но среди не-слов бывают разные. Есть целый диапазон похожести на английские.
                                                                            0
                                                                            Т.е. return false даст 50% успеха?
                                                                        0
                                                                        А словарь в 64k не упаковывается, случаем?
                                                                          +4
                                                                          Я не думаю, что это возможно, но если окажется возможно, то тот, кому это удастся, достоин награды.
                                                                            0
                                                                            Ну мне удалось его в 100КиБ впихнуть. Еще есть, куда оптимизировать, но не уверен, что до 64 ужать получится :)
                                                                            К тому же это после gzip, а его реализация тоже потребует памяти.
                                                                              +3
                                                                              «Вы также можете указать, что Ваш файл данных сжат с помощью gzip. Если Вы отметите соответствующую опцию в форме отправки решения, то содержимое файла данных будет обработано функцией zlib.gunzipSync перед тем, как попасть в функцию init. Этот вариант удобен тем, что Вам не нужно ни внедрять в код на JS двоичные данные, ни писать самостоятельно стандартный алгоритм распаковки. При этом, конечно, ограничение по размеру касается сжатых данных; после распаковки их размер вполне может превысить 64 КиБ»
                                                                                0
                                                                                > … дающая наибольший процент правильных ответов

                                                                                ну, в таком случае, можно упаковать часть словаря :)
                                                                                  0
                                                                                  И это было бы замечательно (и более того — в реальном мире даже сработает !), если бы генерация тестовых выборок у организаторов конкурса использовала частотный словарь, т.е. генерировала реальные слова пропорционально их появлению в реальном мире. А при равномерном использовании шанс получить на входе теста «Hello» и «Actinomycetaceae» равен, что делает Вашу идею не очень перспективной.
                                                                                0
                                                                                100 это сурово. а сколько процентов success rate выходит, если выкинуть часть словаря?
                                                                                  +1
                                                                                  Ну мне удалось его в 100КиБ впихнуть.

                                                                                  Как? У меня 820КиБ, хоть ты тресни.
                                                                                  Хотя, есть идея как сжать сильнее, но время распаковки O(n!) и будет длиться до конца жизни вселенной.
                                                                                    +1
                                                                                    Судя по всему товарищ просто ошибся — либо у него выходит 1МБ с копейками (ошибся на порядок), либо он имеет в виду размер фильтра блума (это для ~50% false-positive), либо он упаковывал с потерями. А так — да, с gzip'ом 100% утрамбовываются примерно в 820-860 КиБ.

                                                                                    Тут ниже есть комментарий о возможности упаковки «где-то в 300 Кб-1 Мб смотря как упаковывать.» — но я постеснялся спрашивать, как была получена первая цифра.
                                                                                      0
                                                                                      Зря я, наверное, так категорично усомнился в способностях незнакомого человека. Посему заранее прошу прощения и вопрошаю 4orever: А действительно ли Вы упаковали словарь в 100 КиБ без потерь И требует ли алгоритм распаковки существенного количество байт на реализацию? Если требуется более одного-двух кибибайт в обфусцированном виде, то, думаю, стоит включить эту цифру в общий размер словаря.
                                                                                        0
                                                                                        Как написал чуть ниже — ошибся конечно. Я экспериментировал с префиксным деревом (тогда я еще не знал о том, как оно называется) + свой наскоро состряпанный формат сохранения в текст, а дальше gzip. Современные архиваторы достаточно умны, чтобы абстрагировавшись от содержимого выдать наилучший результат. Попробовал кое-что нагородить дополнительно, но особой экономии это не дало.
                                                                                        +2
                                                                                        А так — да, с gzip'ом 100% утрамбовываются примерно в 820-860 КиБ.

                                                                                        Какая-то фантастика. Почитаешь комментарии и думаешь, что я тут вообще делаю. Мне чтоб в 820 упаковать пришлось еще некоторую предобработку словаря сделать. И то сжимал winrar-ом. gzip-ом только 920 получается. Как вы это делаете? И что я тут делаю?
                                                                                          –1
                                                                                          >пришлось еще некоторую предобработку словаря сделать

                                                                                          Разумеется я указал размер после «предобработки» и gzip'a, а не просто ужатого gzip'ом словаря. Имелось в виду, что словарь и после обработки содержит 100% информации о словах (т.е. не укорочен/не испорчен блумом/машинным обучением / etc).
                                                                                            0
                                                                                            WinRAR-ом? У меня после предобработки и gz тоже что-то похожее получилось по размеру, но я ещё и 7z попробовал — получилась типа 730 КиБ. Правда непонятно как это может помочь.
                                                                                          0
                                                                                          Да-да, расслабьтесь :) Как написали выше — ошибся, нечего по ночам такими вещами заниматься :)
                                                                                          100Кб было частичное префиксное дерево.
                                                                                          P.S. ДУмал, что удалил тот коммент.
                                                                                        0
                                                                                        $ ./test.coffee
                                                                                        97193/97193 (100.00%)
                                                                                        fn = 0
                                                                                        fp = 0

                                                                                        вот только нет, не упаковывается.
                                                                                          0
                                                                                          А какого размера-то test.coffee?
                                                                                            0
                                                                                            См. выше по комментариям.
                                                                                            https://gist.github.com/vird/453a86cf16903c017b060cdd457baf86
                                                                                            Это просто верификатор. 100% выходит где-то в 300 Кб-1 Мб смотря как упаковывать.
                                                                                              0
                                                                                              vird правильно говорит. мне пока удалось в чуть-чуть меньше метра утрамбовать, есть еще возможности ужаться раза в два, но не больше.
                                                                                              в 64к не влезает даже арифметическим кодированием.
                                                                                          +1
                                                                                          А вы имеете отношение к организаторам конкурса? У меня предложение. В файле words.txt чуть больше 660К слов. А вы можете сгенерировать файлик схожего размера «words_fail.txt» с неправильными словами? Что бы не насиловать онлайн генератор зазря. )
                                                                                            +3
                                                                                            Я и есть ответственный за проведение конкурса.

                                                                                            Насилуйте генератор на здоровье.
                                                                                              0
                                                                                              А зачем? То есть какой в этом смысл? Сейчас придется писать доп. код, который будет получать слова, потом выкидывать оттуда правильные, а ещё судя по тексту и забанить за нагрузку могут…
                                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                  0
                                                                                                  За нагрузку не забаним. Просто можем иногда отвечать «Rate limit exceeded» вместо результата, тогда надо чуть подождать и повторить запрос.
                                                                                                0
                                                                                                Мне тоже было бы интересно получить такой файлик.
                                                                                                  0
                                                                                                  Уважаемые участники, мы предоставили Вам достаточно информации. Чтобы получить её в других форматах, которые вам удобнее, — преобразуйте, пожалуйста, сами.
                                                                                                  +1
                                                                                                  Используйте на здоровье
                                                                                                  for (i = _i = 0; _i < 1000; i = _i += 1) {
                                                                                                    console.log("https://hola.org/challenges/word_classifier/testcase/" + i);
                                                                                                  }
                                                                                                  

                                                                                                  node script.js > list
                                                                                                  mkdir solution_list
                                                                                                  cd solution_list
                                                                                                  wget -i ../list

                                                                                                  Склеивание результатов, думаю, понятно как реализовать.
                                                                                                  0
                                                                                                  При первом подходе 68%. Еще есть идеи, как улучшить :)
                                                                                                    0
                                                                                                    Gratz.
                                                                                                    Мое на 100k sample'ов только 62.67%.
                                                                                                      +3
                                                                                                      70.37% 51200 байт

                                                                                                      Очень жаль, что нету live leaderboard'а.
                                                                                                        0
                                                                                                        У меня 76.3%, но я еще не оптимизировал толком…
                                                                                                          0
                                                                                                          84%
                                                                                                            +3
                                                                                                            Это на какой по размеру выборке?
                                                                                                              0
                                                                                                              После оптимизации и исправлении ошибки в тесте результат гораздо ниже.
                                                                                                              Прошу прощения если эта цифра ввела кого-то в заблуждение
                                                                                                                0

                                                                                                                А сколько именно?


                                                                                                                P.S. Из за вас я выбросил все свои решение меньше 75, и у меня не осталось ни одного :( осталось только идеи как сделать >=75

                                                                                                                  0
                                                                                                                  Ну, знаете ли. После того, как несколько человек тут отписались о результатах больше 80%, а потом сказали, что это была ошибка, я уже и к 75% скептически отношусь.
                                                                                                                  Идеи тут у всех примерно одинаковые. Единственное, что не пробовал — нейросети. Но тут очень велико разнообразие их конфигураций, способов задания входов, алгоритмов обучения. Все перепробовать времени не хватит.
                                                                                                                    0
                                                                                                                    Максимум в комментариях, от которого человек не отказался, вроде 78% у vintage тут, еще 3 мая.
                                                                                                                      +2

                                                                                                                      Прощу прощения, если это выглядело так, как будто я виню Don_Eric за выброшенные решение, это не так, наоборот это мне дал повод на больше размышление.

                                                                                                                        0
                                                                                                                        ИМХО, 75% вполне реально, а вот > 80% — вызывает сомнения. После 70-72% идёт борьба с самим собой за каждые 0.2-0.3%.

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

                                                                                                                        Для себя я сделал вывод, что экспериментирование и обучение подобной сети требует от нескольких дней до пары недель фул-тайм без каких-либо гарантий того, что результат будет удовлетворительным.
                                                                                                                          +1
                                                                                                                          И всё же в топовых местах битва будет идти > 80%
                                                                                                                            0
                                                                                                                            Гипотеза, инсайд или получилось взять порог в 80%?
                                                                                                                              +2
                                                                                                                              Мотивация для остальных, порог взят.
                                                                                                                                +2

                                                                                                                                И у меня >80

                                                                                                                                  +2
                                                                                                                                  О, товарищ! Ещё есть время до пятницы, может удастся преодолеть порог и в 81%. Правда, чтобы добраться от 79 до 80 ушло 5 дней, а чем дальше — тем сложнее даются каждые 0.01%
                                                                                                                                    0
                                                                                                                                    Да, я думаю, что 81% возможен. У меня тоже >80%.
                                                                                                                                  0
                                                                                                                                  до 80% далековато :(
                                                                                                                                  тут наверно только нейросеть поможет
                                                                                                                                0
                                                                                                                                Получил письмо, и, думаю, оно будет интересно и другим участникам, как и мой ответ:
                                                                                                                                Если у вас получилось добиться результата > 80% рад за вас. Но не получилось бы так, что вы вводите в заблуждение всех остальных участников, отбивая мотивацию попробовать что-то ещё сделать в последние пару дней.

                                                                                                                                Смотрите в чем дело. Если вы используете любой алгоритм обучения, та же нейронная сеть к примеру, то вы используете ограниченное кол-во неправильных слов. Все вы просто не сможете выкачать из тесткейсов, их огромное множество и формируются они случайно. Я к тому, что набор тесткейсов на котором организаторы будут тестировать будет выбран случайно, и ваша достигнутая вероятность сохранится лишь тем больше чем больше тесткейсов совпадет в вашей выборке и выборке организаторов.

                                                                                                                                Вы пробовали закачать случайные 10000 (к примеру) тесткейсов те которые вы точно не использовали при обучении и каков был результат? Сделать это 2-3 раза?

                                                                                                                                Если >80% могу вас заранее поздравить с тем что вы точно будете в топе и бороться за призы. А вот если нет, тогда вы вводите в заблуждение остальных! И тогда надо бы ваш комментарий подредактировать, чтобы не отнимать мотивацию у остальных.

                                                                                                                                На мой взгляд такая вероятность которую вы обозначали не достижима по 2 причинам:
                                                                                                                                1. ограниченный размер решения в 64К
                                                                                                                                2. неограниченное число искажений слов (причем отличаются большинство неправильных слов от слова в словаре минимально)

                                                                                                                                По моему мнению, большинству участников интересно узнать, каких результатов добились остальные. Если разница небольшая, то это огромный стимул, а если разница большая — значит у него тесты неправильные :)
                                                                                                                                И если кто-то не выкладывает свои результаты из боязни дать другим стимул, то мне интересно увидеть кто каких результатов добился. Давать точные цифры нет смысла, т.к. каждый использует собственный способ оценки и блоки, на которых прогоняется решение локально и будет прогоняться организаторами — разные, а значит результат будет в любом случае отличаться от опубликованного.

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

                                                                                                                                В моём случае я действительно оценивал локально по относительно небольшой выборке — 23К блоков. После письма мне самому стало интересно насколько результат будет отличаться, если использовать другие сеты с блоками, поэтому я скачал ещё 2 сета по 10К блоков и протестировал своё решение только на них. По сравнению с предыдущим тестированием результат колеблется в пределах 0,1%.
                                                                                                                                  +2
                                                                                                                                  Увидев цифры > 80%, вместо того чтобы улучшать свой метод, я кинулся в последние дни перебирать другие методы…
                                                                                                                                  В любом случае задачка интересная, и будет интересно увидеть в итоге решения других участников.
                                                                                                                                  Возможно, после публикации исходников получится добиться ещё более лучших результатов, чем тот что займёт первое место в этом конкурсе.
                                                                                                                                    0
                                                                                                                                    Если достигнуть результата 80.01%, то можно смело утверждать, что достигнут результат > 80% :)
                                                                                                                                      0
                                                                                                                                      С другой стороны, если достигнуть результата 100%, то можно смело утверждать, что достигнут результат > 80% :)

                                                                                                                                      А по факту все может решить удача. В зависимости от тестового набора результат может значительно плавать.
                                                                                                                                    +2
                                                                                                                                    Ситуация мне напомнила один прекрасный рассказ — «Уровень шума».

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

                                                                                                                                    Даже если 80% — ошибка или фальсификация, это все равно прекрасная мотивация для «поверивших».

                                                                                                                                    Я, со своей стороны, пока болтаюсь в районе 77% и, не обладая верой в собственную исключительную гениальность, вполне допускаю, что вы или кто-то другой достигли 80, а может и 85 процентов.
                                                                                                                                      0
                                                                                                                                      1. 80% как минимум мне уже не кажутся чем-то нереальным. (Если я исправлю баги в построителе решения, я ожидаю получить где-то 78%, а если добавить новых фич (сейчас всего 50), то результат тоже может быть неплохой)
                                                                                                                                      2. С другой стороны я считаю, что как минимум половина достижений написанных тут при кроссвалидации покажет другую цифру. (для некоторых моих решений это было справедливо)
                                                                                                                                      3. Я свои решения не кроссвалидировал (исправляюсь, сейчас начну)
                                                                                                                                      4. Но я все-равно уверен в своих цифрах т.к. 75.19% это по тем блокам, что я выкачал, а по словарю words.txt у меня 85%. Т.е. мне стоило бы задуматься, если у меня было бы решение 75%, а на словаре 60%. Значит заменив выборку результат может быть хуже с большой вероятностью.
                                                                                                                                        0
                                                                                                                                        UPD. Быстрая кроссвалидация (6600 блоков) показала 74.69%. Не всё так плохо, но пол-процента потерял.
                                                                                                                                        +1
                                                                                                                                        спасибо за комментарий, сэкономил мне кучу времени, пытаясь выжать лишний промилле.
                                                                                                                                        пробовать другие методы уже поздновато, так что рад что у кого-то получилось чудо (С) Gromo
                                                                                                                                          0
                                                                                                                                          Спасибо и Вам за подробные комментарии и идеи — очень интересно читать размышления и выводы по разным методам. Я тоже пробовал делать несколькими способами, и описывал частично результаты тут в комментариях. А сдаваться не стоит — у меня локальные тесты неверные был прорыв почти в 3% в тот же день, как я описал, что неделю застрял на 26%.
                                                                                                                                            0
                                                                                                                                            * застрял на 76%
                                                                                                                                              0
                                                                                                                                              image
                                                                                                                                            0
                                                                                                                                            По идее самое логичное это делать все проверки не-слов таким образом, что бы слова проходили проверку с 99%. Тем самым даже если будут другие выборки то вероятность отклонений от результата минимальна.
                                                                                                                                              0
                                                                                                                                              Именно так из-за ограниченности словаря и неограниченности генерируемых не-слов — повторы слов будут встречаться намного чаще, поэтому выгоднее 1% в словах, чем 1% в не-словах. К сожалению, 99% для слов будет давать слишком много false-positive для не-слов — генератор слишком правдоподобные слова отдаёт.
                                                                                                                                            0
                                                                                                                                            81% на горизонте виден?

                                                                                                                                            Тоже уверенно преодолел 80% на официальном тестовом скрипте, но до 81 ещё далеко.
                                                                                                                                            Вообще удивлён тем, что так мало заявок >=80% — все необходимые для 80% идеи написаны на этой странице по много раз.
                                                                                                                                            85% в топовых местах уже не кажутся нереальными.
                                                                                                                                              +1
                                                                                                                                              не все признаются

                                                                                                                                              я дошел до 77.5% и остановился. Знаю как можно набрать еще несколько процентов, но вряд ли успею
                                                                                                                                                0
                                                                                                                                                Ну и что, что перестанут принимать решения для конкурса, я вот всё равно продолжу улучшать свой метод :)
                                                                                                                                                Хочется выжать свой максимум.
                                                                                                                                                  +1
                                                                                                                                                  тут уже упирается в максимум ресурсов тоже, деньги и время. Я сейчас поднял виртуалку с 64 ядрами и 1Тб RAM, посмотрим если поможет
                                                                                                                                                    0
                                                                                                                                                    Интересно будет после завершения конкурса почитать, чем утилизировали и насколько помогло.
                                                                                                                                                      0
                                                                                                                                                      это самое интересное!
                                                                                                                                                0
                                                                                                                                                Думаю, что 81% достижим, и даже 82%, но, имхо, по поводу 85% сомневаюсь, слишком тяжело идут улучшения после 80% — приходится бороться за каждые 0,01%. А в последние два-три дня вообще практически никаких улучшений — любые попытки что-либо изменить только ухудшают результат, и иногда довольно сильно, приходится откатываться к предыдущему решению. Скорее всего я достиг, как говорят, «локального максимума», чтобы поискать горку повыше, нужно спустить пониже и искать другой путь, однако времени на это уже нет, да и идеи уже все перепробовал.

                                                                                                                                                По поводу комментариев в статье — соглашусь, это кладезь идей и информации о решениях, вот только выбрать правильный подход сложно, и нужно время, чтобы выбранный подход довести до ума
                                                                                                                                            +2
                                                                                                                                            на моих тестах, мой результат, который я сегодня залил, был больше 75%

                                                                                                                                            сколько именно сказать не могу: во-первых, и тут мог ошибиться, а во-вторых, по правилам конкурса создалась ситуация когда никто не раскрывает свои цифры, и гораздо «выгоднее» (по теории игр) скрывать свои или вводить в заблуждение других.
                                                                                                                                              0

                                                                                                                                              Этот ответ вполне устраивает меня, спасибо !

                                                                                                                                +3
                                                                                                                                задача кажется чисто математической. Просто подобрать параметры к bloom filter
                                                                                                                                  0
                                                                                                                                  Ну вот, оказалось, что я только что изобрёл bloom filter.
                                                                                                                                    +2
                                                                                                                                      0
                                                                                                                                      Всем хороша статья. Ей бы еще реализацию корректную…
                                                                                                                                      Возможно, отрицательные результаты хеш-функции — не очень большая проблема.
                                                                                                                                      То, что JS прекрасно работает с отрицательными индексами — тоже не проблема (как известно, JS и правду умножит и ложь поделит).
                                                                                                                                      А вот то, что в результате фильтр Блума использует в два раза больший объем памяти — уже проблема…

                                                                                                                                      P.S. эх, а только 85% правильных ответов достиг…
                                                                                                                                        +1

                                                                                                                                        В 2 раза больший по сравнению с чем?


                                                                                                                                        На какой выборке? У меня всего 78 на миллионе. С починенным блюмом и парой эвристик.

                                                                                                                                          0
                                                                                                                                          Реализация из статьи использует удвоенный объем памяти относительно того, что было задано при инициализации. С этой реализацией у меня 85% было на миллионе тестовых слов. И да, есть дополнительная обработка слов.
                                                                                                                                            +1

                                                                                                                                            Речь об отрицательных хеш-суммах? Ну так они и сохранение в файл не переживают :-) Так что по любому надо заменять на сложение по модулю.


                                                                                                                                            Чувствую вся разница реализаций будет именно в предобработке слов :-)

                                                                                                                                              0
                                                                                                                                              Вот я и предупреждаю о некорректной реализации ;) Может кому времени и/или нервов сэкономлю…

                                                                                                                                              В принципе, исправляется достаточно легко — берем по модулю или меняем 0xFFFFFFFF на 0x7FFFFFFF (меньше кода).
                                                                                                                                              И да, разница в основном будет в доп. обработке слов и в эвристиках.

                                                                                                                                              Ну и в подходах к решению — те же нейронные сети не думаю, что стоит сбрасывать со счетов.
                                                                                                                                          0
                                                                                                                                          можно использовать маленькие блюмы только для префиксов например. занимает мало, а шума отсеивает много
                                                                                                                                      0
                                                                                                                                      Не влезает (если я правильно посчитал). При вероятности ложноположительного срабытывани в 1% размер фильтра составляет (-(661000 * ln(0.01)) / (ln(2) ** 2)) / 8 / 1024 == 773КиБ, 10% — 387КиБ, 50% — 116КиБ.
                                                                                                                                        0

                                                                                                                                        50% ложноположительных даёт 75% правильных ответов, что уже не плохо.

                                                                                                                                          0
                                                                                                                                          да, вы правы
                                                                                                                                          http://hur.st/bloomfilter?n=660000&p=0.01
                                                                                                                                          0
                                                                                                                                          Из Вики и статьи:
                                                                                                                                          https://en.wikipedia.org/wiki/Bloom_filter
                                                                                                                                          https://habrahabr.ru/post/112069/

                                                                                                                                          Вероятность ложного срабатывания:


                                                                                                                                          Оптимальное значение k:


                                                                                                                                          Что для этой задачи равно:
                                                                                                                                          k = 65536/660000*ln(2) = 0,09929697*0,69314718 = 0,068827414. То есть оптимум 1.
                                                                                                                                          p = 1 — e^(-n/m) = 1 — e^10,07080078125 = 1 — 4,2296729941409029988465653752585e-5 = 0,9999577

                                                                                                                                          То есть вероятность ложного срабатывания 0,9999577. Что в общем очень-очень плохо.

                                                                                                                                          Поправьте меня если я где-то ошибся в расчетах.
                                                                                                                                              0
                                                                                                                                              Забыл перевести байты в биты.
                                                                                                                                              p = 1 — e^(-660000/524288) = 1 — e^(-1,25885009765625) = 1 — 0,28398039 = 0,7160196

                                                                                                                                              Результат лучше, но все равно не очень хороший.
                                                                                                                                                0
                                                                                                                                                да, получается что общий результат будет 50% + 0.28*50% = 64%
                                                                                                                                                можно его увеличить если добавить юристику — заранее отсеивать шум по грамматическим правилам (типа 5 согласных подряд)
                                                                                                                                                  +1
                                                                                                                                                  Эвристики начнут отъедать место, оставшееся для блум-фильтра :)
                                                                                                                                                    0
                                                                                                                                                    Каждое правило уменьшает длину фильтра.

                                                                                                                                                    Но вообще там в правилах написано что текстовый файл с дополнительными данными можно архивировать. Дальше все зависит от того насколько хорошо сожмется файлик с фильтром. )
                                                                                                                                                      0
                                                                                                                                                      Практика показывает, что сбалансированные бинарные данные для блум фильтра сжимаются очень плохо — всего на 3-4%. Больший показатель сжатия говорит о том, что фильтр недостаточно эффективен: если много бит установлено — будет много ложно-положительных ответов, если много бит не установлено — размер фильтра выбран слишком большой и его можно спокойно уменьшить в большинстве случаев (либо увеличить количество хеш-функций чтобы повысить точность).
                                                                                                                                                  0
                                                                                                                                                  .
                                                                                                                                                +1
                                                                                                                                                Откуда будут браться неправильные слова? специально искривляться или генерироваться или из другого справочника, например другого языка? Больше вопрос такого плана — не будут ли специально подбираться максимально похожие слова для снижения эффективности скрипта?
                                                                                                                                                  0
                                                                                                                                                  Алгоритм генерации не-слов мы раскроем только при подведении итогов конкурса. Как нетрудно видеть сейчас из генерируемых тестов, не-слова генерируются с различной степенью сходства с настоящими, от шума до слов, которые выглядят настолько «родными», что даже понятны носителю языка.
                                                                                                                                                    0
                                                                                                                                                    Некоторые даже настолько понятны, что уже используются (как упоминаемое в условии «sonicative»). ^_^
                                                                                                                                                      0
                                                                                                                                                      Я видел среди генерированных не-слов «defenestrationalism».
                                                                                                                                                  0
                                                                                                                                                  Я правильно понял?
                                                                                                                                                  вес файла архива с помощью gzip + js файла должен быть не больше 64 КиБ.
                                                                                                                                                  а файл в распакованном виде может быть больше чем 64 КиБ.
                                                                                                                                                  +1
                                                                                                                                                  feldgendler, Добавьте, пожалуйста, форму для проверки решения, чтобы можно было убедиться, что решение точно удовлетворяет требованияем. Например, чтобы проверятор запускал решение на 1 блоке и рапортовал ошибки, возникшие при этом (слишком большой размер файлов, не удалось разжать приложенный файл и т.п.)
                                                                                                                                                    0
                                                                                                                                                    Размер файла проверяется формой отправки. В остальном — напишите проверялку сами и выложите здесь, другие спасибо скажут.
                                                                                                                                                      0
                                                                                                                                                      К сожалению, меня не так поняли.
                                                                                                                                                      Я прошу не интерфейс для тестирования, а доступ к тестирующему серверу. Например, в спортивном программировании перед соревнованием проводится пробный тур. На нем участники проверяют, что тестирующая среда ведет себя так, как они предполагают. А в соревнованиях topcoder есть возможность проверить свое решение на тестах из условия задачи.
                                                                                                                                                      Возможность проверить свое решение в реальной тестирующей среде, пусть и с дикими ограничениями, помогла бы избежать самой главной ошибки прошлого hola challenge.
                                                                                                                                                        +1
                                                                                                                                                        Что такое «доступ к тестирующему серверу»? Вы шелл туда хотите, что ли?
                                                                                                                                                          0
                                                                                                                                                          Думаю, достаточно простого запуска выполнения на двух тестовых словах, одно есть в списке, второго нет (хотя бы «a» и «zzzz»).
                                                                                                                                                          Для того, чтобы убедиться, что файл нормально распаковался и модуль загрузился без ошибок.
                                                                                                                                                            +2
                                                                                                                                                            var mod = require('your-program.js');
                                                                                                                                                            var data = fs.readFileSync('your-data.gz'); // optional
                                                                                                                                                            data = zlib.gunzipSync(data); // optional
                                                                                                                                                            if (mod.init)
                                                                                                                                                                mod.init(data);
                                                                                                                                                            console.log('a:', mod.test('a'));
                                                                                                                                                            console.log('zzz:', mod.test('zzzz'));