Как стать автором
Обновить

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

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

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);
});

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

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

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

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

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

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

В test будут подаваться только слова вида [a-zA-Z'-]+, не нужно отфильтровывать пробелы и спецсимволы.
НЛО прилетело и опубликовало эту надпись здесь
Ответы на это написаны в условии.
НЛО прилетело и опубликовало эту надпись здесь
Да.
Зачем подавать в тестах слова с дефисом, если в словаре нет ни одного слова с дефисом?
Это была ошибка в условии, исправлено. Дефисов не будет.
… дающая наибольший процент правильных ответов.

а вдруг повезет
function main(){
  return Math.random() > 0.5
}

module.exports = {
  init: function(data){
    // м-м-м бинарничек
    console.log('бдыщь')
  },
  test: main
}


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

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]
потому что
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
да спасибо уже нашел
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
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 ]

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


Array(10).fill()

?


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

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

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

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

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

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

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

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

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

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

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

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

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

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

тут особо не требуется знаний JS. я до этого не работал с node, да и js знаю кое как — поэтому все эксперименты провожу на scala, python и даже (тсссс) C#.
Закодить потом решение в JS особого умения не надо
Заточен? Вы толстый клиент когда-нибудь писали?
НЛО прилетело и опубликовало эту надпись здесь
Гигабайт и 100 секунд – не противоречит. 10 гигабайт и 1000 секунд – тоже не противоречит. Терабайт и неделя – отказать.

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


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

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

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


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

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

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

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

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

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

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

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

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

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

Насилуйте генератор на здоровье.
А зачем? То есть какой в этом смысл? Сейчас придется писать доп. код, который будет получать слова, потом выкидывать оттуда правильные, а ещё судя по тексту и забанить за нагрузку могут…
НЛО прилетело и опубликовало эту надпись здесь
За нагрузку не забаним. Просто можем иногда отвечать «Rate limit exceeded» вместо результата, тогда надо чуть подождать и повторить запрос.
Мне тоже было бы интересно получить такой файлик.
Уважаемые участники, мы предоставили Вам достаточно информации. Чтобы получить её в других форматах, которые вам удобнее, — преобразуйте, пожалуйста, сами.
Используйте на здоровье
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

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

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

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


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

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

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

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

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

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

И у меня >80

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


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

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

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

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

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

да, вы правы
http://hur.st/bloomfilter?n=660000&p=0.01
Из Вики и статьи:
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. Что в общем очень-очень плохо.

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

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

Но вообще там в правилах написано что текстовый файл с дополнительными данными можно архивировать. Дальше все зависит от того насколько хорошо сожмется файлик с фильтром. )
Практика показывает, что сбалансированные бинарные данные для блум фильтра сжимаются очень плохо — всего на 3-4%. Больший показатель сжатия говорит о том, что фильтр недостаточно эффективен: если много бит установлено — будет много ложно-положительных ответов, если много бит не установлено — размер фильтра выбран слишком большой и его можно спокойно уменьшить в большинстве случаев (либо увеличить количество хеш-функций чтобы повысить точность).
Откуда будут браться неправильные слова? специально искривляться или генерироваться или из другого справочника, например другого языка? Больше вопрос такого плана — не будут ли специально подбираться максимально похожие слова для снижения эффективности скрипта?
Алгоритм генерации не-слов мы раскроем только при подведении итогов конкурса. Как нетрудно видеть сейчас из генерируемых тестов, не-слова генерируются с различной степенью сходства с настоящими, от шума до слов, которые выглядят настолько «родными», что даже понятны носителю языка.
Некоторые даже настолько понятны, что уже используются (как упоминаемое в условии «sonicative»). ^_^
Я видел среди генерированных не-слов «defenestrationalism».
Я правильно понял?
вес файла архива с помощью gzip + js файла должен быть не больше 64 КиБ.
а файл в распакованном виде может быть больше чем 64 КиБ.
Верно.
feldgendler, Добавьте, пожалуйста, форму для проверки решения, чтобы можно было убедиться, что решение точно удовлетворяет требованияем. Например, чтобы проверятор запускал решение на 1 блоке и рапортовал ошибки, возникшие при этом (слишком большой размер файлов, не удалось разжать приложенный файл и т.п.)
Размер файла проверяется формой отправки. В остальном — напишите проверялку сами и выложите здесь, другие спасибо скажут.
К сожалению, меня не так поняли.
Я прошу не интерфейс для тестирования, а доступ к тестирующему серверу. Например, в спортивном программировании перед соревнованием проводится пробный тур. На нем участники проверяют, что тестирующая среда ведет себя так, как они предполагают. А в соревнованиях topcoder есть возможность проверить свое решение на тестах из условия задачи.
Возможность проверить свое решение в реальной тестирующей среде, пусть и с дикими ограничениями, помогла бы избежать самой главной ошибки прошлого hola challenge.
Что такое «доступ к тестирующему серверу»? Вы шелл туда хотите, что ли?
Думаю, достаточно простого запуска выполнения на двух тестовых словах, одно есть в списке, второго нет (хотя бы «a» и «zzzz»).
Для того, чтобы убедиться, что файл нормально распаковался и модуль загрузился без ошибок.
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'));

Скорее всего, говорят о возможности попробовать запустить в окружении. Например new Int32Array(buffer) будет вести себя по-разному в зависимости от endianness операционки. Или кодировка регекспов. В принципе это надо знать и так и при написании модуля учитывать, но тем не менее такие ошибки весьма досадные, поэтому идея загрузить, автоматически попробовать и добавить в табличку результатов — идея здравая, так часто делают.

Linux, x86-64.
Примерно так и будет работать наша тестовая система, в общих чертах.
Спустя 2 недели должен сказать, что подход по которому работает данный скрипт тестирования неправильный. Когда я выкачал ~500 Мб выборки с сервера hola я начал замечать, что результаты как-то отличаются от ожидаемых. Еще раз посмотрев комментарии я, кажется, понял откуда у народа берутся такие большие проценты. Ребята, мой вам человеческий совет — очень-очень внимательно смотрите на код, который выдает % успешного распознавания. Это ключевой момент построения хорошего решения.
Если тестировать более правильным скриптом мое 70+% решение превратилось в 62.9%. Благо решений у меня было много, потому я переsubmit'ил одно 70% решение на другое, которое дает уже честные 69.8%. Но даже после этого я не уверен, что методология тестирования у меня правильная. Более того, я не уверен, что она будет совпадать с тем как будут тестировать организаторы.
Новый скрипт выкладывать не буду и объясню почему. ИМХО придумать идею, которая даст хороший процент — не проблема. Более того, большинство годных идей уже и так упомянуты в комментариях. А вот построить рабочее решение — это всё-таки то, за что тут дают деньги. Всё-таки я потратил на это 2 недели свободных вечеров и выходных, потому я, конечно, выложу наработки, но после конкурса.
Поясняю, как мы будем тестировать, чтобы не было необходимости строить догадки. Мы сгенерируем случайную последовательность целых чисел. Далее, используя эти числа как random seeds, мы получим от генератора тестов блоки по 100 слов. (Для простоты, дубликаты удалять не будем.) Мы загрузим тестируемый модуль один раз, проинициализируем его, как описано в правилах, и вызовем функцию test для каждого слова из тестового набора. Подсчитаем процент правильных ответов.

Как будет считаться % ошибок, если в разных блоках встретятся дубликаты?
Допустим, b1: { w1: true, w2: false }, b2: { w1: true, w3: false }, классификатор отвечает всегда true. Набрано 50% или 33%?

В описанном случае результат будет 50%.
Если бы на вход подавались исключительно уникальные слова, то самой выгодной стратегией было бы всегда возвращать «false».
При бесконечно большом числе тестов будет 100% угадываний.

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

Меня тоже удивляют цифры с результатами выше 80%.
Добился пока что 73% на тесткейсе из 100 тысяч слов, есть ещё пара мыслей, попробую, может ещё получится 0.5-1% выжать из решения.
Для сравнения. У меня 8М слов. На 100k было всё еще хорошо. И до 600k у вас всё тоже будет хорошо, а вот где-то на 2M идея очень жестоко обламывается.
Данный подход не совсем верный, насколько я понимаю из кода. У меня самого почти такой же подход — есть два файла — словарь всех слов и чуть больший словарь «не-слов», по которым я прогоняю тесты, затем складываю проценты от обеих проверок, делю на 2 и вывожу как среднее. Т.е. у меня это выглядит примерно так:

Test correct words - 99.7636%
Test incorrect words - 52.0787%
Average correctness - 75.9212%


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

У меня с равной вероятностью выбирается словарь, а потом берётся из него случайное слово. Так что одно слово вполне попадается несколько раз на миллионе-то замеров. Смысла разбивать на группы по 100 слов не вижу смысла.


А вот брать среднее между результатами по выборкам разных размеров действительно нельзя — нужно суммировать число правильных ответов и делить на общее число замеров.

А вот брать среднее между результатами по выборкам разных размеров действительно нельзя — нужно суммировать число правильных ответов и делить на общее число замеров.


Я в начале так и делал, но если грубо взять словарь в 10 правильных слов и 100 неправильных (приближённо к реальности), при этом и там и там будет угадываться 10 слов, то в моём случае будет (100% + 10%) / 2 = 55%, а в случае общего замера будет ((10 + 10) / 110) * 100 = 18.2%, что неверно.

Объяснение же разницы уникальных и неуникальных слов довольно простое — всё зависит от количества false-negative для верных слов, т.к. повторяются именно они в связи с ограниченностью количества по сравнению с не-словами, коих невероятное множество. При 1-2% false-negative результат по сравнинею с проверкой блоков по 100 слов будет лучше, а вот при большем количестве false-negative результат будет хуже в связи с тем, что многие повторяющиеся правильные слова будут считаться неверными.

Так что одно слово вполне попадается несколько раз на миллионе-то замеров

Судя по test[ word ] = wordsIndex[ word ] || false одно и то же слово несколько раз попасться не может, в отличие от блоков по 100 слов. Думаю, что Object.keys( test ).length не выдаст 1,000,000.

Мне нет смысла настаивать на верности или неверности данного способа тестирования, но обратить внимание на этот момент стоит, просто, чтобы быть в курсе возможных расхождений с результатами тестирования блоков по 100 слов.

Совершенно не важно по сколько группировать: по 10, 100 или 100000. Если размер группы одинаков, то общее среднее значение будет одно и то же.


( X/N + Y/N )/2 === ( X + Y ) / 2N

В вашем примере будет ( 10 + 1 ) / 20 * 100 = 55% Так как мы делаем 20 замеров. Или ( 100 + 10 ) / 200 * 100 = 55%, если делаем 200. Чем больше замеров, тем выше точность.


Дублирование слов происходит в этой строчке:


var word = words[ isWord ][ Math.floor( Math.random() * words[ isWord ].length ) ]
> Мы ожидаем, что многие решения будут содержать генерированный, минифицированый, сжатый код или данные, и поэтому просим отправить нам также и исходники решения
Вопрос: это пожелание или требование? Иными словами, будут ли рассматриваться решения, которые минифицированы/обфусцированы (или, например, скомпилированны из другого языка в javascript) без предоставления исходников? Если это требование, то, я считаю, это следует прописать в правилах более чётко.
Если это требование, то вот ещё более тонкий момент: если я, например, сделал и обучил нейронную сеть, которая решает задачу, обязан ли я описывать топологию сети, а так же предоставлять алгоритм обучения и наборы данных, которые я использовал?
По поводу нейронной сети: именно этого мы и ожидаем, да. Это самое интересное. Словами описывать не обязательно, но надо приложить обучающую программу и данные.

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

Вопрос: вдвоем можно участвовать? Приз потом пополам поделить.
Я Вас уверяю, носители английского языка сказали бы то же самое.

Можно.
>Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя)

Уж простите за вопрос, но правильно ли я понимаю, что существует возможность «перекрестного» приглашения? Обычно в таких случаях «приглашающего» заставляют сначала зарегистрироваться самому, а уж потом приглашать друзей с реферальным кодом.
Мы хотели сделать так, чтобы приглашать могли люди, не собирающиеся участвовать сами. Злоупотребления отфильтруем вручную.
Не сочтите за занудство, но подобное обычно в правилах прописывается изначально, именно для того, чтобы действия наподобие

> Злоупотребления отфильтруем вручную.

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

Как я понимаю метод init(data) запускается один раз и дальше запускается только test(word) много много раз? Или же на каждую сотню-блок — все по новой? Сколько будет минимально блоков?
init запускается один раз, test запускается много раз.

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

а если построить структуру типа trie tree, где каждый узел это буквы алфавита и бит, если это слово в словаре. Вероятность принадлежности слова определять как глубину в этом дереве
А сколько места займёт сериализованное trie?
наверно больше чем 64кб. Поэтому его придется отсекать, пока не влезет
Trie дерево, которое вместит в себя 75% слов, содержит 1 миллион дуг. В 64Кб вряд ли влезет :/
Остается заставить программу по тестовой выборке подобрать оптимальное дерево на 64К, которое даст наибольший процент :)
Только сдается мне, что мы решим не практическую задачу «отсекать несловарные слова», а просто подберем алгоритм, который лучше обманет другой алгоритм, генерирующий псевдослучайные слова.
Мне тоже эта задача именно так видится…
Но это же весьма занимательно!
image
Я начал с префиксного дерева как раз. При прогоне тестов можно в узлах подсчитывать частоту, а потом просто отпилить самые «редкие». Но, судя по всему, вариант не самый оригинальный :).
из-за того, что есть очень много повторений в суффиксах и префиксах, то можно создать 2 дерева, одно проверяет слово сначала, другое с конца
Избыточность суффиксов и префиксов эффективно нивелируется gzip-ом (он словарный) без дополнительных телодвижений.
Как ни странно, подход не работает. Второе префиксное дерево очень плохо режет. Т.е. почти нет улучшений точности по сравнению с отдельно взятым первым деревом.
хм, узнал что это очень похоже на Huffman code
1. Есть ли ограничения по географии участников?
2. С учетом того, что проверки после сабмита нет, будет ли дана возможность исправиться, если засабмиченная версия не запустилась или сразу на выход?
Ограничений нет.

Мы описали API настолько подробно, что считаем, что каждый, кто умеет читать условие задачи, вполне может его выполнить.
Зависит ли от чего-то вес ошибки в итоговой оценке? Ошибочно распознанное как английское и ошибочно распознанное как не-английское будут равноценны? Влияет ли длина слова на это?
Никаких весов. Ложноположительные и ложноотрицательные результаты имеют одинаковый вес, не зависящий от длины слова.
Не нашёл информации в условиях конкурса – под какими лицензиями выкладываются присланные работы на ваш гитxаб в конце (например здесь https://github.com/hola/challenge_linked_list/tree/master/submissions). А так же как будут рассматриваться работы, если в них лицензия указана явно?
Вы можете указывать лицензию сами (включите её в архив исходников), но она не должна препятствовать публикации Вашей работы по окончанию конкурса.
Мы ничего не делаем с лицензиями. http://choosealicense.com/no-license/
НЛО прилетело и опубликовало эту надпись здесь
Насколько сносно, если не секрет?
НЛО прилетело и опубликовало эту надпись здесь
Это только половина задачи. Вторая половина — отсеивать неслова.

На словаре ваше решение даёт 51.5% правильных ответов, что на 1.5% лучше, чем function(word){ return Math.random()>0.5; }
НЛО прилетело и опубликовало эту надпись здесь
Тогда какое количество false positives и false negatives?
Для слов вида overzazazing, что выдаёт?
НЛО прилетело и опубликовало эту надпись здесь
В результате вычисления полного списка регулярных выражений, проверяющих на соответствие словарю, как раз и получится возможное представление префиксного дерева этого словаря, которое уже упомянули выше. Причём, не самое оптимальное представление из возможных.
а может и третью функцию добавите, типа `right_answer(word, answer)`
будет вызываться после test(word) и давать обратную связь алгоритму, чтобы он доплнительно обучался во время теста?

Обучите сами. У вас есть все слова которые считаются правильными. И генератор неправильных.

Это будет совсем другая задача.
Мы будем использовать в тестах только ASCII-строки, содержащие латинские буквы нижнего регистра, а также символ ' (апостроф).

Значит ли это, что из словаря будут исключены аббревиатуры? Аббревиатура в нижнем регистре это уже слово (валидное или нет).
Это значит, что весь словарь можно привести к нижнему регистру перед обучением своей модели.
Более того, передаётся на проверку слово в нижнем регистре, а не как изначально. Из-за этого трётся доп. информация — является ли это слово «аббревиатурой», либо именем собственным, либо просто «словом».
Какая разница что это? Просто набор символов. Задание поставлено довольно чётко: проверить вхождение строки в заданный файл.
разница есть, так как есть зависимости между словами. например очень много слов с одинаковыми префиксами
Аббревиатуры могут попасться, но они будут приведены к нижнему регистру.
«Random English Word Generator using JQuery» — куда прикатился мир…
никто не мешает убрать его )
Что взять за основу для генерации слов?
Не понимаю вопрос.
на чем логику построить?
приставка +корень+суф.+окончание или просто наиболее встречаемые в словаре слова(корни) из них генерить.
Или все это рандомом
Или как?
Вы спрашиваете меня, как решать задачу?
подсказку ищу
Оставлю без комментариев.
Советую попробовать 7мислойный ромбовидный персептрон.
Да чо уж там, выкладывайте сразу решение.
подарки в студию )
спасибо меня наверное этому лет 10 учить надо
https://github.com/sebpearce/gleath/blob/master/main.js
Всё-таки очень нужно чтобы можно было проверить рабочий ли submission на конечной машине. Я уже 2 решения отослал с переоптимизацией от closure compiler. Только сейчас заметил когда ужимал мини-решение.

BTW. Тем временем 60,11% в 683 байта и 82.82% в 62464 байт.
Теоретически существует решение в как минимум 90%. Возможно, даже есть 95%.
Присоединяюсь к писавшим выше про список ложных срабатываний. Т.е. должен быть выделен training set и verification set. Это стандарт для задач машинного обучения. Пока я не вижу, чтобы эти выборки были зафиксированы.

У меня получилось решение, которое на диапазоне сидов 0-1000 работало хорошо, расширил диапазон, упало ниже 65%. Тестовый dataset странный предмет, вроде он есть, но на самом деле он бесконечный.

Решение откатил. Качаю dataset по-больше.
А что мешает вам самостоятельно разделить данные на обучающую и тестовую выборки? На сидах 0-1000 учите, на 1000-1500 проверяете.
Получается немного нечестная ситуация. Я имею одну выборку, а другие участники — другую выборку. И тут смотря как кому повезло. А если есть одна выборка на всех, то тут ни у кого нет особых преимуществ.
Все решения мы будем тестировать на одном и том же наборе тестов. Номера блоков мы пока не скажем, кончено.
Никто ж не говорит, что это строго задача машинного обучения. Это один из возможных подходов к ее решению.
Генератор иногда отдает настолько похожие слова что у меня вопрос: вы потом проверяете, что генератор сгенерировал ТОЧНО слово ВНЕ словаря?
Да, проверяем.
Странно, что про генетическое программирование народ молчит.
А ведь в самом топе будет жесточайшая битва, где победит тот кто лучше сбалансирует все свои словари, фичи и прочие признаки, и ужмёт их в 64 КиБ, вместе с исходником.
Все молчат, чтобы не давать подсказок конкурентам.
кришнаиты )
Вангую, что в первой тройке не будет ни генетического программирования, ни нейронных сетей с, прости Господи, deep learning.
будут массивы регулярок

а жаль
Массивы регулярок — результат применения нейросети с deep learning (т.н. головного мозга примата homo sapiens, возможно, не одного экземпляра) к задаче :)
А в итоге — вытягивания словаря из входных данных :)
Мне казалось, что генетическое программирование это обходной путь для полного перебора, вы уверены что этот подход вообще принципиально применим к задаче?
Думаю, что его можно применить для анализа исходного файла с разных сторон, а не в самом решении.
Да даже те же регулярки, если их будет столько много что они не будут умещаться в 64к, то можно будет подобрать такую комбинацию регулярок, которая будет покрывать больше всего правильных слов и давать меньшее кол-во ошибок на не словах.
Да и сами регулярки тоже можно мутировать, скрещивать, чтобы получилась популяция регулярок, которая не была бы избыточной.
Попробуйте написать пару unit тестов :)
Да уж, с первой попытки дало 57% на 10000 слов из тесткейсов. Что-то даже страшно стало представить себе, чем там занимаются те, у кого уже за 80% перевалило :)
Уже 73.6%, после того как проанализировал те слова в которых ошибаюсь, отсеял наиболее часто встречающиеся паттерны.