Предыстория
Последние несколько лет я всё собирался поучаствовать в соревновании по программированию ICFP Programming Contest. Обычно дело не заходило дальше скачивания задания и чтения отчётов участников. У меня же вечно не было времени, не было команды, или я куда-нибудь уезжал, или... В общем, куча стандартных отмаз. Но в этот раз всё пошло не как обычно.
Еще недели за две до старта было получено принципиальное согласие на совместное участие от Лёши С. Думаю, он тоже давно хотел подрастопить немного жир в мозгах. Соревнование ICFPC казалось нам очень подходящим вариантом. Не слишком долго, много драйва, интеллектуальный челендж. Очень жалею, что не сумел уговорить еще одного персонажа, имеющего солидный опыт индивидуального участия в этом мероприятии. Рома П., пусть тебе аукнется в Цюрихе!
Еще нами было принято не менее принципиальное решение: заранее не готовиться, за спортивными достижениями не гнаться. Решили в час X посмотреть задание, и если оно покажется интересным, то ради фана - и без фанатизма - сыграть в эту игру. В лайтнинге не участвовать. И остановиться как только надоест.
Над названием команды долго не думали. Прошло буквально второе предложение, и мы стали называться "qwerty". Я потом полистал списки команд-участников прошлых лет и выяснил, что мы спёрли чей-то бренд. Нехорошо вышло. Простите.
Ладно, пора начинать. Итак,
Пятница
72 часа
Из асечного лога...
Pashkov Alex (Птн Июн 18 2010 16:00:38):
16:00 однако
Alexey S. (Птн Июн 18 2010 16:00:39):
Ну... И где?
Pashkov Alex (Птн Июн 18 2010 16:00:45):
опубликовали!
Alexey S. (Птн Июн 18 2010 16:00:53):
блииин
Alexey S. (Птн Июн 18 2010 16:01:08):
не грузится :((
Pashkov Alex (Птн Июн 18 2010 16:02:18):
Лёх, а клёвое задание!
Alexey S. (Птн Июн 18 2010 16:03:19):
о!!
Pashkov Alex (Птн Июн 18 2010 16:05:29):
читаешь уже?
Alexey S. (Птн Июн 18 2010 16:05:46):
ага
Pashkov Alex (Птн Июн 18 2010 16:06:00):
придётся участвовать :-)
Лето, жара, пятница, четыре часа дня по Москве. Вокруг меня снуют какие-то недоушедшие домой граждане. Кто-то пытается отвлекать "по рабочим вопросам". Смешно. Я совершенно чётко ощущаю, как так называемый реальный мир постепенно отходит на второй план. И понимаю, что меня затягивает. И знаю, что на той стороне асечного зазеркалья происходит то же самое. И мне нравится это ощущение.
Бегло читаю задание по диагонали. Выдох-вдох, уловить основные моменты. Так, ясно, машины, топливо, кодировка, фабрики. Ух ты, нужно будет "ломать" чужие машины и публиковать свои. Крутая идея! Вспоминается давняя забава под названием Snake Battle...
Лёхе, наоборот, этот момент регламента не нравится. Он мгновенно определяет возможный способ читерства: создание большого числа фейковых команд для публикации более, чем 72 машин с последующим аплоадом топлива к ним из основной команды.
Некоторое время обсуждаем этот вопрос, классифицируем его как возможный баг регламента, но принимаем решение оставить его на совести организаторов (тем более, что пока что не очень понятно, в количестве ли "своих" машин счастье), а самим не читерствовать. Я делаю оценку, что к концу конкурса будет опубликовано 10000 машин.
Перечитываем задание по второму кругу. Вдумчиво, внимательно. Обсуждаем условие "связности" баков в машине. А могут ли компоненты топлива быть отрицательными? Целочисленная ли арифметика? В голову лезут какие-то векторы Фробениуса-Перрона... Сколько камер сгорания ("шамберов") может быть у одной машины? Каков состав "начального воздуха" (initial air) и важно ли это? Вопросов много...
71 час
Утверждаем мини-план работ. Собственно, ясно только следующее. Машинами заниматься рано. Их даже сабмитить не дают, пока какое-нибудь топливо не зальёшь. А "организаторских" машин всего две - это несерьёзно. С топливом тоже какая-то засада. Непонятные 17-тритные префиксы, чёрти чё. Значит нужно разбираться с кодировкой фабрик, осознавать как они работают.
Лёха регистрирует команду. Этот символический жест означает, что мы вписались и теперь нельзя ударить в грязь лицом.
Некоторое время мы тупим. Потом пытаемся сабмитить фабрику-пример на сервер. В процессе узнаём, что "Internal Error" - это такой logout.
И тут у нас случается первый шок: кто-то засабмитил третью машину. А ведь не прошло и двух часов со старта. Может это организаторы? Хз...
70 часов
Лёха экспериментирует с фабриками. Я тоже пытаюсь, но мне до этого хакера далеко. Он подбирает первую одногейтовую фабрику. Потом еще одну. Потом с помощью нуль-гейтовой фабрики получает input. Кодировка фабрики постепенно становится понятной. Излагаю Лёхе свою теорию "взлома" функции гейта. Предлагаю систематически прогнать одно/двух-гейтовые фабрики на известном входе и составить таблицу истинности гейта.
Лёха берётся "взломать" гейт по этой методе, но ему это быстро надоедает. Со словами "тут перебор рулит" он сваливает домой.
А я сажусь за разработку интерпретатора фабрик.
66 часов
С интерпретатором дело сразу не заладилось. Как ни крути, получается какой-то адский кусок хаскельного... кода. Впрочем, скомпилировавшись, он сразу правильно интепретирует id-фабрику "X::X", что меня несколько успокаивает. Не имея "взломанного" гейта, желания "взламывать" его вручную и моральных сил реализовать еще и переборщик функций троичной логики, я отправляюсь домой.
Cуббота
По утверждённому плану, еду к Лёхе в гости. В этот раз Бог не смеётся над нашими планами и в 11 утра я уже плутаю в Яндекс.Картах, пытаясь найти нужный адрес на другом конце Москвы.
53 часа
Первое яркое впечатление нового дня: за ночь засабмичено более 100 новых машин. Народ явно не теряет времени. А у нас еще нет даже префикса...
Ладно, ставим Haskell Platform, пьём чай и плотно садимся за "взлом" гейта. Лёха пытается что-то угадать, вручную вбивая пачки фабрик на сервер. Я планомерно интерпретирую машины на листочке бумаги, восстанавливая таблицу истинности функций гейта. Через некоторое время процесс начинает сходиться. Поднаторевший в разработке фабрик Лёха подключается к процессу и мы дожимаем гейт. Я вбиваю результат в свой замечательный интерпретатор. Сердце поёт в радостном предчувствии.
50 часов
Но предчувствия на сей раз обманули. Интерпретатор, на который возлагались такие большие надежды, правильно интерпретирует только одногейтовые фабрики. Все четыре. И лажает на двух- и более-гейтовых. Баг в таблице истинности? Нет. У гейта есть состояние? Нет. Back-линки иницилизируются не нулями? Нулями. Значит баг в коде. Может back-линки не "дилеят"? Дилеят. И тут случается второе яркое впечатление этого дня: оказывается, что у меня не только back-линки дилеят, но и forward-линки тоже. И это настолько уже вросло в реализацию, что нужно выкинуть практически весь интерпретатор.
Проклинаю себя и вчерашнюю спешку, начинаю чинить. Лёха отводит мне час и обещает посидеть рядом. По грустным глазам видно, что хаскель ему не нравится. Особенно в моём исполнении. Но тем не менее терпеливо ждёт, честно смотрит в 42"-монитор и даже что-то подсказывает. Я лихорадочно переписываю интерпретатор. В процессе даже успеваю поставить Emacs и haskell-mode. И когда остаётся вот буквально вот тут еще вот эту функцию реализовать, Лёха сообщает, что моё время вышло и просит час на реализацию интерпретатора на C#. К этому времени уже ясно, что с хаскелем мы каши не сварим, а C# хотя бы оба члена команды неплохо знают. Соглашаюсь. Но смотреть в монитор не буду. Вместо этого начинаю работать над "Теорией Синтеза" фабрик.
46 часов
Интерпретатор действительно готов ровно через час. Мы наконец получаем префикс! Тут же его огугливаем и убеждаемся, что он правильный. Мда. А с начала соревнований уже больше суток прошло. Сервер начинает ощутимо подтормаживать. Похоже, на нём уже завелись роботы. А у нас еще только префикс.
Лёха не долго думая реализует "Подбиратор", который умеет перебирать все схемы из N гейтов. До 6 гейтов нужная нам фабрика для нулевой машины не находится (да-да, этот факт до сих пор остаётся для нас необъяснимым). Перебирать 7-гейтовые фабрики кажется бессмысленным. Лёха переключается на подбор "элементарных" функций: констант, тождественной (id), задержки на такт (delay). А я грызу ручку и смотрю в таблицу истинности гейта. Через некоторое время я понимаю, что левая нога - это разность входов, а правая - произведение входов минус единица. Лёха обзывает это "результатом". Я горжусь собой.
Завязывается дискуссия о том "базис это или нет". Лёха хочет, чтобы был базис. И вообще, он хочет натравить на эту задачу всю мощь теории синтеза схем из функциональных элементов. Мы даже полистали минут пять Яблонского на эту тему. У меня же нарастает подленькое чувство, что "ни разу не базис". Оно основано на "похоже-невозможности" получить "раздвоятор" входа и подкрепляется дальнейшими экспериментами, которые показывают, что все Лёхины "константы" и "id", на самом деле перестают быть таковыми на более длинном входе. Правда есть мнение, что вход на сервере периодический. Но это пока неясно. Зато сбрутфорсенный 3-гейтовый элемент Delay работает замечательно. И это тоже наводит на мысли...
Настя, Лёшина жена, сваливает на дачу. По официальной версии, ей очень нравится, чем занят муж на этих выходных и она не хочет нам мешать.
43 часа
Кому-то приходит в голову мысль, что если не получается 6-гейтовая фабрика для нулевого топлива, то может быть получится 6-гейтовая фабрика, которая сгенерит правильный вход для фабрики-примера? Запускаем "Подбиратор" и - о чудо! - не остановленный вовремя, через несколько секунд он выдаёт... 7-гейтовое решение. Вот она, роль Случайности в Истории Мира. Комбинируем решение с 20-гейтовым примером и сабмитим на сервер. Ура! Мы ровно 100-ая команда, справившаяся с этой задачей. Через несколько минут сервер начисляет нам первые 7 очков.
Воодушевлённые, мы пытаемся разработать "Теорию синтеза". Но не тут-то было. Единственное новое наблюдение - это "странный аттрактор". Характерный цикл в таблице истинности гейта. Но выжать из этого ничего не удаётся. Начинается тупняк, идей нет вообще. Мораль стремительно падает, нужно срочно переключиться. Поскольку нам теперь можно сабмитить свои машины, то я с головой ухожу в исследование кодировки машин и топлива. На все вопросы отвечаю односложно "Ja" или "Nein". Лёха продолжает свои эксперименты с "Подбиратором". Но новых результатов так и не появляется.
41 час
Подводим итоги, строим планы на завтра, ложимся спать. Всё-таки с возрастом что-то меняется. В студенческие годы мы наверняка зарубились бы на всю ночь :-)
Воскресенье
30 часов
Снова в строю. За ночь наша позиция в рейтинге не изменилась, хотя уже 150 команд справилось с тривиальным топливом. Нам же нужно двигаться дальше.
Кровь из носу нужна "Теория Синтеза". Мне не даёт покоя "странный аттрактор" в значениях гейта. Кажется, что еще чуть-чуть и я ухвачу какую-то красивую идею за хвост. Лёха же выступает за более системный подход. Еще с вечера он выдвинул набросок общей схемы синтеза фабрик. Генерить независящие от входа последовательности, в которых только один элемент (в заданной позиции) отличен от нуля. Полученные "орты" склеивать функцией max.
Есть две маленькие проблемы. Мы не умеем генерить даже просто константу "0", независящую от входа, не говоря уж об ортах. У нас нет функции max. Лёха берёт на себя первую задачу, а меня просит отложить кодировки машин и аттрактор и заняться поиском максимума, поскольку "Подбиратор" с этой задачей не справился.
Максимум никак не ищется, зато через некоторое время меня осеняет, что нам достаточно "конечных ортов", которые несложно сгенерить, имея элемент Delay. И пока Лёха реализует "комбинатор последовательной склейки фабрик", до меня доходит, что max нам тоже не нужен. Вместо max вполне подошёл бы любой "убер-комбинатор", который совпадает с max, если хотя бы один из входов равен "0". Например, нам подходит обычная сумма или... или разность! Так рождается долгожданная "Теория Синтеза". Мы прекрасно осознаём, что синтезируемые фабрики имеют квадратичный порядок сложности от длины кодировки топлива и не используют серверный вход. Огромный простор для оптимизации. Но сейчас важнее двигаться дальше. Лёха опять садится за C#, а я возвращаюсь к кодировкам машин и топлива.
27 часов
У нас появляется работающий "Синтезатор". А я уже почти понимаю кодировку. Но не совсем. Поэтому первое нетривиальное топливо, фабрику для которого мы сабмитим, выглядит так: "1111". Топливо сразу подходит первой же машине, на которой мы его пробуем. Заливаем его еще штук на 20 машин. На это уходит где-то 20 же минут. Это не дело. Машин же засабмичено уже порядка полутора сотен. И ясно, что нужен "Continuous Integration". Пока откладываем этот вопрос, чтобы дожать кодировку. Я демонстрирую Лёхе накопленный опыт в области "машиностроения". В ответ он быстро строит "Теорию Чисел". Она оказывается не совсем корректной и впоследствии требует доп.глав в виде "Теории Чисел Высших Порядков". Но сейчас это не важно. Поняв, как устроено число, я сразу понимаю, как устроено Всё. Для доказательства своего всемогущества и тестирования вражеских роботов сабмичу подряд 4 простенькие машинки, к которым подходит скалярное топливо. Через несколько минут ко всем залито 8 видов топлива. Это оценка количества самых шустрых роботов по состоянию на
24 часа
Нужно писать своего робота для заливки решений на сервер. У нас нет под рукой Linux'а с его wget и curl. Из очевидных решений под винду - это либо .NET, либо что-то типа selenium'а. Поскольку на сервер нужно логиниться, останавливаемся на последнем. Selenium сразу начинает работать, бодро логинится на сервер, учится скачивать список машин. Первые грабли случаются, когда в решение инвестирован уже час времени. Selenium отправляет наши гигантские фабрики в браузер байт за байтом, имитируя нажатия кнопок пользователем. Это занимает бесконечно много времени. Скорость особо не регулируется, т.к. у нас 100% cpu usage. Быстрее - никак. Одинаковый результат в трёх браузерах (Firefox, Chrome, IE). Лёха пытается использовать Microsoft Web Testing Framework. Но учиться пользоваться новым продуктом в условиях цейтнота - не вариант. А нам так хочется еще чужие машинки сегодня порешать. А время летит. В итоге переписываем ту часть, что сабмитит форму на .NET WebRequest. Ох... Заработало с грехом пополам. Даже, прямо скажем, 1 к 9 с грехом. Из десяти запусков робота буквально в одном случае он ухитряется дойти до сабмита раньше, чем его выкидывает по таймауту. Сервер тормозит уже совсем неприлично. На горизонте ясно просматривается Epic Fail.
18 часов
Возвращается Настя и мне пора домой. Фактически, соревнование для нашей команды закончилось. Мы ухитрились-таки засабмитить топливо для 104 скалярных машин (с различным числом баков) и даже поднялись в топе примерно до 80-ой позиции. Впрочем, всё это не очень утешает, т.к. мы не успели добраться до содержательной части задачи - подбора топлива для вражеских машин и построения своих машин.
Я еду домой, а Лёха за этот час успевает придумать свою нескалярную машинку. Просит, если я еще не лёг спать, попыться её засабмитить, когда европейцы отправятся в объятья Морфея и оставят сервер в покое. Кроме того, он еше успевает реализовать подбиралку матричных решений и сделать наброски "Теории Топлива".
Понедельник
16 часов
Приехав домой я выясняю, что организаторы сделали интерфейс для инкрементального скачивания новых машин. Это открывает некоторые горизонты для автоматизации. Плюнув на завтрашнюю работу, сажусь переписывать "Continuous Integration" робота. Через некоторое время у меня есть небольшая база данных в виде csv, в которой сложены все машинки с сервера и код засабмиченного нами к ним топлива. База постоянно пополняется. Количество машин быстро растёт и уже зашкаливает хорошо за 1000. Подход "а попробуем это топливо на всех машинах" перестаёт работать. Нужен валидирующий аплоадер. Нужен - делаем.
9 часов
Всё вроде работает, если не считать мелких багов в аплоадере. И я вспоминаю Лёхину просьбу залить машинку. Сервер действительно работает более или менее вменяемо. То ли роботы спят, то ли организаторы дровишек подкинули.
Ладно, а что машинка? Машинка отличная! Но её кто-то засабмитил на сутки раньше нас. Она называется 19991 - красиво. Пытаюсь обломать этому человеку кайф, засабмитив топливо. "not connected". Млин. Слишком длинная фабрика. А всего-то 20 тысяч гейтов...
Трезво оцениваю ситуацию. Помочь Лёхе в разработке "Теории Топлива" или улучшить "Теорию синтеза" я уже сегодня не смогу. Зато я могу отлично запускать, мониторить и дорабатывать "Continuous Integration" роботов. Бессонница этому особо не мешает. Ну что ж, поехали.
1 час
Засыпаю под мерное жужжание робота, который продолжает методично заправлять подъезжающие машинки скалярами.
-1 час
Проснулся от телефонного звонка. Звали играть в волейбол. Дело хорошее и нужное, но не после полутора же суток без сна. Полез смотреть статы. Сухой остаток: решено 511 вражеских машин, 4 своих, 101.550 очков, примерно то же 80-ое место.
Hall Of Fame
Ушёл играть в волейбол.
Послесловие
Получилось у нас как в известном анекдоте: "Ложечки потом нашлись, а вот осадочек остался..." Вроде мы сделали всё, как хотели: получили море впечатлений, адреналина и прикольный опыт. Трое суток пролетели как одно мгновенье. И оно было прекрасно.
Но...
Во-первых, аппетит как всегда пришёл во время еды. Уже в воскресенье были провокационные разговоры про топ-50 и т.п.
Во-вторых, осталось много "хвостов" - нерешённых или неэффективно решённых задач, которые до сих пор покоя не дают.
В-третьих, чисто организационные моменты. Ну нельзя из 72 часов тратить 24 на разработку скриптов для работы с HTTP.
Лёха после окончания соревнования сказал, что всё нужно было делать на сутки раньше. В пятницу получать префикс и фабрику для тривиального топлива. В субботу - "Синтезатор" и "Continuous Integration". А воскресенье посвятить разработке своих машин и взлому вражеских. Трудно с ним спорить... :-)
В общем, готовиться надо было. Чего тут еще скажешь? В следующем году - а участвовать теперь надо по-любому - всё это мы учтём.
Заребрендимся по-человечески.
Усилим по возможности состав. Нужен еще как минимум один - а лучше пара-тройка - человек.
Подготовимся в техническом плане. Нужно заранее согласовать используемые тулзы, чтобы не метаться в процессе с haskell на C#. Нужны как минимум готовые решения для работы с HTTP. А по-хорошему, вообще нужна куча хорошо изученных библиотек: алгоритмы на графах, линейная алгебра, теория чисел и т.д. и т.п. Средства коммуникации на случай географически распределённой команды. Амазоновское облако для брут-форсеров... Размечтался я что-то.
Еще есть тема заранее ознакомиться с научными работами, выпущенными Организаторами за последние годы :-)
Кстати, об организаторах. Хотел напоследок покидаться в них какашками, но не буду. Молодцы они всё-таки. Задание было хорошо продумано, в него не пришлось вносить существенных исправлений, как в прошлом году. Никаких заморочек с различиями в архитектуре используемого железа. Не очень большой объём кода, который требовалось разработать. Достаточно интересно и сложно.
А о плохом писать не хочется. Ни про лагающий сервер, ни про вопросы этики при использовании "коллективного разума" участников для решения своих задач, ни про использование чужого кода сами участниками. Это всё не так важно.
Главное, мероприятие удалось на славу. С чем всех причастных и поздравляю!
Отчёты других команд
