среда, 23 июня 2010 г.

ICFPC-2010

В этом году я второй раз участвовал в ICFP Contest (отчёт об участии в ICFPC-2009 ). Ожидалось заранее, что будет какое-нибудь устройство, которым можно будет управлять. Но ожидания слегка не оправдались. :) В этот раз задача походила на сказку - пойди туда не знаю куда, сделай то не знаю что. Участвовал в команде Skobochka и набрали где-то 3 с чем-то балла. Но обо всём по порядку:

День1
Прямо к четырём оказаться для контеста у меня не получилось, поэтому я опоздал где-то на полчаса. Начал читать задание. Кто-то в это время уже набросал в CLOS модель машин и разгадывал фабрику. Фабрика представляла собой гейты с двумя входами (левый и правый) и двумя выходами (также левый и правый) и соединениями между ними. При этом соединение к одной точке (вход или выход) могло производиться только одной линией. Также фабрика содержит специальный гейт, называемый внешним, от которого поступает информация и на который эта информация уходит. В чате все предположили, что слева - входы гейта, справа - выходы. Ну и описание соответственно. Приведу прмер фабрики, которая была в задании:

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] и на выходе бы получился ключ, который должна выдавать каждая из фабрик.
Посмотрев, как входы и выходы специфицируются на каждом гейте и как вход на цепь специфицируется входами гейтов я сразу же подумал подать пустую фабрику "X: :X" и получил последовательность. И тут, как говорится, "Остапа понесло". Я предположил, что незвестна не только функция гейта, но ещё и функция внешнего гейта, на котором также происходит преобразование. Весь оставшийся день прошёл в попытках решить аналитически две неизвестные функции гейтов.

День2
День второй продолжился тем же, чем и закончился, а другие команды уже набрали свои первые очки. После обеда я всё же решил предположить, что внешний гейт - это всего лишь соединение машины и никакого преобразования там не происходит. Подавая разные топологии фабрик я всё же получил функцию активации гейта. На этом я почувствовал себя обессиленным. Наши же в это время создали создавалку случайных фабрик и сабмитилку прямо на сервер. И как бы было не смешно, но это принесло нам первые очки. Созданная симуляция фабрик не работала, дружно обсуждали семантику обратных связей, но так внятно ничего сделать уже не смогли. Перебиралка засабмитила решения ещё для двух машин. Пытались найти формат машин, но как-то безуспешно. К концу дня почти все сдались и перешли в разряд наблюдателей. К этому времени остальные команды закончили аналитику и дописали своих ботов. Сервер лёг.

День3
Состязание завершилось. 3 балла.

Итог
В следующем году обязательно буду участвовать. Всей команде Skobochka (allchemist, vseloved, rigidus, treep, dmitry_vk, ...) спасибо.

Комментариев нет:

Отправить комментарий