Вступление

ICFPC – это контест, на котором команды в течение трех суток пытаются решить какую-то одну забавную задачу по программированию. Язык программирования, который использует победившая команда, признается лучшим языком программирования года до следующего контеста. Я о соревновании узнал впервые в начале этого года, случайно увидев ссылку на него на википедии со статьи про TopCoder, и очень захотел попытаться в нем принять участие. В тот момент информации о контесте 2010 еще не было, а потом я че-то зафтыкал и забыл. Так бы я его в общем-то и пропустил, если бы мой бывший одногруппник Кирилл не написал мне на Вконтакте, что он собирает команду для участия в нем, и приглашает меня принять участие.

 Я относился к этому скептически, потому что собственно я хотел писать на C#, а ребята собравшиеся в той команде – линуксоины.  Моно все еще нормально .NET 4.0 не поддерживает. Или, по крайней мере, найти такое Моно, не очень легко. Но вариант писать с командой победил просто потому что это казалось более интересным. Про язык пока думать не хотелось. В команде два человека писало на Ruby, и один на С++.

Готовясь к контесту мы завели, как видимо и почти все команды, хранилище кода н github, завели дашборд на EtherPad, настроили Jabber-конференцию (Все-таки в конце концов мне пришлось его завести. Оказалось безболезненно – в миранде он как выяснилось есть по дефолту, без необходимости ставить плагины :о))

Контест по моему времени начинался в пять утра в пятницу. Я встал где-то около семи...

День первый, Пятница

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

Итак, чтоже от нас хотят. Ссылка: (http://icfpcontest.org/2010/task/) У нас есть машины и топливо. Машина состоит из чемберов, чемберы состоят из двух пайплайнов – верхнего и нижнего. Пайплайн по существу – лист чисел от 0 до 5. Так же каждый чембер является либо основным, либо нет.

Топливо – это от одной до шести квадратных матриц произвольного размера.

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

После прочтения этого это можно сразу забыть на пару дней :о) Потому что дальше начинается самая жопа. И машины и топливо задаются в тернарном формате. Про него известно то, что он тернарный, описывает числа, листы и туплы, и что он может описывать бесконечно большие числа и бесконечно длинные листы. И все :о Ну и еще у вас есть пример машинки, описанной в тернарном формате, но не более того. В этом и есть весь шарм ICFPC и его отличие от соревнований типа SRM или Marathon – вы даже не знаете, ЧТО вам надо решать :о)

Далее, на этом организаторы тоже решили не останавливаться. Чтобы делать топливо, нужно строить фабрики. Фабрика – это граф, где у каждой вершины (гейта) есть два входящих ребра, и два исходящих (порядок ребер важен – то есть если поменять два входящих ребра местами, получится другая фабрика). Порядок вершин тоже важен: если ребро идет из вершины с меньшим номером в вершину с большим, то результат передастся моментально, иначе только на следующий такт.

Ну и фабрику надо выводить в специальном формате, который тоже не описан, но дан пример фабрики, описанной в нем. Также дана последовательность. Скармливание этой последовательности на данную фабрику даст нам некоторую ключевую последовательность. Любое топливо должно начинаться с ключевой последовательности.

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

Многое не понятно? Не беда, мы чуствовали тоже самое :о)

Задача контеста – засылать топливо для существующих машин. Точнее, засылать фабрики, которые его производят. Чем меньше команд кроме вас поставляют топливо для заданной машины, тем больше профита вы будете получать за нее каждые 15 минут. Чем короче фабрика (чем меньше у нее вершин), тем больше вы будете получать профита с нее.

Окей. Задачу прочитали, надо думать :о) Все что у нас есть в начале – это возможность засылать фабрики на сервер и смотреть, какой тернарный аутпут она дает, если на вход ей подана секретная входная последовательность, лежащая на сервере.

Собрав несколько фабрик руками, мы поняли, что без визуального редактора нам не жить. Как написать визуальный редактор, чтобы он запускался и у меня на винде, и у ребят на линухе? Qt мы допустим не знаем. Ок, на ум пришло JavaScript + HTML5 Canvas – Firefox-то есть у всех.

Начинаю писать. Время где-то 9:15 утра. В 10:00 утра на работе митинг. Пытаюсь успеть, но необходимость позавтракать, умыться, и, собственно, дойти до работы, сыграли свою роль.  Я успел буквально только набрать в Bing “html5 canvas tutorial” и по уроку сделать, что клики по канве рисуют гейты, складывая их в массив.

Дальше я бегу на работу, митинг проходит не очень продуктивно, так как я, под видом записей заметок, обсуждаю с ребятами фабрики в джаббере :о)

После митинга я за час заканчиваю редактор фабрик (да, это оказалось не так просто :о)), и мы начинаем тестировать. Не очень быстро, но становится понятно, что гейт – это функция тернарная функция f(x,y)=>(x,y), и мы постепенно начинаем восстанавливать  эту функцию засылая разные фабрики. Когда функция восстановлена, я прикручиваю к нашему редактору на JavaScript эвалуейтор фабрик, который по последовательности на входе и фабрике генерит ее выход. Получаем “key sequence” – тернарку, которая должна идти в начале любого топлива. Вот это уже было тупо. Редактор на JavaScript было премлемо, но любой код, который может пригодиться потом – это было тупо. В это же время примерно один из участников команды – Бегемот, расшифровывает входную последовательность на сервере, но у него отпадает интернет, и он не успевает ее послать. Я расшифровываю ее тоже мелкой кодякой на С++, и успеваю как раз к моменту, когда он входит в интернет, и мы одновременно почти отправляем ее в Jabber :о)

Теперь задача найти фабрику, которая будет генерить эту последовательность. Вот тут настал тупняк. Ребята ушли уже спать, а я начал думать. Брутфорс писать было лень (и слава богу, потому что в этот момент я не знал, что потом надо будет делать фабрики для производства топлива длиной под тысячу символов, которые бы не брутились). Начал выводить фабрики, которые не зависимо от входа будут делать нужный выход. Научился делать два блока – один возвращает ноль, а затем поданную на вход последовательность, другой – получает на вход последовательность и возвращает ее, увеличенную на один. Первый из шести гейтов, второй – из десяти. Их комбинации, очевидно, могут создать фабрику для любой последовательности. Тока фабрика будет иметь длину, в 20 раз большую длины входной последовательности :о)

Пишу на JavaScript конвертер выходной последовательности в фабрику (ну опять, почему JavaScript???), и засылаю ее на первую машинку. Команда получает 0.014 баллов :о) Я писаюсь кипятком – у нас не ноль :о)

На другие машинки не засылается. Теперь надо думать над тернаркой. Сразу бросается в глаза, что часто встречаются две подряд идущие двойки. Кроме того, почти все машинки начинаются с двух двоек и заканчиваются 10. Казалось бы, 22 – начало листа, 10 – конец. Но не работает. Да и есть машинка, заканчивающася не на 10, а самые простые машинки начинаются не на 22, а на 1.

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

До ночи ничего не придумываю, ухожу спать с надеждой, что ребята расшифруют.

День второй, Суббота

Утром тернарный формат еще не был разгадан. И никаких зацепок не было.

В девять утра был первый отборочный на топкодер, и я решил поискать подсказок в чате. Один чувак отозвался на фразу IFCPC, и в диалоге с ним я прозрел. Префикс у топлива не является вообще валидной тернарной строкой, и описание топлива идет после префикса, а не начиная с него! Это даже прямым текстом указано в условии, но че-то я затупил. С этой информацией Бегемот засылает наконец-то топливо на хоть какую-то машину, кроме пустой, просто перебирая текст после конца префикса. Кирилл пишет на Ruby бота, который рассылает это топливо на все тачки, и он подходит на неслабое их количество. Баллы начинают течь рекой! Конечно, не сравнимо с другими командами, которые так долго не тупили.

Следующее прозрение происходит, когда мы понимаем, что если подать валидное топливо (а у нас теперь есть хотя бы одно такое), то можно изучать ошибки парсера машинки. Ошибки были четырех типов: «ожидается 0, 1 или 2, а обнаружен конец», «ожидается 2, а обнаружен конец» и «ожидается 0, 1 или 2, или число здесь должно быть 0 или 1, а обнаружен конец». Третья ошибка выносит мозг. Ожидается 0, 1, 2, 0 или 1? Что это значит? Иногда пишет, что машинка валидна, но что-то с ней не так: нет ни одного мейн чамбера, или топливные баки не соединины (там есть определенное правило по соединению топливных баков). Долго, очень долго, мы втупляем, каждый сам по себе, иногда кидая мысли в джаббер. Копим разные последоавтельности с ошибками, составляем полный список. Спустя пол дня, где-то после обеда уже, я нахожу машинку, которая пишет «не соединен 0 бак сам с собой». Замена на конце нуля на 10 меняет ошибку на «не соединет нулевой с первым». Начинаю перебирать и умудряюсь восстановить формат представления чисел. Awesome. Перебираю еще пол часика и понимаю весь формат. Я не мог поверить своему счастью. Конечно, когда он уже расшифрован, он кажется очень простым :о) И он реально крут. Мы готовы приступить к непосредственно задаче. Прошло всего полтора суток из трех :о)

Сразу пишется на JavaScript (ну твою ж за ногу) парсер машинок из тернарки в JSON и парсер топлива из JSON в тернарку и сразу в фабрику.

Кирилл улучшает скрипт, чтобы тот рассылал больше типов топлива, и уходит спать. Скрипт убивается через 10 минут после этого, когда сервер вернул 503. Не очень Robust :о)

Сначала я решаю руками некоторые простые машинки, где матрица имеет размер 1 на 1 (открыть машинку, подать ее на парсер, подумать, написать JSON топлива, закодить в фабрику, заслать – автоматизацией не пахнет :о)), пока не нахожу машинку 13252. Смотря на нее я понимаю, что некоторые числа в описании топлива в решении могут быть очень большими, знаков по 100. И мое решение на яваскрипте явно не способно их обрабатывать. Приходится переписывать половину кода на Java – потеря времени -  с BigInteger, с осознанием того, насколько изначально было тупо писать все на JavaScript. Теперь весь код, уже готовый, невозможно использовать, потому что JavaScript даже не научишь писать в файл/читать из файла. При этом конвертор в фабрики я не переношу, и автоматизация все еще хромает, так как надо сконвертить машинку в JSON на стринчке, запустить ява-приложение, и опять на страничке сконверить аутпут в фабрику.

После этого я решаю все машинки вида 13252, и на этом получаю сильный старт – такие машинки к тому времени решены 6-7 командами, а значит баллов за них дают неплохо. Обгоняю постепенно в таблице результатов соседние команды, спустя какое-то время мне уже не надо проматывать странцу чтобы найти нас :о)

Далее вырисовывается несколько путей развития:

1.      Улучшить наши фабрики – сделать их покороче, чтобы баллов за них капало побольше

2.      Написать решалки каких-то базовых машинок

3.      Или сделать свои машинки

Я выбрал третий путь, и начал делать машинки, выбирая несколько больших степеней двойки, и рисуя семь чемберов, которые, видимо, можно будет решить только подобрав эти степени двойки. Засылаю одну такую машинку, и ее почти сразу решает пять команд...

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

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

День третий, Воскресенье

С утра мы уже на 14-ом месте с 300К очков, наши машинки уже решило по 5-6 команд не считая нас, и к списку решенных нами машинок добавилось порядка 60 нубских. Мы все еще растем неплохими темпами (не смотря на то, что наши машинки научились решать).

Я ухожу смотреть матч Бразилия – Ивори Коаст, а ребята продолжают улучшать бота и думать. Просмотр матча в баре без выпивки не удался, и вернулся я в состоянии, не пригодном для решения задачки. Однако новости хорошие – Бегемот придумал новый способ генерить фабрики, который позволит делать фабрики в 10 раз короче!

Сервер соревнования лежит. Администраторы, видя это, дают несколько вспомогательных ссылок, среди них полный список машинок с длинами всех решений, где мы видим, что наши решения самые длинные (и, как следствие, приносят меньше всего очков). 

В это время я начинаю писать брут для топлива на C# (как хорошо, что в .NET 4.0 есть BigInteger), который перебирает одноингридиентные топлива с кажным элементом от 1 до 10. Парсер написался легко, но попытки найти машинку, которую бы он решал, заканчиваются буквально нахождением двух трех.

При этом копировать аутпут брута на JavaScript страничку, чтобы сконвертировать топливо в фабрику, очень неудобно, и встает необходимость перенести конвертор топливных фабрик на C#. Раз уж надо переносить генератор, решаю сразу писать идею Бегемота. Это занимает ужасное количство времени (вероятно не последнюю роль в этом сыграл побочный эффект матча Бразилия – Ивори Коаст), но в конечном итоге новый конвертор топлива в фабрики, готов.

Затем запрос “C# WebRequest” в Bing и 30 минут учат софтинку грузить список машинок с сервера, грузить машинки, брутить их, конвертить и засылать, и за несколько минут количество решенных нами машинок увеличивается в 1.5 раза! :о)

При этом софтинка перепосылает все уже решенные нами машинки с более короткими фабриками.

Теперь внимание вопрос. Почему я написал брут форс, а не линейное программирование, если даже ребенку очевидно, что это – задача на линейное программирование? Большинство конкуретнов, которые нас потом обошли не очень сильно, разумеется написали ЛП.

Вечером, когда ребята проснулись, возникает печаль. Mono с .NET 4.0 не так-то легко найти. Они оба не могут запустить мою софтинку. Я генерирую у себя на машине все простые топлива, чтобы Кирилл добавил их в свой скрипт. Теперь на новые машины сразу засылается новое топливо. К сожалению, мой C# кодяк в отличие от бота Кирилла, не запоминает решенные машинки, и каждый раз идет по всему списку. Чтобы он как-то все-таки решал свежие машинки, я запускаю его восемь раз с разным стартовым отступом. Оборачиваю пол кода в try-catch, чтобы не повторить подвиг Кирилла с падением через 10 минут. Ухожу спать в полночь, до конца контеста пять часов.

Ночью происходит забавный момент. Во-первых, уже с вечера многие команда, похоже, написали ЛП-солвер, и начали очень быстро расти. И конкуренция в последние часы просто дикая. Нас рвет SnakeTeam, которую Бегемоту было принципиально порвать, и дерет нас за счет... своих машинок! Потому что 1000 решенных простых машин дает порядка 10 баллов за прирост, в то время как 72 своих (72 - лимит), которые решит одна команда кроме вас, дает 30 баллов за прирост! Прогадал я, однако, с засылкой машинок под лимит раньше времени.

Так вот, забавный момент. Была под нами команда SzM – стыдно за МГУ. Бегемот открыл ихнюю машинку, прочитал, и понял, что он знает как ее решать, в тоже время, наши боты пока ее не умеют делать. Он решает ее, и решает все машинки SzM. В итогде, в конце контеста SzM за нами с минимальным отставанием :о) Получается ихние же машинки не дали им нас обойти :о)

В итоге мы на 19-ом месте. Вокруг невероятная концентрация российских команд: над нами TBD, повыше SnakeTeam, под нами Стыдно за МГУ, jabber-ru.

Вот в общем такая история. Основные уроки, которые были вынесены:

1.      Подумай 10 раз на каком языке пишешь.

2.      Не пиши на JavaScript :о)

3.      Внутри команды используйте один язык программирования :о)

 В следующем году обязательно буду писать снова :о Никакие из соревнований, где я участвовал прежде (кроме конечно ICPC 2008 - с этим ничто не сравнится :О)) по накалу страстей даже рядом, по-моему, не стояли :о)