?

Log in

No account? Create an account

Previous Entry | Next Entry

ICFPC'10

Назвался груздем - пиши отчет о полезании в кузов.
В понедельник завершилось ежегодное программистское соревнование ICFPC, в котором я традиционно участвую с 2007 года (мои предыдущие отчеты: 2007, 2008, 2009).

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

19L:
12R13R0#1R12R,
14R0L0#4R9L,
9R10R0#3L8L,
2L17R0#5L9R,
15R1L0#10R13R,
3L18R0#6L15L,
5L11R0#13L12L,
19R16R0#11R8R,
2R7R0#11L10L,
1R3R0#18L2L,
8R4L0#16L2R,
8L7L0#15R6R,
6R0R0#14L0L,
6L4R0#14R0R,
12L13L0#17L1L,
5R11L0#16R4L,
10L15L0#17R7R,
14L16L0#18R3R,
9L17L0#19R5R,
X18L0#X7L:
19L

Было сказано, что получив на вход последовательность [0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1], эта фабрика произведет некоторую последовательность тритов, которую нужно использовать в качестве ключа - ее нужно ставить в начало любой последовательности, описывающей топливо. Т.е. наши фабрики для топлива должны сначала выдавать 17 цифр ключа, а потом уже цифры топлива. Предлагалось начать с построения фабрики, выдающей только ключ. Отправив такую фабрику для машины с кодом 0, можно было получить первые очки.

С учетом моего часового пояса конкурс для меня начинался в 7 вечера пятницы. Вернувшись вечером домой, я стал неспешно вникать в задание. Изучение примера и попытки отправить на сервер что-то похожее на фабрику привели к тому, что ближе к полуночи формат фабрики обрел для меня смысл: каждая строчка с # описывает гейт, слева от 0# пишется откуда в гейт приходят провода, справа - куда они уходят. Например, 12R13R0#1R12R означает, что в левый вход приходит провод от правого выхода 12-го гейта, в правый вход - от правого выхода 13-го гейта, из левого выхода идет провод в правый вход 1-го гейта, а из правого выхода идет провод в правый вход 12-го гейта. Х означает вход или выход всей схемы. В итоге вся фабрика из примера выглядит как-то так:



Поняв это, я пошел спать. В субботу стал разбираться с устройством гейтов и алгоритмом работы фабрики. Было сказано, что по проводам вперед цифры идут мгновенно, а назад - с задержкой в один такт. Что именно означало "вперед" и "назад" не было понятно, пришлось разбираться экспериментально. Для определения функций гейта я стал строить простенькие фабрики и посылать на сервер, изучая их выход, первые 17 цифр которого сервер выдавал в ответ. Пришлось соорудить 18 разных фабрик: 9 возможных комбинаций на входе * два выхода:



В результате была составлена таблица зависимости выходов от входов гейта:



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

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



Вернувшись домой и почитав IRC, увидел подсказку, что из трех гейтов можно сделать фабрику, которая выдает определенную цифру на выходе, а затем повторяет входную последовательность (задержав ее на один такт). Для 0 и 1 мне удалось быстро придумать такие фабрики, а для 2 не получалось. Утром в воскресенье написал полный перебор фабрик с заданным числом гейтов. Он тут же нашел два решения. В результате у меня для любой цифры были трехгейтовые компоненты фабрики, которые выдают данную цифру плюс входной поток:



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

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

В понедельник с утра увидел, что организаторы на отдельном сервере сделали пару страничек на happstack, где можно было получить коды машин (коих стало уже более полутора тысяч) и проверять свои решения. Написал автоматическую забиралку машин. Этот второй сервер не требовал логина и идентификатора сессии в cookie, зато данные получал в multipart/form-data, пришлось немного помучаться (у меня в таких вещах опыта маловато). Вскоре скрипт на Руби для получения машин и отправки топлив на основной сервер был написан, примитивное топливо подошло к трем сотням машин. До конца оставалось шесть часов. Увидев в IRC, что люди по 12 часов мучались, разгадывая формат топлив и машин, я решил этим не заниматься, а заняться сокращением имеющейся фабрики. Заметил, что зная первые 17 цифр входного потока, и имея перебиралку фабрик, которая проверяла все комбинации фабрик из пяти гейтов за минуту, можно подобрать фабрику для некоторого количества цифр. А поскольку каждый трехгейтовый компонент моейт текущей фабрики сохраняет входной поток, просто его задерживая на такт, можно конец последовательности генерировать, используя часть входного потока. В результате сократил фабрику для примитивного топлива до 38 гейтов. Отправил ее на сервер для кучи машин в порядке возрастания длины описания машины (чем проще машина, тем больше вероятность, что к ней подойдет простое топливо). Пока работала сабмитилка попробовал поподбирать более сложное топливо, научился кодировать цифры 0, 1 и 2, но далеко не продвинулся, т.к. не знал формат списков и матриц (по условию топливо содержало одну или несколько квадратных матриц с натуральными коэффициентами). За пару часов до конца обновил список машин, чье число выросло к этому моменту до 2700. Опять запустил сабмит в порядке возрастания длин машин, пропуская машины с ID менее 130000, которые были обработаны ранее. Сервер работал небыстро, поэтому за 2 часа скрипт сделал чуть больше тысячи запросов и увеличил число решенных машин до 402.

На этом соревнование закончилось. В итоге я успел заработать 75.949 очков и оказаться на 90-м месте из 872 зарегистрированных команд. В этот раз особенно хорошо чувствовалось преимущество тех, кто работал в команде из нескольких человек - пока один пишет перебиралки и сабмитилки, другие могут заниматься разгадыванием форматов, думать над построением более коротких фабрик и т.д. В одиночку всего этого не успеть.

В процессе было написано 300 строк на Окамле (два интерпретатора фабрик, подбиралки, генератор фабрик по топливу, всякие эксперименты), 100 строк на Руби (взаимодействие с сервером) и много рисунков на бумаге и доске.


Tags:

Comments

( 2 comments — Leave a comment )
larubin
Jun. 24th, 2010 05:09 am (UTC)
Location для ICFPC зачетный, конечно :)

А таблицу гейта мы как раз так и декодили. По-моему элементарно. Не понимаю команды, которые это делали перебором!
jones_galipeaux
Jul. 11th, 2010 12:10 pm (UTC)
thedeemon. интересно
( 2 comments — Leave a comment )