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

    Спасибо всем, кто уже поучаствовал или собирается участвовать в нашем конкурсе по программированию!

    Мы решили опубликовать ряд важных разъяснений к правилам, чтобы помочь участникам избежать типичных ошибок. Обидно было бы дисквалифицировать интересное решение из-за чисто технической ошибки.

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

    Для отправки работ осталась ещё неделя. Если этот пост помог Вам найти ошибку, ещё есть время её исправить.

    Английская версия этого поста размещена на GitHub.

    Часто задаваемые вопросы


    • Как же я смогу прочитать файл words.txt, если нельзя загрузить модуль fs? А можно ли скачать его из интернета? Можно ли использовать process.binding?
      Ваша программа не будет иметь доступа к файлу words.txt. В этом и смысл. Если бы можно было просто прочитать этот файл, задача была бы тривиальной. Ничего нельзя скачать, потому что для этого понадобились бы такие модули, как http или net. Включить словарь в своё решение тоже не получится из-за ограничения по размеру.
      Это означает, что написать решение, всегда дающее правильные ответы, скорее всего, невозможно. Но можно написать программу, которая чаще угадывает правильно, чем неправильно, и тот, чья программа точнее угадывает, победит.
    • В словаре есть некоторые слова с прописными буквами. Могут ли они попасться в тестах?
      Могут, но они будут переведены в нижний регистр.
    • Что означает «64 КиБ»?
      64*1024 = 65536 байт.
    • Если мой файл данных сжат методом gzip, то должен ли его размер до или после сжатия укладываться в 64 КиБ вместе с текстом программы?
      Учитывается размер после сжатия.
    • Что за странный словарь! Там полно каких-то непонятных слов.
      Мы знаем, что он странный. Это самый большой словарь английского языка для проверки правописания, в который входит большое число аббревиатур, заимствований, редких слов, диалектизмов и даже невозможных словоформ. Тем не менее, мы выбрали именно этот словарь, поэтому для данной задачи «английское слово» — это то, которое встречается конкретно в этом словаре.
    • Какого размера набор «не-слов», используемый в генераторе тестов?
      Генератор тестов не использует какого-либо фиксированного набора «не-слов». Он генерирует псевдослучайные слова, похожие на английские, непосредственно при запросе по алгоритму, который мы опубликуем при подведении итогов конкурса.
    • Как тестовая система будет учитывать дубликаты, то есть слова, встречающиеся более чем в одном из блоков по 100 слов?
      Каждое вхождение будет учитываться как отдельное слово. Посмотрите, как устроен наш скрипт для тестирования.
    • Что, если победителю ссылку на конкурс прислали два человека?
      Премию получит тот, кто прислал её первым.


    Типичные ошибки


    К сожалению, во многих решениях, которые мы получили на сегодняшний день, содержатся похожие технические ошибки:
    • Функции test и init не экспортированы или экспортированы неправильно. Недостаточно просто объявить функции, их надо экспортировать из модуля. Если Вы не уверены, что сделали это правильно, проверьте свою программу нашим тестовым скриптом.
    • Функция init работает со своим аргументом data как с текстовой строкой, тогда как в условии явно сказано, что это будет Buffer.
    • Программа использует файл данных, но он не приложен.
    • Файл данных упакован методом gzip, но соответствующая опция в форме отправки не выбрана.
    • Опция gzip в форме отправки выбрана, но файл вместо gzip представляет собой zip-архив. Это не одно и то же!
    • Программа пытается использовать require или process.binding. Это запрещено правилами.


    Удачи всем участникам!
    Hola 56,96
    Компания
    Поделиться публикацией
    Комментарии 75
    • 0
      обязательно называть свои файлы solution.js и data.gz?
      • +3
        Именно для тестового скрипта — да. При отправке решения файлы могут называться как угодно.
        • 0
          судя по тому, что файлы отправляются через форму, не обязательно
        • +1
          Большое спасибо, что создали еще одну тему, теперь я могу писать сюда комментарии, и еще большее спасибо за тестовый скрипт. Скрипт бесценен, поскольку я не программирую на JavaScript и не знал таких подробностей, как экспорт функций.

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

          В итоге перешел к эвристическим методам, пока достиг 75+%
          • +1
            feldgendler, моё решение в этом тестовом скрипте проверяется со скоростью ~50 слов в секунду (против 4000 в секунду моим скриптом), я так полагаю, это из-за виртуальной машины.
            Это 5 часов на 1 000 000 слов.
            Такая скорость проверки считается разумной? Или мне надо что-то исправить?
            • 0
              Такая скорость вполне удовлетворительна.
            • 0

              Доступен Buffer.allocUnsafe ;)
              Не забудьте в параметр запуска добавить --zero-fill-buffers, а то можно 100% набрать.

              • +1
                С приведенным примером тестирующего скрипта получить 100% можно и проще.

                Описал способ feldgendler в личку, если он будет не против — могу рассказать и здесь (все равно решения победителей, я думаю, будут вручную просматриваться и всякие хаки там не прокатят).
                • 0
                  Не против. На всякий случай предупреждаю всех любителей обходных путей, что за манипуляцию тестовой системой последует дисквалификация.
                  • +3
                    Для пущего веселья я решил заодно уместить свое решение в 3 строчки (и 146 байт), по-прежнему набирая этим кодом 100% :)

                    exports.init = exports.test = () => {
                      Buffer.prototype.toString = () => '{' + new Array(100).fill().map((_, i) => `"${i}":0`).join(',') + '}'
                    }
                    
                    • +2
                      А после этого некоторые удивляются, почему нет живого leaderboard. А потому что не будем мы непроверенный код автоматически запускать на своих серверах, и не просите.
                      • +1
                        теперь понятно

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

                        но в данном случае и leaderboard не поможет, так как всегда можно придержать лучшее решение на последний момент, или посылать решения которые нарушают правила. Тут только сработает формат kaggle
                        • +3
                          А чего бы не запускать в docker-контейнерах например?
                          • 0
                            Конечно, есть способы. Но затраты труда на проведение конкурса всё-таки ограничены.
                          • +2
                            Я не очень понимаю, как вы предполагаете проверять код перед запуском? Каждое решение глазами? Там же, вполне вероятно, будет минифицированный код. Также часть кода, я, например, запихнул в data.gz и исполняю через eval. Как вы этот код проверите, кроме как запуском?
                            • 0
                              Поэтому просят прикреплять исходники.
                              Если это будет попытка обойти систему, то его не так и сложно отследить, даже в минифицированном варианте.
                              • +1
                                Главное, что результат из скрипта не попадёт автоматически в публичную таблицу. А так всё равно всё ещё и в виртуальной машине.
                    • 0
                      > Функции test и init не экспортированы или экспортированы неправильно. Недостаточно просто объявить функции, их надо экспортировать из модуля. Если Вы не уверены, что сделали это правильно, проверьте свою программу нашим тестовым скриптом.
                      Если доходи до такого, может лучше выложить шаблон кода? Пусть test содержит там хотя бы просто return true; но это поможет избежать нелепых ошибок тем кто видит js первый раз.
                      • +4
                        exports.init = function(data){ ... };
                        exports.test = function(word){ ... };
                        
                        • +1
                          Спасибо, конечно но я знаю. Я имел ввиду добавить в статью. Для незнакомых с js вообще.
                          • 0
                            Заголовок топика — «Конкурс по программированию на JS».
                            Вряд ли люди, незнакомые с js вообще, решат принять в нём участие.
                            • +6
                              Поскольку наша корыстная цель — найти программистов для повседневной работы именно с Node.js, то нас это вполне устраивает.
                      • 0
                        Почитал комментарии к прошлой статье и возник вопрос: почему никому применение нейронных сетей здесь не кажется странным? Это же совсем не задача машинного обучения. Его задача — классификация и обобщение, но уж никак не запоминание. А тут, судя по сетам правильных и неправильных слов (честно признаюсь, не сильно в них всматривался, но все же), они сгенерированы одним и тем же генератором, т.е. нет никаких паттернов, по которым их можно было бы различить. Нейронные сети тут будут выдавать более-менее приемилимый результат только в результате переобучения, а в этом случае теряется весь смысл нейронных сетей. P.S: Хотя вот задача распознования лиц тоже решается нейронными сетями и это может ввести в заблуждение, но только вот там применяются CNN, которые, грубо говоря, отображают лица в набор особенностей и производят переобучение на этих наборах. Т.е. их использовать удобно потому что они автоматически выявляют признаки, а не потому что у них хорошая память.
                        • +1
                          Потому, что некоторые рассчитывали, что в словообразовании есть некоторые правила и их можно выявить с помощью нейронной сети.
                          Но большинству уже понятно, что зря.
                          • +1
                            Вам же интуитивно понятно, что «dfowyy» не похоже на английское слово? А определяете Вы это нейронной сетью, больше нечем. То есть на нейронных сетях задача вполне решается, только не обязательно легко.
                            • +2
                              Чем я это определяю большой вопрос. Т.е. в обобщенном смысле конечно нейронной сетью. Только вот между нейронной сетью о которой мы тут говорим и нейронной сетью мозга пропасть.
                              Ну и кроме того этой же нейронной сетью я определяю что pfd тоже не фига не английское слово, а вот какой-нибудь ongaze мог бы и проканать. Боюсь если определять буду я, то не обгоню в этом конкурсе даже самый простые алгоритмы.
                              • +1
                                Да, 100% Вы не определите. Генератор устроен так, что он выдаёт слова разной степени схожести с английскими — от белого шума до почти неотличимых. Это сделано для того, чтобы разные программы могли соревноваться в различении большего числа «ступеней» сходства.
                                • +1
                                  И вот об эти слова как раз и споткнется нейронная сеть! Так же как спотыкается наш мозг. Тут нужно действительно решение которое хорошо запоминает данные в минимальном объеме.
                                  • 0
                                    Никто не запрещает комбинировать различные алгоритмы: нейросеть для отсева «dfowyy», и что-нибудь другое для отсева «ongaze».
                        • 0
                          немного ламерский вопрос — у меня установлена версия 6.2.0, и скрипт на ней проходит ок (после комментирования строчки с проверкой на «6.0.0»). Нет ли никаких breaking changes с тех пор? Особыми фичами языка не пользуюсь

                          П.С. а не могли б организаторы посылать при каждой заявке на мейл также результат предварительной проверки? Было б очень здорово
                          А если б еще и leaderboard… :)
                          • +2
                            $ npm install -g nvm
                            $ nvm install 6.0.0
                            $ nvm run 6.0.0 your_app.js
                            
                            • 0
                              спасибо. хотя nvm не сработал, но получилось через n
                              • 0
                                Спасибо, я не знал про n. А как именно не сработал nvm, чтобы можно было багрепорт отправить?

                                p.s. Интересно, чем вызван минус…
                                • 0
                                  минус не я поставил, но скомпенсировал плюсом :)

                                  >nvm download 6.0.0

                                  >sudo nvm install 6.0.0
                                  Not built yet

                                  >sudo nvm build 6.0.0
                                  Configuring… File "/Users/Roman/.nvm/node-v6.0.0/configure", line 481
                                  '''
                                  ^
                                  SyntaxError: Missing parentheses in call to 'print'


                                  Запускал на маке
                                  • 0
                                    У меня тоже мак… крайне странно! У вас nvm 0.28.0? Дело в том, что он не должен билдить node, а только скачивать и распаковывать готовый, плюс мой вообще не имеет команды build!

                                    И да, я, кажется, понимаю, за что минус.
                                    $ npm install nvm
                                    npm WARN deprecated nvm@0.0.3: This is NOT the correct nvm. Visit http://nvm.sh and use the curl command to install it.
                                    
                                    Я пребывал в ошибочной уверенности, что ставил nvm через npm.
                            • 0
                              Мы будем тестировать ровно на 6.0.0, ни больше, ни меньше.
                              • 0
                                Мы для того и опубликовали тестовый скрипт, чтобы каждый мог заранее убедиться, что его программа не содержит технических ошибок.
                              • 0
                                вопрос к организаторам — а вы можете сказать какое будет минимальное кол-во блоков для тестирования? Мой результат стабилизируется до промилле после 4000, и надеюсь что в тесте будет больше
                                • +2
                                  Такое, какое потребуется, чтобы увидеть уверенную разницу между лидерами.
                                  • +1
                                    Что является уверенной разницей?
                                    Например, на одном блоке одно решение даст 65% а другое 75%. Является ли это уверенной разницей?
                                    У меня разброс между самым удачным и самым неудачным блоком в тестовом наборе больше 20%
                                    • 0
                                      Начнём с 1000 блоков, а потом видно будет.
                                      • +1
                                        Более-менее результат стабилизируется после 10000 блоков. По крайней мере у меня.
                                        • 0

                                          У меня примерно так же, >10k среднее стабилизируется в пределах 0.05% (по Y доли %, % скрыт):


                                          • +2
                                            Не пугайте так, я сначала подумал, что слева шкала до 1.00 :)
                                    • 0
                                      А хотя бы с порядком не сориентируете(тысячи/десятки тысяч/сотни тысяч/миллионы)?
                                      • 0
                                        Вы для выявления уверенной разницы будете «гонять» все решения или только лучшие?
                                        • +2
                                          Когда решим, сколько нужно для лучших, прогоним на этом количестве всех.
                                    • 0
                                      feldgendler, а можно нескромный вопрос? Планируется ли какое-то поощрение участникам, которые не попадут в ТОР-3 но будут очень близки к этому? У меня складывается впечатление, что разница между победителями и лучшей десяткой будет меньше 1%. Обидно будет участникам не попавшим в призы из-за пол процента. Или это жесткий конкурс, где даже сотая процента отделяет «всё или ничего»? :)
                                      • +4
                                        Во множестве видов спорта разница между лидерами гонки может оказаться ничтожной. Не вижу причин, почему здесь должно быть иначе.
                                        • 0
                                          Во многих видах спорта деньги дают больше, чем за 3 места. Скажем, в биатлоне — 8.
                                          • +6
                                            я б сказал спасибо что вообще дают.
                                        • +1
                                          Судя по описанию конкурса можно получить спец призы за интересные и оригинальные решения на усмотрение организаторов конкурса. По мне очень даже справедливо. К тому же место в первой десятке тоже довольно сильно тешит ЧСВ :)
                                        • 0
                                          Возможно ламерский вопрос.
                                          в условии кроме рачего скрипта позволяется еще файлик с «мини-словарем» (ну или той инфой что мне нужна). Как его прочитать?
                                          • 0
                                            Ваш файл данных будет прочитан тестовой системой и передан Вашей функции init в качестве аргумента типа Buffer.
                                          • 0
                                            Хотел предложить объединить тесты в один большой файл вида:
                                            post 1
                                            ch'stalietized 0
                                            magnanimously 1
                                            ...

                                            что могло бы ускорить прогон тестов до 3-х раз…

                                            Но с текущей реализацией тестирования это не даст желаемых результатов.

                                            На простом решении вида «return 0» с 20-ю миллионами тестовых слов (200к блоков) получил такие результаты:
                                            1. Решение с обходом каталога, vm (из статьи): 12m23.839s
                                            2. Решение с обходом каталога, «честный» require: 0m59.152s
                                            3. Решение с одним большим файлом (через readline), «честный» require: 0m18.198s

                                            Сделал несколько прогонов, чтобы файлы были в кэше.
                                            Диск SSD, оперативки с запасом (16GB).
                                            • 0
                                              Спасибо. Мы этот скрипт не оптимизировали, тут цель была дать возможность проверять корректность. Когда при подведении итогов встанет задача прогонять большое число решений на большом числе блоков, скорее всего, так или иначе оптимизируем.
                                              • 0
                                                Я для эстетики еще аргументы местами переставил, заодно и парсить проще:
                                                1 post
                                                0 ch'stalietized
                                                1 magnanimously
                                                • 0
                                                  Не вижу особой разницы в эстетике или в парсинге…

                                                  Понятное дело, что подобный файл сортировать построчно нельзя.
                                                  Но если вдруг отсортируют… Будет нарушено одно из условий работы тестового генератора — на 100 тестов (1 блок) примерно поровну слов и не-слов.
                                                  А в предложенном мною варианте сортировка не будет столь катастрофична :-)
                                              • 0
                                                Почитав соседнюю ветку, пришел к оценке, что по крайней мере 5 человек смогли преодолеть порог в 80%, или, по крайней мере, верят в то, что смогли преодолеть. Так что, вполне вероятно, кто-нибудь и покажет результат в 85%
                                                • 0
                                                  Так что, вполне вероятно, кто-нибудь верит в то, что покажет результат в 85% )
                                                • 0
                                                  А можно описание решения выложить попозже? Например, после предварительных итогов. А-то сейчас код представляет собой некоторую кашу из Java, Python, Shell-скриптов и JavaScript, которую я, конечно, приложу сразу, но в которой, вообще, трудно разобраться.
                                                  • 0
                                                    Присылайте кашу. Да, вполне можно будет дослать текстовый файл потом.
                                                  • 0
                                                    Дрожащими руками залил решение. Неплохо бы на будущее, чтобы еще MD5 от файлов приходило на почту, чтобы можно было проверить то или не то загрузил
                                                    • 0
                                                      Можно проверять по байтовому размеру загруженных файлов из письма, к примеру.
                                                      • 0
                                                        Да, я именно на этом и остановился :)
                                                    • +1

                                                      Решение не отправил, но решил поделиться опытом.

                                                      • +6
                                                        А будут сегодня какие-нибудь «предварительные результаты»?
                                                        • 0
                                                          Похоже, придётся отложить до понедельника, не успеваем.
                                                          • +7
                                                            Я все понимаю, непредвиденные обстоятельства, много участников, долгое тестирование и т.п.
                                                            Но ведь совершенно не сложно просто оставить коммент «К сожалению мы не успеваем в понедельник, предварительные результаты будут тогда-то». За это не расстреливают ;)
                                                            • +5
                                                              Похоже лидеры очень медленно обучаются и все еще работают, с каждым часом наращивая лишние полпроцента. Теперь орги ждут кто первый доберется до 146…
                                                              • +1
                                                                Возможно, какая-то программа так сильно обучилась, что теперь организаторам приходится бороться с недружественным ИИ.
                                                                • 0
                                                                  Надо будет feldgendler-у капчу показать, ИИ может писать с его аккаунта, так, чисто мера предосторожности.
                                                        • +6
                                                          feldgendler А как сегодня с результатами?

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                        Самое читаемое