ICFP Contest 2010. Троичная машинная индустрия

Для тех кто не совсем в теме

Спешу поздравить всех –  не так давно прошел очередной ICFP Contest,  в котором мы очередной раз учавстовали. Для тех, кто еще не знает, в двух словах – это международное сореврнование для людей, обладающих даром программирования ;) Так, в этом году в этом соревновании более-менее активно учавствовало около 200 команд.

Как обычно соревнование проходило три дня. Команды, которые отослали решения в первые 24 часа, учитываются в т.н. lighting round’e. Все-все хватит ;) Правила и условие задачи можно спокойно прочитать в интернете.

Участники

В этом году в нашей команде было всего два человека – это Я (tt.kilew) Павел Тайкало, и Роман Мазур. Кроме нас, время от времени, подключался Александр Тищенко (amenaphes), и Павел Башмаков (pbashmakov).

Поиски подсказок и планы

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

[sourcecode language='java']
package com.stanfy.icfp10;
public class ICFPTaskSolver{
  public static void main(String[] args) {
    ICFPTaskSolver icfpTaskSolver = new ICFPTaskSolver();
    icfpTaskSolver.initialize();
    icfpTaskSolver.makeICFPTask();
    icfpTaskSolver.submitICFPTask();
    icfpTaskSolver.profit();
  }
  public void initialize() {
    System.out.println("Initialized");
  }
  public void makeICFPTask() {
    System.out.println("ICFP Task Started");
  }
  public void submitICFPTask() {
    System.out.println("ICFP Task submitted");
  }
  public void profit() {
    System.out.println("Profit");
  }
}
[/sourcecode]

Как оказалось, такой план, был не только у нас.

Начало непонимания

15:00(Дальше все время по локальному киевскому +3:00 GMT). Сервер, как ни странно, выдержал первую атаку ICFP-шеров. И уже через минуту мы уже вгрызались в полученное нами задание.

“Нипаняяяяяятнааааа, ну нипанятна же!” . По-моему первая фраза, которая был произнесена мною, после получения в руки заветных 4-х листов с заданием. То ли я был не в форме, то ли одно из двух, но задание я перечитал не раз и не два, пока в моем мозгу начались вырисовываться хоть какие-то знакомые образы.

15:10 Мы ПЫТАЕМСЯ зарегистиовать команду. К этому времени, как я понял, хлынул основной поток людей, и сервер был в жутком состоянии. В результате мы-таки зарегистировали команду под названием Stanfy, однако сервер выдавал Internal Error при логине. И было непонятно. то ли это глюк сервера, то ли это конкретно на нашей команде такое происходит. Как оказалось, возникла проблема при регистрации, и пришлось перегистрироваться под названием stanfyteam, осознание этого заняло у нас около трех часов(Как говорят други источники, сервер как раз-таки и отсуствовал примерно часа три). Правда, их мы провели достаточно продуктивно (Хоть задание прочитали).

На самом деле регистрация команды это было довлоьно критично для нас – т.к. многие задачи сводились к т.н. reverse-engeneering’у, и в случае остутствия сервера, можно было спокойно сдаваться, если нкито не обладает навыками телепатии или чего-то подобного.

Задание

Начнем в обратном порядке. Так вроде, проще для понимания :)

1. Есть машины. Для них есть топливо.
2. Надо собрать как можно больше машин.
3. Надо подобрать как можно топливо как можно к большему количеству чужих машин.
4. За каждое “подобранное” топливо к машине, включая и свою, вы получаете у.е. Причем тем больше, чем меньше людей подобрало топливо для этой машины. Так если к машине подобрали топливо только Вы, то ВЫ получаете 100% от дохода. Если еще кто-то, то прибыль делится 50/50, если еще кто-то, то 33/33/33 и так далее.
5. Топливо – это матрица (или набор матриц) из набора коэффициентов.
6. Машина – это (воспользуюсь описанием от adept’a) набор неравенств вида ABCDCBDBE – BCBDE > 0, где A, B,C ,D – это матрицы.
7. Описания Машины, и Топлива записываются строкой вида ’0102010201021121′. Т.е. набором из троичных битов (тритов).

Что обозначают эти нолики единички и двойки в описании топлива и машины – заранее не было известно. Нужно было “скармливать” эти строки серверу, и по результатам их интерпретации, делать какие-то выводы о формате описания. Изначально было известно, что эти строки могут описывать числа любой длины, могут описывать списки, списки списков, и т.п.

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

Организаторы, снова “зная”, что участникам этого покажется мало, придумали следующее. Устройство гейтов – заранее неизвестно. Т.е. гейт – это черный ящик с двумя входами и двумя выходами.Подумаешь, сказали мы. Элементы, ну и пусть что троичные. Нам-то какое дело! Поставил что-то на вход, померял значения на выходе. Записал. Изменил занчения на входе. Посмотрел на выход, записал. Делов-то!

Однако, организаторы не прекращая “знать”, что участникам этого покажется мало, придумали следующее. Перед тем, как отослать схему серверу на проверку, сначала надо было ее правильно описать. И, как уже, наверное многим стало понятно. Спецификации описания схемы не было. Была дана только работающая схема-пример, и сказано, что если на эту схему подать кое-какие данные (были указаны) , то в результате, мы получим префикс из 0, 1 и 2-к, которым мы должны “подписывать” свое топливо. Описание схемы выглядело следующим образом:

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

Фаза 3. Работаем!

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

где-то в 19:00 у нас готов каркас, который умеет выводить описание схемы. В виде, который понимает сервер.

В течение следующих часов четырех мы пытаемся найти функцию, по которой работают элементы схемы. Параллельно я пытаюсь найти/написать/придумать визулизатор схем, но потом отбрасываю эту идею за ненадобностью. Где-то в это время у нас появляется идея, что скоре всего, внутри элемента используются обыкновенные простые функции типа OR, AND, NOT и т.п, которые нам помогут. Поэтому в течение следующих несккольки часов мы, подбирая функцию, пробовали все подряд. В результате оказалось, что функции не такие и простые.

23:15 (8 часов после начала) Мы узнаем. как работат элемент схемы. Восстанавливаю по памяти. :)

Таблицы ТРИстинности

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

День второй. Да будет свет!

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

11:10 В процессе реализации основы для генератора машин, я вдруг осознаю. почему у нас неправильно работает схема. Оказывается, что на каждом такте обход схемы производится не с главного входа и потом к выходам, а начиная с 0-го элемента схемы, и дальше по нумерации. Осознав это, я впадаю в небольшое уныние, прикидывая, сколько драгоценного времени уйдет на переделывание логики раобты схемы. Рома справляется за 30 секунд, и радостным криком оповещает, что мы наконец-то получили префикс(ключ), которым мы должны “подписывать” наше топливо.

Вот таким он был  : 11021210112101221112

11:12 Садимся и брейнстормим по поводу того, как собирать схему по генерации топлива. После недолгих размшылений, мы не приходим к общему мнению, и Рома садится писать брутфорс для подбора необходимой схемы, я же пытаюсь логически осознать, что должно быть в схеме, и как она должна работать.

И где-то вот тут у нас начинается время откровенного “витания в облаках”. Надо было бы, как многие делали, сходить в гугл да поискать открытые репозитории, может нашли бы что-нибудь.

12:40 Я в который раз бросаю тщетные попытки визуализировать происходящее, и беру себе в личное пользование доску, таблицу ТРИстинности, и пытаюсь придумать что-то со схемой. Решение не хочет “рожаться” само собой, так что в большинстве своем, я рисую и стираю уже изряно поднадоевшие мне элементы.

15:00 Рома запустил 3-ю версию своего брутфорсера по подбору схемы генерации, говорит, что сомневается в правильности того, что он использует одинарные элементы. Мы уходим обедать. ибо мозги, видя отсуствие какого-либо продвижения, отказываются работать без приема пищи.

16:00 Как обычно, в процессе приема пищи, рождаются новые идеи. Рома придумал новый вид перебора схемы, я придумал какую схему надо собрать, чтобы получить необходимый нам выход. Идея заключалась в следующем : собрать банальный “повторитель”, который бы транслировал входные сигналы на выход, а потом путем его “улучшения”, сделать его таким образом. чтобы он первый раз отдавал заданный символ, а дальше работал как повторитель. Входной сигнал решили игнорировать.

Довольно быстро я и еще один Паша, придумываем как посмтроить простой повторитель с использованием трех элементов. Он тут же нарекается повторителем Тайкало-Башмакова ;) И мы подумываем над созданием методички, в которой объяснялся бы принцип его построения.

20:21 Долго ли коротко ли, но я вымучиваю три схемы (для 0, 1 и 2), на доске, до того. как брутфорсер Ромы подбирает схему генерации префикса( у Ромы не совпадает всего 1 или 2 трита в ответе ;). Мы их реализуем, и Вуаля! Размер фабрики относительно большой (3*N), но глядя в IRC канал, и увидя, что есть люди у которых 8 элементов на трит, при этом осознавая. что мы потратили на это почти целый день, решили ничего не править, оставить как есть, и по-быстрому раскопать формат топлива.

21:30 Рома находит замечательное топливо. которое во-первых, принимается сервером, а во-вторых подходит к какой-то машине. В результате недолгой проверки, мы обнаруживаем, что таких машин всего много, и руками их туда сабмитить не получится, учитывая то. что сервер под вечер хотя еще пока не лежал, но время ответа было приличное. Для автоматического сабмита, мы быстро прикручиваем WebHarvest, и запускаем его.

22:30 Формат топлива до конца так толком и не ясен, однако мы находим еще одно топливо, меньшей длины, которое тоже подходит к машинам. Запускаем WebHarvest, и подбираем топливо для 63 машин под конец дня.

День третий

Дают о себе знать интенсивные нагрузки на мозг ;) Но! Как ни странно, хоть организм и не выспался, разогретые мозги работают довольно-таки шустро.

10:54 Собран генератор машин для двух опливных баков. Он был получен в результате попыток разбора формата машины. Формат окончательно не ясен, но основные компоненты уже выделены, остается дело за малым.

11:50 С топливом тоже не все так плохо, и в это время я закончил генератор топлива для произвольного количества топливных баков и интгридиентов в воздухе. Как потом  окажется, работал он не всегда правильно. Однако даже в таком виде он нам помог очень сильно с подбором топлива для машин.

12:45 Наконец-то мы получаем полностью рабочий парсер машин, что позволяет сосредоточиться на задачах более полезных, таких как подбор топлива для других машин. Сервер как всегда, подлагивает, WebHarvest, исправно собирает статистику о новых машинах, мы оптимизируем наши достижения. В процессе оказывается, что проверка “подходимости” топлива к машине, у нас сильно хромает, и часто выдает неправильные значения. Кроме этого, мы понимаем, что генератор топлива у нас тоже работает не всегда, поэтому настраиваем WebHarvest на автоматическую заливку того, что 100% решается, а сами ищем, где же мы ошиблись.

17:10 Наконец-то! Я нахожу ошибку в формировании строки топлива. Вернее, даже не ошибку, а особенность формата задания топлива. Все дело в том, что не все числа должны были быть в одном формате ;) В этом мы и просчитались, собственно. На самом деле, нам не очень просто “дался” первый формат чисел, и, мы не могли даже подумать, что может иметь место два формата чисел.

17:30 И вроде бы все есть, но чего-то сильно не хватает (Ц)итата. Мы активно постим те решения, которые у нас есть, Рома улучшает свой брутфорсер для генерации топлива для машин. главной проблемой становится то, что у нас не получается 100% проверить, подходит ли топливо к машине или нет. Мы перечитываем условие, перепроверяем по 10 раз, но где-то в 80% случаев наше топливо не проходит проверку на сервере. Процесс усложняется тем, что сервер “висит”, и каждая следующая проверка правильности генерации топлива занимает много времени. Мы меняем int на long, затем long на double, греша на точность вычислений и переполнение разрядной сетки. Мы все-таки находим баг в рассчете топлива, однако сервер все еще отсекает наши 60% решений.

20:40 Решаем сабмитить то, что есть, и, так как на данный момент времени мы сгенерировали всего 6 машин, мы решаем, пользуясь тем, что сервер активно глючит, залить свои машины с целью получить свои “дивиденды” ;) логика наша проста – сервер глючит, следовательно никто не сможет засабмитить решения для наших машин. и мы некоторое время будем получать от них максимальный доход ;) Однако, это нам не удается – ибо сервер глючит настолько, что часто невозможно даже просто зайти на сайт, не говоря о том, чтобы совершить пару кликов. WebHarvest постоянно сообщает нам о Request-Timed Out.

23:10 Идем домой, видя что все наши попытки сделать хоть что-то упираются в то, что сервер откровенно лежит.

День четвертый (заключительный)

01:20 У меня наконец-то получается достучаться до сервера, и он принимает все наши 72 машины (максимум). Я потираю руки, видя, что сервер временно отказывается принимать решения для машин.
07:40 С этого времени и до самого конца контеста, мой алгоритм работы был следующим – помотреть, работает ли Web-Harvest, проверить, не загнулся ли БрутФорсер по подбору топлив для машин, подправить CarSolver, чтобы мы все-таки правильно “расчитывали” топливо для машины. На этот момент у нас 70 место.

14:07 Я бросаю гиблое дело по уточнению правильности работы подбора, видя что остался всего час. Все в последний раз перевроверяю.

Из 2600 (на тот момент) машин у нас “решено” ;) около 1900. Правильно решено – ровно 600;)

15:00 Окончание контеста. За минуту до окончания, мы занимали 40-е место. Однако по правилам контеста, где-то там вычитались налоги за каждую машину, и в результате в последнюю минуту мы скатываемся на 52е. Обидно ;) Но все равно ;) Приятно себя видеть на первом экране, не пользуясь скроллингом ;) (Главное монитор взять побольше;)

PS ;)

ICFP контест этого года понравился. Понравился больше, чем в прошлом году, кто и что бы там ни говорил ;) Наверное, мне просто нравится data-mining :) и reverse-engeneering. Было весело! Организаторам – большая благодарность ;) Вот, кстати, Hall of fame текущего года ;) Здесь просто собраны все команды, получившие хотя бы одно очко в результате. А по этим линкам, можно прочитать. как мы принимали участие в прошлом году.

Результат

• Команда - StanfyTeam
• Язык – Java + немного Groovy + немного WebHarvest
• IDE – Eclipse
• Tools – SVN, Skype :) И все, наверное ;)
• Место – 52