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

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

Время на прочтение 5 мин
Количество просмотров 73K
Всего голосов 38: ↑34 и ↓4 +30
Комментарии 620

Комментарии 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, а его реализация тоже потребует памяти.
НЛО прилетело и опубликовало эту надпись здесь
> … дающая наибольший процент правильных ответов

ну, в таком случае, можно упаковать часть словаря :)
И это было бы замечательно (и более того — в реальном мире даже сработает !), если бы генерация тестовых выборок у организаторов конкурса использовала частотный словарь, т.е. генерировала реальные слова пропорционально их появлению в реальном мире. А при равномерном использовании шанс получить на входе теста «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%, после того как проанализировал те слова в которых ошибаюсь, отсеял наиболее часто встречающиеся паттерны.
А как можно верифицировать отправляемые файлы? Код написан и отправлен, однако боюсь, что ввиду своей рассеяности где-то сглупил (например, опечатался в названиях методов или перепутал файлы при отправке), из-за чего всё труды пойдут насмарку.
Слова английского языка?! Мне прямо стихи попались:
xv
xvi
xvii
xviii
xw
xx
xxi
xxii
xxiii
xxiv
xxix
xxv
xxvi
xxvii
xxviii
Я чисто случайно Зюганова нашёл в исходном файле (words.txt). Он там почти в самом конце файла.
Если кому-то нужен файл false-set, размером примерно с true-set, можете брать: false-words

Он каким образом получен-то?

Самым тривиальным — через ихний генератор testcase. Это для тех, кому лениво самому парсить json, и ждать пару часов, пока наберётся достаточная выборка.
Я вообще не понимаю мотивации доброхотов, которые подсказывают решения — «а давайте нейронными сетями, а давайте генетическим алгоритмом, а давайте префиксным деревом». Этим людям не нужны 1000-3000$? Зачем вы помогаете прямым конкурентам? -_-
затем, что для программиста деньги — вторичное
Лихо вы за всех расписались, я аж программировать разучился от такого заявления.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Предлагаю другую формулировку: Соцсеть а-ля знакомства. максимум 100Кб, приз за первое место: 1000USD. Так гораздо интереснее.
Выходите с этим конкурсом на главную. И нет, я не шучу сейчас.

У меня как раз есть такое. Кроссплатформенный клиент + бэкенд. $1000 за ребрендинг и вырезание всего лишнего получится. Обожаю свою работу :-D


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

И да, не всё меряется деньгами и первыми местами в конкурсах.
Кооперация — это компромиссы, на которые готовы пойти конкуренты :).
Поддержу. Я вот про фильтр блума из этой ветки узнал, но до сих пор никак не допру, как он работает :)
Попытаюсь «на пальцах» объяснить. Не бейте ногами — аналогия заведомо некорректная, но может помочь понять принцип работы.

В природе существует туча разных молекул.
Перед нами стоит задача перебирать пролетающие мимо молекулы и отбирать только молекулы кислорода (O2) и воды (H2O).
Для этого мы будем использовать фильтр блума:
За первую хэш-функцию возьмем процедуру «получить названия атомов», которая возвращает список атомов, из которых состоит молекула.
Применим эту хэш-функцию к необходимым нам молекулам, и получим результат в виде «О» для первой молекулы и «Н, О» — для второй.

Минимальный фильтр блума с максимальным количеством false-positive в нашем случае будет выглядеть так:
H О
1 1

То есть ловя каждую молекулу и применяя к ней хэш-функцию «получить названия атомов», а затем сверяясь с нашим фильтром, мы ни за что не пропустим ни кислород, ни воду, однако мы «нахватаем» false-positive на таких молекулах как H2SO4, С2H5OH, HCl и т.д. Т.к. в этих молекулах тоже содержится H и/или O.

Для уменьшения количества false-positive, мы увеличим размер фильтра. Для максимального уменьшения false-positive на нашей хэш-функции, расширим фильтр до полной таблицы Менделеева.
В итоге мы получим подобный фильтр для наших O2 и H2O:
H He Li Be… O F Ne… Nb Mo…
1_0__0_0_..._1 0 0__… 0__0…

Теперь наш фильтр не пропустит молекулы С2H5OH и HCl, поскольку при применении к этим молекулам хэш-функции «получить названия атомов» мы получим результаты «C,H,O» и «H,Cl».
Пытаясь сверить «C,H,O» с нашим фильтром мы увидим, что, в нем хоть и установлены биты на местах H и O, но также не установлен бит на месте «С», Что говорит нам о том, что в списке того, что нам нужно, этой молекулы точно нет.

Однако у текущего нашего фильтра все еще будут случаться false-positive на таких молекулах как O3 и H.

Для решения этой проблемы мы введем вторую хэш-функцию вида «получить количество атомов в молекуле», которая будет возвращать количество указанных атомов в тестируемой молекуле.
Она будет применятся после сразу основной на каждом атоме из списка, возвращенного первой хэш-функцией. Наш фильтр тоже увеличится и будет теперь выглядеть примерно так:

H1 H2 H3 H4 H5… He1 He2 He3… O1 O2 O3 O4 O5…
0__1__0__0__0_..._0___0___0__..._1__1__0__0__0…

Этот фильтр уже не пропустит H, потому что после применения обеих наших хэш-функций к этой молекуле мы получим позицию «H1», для которой в нашем фильтре бит не установлен.

Стало хоть сколько-то понятней?
П.С.: Шрифт не моноширинный, парсер жрет пробелы, простите за извращения с "_"
Благодарю, аналогия прекрасная, моноширинный шрифт не проблема :)

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

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

900 килобайт — это более 7 мегабит, что даёт крайне высокую точность в фильтре блюма для 600 килослов.

смотря что называть «приемлимой точностью»

300Кб для блюма дает точность больше 90%
60Kb — около 70%

Приемлемая точность — 99%. У меня с разными ухищрениями получилось 900 килобайт, то есть значительно больше 64. И это только данные, без кода.
я думаю в этой задаче приемлемая точность будет гораздо ниже 99%, и почти уверен что меньше 85%.
Я тоже долго не мог допереть. Логичеки вроде понимаю отдельные куски, а сложить в целую картинку не получалось. Может поможет https://www.jasondavies.com/bloomfilter/ — тут наглядно визуализировали работу фильтра Блума.
Кто говорит — не знает, кто знает — не говорит.
Скорее всего далеко не все, кто пишет, участвуют — так что просто высказывают свои мысли по этому поводу.
я не собираюсь участвовать в конкурсе, потому что я не верю что выиграю и жалко на это тратить время, но пообсуждать в решении задачи очень интересно.
Зачем люди отвечают на StackOverflow? Зачем люди пишут статьи на хабр?

И да, я сомневаюсь, что человек, который первый раз услышал про нейронные сети/генетику/префиксные деревья только что, имеет шанс успешно воспользоваться этим «советом» :)
Проверил. В списке нету слов из words.txt.
Совпадения с моим списком 55012
Различия 614277 (т.е. в 11 раз больше)
Список претендует на то, что он был получен честным способом.

Я уже организаторам говорил «а давайте всё-таки один общий false dataset». Ну вот. Теперь есть как минимум 2 dataset'а, которые отличаются друг от друга.
Только одно замечание. Наличие дубликатов.
626919 — без дубликатов
669289 — с дубликатами
Некоторые по несколько раз, например, overwort
Какие тесты качались? Брались подряд или с помощью редиректа на случайный тест?
По ходу тупо рандом, т.к. у меня первые 100k и набор другой.
В вашем false-set 20532 повторов.
Просто к сведению.
Для моих алгоритмов так и надо, мне нужны именно неочищенные данные.
Пытаешься атаковать генератор? У меня такая идея была, но отбросил. Мне кажется что выхлоп генератора еще более изотропный чем словарь.
У меня нашлось 43370 дубликатов. но я их lowercase сходу делал.
Непонятно, где вы нашли эти 43370 дубликатов, потому что в файле caveeagle всё и так в lowercase.
У меня вопрос к организаторам: сколько всего «не-слов» у вас сгенерено?
Хочу скачать их все, но надо же знать когда остановиться.
Они реально генерируются в момент запроса. У нас не хранится какого-то запаса не-слов.
Выходит что на «не словах» тренировать программу бесмысленно?
Я этого не говорил.
Я знаю что не говорили. Спрошу немного по другому — ваш алгоритм генерации не-слов может генерить бесконечное количество не-слов, или есть какой-то предел?
Понятно, что есть только конечное число слов любой ограниченной длины. Практически достижимых ограничений нет.
Немного забавной, хоть и бесполезной статистики.

Сумарно с сида 1 по 254200 всего встречается 10'041'446 уникальных не-слов, и 630'403 словарных слов. В словаре всего 630'404 слова, и единственное, которое до сих пор не встретилось — «constructor». С момента обнаружения последнего уникального слова в сиде 175475 прошло уже 78725 сидов. Для сравнения, чтобы найти предпоследнее слово, потребовалось всего 4475 сидов, в 17.6 раз меньше.

Так что есть хорошая вероятность, что слово «constructor» не встретится в выдаче вообще никогда.
It probably has something to do with a «constructor» property of javasctipt objects. Looks like a bug.
Я выполняю парсинг Python-овским json.loads(), а ему глубоко пофиг на специальные свойства JavaScript-а. Так что если баг и есть, то не на моей стороне.

Проверил на node.js для очистки совести:
> s = JSON.stringify({constructor: "foobar"})
'{"constructor":"foobar"}'

> JSON.parse(s)
{ constructor: 'foobar' }
Возможно, для набора с «constructor» генератор вернет 99 слов, а не 100.
В исходном файле words.txt есть слова, которые отличаются лишь регистром (например, ABEL, Accra).
Их не так уж и мало — приблизительно 31 000, привожу скрипт (mysql) для их выборки:
	SELECT word, COUNT(*) AS quality
	FROM words_good
	GROUP BY LOWER(word)
	HAVING quality > 1

Думаю, их стоит исключить из списка, поскольку по условиям задачи все слова будут в нижнем регистре.
Об этом уже писали. Словарь дается «как есть», проверяться все слова будут в lowercase безотносительно того, в каком регистре они были в словаре.
Самому сделать не судьба?
Вы предлагаете организатору конкурса сделать работу за конкурсантов?
НЛО прилетело и опубликовало эту надпись здесь
Теперь это codegolf-тред.

cat words.txt | sort -fu | tr A-Z a-z > words_dedup.txt
У меня на два непробельных символа короче :)
Useless use of cat

sort -fu words.txt | tr A-Z a-z > words_dedup.txt
cat words.txt | sort -unique > words_dedup.txt
Тогда уж sort -unique < words.txt > words_dedup.txt, но мой sort не знает -q.

А мой шелл не знает < :-)


строка:1 знак:14
+ sort -unique < words.txt > words_dedup.txt
+              ~
Оператор "<" зарезервирован для использования в будущем.
    + CategoryInfo          : ParserError: (:) [], ParentContainsErrorRecordException
    + FullyQualifiedErrorId : RedirectionNotSupported
Хреновый шелл у вас
Я немного подостыл к задаче и особо нет времени дальше биться за проценты. Поэтому выкладываю свои дилетантские, далекие от всяких Блюмов и нейросетей, размышления. Может кого-то натолкнут на свежие мысли.
1. Собираем статистику по длине слов на выборке в 1 млн. и выясняем, что простейшее if(strlen > 20 (или около того)) return false; else return true; дает что-то порядка 60% (точную цифру не сохранил).
2. Если тупо проанализировать словарь на отсутствующие 3-х буквенные комбинации с привязкой к длине слова и позиции относительно начала слова, то без всякого ИИ можно получить порядка 72%. С помощью перфиксного дерева можно много комбинаций запихнуть в 50+К, на код останется порядка 14К, вполне достаточно.
3. Любопытно, хотя и ожидаемо — анализ из п.2, но по контрольным суммам дает 50% :) Алгоритм расчета контрольных сумм дает равномерность распределения.

Не имел опыта работы с нейросетями, но общий смысл представляю так: Есть некий набор входных параметров, влияющих на выходные. При этом у каждого входного параметра есть некий весовой коэффициент, от которого зависит, насколько он влияет на результат. Весовые коэффициенты подбираются эмпирически в процессе обучения. Многослойность и т.п. — это уже детали, можно разобраться при желании. Но встает вопрос. Выходной параметр в текущей задаче это есть/нет в словаре. А что можно взять за входные параметры? Длину слова? Префиксы/постфиксы? Ну т.е. буквально на пальцах какие такие признаки будет искать этот пресловутый ИИ в мешанине слов и недослов?
Вопрос про «буквально на пальцах» (о том, как моделировать задачу и как представлять фичи) как раз и является основной сложностью применения машинного обучения (в любой задаче). Ответ на него будет достоин написания отдельной статьи (после конкурса).
Я подозревал, что в этом месте подвох :)
я начал с самого простого — задал каждую букву как параметр. Получилось 67%

Интересно попробовать adversarial networks
Добавлю немного своих размышлений и результатов исследований:
1. Используя префиксное дерево, дающего 100% результат удалось добиться размера 845Кб
2. То же префиксное дерево, но с результатом 98% весит уже 784Кб
3. 89% — 474Кб
4. 85% — 356Кб
и т.д…

Данная статистика наглядно показывает зависимость размера от результата.

Использование фильтрации по неиспользуемым сочетаниям букв даёт нулевой результат — 3-х буквенные неиспользуемые сочетания занимают 12Кб места, а толку от них 0, т.к. в выборке сгенерированных «неправильных» слов размером в 500тыс слов (ссылка в комментах выше) ни одно из этих сочетаний не используется.

Попытки найти какой-либо шаблон в словах, который бы использовался в словаре, но не использовался бы в сгенерированных словах, не удались. Сгенерированные слова слишком похожи на слова из словаря, а слова из словаря слишком разные. Например, слова с 5 согласными буквами подряд встречаются в словаре 1053 раза, а слова с одной и той же буквой 3 раза подряд встречаются 109 раз. При этом данная статистика бесполезна.

Следующим шагом была попытка использования масок для слов, например, 010101100 — где 0 — гласные, 1 — согласные, либо маски, сгруппированные по буквам, например, проверка одного и того же слова сразу по нескольким маскам, использующим различные группировки букв. Толку от подобного подхода слишком мало — опять же из-за сильной схожести сгенерированных слов со словами из словаря.

Наибольший результат достигается использованием фильтрации по первым буквам слов — для 3 букв при размере 17.5Кб результат — 57%, для 4 букв — 89Кб и 64%, для 5 букв — 73% (размер не смотрел). Использование префиксного дерева позволяет уменьшить размер — 3.5Кб для 3 букв, 24Кб — для 4 букв, 89Кб — для 5. Отсекая малоиспользуемые префиксы для 5 букв можно добиться результата в 71% при размере 60Кб (мой лучший результат). Попытка дополнительно учитывать длину слова и/или конечные буквы значительно увеличивает размер, при этом мало влияя на результат. Например, попытка использовать 2 префиксных дерева по 4 буквы для отсечения слов и с начала и с конца, даёт 66% при размере 58Кб, 5 с начала и 3 с конца — 71% при размере 67Кб. Выводы можете сделать сами.

Думаю, что нейронные сети могут найти более хороший подход к решению данной задачи, однако каким образом можно будет запихнуть результат обучения подобной сети в 64 Кб — не имею ни малейшего представления.

P.S. когда я увидел возможность упаковки 6.3Мб словаря в 100Кб, я был очень удивлён, но у меня появился стимул. Очень жаль, что это оказалось усечённое префиксное дерево :(.
Прошел через все описанное, более-менее. Кроме фильтрации по первым трем (4-5) буквам (делал прямо сейчас) — спасибо за стат по этому подходу. Теперь не стану.
Осталось добавить что попытка использовать описанные алгоритмы совместно, не дает хороших результатов, так как множества слов по которым алгоритмы отрабатывают имеют мощные пересечения и если каждый алгоритм дает скажем 57% то совместное применение разве что 58%.
Что до упаковки… как только мы пытаемся применить какую-то допобработку к словарю, степень сжатия результата сильно уменьшается. Мне например удалось ужать словарь что-то до 4,8Мб без потерь, но в итоге упаковался он в те же условные 100Кб.
Что в общем логично, так как любая уменьшающая словарь допобработка уменьшает его избыточность, а меньше избыточность == меншь степень сжатия.

: (
Например, слова с 5 согласными буквами подряд встречаются в словаре 1053 раза, а слова с одной и той же буквой 3 раза подряд встречаются 109 раз. При этом данная статистика бесполезна.

Не скажите. А сколько раз слова с 5 согласными встречаются среди «не слов»? Если их в разы больше, это вполне можно использовать.
Добавление подобной проверки не дало ощутимой разницы при тестировании на 12К случайных слов, но ради интереса я проверил в словаре «неверных» слов и результаты интересны:

Total words: 598216
Words with 5 consonants: 68502 or 11.45%
Words with 3 same letters: 2835 or 0.47%

Против статистики «верных» слов:

Total words: 630404
Words with 5 consonants: 1053 or 0.17%
Words with 3 same letters: 109 or 0.02%

Так что я ошибался — проверка на 5 согласных подряд должна добавить несколько процентов.

Добавлю сюда результат проверки для 4 гласных подряд:

Correct words with 4 vowels: 2447 or 0.39%
Incorrect words with 4 vowels: 6467 or 1.08%
Всего лишь нужно эти правила научиться подбирать автоматизировано, и ваша программа превратится в machine learning.
Теория и практика:
— теоретически проверка 5 согласных подряд даёт дополнительно несколько процентов
— практически результат улучшился всего на 0.08%
Я думаю что нейронные сети смогут эффективно отличить только шум и слишком непохожие слова. Чтоб отличать похожие слова, они должны их запомнить, а тут уже места не хватит.
тут описан интересный алгоритм , который ужимает префиксное дерево:

Step 1:
image
Several steps later:
image
Подобная идея приходила мне в голову, однако подобное усечение повторов сведет эффективность «бесплатного» gzip'а к минимуму.

Как бы там ни было, скорее всего в итоге вы будете в небольшом выигрыше. Все зависит от того, как вы изначально сохраняете trie в файл — попробовать стоит.
Думал об этом, но не получилось — ужимается дерево в памяти за счёт повторного использования узлов, но есть 2 «но»:
1. дерево ужимается в памяти, но не при сериализации (главный аргумент)
2. последние уровни усечённого дерева настолько разные, что смысла ужимать нет

Также думал о побитовом сжатии — использовать биты вместо 26 букв и апострофа, тогда вместо потенциальных 27 байтов можно использовать 4 (3 при усечении алфавита). И это действительно даёт преимущество в сериализации 2-3 первых уровней, где используются практически все буквы из алфавита, но на на последних уровнях, которые заканчиваются на 1-2 возможные буквы, это преимущество оказывается избыточным. Усечённое дерево, обычно сжимаемое до 60Кб, с использованием битовой маски превращается в 200Кб
Пока что я пришел к выводу, что никакие хитрые алгоритмы не помогут отфильтровать похожие слова, и это натолкнуло меня на мысль посмотреть сколько есть похожих слов, насколько они похожи, может даже понять как они генерируются и можно ли это использовать.
Похожесть я смотрел по Levenshtein distance, и вот некоторые результаты:
29% не-слов отличаются от словаря на одну букву, 20% на 2, 12% на 3, и так по убыванию…
В случаях когда есть одно отличие, то в 60% поменяли букву, 30% добавили букву, и в 10% убрали.
В 17% меняли букву а, 9% букву b, 7% d,c,e. потом r 5.5%,l 5.3%,' 5.3%,n 4.3%,s 4.2%…
В 43% менялась первая буква, 11% 2 и 3я, 9% 4я…
В тех случаях когда добавляли или удаляли букву, то значимых отличий не наблюдается. Буквы s,e,a,i,' добавляются чаще остальных, e,a,i удаляются.

Очень любопытный факт, что если смотреть на похожесть слов в словаре между собой, то в 72% слов она равна 1, 24% равна 2, 3% равна 3, 1% 4, и гораздо меньше 1% в остальных случая.

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

Надеюсь, после конкурса будут предоставлены исходники генератора (чтобы убедиться в его «равномерности» на всех номерах блоков), а также доказательства случайного выбора номера блока для финальной проверки (а также того, что этот номер был выбран непосредственно перед зачётным тестом).
в условиях не сказано, но могут ли организаторы поменять алгоритм генерации во время конкурса?
Если они не гарантируют неизменность генератора и случайность выбора тестового блока, то наиболее универсальным решением окажется самый простой фильтр Блума без эвристик, а все старания «машинных лерненгистов» сольются (если принять, что полный словарь заведомо невозможно сохранить в 64КиБ, а все эвристики заведомо опираются на явные и неявные закономерности в поведении генератора «несловарных» слов, от которых и нужно отличить «словарные»).
из-за того, что 50% не-слов очень похожи на словарь, то универсальное решение не будет самым лучшим.
наиболее оптимальным, на мой взгляд, будет что-то типа:
отсеять непохожие слова с помощью эвристики, регулярок, сетей ит.д. | проверить похожие слова в Блуме
Всё верно, именно об этом я и говорю: универсальное («агностическое» к генератору) решение не будет содержать эвристик, а неуниверсальное — будет содержать эвристики, подходящие только для этого конкретного генератора (ну, или некоего их класса, в зависимости от «ширины» эвристик).
И это нормально. В реальной жизни оптимизируемые места тоже содержат эвристики, подогнанные под поток входящих данных.
«Мы будем генерировать тесты тем же генератором, который описан выше. Мы сгенерируем некоторое количество блоков по 100 слов. Решения всех участников получат одни и те же наборы тестов. Мы возьмём столько блоков по 100 слов, сколько потребуется для того, чтобы с уверенностью различить между результатами тройки призёров. […] Вместе с результатами конкурса мы опубликуем начальные значения псевдослучайного генератора, которые мы использовали для тестирования, и исходный код генератора тестов.»

Почему разочаруются? Probabilistic data structures с их характеристиками и выбором оптимальных параметров и без того детально изучены. Очевидно, что в решении будет одна из них + эвристика, полученная в результате аналитики, знаний или обучения.
Вряд ли кто-то ждёт, что весь словарь удастся засунуть в чудо-структуру размером 64кб.

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

Я вот попробовал прогнать словарь с помощью функции metaphone (Функция metaphone была написана Lawrence Philips и описана в книге [«Practical Algorithms for Programmers», Binstock & Rex, Addison Wesley, 1995].), получился словарь не порядка 660 тысяч слов, а уже порядка 250 тысяч. При этом % угадываний на тесткейсах колеблется между 75-80%.

Хеши от 660 тыс. слов у меня получилось ужать в 429K (только данные), новый словарь пока не пробовал ужимать.
И ещё такой момент, список хешей можно отсортировать, а затем привести к одинаковой длинне в битах и эту таблицу вместо длинного столбца развернуть в несколько строк, эти строки лучше жмутся.
В 95K жмётся словарь пропущенный через metaphone.
Если сохранять не последовательности, а только смещения чаркодов, т.к. данные изначально отсортированы, то получается 84K.
При таком сжатии получается на 10 тысячах слов из тесткейсов следующее:
success: 81.53%
negatives: 100%
positives: 0%

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

success: 68.15%
negatives: 0%
positives: 100%
но идея очень красивая, я уже порадовался за вас, 80% это хороший результат
Очень крутой результат. Добивался такого же только с помощью аналогичных же ошибок в счетчиках.
Ещё были мысли, в хеш зашивать доп-информацию о слове, например, биты отвечающие за чётность/нечётность числа обозначающего длину слова, и т.п.
Но у меня получается, что на 1 хеш приходится довольно много срабатываний разных слов, поэтому эту идею пока что забросил.

Уже приблизился к такому результату:
success: 69.5%
negatives: 32.79%
positives: 67.21%

Тут ещё мысль пришла, можно ведь выбрать некое число бит под хеш, полный список всех хешей можно сгенерировать скриптом в отсортированном порядке, затем погонять тесты так, чтобы собралась некоторая статистика true и false срабатываний по каждому хешу. Затем всему этому списку хешей можно в оконцовке поставить бит 0 или 1, в зависимости того как часто срабатывало попадание слова в словарь. Ну и в итоге достаточно будет хранить лишь 1 бит на хеш, т.е. в 64к поместится 512000 бит. Например, мой словарь который получился по metaphone+crc32 уже можно уместить без потерь, даже не применяя gzip сжатия.
При таком подходе хэш от слова должен быть 18-19 бит, т.е. всего 262144 — 524288 возможных хэшей что сравнимо с количеством слов в словаре с обработкой или без нее. Т.е. у вас будет приходится примерно по 1 слову на 1 хэш при использовании качественной хеш-функции. А это значит каждый нолик будет давать false negative.
Ненастоящие слова будут распределены по всем возможным хешам тоже примерно равномерно и вряд ли вам удастся выделить небольшое количество хешей, на которые приходится много попаданий из ненастоящих слов так чтобы проставить им нули.
У меня хеш 20 битный.
Тогда это порядка миллиона значений, которые вы даже по 1-му биту на каждый в 64к файл не поместите.
Есть же gzip из коробки.
Ну попробуйте) У такого файла избыточность будет нулевая, ни один архиватор ему ничем не сможет помочь.
И вообще, то что вы описываете, по сути, и есть фильтр Блума, только с одной хэш-функцией.
Кто-то минусанул все мои комменты в этой ветке, а мне ведь удалось ужать все 20 битные хеши без урезаний + прочие данные в 61КБ.
И порядка 3400 байт занимает код.
Судя по -1 кому-то одному не понравились комменты в этой ветке. А так — крассавчик
А Вы уже добились результата больше заявленного ранее 69.5%?
Да, добился.
Запостил своё 74+-1% решение:

solution.min.js (1439 B)
data.gz (63761 B, gunzip before use)

Ещё (65535-63761-1439= 335B в запасе осталось).
Надеюсь, всё правильно сделал.
удачи!
если это даст стимул и поможет улучшить, то у меня результат получился больше 75.5%
У меня тоже есть решение дающее больше 75%, но там пару килобайт не вмещается, но есть идеи как сделать чтобы вместилось. В общем, ещё не пятница :)
Имея 20 бит на хеш, получим 1.048.576 (2^20) возможных комбинаций ~ 128Kb, которые ещё нужно ужать до 60-62Кб, т.к. не нужно забывать про место и для кода, который должен эти данные обрабатывать.

Если получится всё уместить в 64Кб, то дальше будет борьба за каждые сотые доли процента ;)
Ну пока что мне удалось уместить это в 72КБ.
Вообще, можно и нужно функцию хеширования переделать. А потом уже можно будет эксперементировать с обрезанием части хешей, чтобы запихнуть всё содержимое вместе с исходниками в 64КБ.
У crc32 слишком много хешей от не слов пересекаются с хешами от слов.
Чтобы получить ровно 64Кб, достаточно использовать 19-битный хеш — тупо обрезаем один бит с начала или с конца. Немного магии архиватора и получим дополнительно пару Кб места для кода. Правда на сколько процентов при этом пострадает результат сложно сказать, но могу предположить 2-3 процента от текущего результата.
19 бит слишком не хардкорно, хочется 20.
так и будет
ИМХО, было бы неплохо ради спортивного интереса, если бы один из спец призов достался тому, кто сумел бы упаковать решение, дающее 100% результат, в наименьшее количество байт. Только через форму данное решение не отправить, т.к. подобное решение наверняка превысит 64Кб
Ну это менее интересная задача. И требует только подхода в сжатии информации. В оригинальной же задаче все намного интереснее — тут надо пораскинуть мозгами.
В таком виде задача совсем неинтересна. Жёсткое ограничение по размеру выключает привычку огромного количества программистов пытаться добиться недостижимого идеала (в последний день перед публикацией мы снизили лимит с 256k до 64k, поскольку компрессия всего словаря в 256k казалась в принципе возможной), а оптимизация по проценту корректности смещает акцент со знаний потрохов технологии и перебора алгоритмов сжатия в сторону размышления над алгоритмами.
Полностью поддерживаю ограничение в 64Кб — задача поставлена очень интересно и требует много размышлений и проб. Поэтому я и не предлагаю назначить какой-либо из главных призов, чтобы большинство программистов продолжало пытаться уложиться в 64Кб, но в то же время интересно было бы посмотреть сколько места может занять программа, выдающая 100% результат.

Или можно будет где-то организовать доску с результатами попыток сжатия, но уже без финансовой мотивации — чисто ради интереса.
задача поставлена верно, а что касается
> сжатия, но уже без финансовой мотивации — чисто ради интереса.
то я бы ограничился
cat words.txt | gzip --best > data.gz
Не знаю как Вы, но мне было бы интересно посмотреть на решение, занимающее 256Кб. Зип жмёт словарь в 1.62Мб. С использованием префиксного дерева мне удалось сжать решение до 825Кб, и верю, что это не предел. Т.е. тут влияет не только архиватор, но и способ хранения. В любом случае, решать не мне, и, скорее всего, я предложил слишком поздно.

Мой коллега предложил гениально-простое самое маленькое возможное решение, которое будет давать 100% результат — это сгенерировать md5 хеш от словаря, и затем восстановить весь словарь перебором. Жаль, что ограничение по времени — 1 неделя :)
это не гарантирует 100% восстановления
Если использовать чисто хеш — да, из-за коллизий. Но можно уменьшить вероятность коллизий практически до 0 задав исходный размер строки и, при необходимости, ещё какие-либо дополнительные параметры. И, конечно же, протестировать решение до того, как отправлять. Т.к. строка будет генерироваться в той же последовательности, это гарантирует факт, что решение, протестированное локально, будет работать так же и на тестовом сервере.
Всё равно не получится. Размер словаря — 6906809 байт. Число текстов такой длины — 2^(6906809*5) (я взял грубо 5 бит на символ). Число различных возможных значений на выходе функции MD5 — 2^128. Среднее число текстов длиной со словарь, приходящихся на одно значение хэша — 2^(6906809*5) / 2^128 = 2^34533917. Если эти тексты пронумеровать, то номера будут иметь длину свыше 4 мегабайт. Вы можете задавать дополнительные предикаты, позволяющие сузить поиск, но размер кода, реализующего необходимое количество проверок, скорее всего, будет больше 64 килобайт.
В чем профит этого решения? Тратить процессорное время в пустую, чтобы получить искомый хэш словаря и сам словарь, который по не нулевой вероятности будет отличатся от исходного?

Напоминает анекдот, когда девушка идет к гинекологу из-за проблем.
Доктор: Тут болит?
Она: Нет
Доктор: А тут?
Она: Нет
Доктор: Тут?
Она: Да!
Доктор: О, милочка, это у вас гланды!
Уже который раз подобный способ сжатия предлагают на хабре (и не только) — не понимаю, откуда берётся вера в то, что магическим образом можно сжать любые данные почти до нуля? Не важно, какое время компресии/декомпрессии, всё равно нельзя в общем случае сжать любой файл размером 10 Мб даже до (10 Мб — 10 байт), просто потому что количество файлов большего размера во много раз больше.

Да, конечно во всех реальных случаях сжимаются не произвольные данные, но такой способ всё равно даст огромное количество коллизий, как ни крути.
На самом деле все не так однозначно. Соглашусь, что «любой файл размером 10 Мб» сжать в пару байт не выйдет, но только в том случае, если между данными нет зависимостей (ну или если они нам неизвестны). К примеру файл с 10 миллионами цифр числа пи после запятой вполне можно сжать до нескольких байт, просто сказав что там 10 миллионов знаков числа пи. Тут такая же ситуация, возможно между данными в словаре есть зависимости которые позволят ужать исходный словарь до 64 КиБ (вместе с кодом который на основании этих зависимостей все распакует обратно). Но я честно сомневаюсь в этом ;)
Даже теоретически это работать не будет, так как множество других строк дадут такой же MD5, как словарь.
Ответил выше ns5d по поводу коллизий. Но невозможно тут по другой причине — слишком долго.
Да нет. Увы, проблема с коллизиями так просто не решится. Вы можете задать ограничение на такую же длину, можете добавить сколько угодно дополнительный проверок (например, совпадение первых и последних 1000 символов словаря) но до тех пор, пока размер информации меньше, чем наиболее оптимальное сжатие словаря (в 64к без потерь не вмещается) все равно будут коллизии равные объему нехватки информации.
Моя идея была в том, чтобы сгенерировать вначале словарь локально и, если натыкаюсь на коллизию, продолжать генерировать дальше, запомнив количество колизий, которое нужно пропустить до генерации нужной строки. Это как один из вариантов. Но похоже, что число коллизий, которые нужно будет пропустить, хотя и на много порядков меньше 2^34533917, но всё же довольно большое.

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

уважаемый feldgendler, разрешено хранить часть кода в файле данных?
Да.
Правильнее бы было обратиться к провайдеру за разъяснением причин, по которым он настолько неправомерно себя ведёт.
Hola представляет решения для обхода блокировки естественно провайдерам это не нравятся, вот и блокирует.

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

Вопрос такой: а обучающие выборки прикладывать к нему? Они достаточно большие. С одной стороны надо, потому что без них аналогичный файл не получить. С другой стороны — если на github будете выкладывать, ему поплохеет от такого количества файлов.

Лучше скрипты, которыми Вы их получили.
Попробовал другой вероятностный алгоритм,HyperLogLog, который к сожалению показал плохие результаты
HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset

Идея была в том чтоб хранить весь словарь в hll, в тесте добавлять туда слово и проверять если изменился общий счетчик. Для 64Кб hll ошибается на 0.15% в оценке общего кол-ва слов, но для проверки одного слова этого недостаточно

А сколько результат в процентах получается? У меня, каким бы методом я ни пробовал, 64Кб даёт среднюю точность 70% ± 2
Bloom filter — 70%
HLL — 60%
Вы же выше писали о 84%
Выше я писал про общий результат, тут про отдельно взятый алгоритм
Можно уточнить, 84% результат при ограничении в 64 КиБ?
к сожалению нет, эта цифра была до оптимизации и никак не получилось достичь что-то похожее с ограничением 64К
Жаль, в ином случае вы совершили бы чудо :)
я еще не сдался :)
Эх, очередная цель опровергнута. Может у кого-то всё же получится совершить чудо — упаковать весь словарь в 100Кб или добиться >= 80% :)

Я уже неделю как застрял на 76%, всё пытаюсь выжать очередные 0.2-0.5% в надежде как-нибудь добраться и до 80%, но пока тщетно. Правда теперь я уже не уверен насколько мои проценты «честны», прочитав комментарии выше по ошибке проверки точности алгоритма.
я тоже надеюсь у кого-то получится особый результат. Будет обидно проиграть из-за разницы типа 0.001%
Можно ли считать, что код будет выполняться не в strict mode? Т.е. можно ли использовать при минификации оптимизации, которые будут в strict mode выдавать ошибки?
Если напишете «use strict», будет strict mode. Если не напишете, не будет.
Результаты machine learning:

попробовал стандартные алгоритмы — decision tree, random forest, gradient boost trees и нейронные сети. Фичеры особо не выбирал, взял сами буквы и разные счетчики. Все алгоритмы дали примерно одинаковые результаты, около 65%, причем нейронные сети показали хуже всего.
Наилучший результат достиг с помощью GradientBoostedTrees, 73%, с помощью 100 деревьев глубиной 10, но я не уверен что получится их ужать в 64кб

Сейчас проверяю очень интересную идею с помощью deep learning. Надеюсь она не оправдает себя, так как не представляю как можно потом перевести код python и theano в javascript
Deep learning:

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

Картинки
image
image
image


В этой работе используют CNN чтоб классифицировать текст твиттера и его хештеги по его сентиментальности, и в принципе, простой заменой данных на наш словарь можно попробовать этот алгоритм (нужен python и theano). Код на гите
Алгоритм показал 64% при начальных параметрах, и вполне возможно добиться более лучших результатов если настроить несколько hyper parameters. К сожалению, у меня компьютер не настолько мощный, и theano лучше бежит на GPU — поэтому я это оставил.

Understanding Convolutional Neural Network for NLP — еще одна хорошая статья на эту тему

Character-level Convolutional Networks for Text Classification — Похожая работа, но использует для прогонки lua и Torch. Запустить не получилось.

И еще в копилку deep learning, можно упомянуть RNN, рекуррентная нейронная сеть. Один из крутых специалистов, Andrej Karpathy, в своей статье описывает как ее можно использовать для похожих задач.
The Unreasonable Effectiveness of Recurrent Neural Networks

Тут можно посмотреть как с помощью RNN предсказывают следующую букву в слове. Кстати, в его гите много библиотек для machine learning, написанные на javascript, в том числе cnn и rnn
Просто закину сюда немного информации, чтобы отвлечь конкурентов. :)
http://lbd.udc.es/Repository/Publications/Drafts/1441181386528_practical_compressed_string.pdf
compression ratios of 5%, 10%, and 30% can be achieved

конкуренты нервно курят в сторонке
Чтоб до 1% сжать, нужны impractical compressed string dictionaries.
Жаль нет специальной номинации за лучшее соотношение %/размер
Так бы можно было запостить решение на 66.978 % в 1714 байт
Или 66.093 % в 979 байт

Или 50% в 0 байт ;-)

В 0 байт не получится
Самый минимум 18 байт
module.exports=/!/
Т.к. Регулярка имеет функцию test, то всё пройдет нормально
exports=/!/
Ваше решение не проходит тест скриптом, который опубликовали организаторы, а мое проходит.
Т.к. организаторы не делают честный require
Таки да, вы правы :)
Оно не пройдет и с честным require — при подобном присваивании перезатирается ссылка exports и модуль ничего не экспортирует.

Минимум всё-таки 17 байт: exports.test=w=>0

Итак. Есть две новости.
1.
75.57-75.36 % (Реально если протестировать на большой выборке будет где-то 75%, ИМХО)
59989 байт
Решение подобрано используя OpenCL
2. Решение ломает ЛЮБОЙ скрипт тестирования где-то на 18-й 23-й тысяче запросов.
Воспроизводится на 6.0.0 и на 6.1.0
Ломает в смысле вызов функции приводит к зависанию. Тестовый console.log внутри функции даже не вызывается.

Потому вопрос к организаторам. Как быть?
Скажите ID засланного решения, мне надо увидеть, в чём там дело.
UPD. Работает на node 0.10.38
75.19%
На 8684372 слов время тестирования 03:57:45
Эта скорость еще приемлема для решения?
Вполне.
Решения принимаются до 27 мая 2016, 23:59:59 UTC.

Я правильно понимаю, что по Москве это 28 мая 02:59:59?
Да. Форма закроется и перестанет принимать решения.
Я отправил решение, а как проверить что оно корректно отработало на ваших серверах? Не хотелось бы из за какой-нибудь мелочи потерять несколько дней работы
Скрипт не поможет, если, например, случайно отправить не тот файл.
Воспользуйтесь тестовым скриптом. Мы ничего не запускали ещё.
Уважаемые организаторы! Об этом нигде не написано в посте, поэтому обращаюсь к вам с просьбой, которую остальные, надеюсь, поддержат.

Пожалуйста, после того, как закроется форма для приема решений, и обычный человек уже ничего не сможет изменить — опубликуйте все присланные решения (js + данные + объяснения) на гитхабе? Если вам так будет удобнее, то выложите их без указания авторов, просто под какими-то ничего не значащими номерами, чтобы имя победителя до последнего оставалось в тайне.

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

Спасибо.
Насколько я знаю, результаты будут опубликованы вместе с отправленными решениями так же, как и в предыдущих конкурсах: https://github.com/hola?utf8=%E2%9C%93&query=challenge
Мы выложим все присланные решения.
После завершения конкурса лично я, например, ещё и на своем гитхабе планирую выложить своё решение. Возможно, будет удобно, если организаторы в своем репозитории сошлются на него как на подмодуль.
В агонистических попытках увеличить процент в последний день конкурса наконец-то решился на «крайность» — попробовать отфильтровывать непроизносимые сочетания согласных. Поиск в гугле не дал каких-либо универсальных алгоритмов, которые можно было бы применить, а те, которые имеются, слишком сложны в реализации (и для понимания, и в размере реализации тоже).

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

И такой фильтр даже работает, но итоговый результат получается хуже из-за того, что реализация занимает место и приходится жертвовать чем-то другим. Если бы генератор генерировал больше случайных последовательность букв, возможно этот вариант бы и сработал, а так слишком много «не-слов» практически не отличиются от «слов», что делает подобную проверку бесполезной (в моём случае).
У меня в false positive вообще 90% слов не отличимы от оригинальных, т.е. дальше ловить нечего.
Примерно так же и у меня было когда я анализировал слова. Основная проблема в том, что слишком мало различий не-слов от слов. Можно только шум отфильтровать. Произношение вряд ли сможет помочь при таких ограничениях — есть много не-слов которые вроде нормально произносятся. Скорее всего выиграет какое то гибридное решение, т.е. проверка на шум + еще доп проверки.
И сколько процентов получилось если не серет?
По моим замерам 81 с копейками.
Я ещё вчера порубил слова из словаря алгоритмом Ляна-Кнута, но не успею уже проанализировать этот момент на сочетаемость слогов.
Ну вот и я оказался в потенциальной яме.
На одном миллионе тестовых слов 82.05% на другом 82.1%
Все последние изменения, которые я пробовал сделать, приводили к увеличению максимум на +0.01%. Это очень мало, буквально в пределах погрешности. Т.к. я выбрал медленный алгоритм, то ожидание генерации файла и проверка на миллионе слов превратились в пытку :)
Скрипт тестирования неправильный, однозначно :)

Я думал, что 82% достижимо, но так и не смог добраться — остановился на 81%. А миллион тестовых слов — это 10.000 блоков? Или всё же 1 миллион уникальных слов?
10 000 блоков.
интересная статистика генератора, которая помогла улучшить результат на 1.2% двумя строчками кода:
так как кол-во слов ограничено, то на 60,000 блоках кол-во повторений почти 45%, из которых 39% это слова и 6% не-слова.

Публикую это потому что это все-таки хак, а не интересный алгоритм, да и зависит от кол-ва блоков в финальном тесте
Почему хак? Мы же не вылезаем за пределы виртуальной машины, никаких модулей и пр. не грузим. Самообучение, ничего криминального. Проблема в том, что в начале идет провал, и помощь приходит только на большом расстоянии от старта. Да и не стоит забывать о памяти, в общем любое решение тут будут одни компромисы. У меня этот подход составляет часть решения.
Не смог не удержаться и опубликую свою глупость здесь: как последний студент, я сидел и оптимизировал свой алгоритм до последнего, свято веря, что у меня 23:59 по UTC будет в 4 утра… Только это оказалось в 3 утра. Случайно заметив это без 15 минут (я решил зайти на utc часы онлайн) я побежал экспортировать свои функции init и test))

Зато меня порадовало сообщение (на часах 02:59), что «Вы можете публиковать еще и еще свои решения до наступления deadline»...)))
Я правильно понимаю, что по Москве это 28 мая 02:59:59?


Я не зря выше переспросил ;) Сам отправлял за час до закрытия ибо уже было все равно.

Отправил результат с 83.5%.


график

(собран на свежей выборке, официальный скрипт выдаёт такой же результат)

круто! интересно узнать как получилось добиться такого результата

Заменил группы префиксов и суффиксов, отфильтровал непроизносимый мусор по статистике 2х-буквенных комбинаций, длине, стоп-словам, повторам и количеству гласных-согласных, проверил существование первой тройки. Остальное (а это стало 280k слов) в bloom filter, из которого удалил редко используемые словами, но часто используемые не-словами биты.
Префиксы-суффиксы подбирал скриптом, с которого можно было периодически собирать "урожай". Судя по тому, что % продолжал расти на 0.1..0.2% в день вплоть до последнего дня, я сильно сглупил, можно было начать делать раньше.
Напишу пост, если не очень далеко в рейтинге буду. В топе вполне может быть 86..88%. Возможно, есть даже 90.

Напишите обязательно! Я делал почти тоже самое, и тоже дошел до уменьшения слов до около 300К+ для скармливания их блуму, но так и не успел разобраться, как сохранить результат в <64k. В лучшем случае получал 120. Напишу об этом во второй части статьи.

Мой самый эффективный способ сжатия фильтра блума состоит в том, что сначала переводим его в символьное представление по 8 бит на символ, а потом сжимаем его через lzma — даже с учетом 7 килобайт кода на распаковку я выигрывал в среднем около 2кб по сравнению со штатным сжатием gzip. Его я тоже применяю сжимая уже заархивированный фильтр вместе с кодом для его распаковки и другой логикой решения. Фильтр естественно уже не жмется, а вот код худеет еще на 3кб.
У меня почти такое же решение, все аналогично кроме «удалил редко используемые словами, но часто используемые не-словами биты.». Остальное все то же — замена аффиксов, мусор по 2 символа, длина, гласные согласные, мелкий блум на первые 3 символа. Но я видимо поленился подбирать параметры лучше, или где-то накосячил, так как у меня 80.6%. Но все что вы описали — ровно такой же алгоритм. В мой большой блум на 61000 байт я запихивал 250к слов

Их удаление дало 2%. Параметры потом подобрал оптимизатором за пару дней.

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

Вот этот момент не ясен, я тоже так сначала начал, но по факту оказалось, что я подстраиваюсь под обучающую выборку не-слов. Решил что это не очень хорошо и перестал, видимо зря. Возможно для больших выборок это уже получается подстройка не на обучающую выборку, а на зависимости в генераторе, что имеет смысл. Мой вариант в начале набирает около 80%, но он учится по пути, если можно так сказать, и скажем на 10 миллионах вполне показывает результат в районе 85%, а на 20 миллионах ближе к 90%, вот только вопрос станут ли организаторы действительно тестировать на большом кол-ве блоков.

В ошибках много повторов, поэтому это может дать результат.


учится по пути

Интересно. Он действительно учится, т.е. меняет правила, по которым работает? Как он корректируется: по количеству ошибок на 100 слов? Интересная идея, я о ней думал, но сделать не смог.

Все прозаичнее, я пользуюсь тем, что слова в словаре идут в ограниченном объеме. Т.е. я коплю входные слова и дубликаты считаю за слова из словаря. На определенном этапе алгоритм ограничивает длину слов в 16 (остальные считает плохими), где-то после 20 килоблоков он переходит на ограничение в 13 и его начинает вытягивать накопленная статистика. Каждые 50 килоблоков увеличивается показатель того, что считать дубликатами (начиная с 100 килоблоков), поскольку не-слова тоже начинают заметно дублироваться.
В общем график приблизительно такой:
https://www.dropbox.com/s/q93jus7g056kyjm/res.png?dl=0
Это на 200 килоблоках (20 миллионов слов)
У этого метода есть минус — большой провал в начале, не смог его никак побороть. Мое первое решение давало около 81% на всем протяжении, т.е. выигрывало у этого в начале, но сливало в конце, поэтому я решил рискнуть и отправил все же это, в надежде что организаторы будут тестировать на большом кол-ве блоков и я успею догнать фаворитов раньше, чем прекратят тестирование ;). И как выясняется вариант с 81 точно ничего бы не выиграл даже близко, так что у меня остается шанс.

Нет, у меня в начале провала нет, среднее по 1k стабильно на всём протяжении. Я не рискнул копить статистику, интересно, прокатит ли такое решение, поглядим.

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

Очень хороший результат получился, если организаторы не против, как вы ниже пишете, тогда круто. Эх, надо было тоже спросить, я не догадался.

Хорошая идея с префиксами и суффиксами.

Судя по тому, что удалось понять, глядя на «неправильные» слова — они все (за исключением мусора) сформированы по принципу [префикс]основа[суффикс] (префикс и суффикс опциональны), а все префиксы, основы слов и суффиксы получены из словаря.

Например:

enzedrinesiancy = [enzedrines] + iancy <= [b]enzedrines + [r]iancy
testabaxilement's = test + [aba] + xilement's <= test[s] + [b]aba + [e]xilement's

Кажется, что префиксы и суффиксы строятся откусыванием кусков, которые сами по себе входят в словарь, а основы слов — откусыванием полученных префиксов и суффиксов. Впрочем, уверенности нет, да и в моем решении это никак не помогло (у меня 81.1%).

Ага, тоже заметил такую особенность генератора. Поэтому префиксы/суффиксы я не выкидывал, а заменял на другой из группы. Например, micro=>macro, gravi|aero => gyro.

Что вы подразумеваете под «стоп-словами»?

Если найти наиболее частые части слов, можно проверить то, что до/после них. Например, bilit[^iya]: в словах 10, в ошибках >150.

С нетерпением жду опубликования вариантов решений
Очень круто, я подозреваю что ваш алгоритм в результате поиска лучшего решения подстроился под особенности генератора.
у меня получилось 77.5%, и набиралось еще 1.2% на 50К блоков если запоминал слова в тесте, и возвращал true если это слово уже было (после 3000 блоков)

словарь я никак не обрабатывал, мне было интереснее попробовать больше алгоритмов. Сначала взял каждую букву как параметр в machine learning, и добавил еще другие: длина слова, кол-во гласных, согласных, их отношение. Местоположение апострофа с начала и с конца, перед и после какой буквой он идет. Средняя сумма частот букв в слове. Конволюцию (свертку) с окном в 3 буквы.
После этого попробовал все стандартные алгоритмы классификации, и наилучший результат по отношению к размеру показало дерево решений: глубина 7 и 250 узлов дало 66.3%. Дерево заняло 1.2Кб, сам код тоже немного, а остальное место использовал под bloom filter, взяв первые 6 букв слова. Это решение ушло в hola.

Другие решения:
Лес деревьев решений (100 штук) вместо 66.3% давали 72%, но размер был очень большой. Нейронная сеть с 100 нейронами в Spark mllib показала 65%, а в Azure ML почти 70%, но у меня не получилось вытащить этот слой, или повторить результат в open-source frameworks. А жаль, имплементация нейронов очень простая, и 100 штук ужималось как одно дерево. В последний момент даже поднял 2 виртуалки в Azure на 32 ядра каждую, но особо результат не улучшили.

Были еще попытки deep learning на theano и torch, но все бежало очень медленно, так как не было сильной графической карты.

Кроме machine learning я пробовал построить префиксное дерево, получилось слишком большим. Была еще попытка анализировать расстояние между словами и построить автомат Левенштейна, где все слова представлены как граф, и для проверки слова надо было взять все узлы с его начальной буквой, и попробовать найти путь с этим словом (благо времени достаточно). Предварительные результаты были хорошие, но постройка минимального графа для всех слов бежала почти бесконечное время.

Почти все опыты проводил на scala в кластере Spark, или локально на C# с помощью Accord.Net. Фичеры и алгоритмы, их hyper parameter tuning, сравнивал в Azure ML
Схема обучения в Azure ML
image


Огромное спасибо организаторам за бесценный приобретенный опыт и интересное время!
Влияние памяти на результат
image
У меня совсем другой результат получился: https://www.dropbox.com/s/q93jus7g056kyjm/res.png?dl=0
Это на 200 килоблоках (20 миллионов слов)
я столько блоков не проверял. Даже не поверил что можно дойти до 90%, это впечатляет
Все зависит от возможностей базового алгоритма, ведь он вытягивает то, что статистика пропустила.
в какой-то момент кол-во не-слов начинает замусоривать алгоритм. или надо ставить счетчик, и смотреть уже трешолд по нему?
Да. Начиная с 10 миллионов каждые 5 миллионов слов надо увеличивать на 1 кол-во дубликатов.
0-10М — слова это те которые повторились 2 и более раз
10-15М — те которые 3 и более раз и тд.

А вообще каждые 5 миллионов можно было проходить по статистике и у всех уменьшать счетчик на 1, а те которые стали 0 — удалять. Тогда алгоритм не выйдет за память никогда и в итоге даст число максимально близкое к 100% на бесконечном наборе входных данных. Но я все это отправлял в торопях и писалось все в полубессознательном состоянии уже, поэтому этого не сделал.
Сейчас скачал другую выборку, потому, что ту которую использовал до этого собирал из чего было и видимо напортачил немного (не было времени выкачать столько данных). Новая настоящая выборка дала несколько меньший результат, в общем будем ждать результатов тестирования ;)
В соседней ветке https://habrahabr.ru/company/megalenta/blog/302020/#comment_9632518 меня уже обошли ;)
Я просто оставлю это здесь.
Судя по комментариям участники не брезговали использовать читерскими методами подкручивания статистик.
Например накопление словаря или статистик аргументов вызова функции.

Т.к. цитирование переписки с организаторами здесь поощряется, то
Некоторые детали запуска скрипта
Действительно, на каком-то по счёту блоке компилятор-оптимизатор V8 вешается. Какой-то баг в версии 6.0.0. Если такое будет в с финальными решениями, будем решать вопрос или об апгрейде версии Node.js, или о разделении работы на несколько запусков программы.


Я ничего не берусь говорить, но читая предыдущие отзывы о конкурсах от hola, я специально очень сильно расспрашивал про методику проведения и оценки. Я пока сделаю гипотезу, что скрипт, который будет проверять решения будет сбрасывать состояние решения каждого участника каждые 1000 блоков, к примеру. Потому все решения, которые базируются на запоминании потока вызовов внезапно превратятся в тыкву. У меня в кармане тоже были читерские методы подкрутки решения, например корректировка до априорной вероятности, но я не рискнул их включать в решение из-за боязни изменения условий тестирования в последний момент. Ждем комментариев от организаторов.
Организаторы в условиях задачи указали, что init будет запускаться один раз. Не соглашусь с вами насчет читерства, ведь мы не вылезаем за пределы ВМ, многие алгоритмы работают по принципу корректировки по накоплению ошибки и пр., т.е. используют историю для улучшения своих результатов. Я бы назвал это самообучением в процессе. Вообще конечно решение за организаторами.
Главное, чтобы решение не вылетало за пределы 512 Мб оперативки. (Кажется такой дефолтный лимит по памяти)
Мне очень интересно какую методологию тестирования будут использовать. Насколько я понял минимальным гарантированным квантом является один блок по 100 слов.
Постараемся обойти баг по-другому и не перезапускать.
Я задавал этот вопрос организаторам. Мне дали ответ что они не возражают против такого решения.
мне тоже не нравится этот метод, и я не включил его в финальный скрипт. Но я постарался опубликовать его, как только обнаружил, чтоб и остальные могли решить для себя
Кроме того, априорная статистика это не совсем читерство и вполне соответствует правилам и даже условию задачи
А если немного подкрутить генератор, например, чтобы он давал 20% слов из словаря и 80% неправильных слов, то «читерские» решения опять же окажутся тыквой. А «честные» покажут примерно тот же результат.
организаторы обязались не менять генератор
Да, я знаю. Просто интересно было решать задачу в более общем виде, а не подстраивать под генератор. Например, можно собирать статистику разных комбинаций букв по словарю и отбрасывать редкие варианты. Количество всех вариантов получается небольшим, а отбрасывание редких сильно уменьшает выборку. Но вот если взять множество всех возможных неправильных слов, то их количество на порядки (даже экспоненциально) больше. И в общем случае нет возможности отсеить редкие комбинации. Тут как раз и возникает соблазн собирать такую статистику по неправильным словам из генератора. Жаль, что я так и не решился на это.

Это не работает. Редкие комбинации эффект дают, но не решающий.

У меня это сильно сокращало объем сохраняемых данных. К примеру, берем все 4-х буквенные префиксы слов. Всего их, допустим, 70000. Если отбросить редкие, получаем всего 10000 префиксов. Объем сохраняемых данных уменьшается с десятков килобайт, до нескольких килобайт. На результате тоже сказывается, но не так сильно. И это очень хороший эффект. А вот всех возможных неправильных четырех буквенных префиксов 531441 — 70000 = 461441. И понять, какие из них чаще встречаются в неправильных словах можно только собрав статистику по генератору.

Я это всё делал, но пришел к выводу, что большинство генерируемых слов – "псевдонеправильные". Ну невозможно описать правилами большинство неправильных слов типа "numismatograph" и "troid".

Нет, не покажут, у многих false-positive гораздо выше false-negative, оно и понятно, генерируемые слова очень похожи на слова из словаря (если откинуть явный шум) и по фонетике и по морфологии. Так что у всех просто снизится процент, не более.
Мне это решение тоже пришло неожиданно в последний день конкурса во время прогулки с собакой. На этом гулянка сразу закончилась.
Главное, что мне непонятно, — как Вашему решению поможет самообучение, если тестовая система не сообщает ему правильные ответы?
Так он же не использует эти данные. Там ищутся повторы, предполагая, что с большой вероятностью повотор — это слово, что вобщем-то логично, так как словарь ограничен, а неСловарь — нет. Чистая атака на генератор.
Будет забавно, если лучшее решение окажется ещё и самым маленьким.
Я буду локти кусать, потому что сразу отбросил идеи анализа генератора и исходил из того что решение будет получать всегда только одно слово на проверку и умирать. Так же решил что false-negative быть не должно вообще.
Почему вы думаете что организаторы конкурса будут запускать тест на таком огромном количестве блоков?
Как то мне это 50/50, если они на это решаться — вы в топе.
В любом случае будет много негатива с обеих сторон, какой бы путь не был выбран.
Мы будем тестировать именно так, как обещали. Это было частью условия задачи. Не вижу в таком оригинальном подходе никакого мошенничества. Действительно, для классификатора, отличающего шум от сигнала, повторяющиеся элементы — скорее сигнал, чем шум. Не вижу причин этого не использовать.
Анализ генератора все равно производится во многих решениях, пусть и в неявном виде. Т.е. ищутся зависимости которые присущи не-словам, это точно также атака на генератор. Перебор параметров для блум фильтра или обучение нейросетей это та же самая задача атаки на генератор.
Выглядит как читерство, но идея классная, жаль сам не додумался :)

В голову приходит только ограничение максимального количества блоков, чтобы не дать собрать статистику, либо действительно перезапускать init через какой-то интервал.

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

Подскажите, я правильно понимаю, что есть как минимум несколько решений в котором словарь «вытягивается» из генератора? В моём представлении мы просто считаем слова и те которые чаще попадаются, мы считаем словами. Количество слов известно. А значит на большом наборе данных мы его можем полностью восстановить. А имея в каком-то моменте полный словарь мы будем угадывать слова 100%. И дальше процент угадывания будет только улучшаться и стремиться к 100%? То есть будет несколько решений стремящихся к 100%? Они и заберут 3 места, да еще и пойми, кто первый.
Имхо, организаторы конкурса в курсе этого изъяна в тестировании. Для того, чтобы подобное решение не сработало, достаточно ограничить количество блоков со словами, или можно запустить несколько тестов используя фиксированное количество блоков, затем вычислить среднее (что немного не совпадает с условиями запуска функции init только один раз).
По моему где-то тут в комментариях читал, что организаторы для начала возьмут 1000-2000 блоков по 100 слов, но сейчас не смог найти, видимо отредактировали тот комментарий.
Возможно это было где-то тут: https://habrahabr.ru/company/hola/blog/282624/#comment_8887076
Поправьте меня, если ошибаюсь.
Это было в дополнительной статье к конкурсу
На мой взгляд это не изьян, а свойство, которое прямо выводится из условий конкурса. Оба решения легитимны, но проблема в том что оно позволяет организаторам манипулировать результатами.
Мне, конечно, нравится решение с алгоритмами, да и уверен что участники потратили гораздо больше сил, времени и проявили больше смекалки, чтоб выжать лишнюю долю процента. С другой стороны также признаю что конечный результат у второй группы гораздо выше.

В общем, запасаемся попкорном 3е июня…

(Надеюсь, что победит гибридное решение, которое стартует с 85% и доходит быстрее всех до 100)
В таком случае, получается, что сместился акцент конкурса. Вместо соревнования на определение максимума слов, получилось соревнование на скорость, с которой достигается максимум. А сам максимум будет зависеть от количества тестов. Это как в спорте. Вместо того, чтобы соревноваться, в весе поднимаемой штанги, будут соревнования по количеству подъема штанги определенного веса. А все участники, кто вообще не может поднять этот вес, автоматически отсеиваются. Я из тех, кто отсеился ) Буду с интересом наблюдать за поднимающими штангу )
Я бы попробовал настоять на том, что соревнования все таки о весе штанги.
получилось соревнование на скорость

Организаторы ничего по этому поводу еще не решили.
А такое есть? Я в комментах не видел.
По условию конкурса написано «Мы возьмём столько блоков по 100 слов, сколько потребуется для того, чтобы с уверенностью различить между результатами тройки призёров». Если у кого-то решение стремится к 100%, то он всегда может утверждать, что было взято недостаточно блоков для его алгоритма. И действительно, повышение кол-ва тестов будет улучшать его результат. Ну и, конечно, понятие «на большом количестве слов» у всех разное.
Я бы сказал, что эти решения претендуют на спецпризы «за чрезвычайно оригинальное решение». Но проблема остается в том, что кроме своей чрезвычайной оригинальности они ещё и результаты показывают значительно лучшие, чем чистые (pure — по аналогии с pure functions) решения.

Организаторы конкурса были на высоте. Вовремя и корректно отвечали на вопросы и все такое. Но все же один минус есть. Я считаю, правильным было бы указать точное количество слов, на котором будет проходить тестирования. Формулировка "Мы будем тестировать Вашу программу на большом количестве слов" не является корректной. 1 млн. — это большая выборка? или 100 млн большая? — все относительно. Получается, зная алгоритм работы всех программ участников, организаторы сами могут выбрать победителей просто меня объем выборки. Это точно также, если судья двух боксеров (один который молотит как из пушки первые 3 раунда, а потом остается без сил, а второе менее активный в начале и более выносливый), решит судья, что 3 раунда будет (ВО время боя) — победит первый боец, решит что 5 раундов — второй. Было бы правильней предупредить обоих бойцов о количестве раундов ДО начала боя. А так, больше никаких замечаний к организаторам нет. Они молодцы.

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

Условия конкурса должны быть таковыми, чтобы каждый участник мог проверить решение другого и признать, что его хуже или лучше. От судей должно требоваться только запустить все тесты и взять 3-ку лучших. Более того, хотелось бы видеть предварительный результат своего решения (просто, чтобы удостоверится что тот файл отправил и тому подобное). Не нужно менять правила на ходу. Достаточно учесть замечания участников (если они объективны) и в следующем конкурсе не допустить подобного. А сейчас организаторы поставили себя в неудобную ситуацию, где в любом случаю будут недовольные. Я же стремлюсь к таким условия, где я и любой другой смогут признать свое поражение и не искать себе оправдание типа "если бы организаторы взяли другую выборку или объем данных я бы точно победил!". Все должно быть максимально прозрачно!

Согласен, но то, что случилось уже случилось и всего предусмотреть невозможно. С другой стороны, следующий конкурс будет еще более продуманным. А вообще ничего страшного я считаю, мне уже честно все равно кто победит. Просто хочу сказать организаторам спасибо за возможность поучаствовать в интересном конкурсе, получен определенный опыт, его я уже точно не проиграю )
Сейчас всё и есть максимально прозрачно. Мы написали, как конкретно будет проходить тестирование. Конечно, мы не могли заранее опубликовать число блоков, потому что смысл тестирования на большом числе в том, чтобы различить между лидерами, которые, скорее всего, будут идти ноздря в ноздрю. Заранее мы не могли знать, сколько блоков для этого потребуется.

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

Все конкурсы разные, и в каждом можно найти какой-то изъян, что-то, чего не предусмотрели.
Я думаю что основной прокол произошел вот тут «нет ограничений по памяти или по скорости работы». Надо было задать определенные пределы. С другой стороны по опыту ACM прекрасно помню, что решить задачу определения сколько памяти расходует решение крайне проблематично.
По памяти ограничение есть, оно встроено в Node.js. С настройками по умолчанию это 2 ГБ (для кучи).

А чтобы сформулировать ограничение по времени выполнения, пришлось бы в точности описывать тестовую систему: железо, ось, настройки всевозможные. То есть вернулись бы к вопросу «как справедливо измерять производительность», от которого хотелось уйти.
Соглашусь. Я думаю что вы все равно как-то разрулите эту ситуацию. В любом случае, спасибо за конкурс, было очень интересно участвовать, уже жду следующего!
Ограничение по памяти тут тоже может оказаться причиной трудностей в судействе.

Допустим, одно из решений падает (из-за переполнения памяти, например) после 1 миллиона тестов, другое — после 2, третье — не падает никогда. Непонятно, как быть, если все три решения при этом постоянно улучшают свои результаты при длительном тестировании.

Дотестировать до 1 миллиона, до 2 или до какого-то большего числа? Для упавшего решения брать последний результат или 0?
Решения не должны падать. Они должны быть способны работать бесконечно. Участники, которые решили накапливать в памяти неограниченно возрастающий объём информации и никак его не прореживать по старости, подставляются под дисквалификацию.

Посмотрим, на самом деле, насколько распространённой окажется эта проблема.
Вот тут моё решение могло бы спасти всех с участников с «чистыми» решениями.
У него скорость ~50 слов в секунду, плюс обещание тестировать решения на одинаковых блоках :)
Сейчас немного жалею, что не отправил решение со скоростью 10 слов в секунду и +0.1%.
Это без VM? Всего 4млн. слов за сутки получается.
Это с VM

Все это понятно. Критика (пожелания) были направлена не на то, чтобы обвинить организаторов в чем-то, а на то, чтобы задание описывалось на основе системы тестирования. Т.е. в начале должна создаваться система тестирования. На этом этапе Вы смогли обнаружить простые вопросы типа: а сколько памяти? а сколько времени? а сколько выборки?.. и только после того как система тестирования готова, описывать задание. Ну я бы поступил так (задним умом мы все сильны). Что дает такая система? Если на каком-то этапе обнаружится, что система работает не совсем корректно или что-то не учитывает, Вы исправляете и заново прогоняете решения. Может мои идеи утопичны и/или я плохо мысли выражаю.

Мы опубликовали тестовую систему. Сейчас стоит вопрос о том, надо ли её исправлять и тем самым менять заявленные изначально условия тестирования.

давайте новый конкурс! мне понравилось)) хочу еще.

Заметим, что чем интереснее задание конкурса, тем сильнее уходит на вторичный план финансовая составляющая победы. Мне кажется, это — здорово!
Да! Главное — это соревновательный дух. Решать задачу в одиночку скучно и уныло. А когда ее решают сотни других людей, хочется, чтобы именно твое решение оказалось лучшим.
Кстати, есть же открытые задачи, за которые даже есть награды. Например, поиск чисел Мерсенна.
Как то участвовал в решениитакой бесплатной задачи. Хоть и бесплатно, хоть и простая числодробилка, но, блин, интересно от того, что задачу еще кто-то кроме тебя решает.
тогда уж ProjectEuler.net
есть куча соревнований на Kaggle. И формат там очень удобный, надо предоставить только результаты на тест группе, и неважно каким способом решается задача. И видно сразу на каком месте находится решение.
Спасибо за ссылку.
Да это было очень круто! ))) Люблю нетривиальные задачки )
В новых конкурсах можно применить краудсорсинг:
Прописать в условиях, что в течении какого-то срока (скажем первая неделя из 4х) условия могут уточняться.
За неделю силами самих участников какая-то часть неоднозначностей будет устранена.
Если бы мы написали, что условия могут уточняться, то получили бы кучу негатива по этому поводу, потому что всем хочется прозрачности и предсказуемости.

Единственное, что может обеспечить проведение конкурса без скандалов, — это предвидение всех проблем с тестированием, — а это невозможно.
Самым лучшим выходом из положения, ИМО, было бы проведение двух отдельных тестирований — с перезапусками и без перезапусков — и публикация двух отдельных рейтинговых таблиц.
И тогда победители по каждой из версий будут уверен, что призы должны получить именно они.

все равно на версию, может просто определить объем выборки равной количеству слов в словаре (640K)

С достаточно большой вероятностью, топ-3 в обоих рейтингах совпадут :-)

вероятность совпадения дробнынх чисел (процент правильно угаданных) стремится к нулю

Я имел в виду, что не проценты совпадут, а имена участников.

Мозги другим заняты, не сразу сообразил.


А так да, согласен. Может зря холивар разводим.

согласен

Интересный конкурс! Спасибо и авторам и участникам, комментарии буду, наверное, неделю читать. Тоже решил поучаствовать. Так как я работал с распознаванием текста, для создания универсальной системы автодополнения текста, в курсе об устройстве спам фильтров и как создаются дорвеи и что противостоит им, — мне показалось, что я с лёгкостью решу эту задачу. И я решил её, — используя знакомые мне сети Маркова, в моем решении можно указать какую точность вы хотите получить, — вплоть до 100%, — но, увы, сжать решение до такого компактного размера (в 20 раз), как я не мудрил — не получилось. Так что отправлять, конечно, не стал.

Я хотел бы ответить на комментарий @hellosandrik, — это всё же задача обучения, — может ей быть! Самообучающийся алгоритм способен распределить грамматические и синтаксические правила языка, — просто оценивая вероятность появления буквосочетаний. — И это не очень сложно для создания, но трудно для анализа и весьма ресурсоемко может оказаться, — вероятностные сети охочи до памяти и процессора. В естественном языке есть правила и исключения, этому нас даже в школе учат, — так вот правила — статистически классифицируются, а вот исключения нет. Мои сети при размерах образцов в три символа прекрасно отбрасываю всякий шум, но псевдослова начинают хорошо определять при размерах сэмпла в 4 символа, а это значит что дата-файл уже будет не менее пол мегабайта, при размере сэмпла в пять символов достигается оптимум, сеть полностью распределят правила языка (и это коррелирует с длинной корней, суффиксов и префиксов в словах). Я проверял следующим образом — давал программе половину словаря, но результат классификации не менялся, давал ей четверть словаря, и т.д. наступает момент когда обучающей выборки недостаточно, чтобы определить вероятностные законы языка, — это тонкий порог, определим лишь эмпирически.
Я бы с удовольствием посмотрел на ваше решение.
Подготовлю код для паблика и опубликую завтра)
Как-то затруднился код задокументировать, там всего-то решение на 50 строк)
https://gitlab.com/richtrr/qualifierWords.git
Сети Маркова кажутся очень красивым и интересным решением, мне тоже интересно посмотреть

Что же касается «задачи обучения», то я пришел к выводу что ни одно решение не будет лучше чем узко-направленного анализа словаря и битовой оптимизацией на уровне блюм фильтра. Максимум, что у меня выходило это 72% (в 64 Кб рамках)

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

Немного не по теме, но опубликуйте, пожалуйста свои приложения в альтернативных маркетах или выложите просто в открытый доступ. А то как-то странно получается – я хочу скачать приложение для андроида, чтобы пользоваться сервисами гугла в забаненном гуглом регионе (Крым, например). А куда ведёт ссылка на установку с вашего сайта? В Гугл-плэй, который в этом случае недоступен. Такое "тонкое" издевательство в итоге получается?

Здесь есть прямые ссылки для скачивания: http://hola.org/download

Спасибо. Но, тем не менее, надо сделать это более очевидным, т.к. я даже при запасе позитивного настроя и желании установить найти где скачать и установить на андроид-устройство так и не смог. Кнопка "скачать" просто никак не реагировала на нажатия. Беглый анализ ajax-запросов, к сожалению, ничего полезного не дал.
p.s. Господа, желающие минусануть в карму, эти мои комментарии на текущий момент являются самым полезным, что получила компания Hola из своих постов c конкурсом – обратную связь от реального потенциального пользователя.

если открывать с устройства, то ссылок нет.
Андроид 6.0, Nexus 5:
image
image