Отчёт об ICFPC-2010

До чего дошёл прогресс -
До невиданных чудес!
Опустился на глубины
И поднялся до небес.

Позабыты хлопоты, остановлен бег -
Вкалывают роботы, а не человек.

Введение

ICFPC-2010 закончился еще в понедельник, но он оказался настолько емким, что полтора дня я только и мог, что кататься на велосипеде и проветривать мозги. Да и сейчас на подробный отчёт меня не хватит, так что ограничусь только кратким описанием того, что происходило со мной во время ICFPC-2010.
Итак, начнём с того, что в этом году меня пригласили поучаствовать вживую в харьковской команде THIRTEEN. Команда сыгранная и довольно сильная, до этого я с ними сталкивался на Sapka и ICFPC-2009.
На время прохождения контеста мы все собрались в квартире-офисе одного из членов команды. Отсюда первое и самое сильное впечатление: общение с живыми людьми, участие действительно в реальном времени(без перерывов на сон в собственной постели) - это нечто невообразимое. Представьте, что вы провалились в кроличью нору и попали в страну, где жители решают странные задачки, где сон и еда - досадные раздражители, а производительность труда взлетает до небес.
Второе впечатление - для участия в таком конкурсе нужна не команда из программистов, каждый из которых будет писать код. Нужны математики, физики, спецы по схемотехнике и прочие головастики. А программить могут 2-3 человека, не более того.

Кратко о происходившем

Задание повторять не буду, вы можете найти его краткое описание в отчете Futamura Rejection. В первую очередь, все бросились разбирать формат фабрики. Довольно быстро я написал парсер на Python, который генерил картинки в graphviz. Однако красивыми картинки сделать не получилось и в итоге все фабрики рисовались на бумаге. Как только с форматом более-менее разобрались, начали подбирать функцию гейтов. Мудрым решением здесь было предположить, что Undefined сигнала не существует и он заменяется 0. Я сделал простейший эмулятор на Python и с его помощью пытался подобрать функцию гейта(в виде матрицы). Но где-то в коде закрался баг и пока я его искал, sannysanoff на Java реализовал такой же симулятор без багов и нашел эту самую функцию.

А дальше пошло самое интересное: нужно было придумать генератор, который будет генерить фабрики в соответствии с нужной выходной последовательностью. При этом на входную последовательность завязываться было нельзя. Пока я крутил в голове всякие мысли со стейтами, переходами между ними и применением алгоритмов из теории графов для построения таблицы переходов между стейтами, Rst7 и SAS мозговым штурмом предложили довольно простой и естественный способ генерации фабрик из таких макроэлементов, как "генератор 0", "генератор 1", "генератор 2", "задержка", "задержка с вычитанием", "вычитатель". sannysanoff его быстро закодил(кстати, я впервые видел применение настоящего ООП в спортивном программировании. До этого я считал, что ООП слишком затратно, чтобы его применять при жестких временных рамках). Фабрики получались довольно большими, но работали.

Это был вечер пятницы. Начиная с этого момента начинается хмурая и безрадостная эпопея разгадывания внутреннего кода машин и топлива. Одна из причин этой хмурости (и один из основных лучей ненависти к организаторам) - в том, что попытки работать из под одного IP на нескольких машинах заканчивались провалом. Видимо, организаторы сделали привязку по IP и, соответственно, если заходить всем под разными аккаунтами, то аккаунты шарились между машинами, а при заходе по одному аккаунту высвечивался Internal Error. В итоге, я и sannysanoff зарегистрировали два фейковых аккаунта (fake001 и fake002) и использовали их через собственные туннели. Аккаунт THIRTEEN был под управлением brox и через его машину мы сабмитили официальные решения. Таким образом, несмотря на то, что участников было довольно много, разбираться с форматом данных могли только два, максимум три человека: ведь для того, чтобы понять формат, нужен был доступ к серверу.

Суббота прошла туманно. С утра я написал на Python скрипты, которые позволяли заливать тривиальные решения для тривиальных машин. Это дало ощутимый прирост к очкам. Всё остальное время было посвящено разгадыванию кода. Почему-то это шло очень медленно и к вечеру субботы полного понимания даже структуры топлива еще не было. Более-менее был ясен только способ кодирования чисел. Где-то в это же время я написал command-line интерфейс к парсеру на сервере, открыл к своей машине терминальный доступ и за разгадывание формата взялся Rst7. После нескольких часов, он предложил вариант формата, который мы успешно(!) использовали до утра понедельника. После этого Rst7 и SAS увлеклись идеей оптимального генератора фабрик. Они его разработали, хотя я до сих пор лучше понимаю, как работает первый вариант генератора.

Таким образом, к началу воскресенья у нас не было еще формата описания машин и не было никаких наработок по алгоритмам их решения. Я не помню точного времени, но где-то в этот момент, руководствуясь подсказками из чатов, до меня начал доходить формат описания машин. Однако полностью это понимание сформировалось позже. Читая отчёты других команд, я завидовал тем людям, которые выписав колонки чисел, сразу догадались, что два формата чисел отличаются сдвигом и отбрасыванием двойки. Я к этому сдвигу шел долгие часы, а 22 вообще долгое время считал признаком начала списка. Всё же, совместно с sannysanoff мы разобрали этот формат, я написал простенький енкодер машин. Еще ранее был написан интеллектуальный посылатель тривиальных машин. Он проработал совсем немного - до момента падения сервера. После поднятия сервера организаторы отключили нужные для работы ссылки на список всех машин, но оставили рабочей скрытую в недрах ссылку на список всех машин с принадлежностью к командам. Переписать скрипт, чтобы он использовал эту ссылку - дело 3-х минут. Как я понимаю, к моменту, когда мой бот снова начал работать, остальные участники еще не успели модифицировать собственные скрипты - скорость работы сервера была великолепна!

Также где-то в ночи появился переборный решатель от sannysanoff и dshoot. К нему так же был написан скрипт на Python, который запускал программу на Java для нахождения решений и отсылал результаты на сервер. Так решались небольшие нетривиальные машины. В это же время стало очевидно, что мы многое теряем, н придумывая свои машины. Этим занимались SAS и brox. В это же время действовало ограничение на 100 символов на машину. Поэтому почти все наши машинки - небольшие и поддаются перебором. К сожалению, мы пропустили момент, когда ограничение на 100 символов было снято.

Утром в понедельник вовсю работали скрипты, мы постили шаблонные машинки, а sannysanoff обнаружил, что топливо у нас кодируется неправильно. Часов за 7 до окончания контеста. Однако проблему удалось решить, хотя это нам и не сильно помогло. Последние участники разбрелись за час до окончания.

Итог

30 место, 69 машинок, около 700 топлив. Великолепное задание, отвратные кодировки. Я успел покодить на Python, C и Java. Кстати, этот ICFPC-2010 - наглядное доказательство того, что скриптовые языки вроде Python - очень нужны в таких контестах. Без Python не было бы ботов, написанных в считанные минуты, без Python не было бы быстрого прототипирования.

Заключение

В голове у меня эти дни отпечатались размыто. Действительно, как сон Алисы о Стране Чудес. Я мог перепутать время, потому что не помню, когда заканчивался один день и начинался другой. Я ничего не упомянул о том, как brox пытался на С подобрать очень короткие макроэлементы а я писал ему алгоритм пермутаций, как я оптимизировал генераторы 1 с задержкой, как вместе с Rst7 мы пытались решить машины аналитически с помощью Matlab, как я пытался реализовать рекурсивный энкодер чисел и как у меня ничего не вышло.

Немного сумбурный отчёт от sannysanoff. Если чей-то ник или какие-то события я указал неправильно - поправляйте.
ICFPC 2010 - кулаками после боя (by brox)