ICFP 2007 или "Как лодку назовёшь..."

[himself]

Конкурс ICFP 2007 торжественно завершился. Команда, в которой я играл, EFG (Epic Fail Group, "команда эпического провала" ), в полном соответствии со своим названием, заняла почётное 64-е место из 869-ти.

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

Да и вообще, единственное, что принесло нам копейку - это случайно обнаруженный внутри файла...

(далее)

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

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

А теперь подробнее.

Авторы ICFP обожают придумывать своим заданиям любопытные предыстории. Вот и на этот раз, случилось так, что на планету Земля из космоса грохнулся маленький Эндо расы Фуун. Тело Эндо совершенно не приспособлено к жизни в условиях ночи, дождя, гопников и химических удобрений. Ему хочется солнца, лета, девуш... ну и ещё он хочет быть не пришельцем, а коровой (чтобы переносить нашу гравитацию). Без всего этого он немедленно же умрёт, а чтобы этого не случилось, поломанный его корабль законсервировал Эндо, и пытается изменить его ДНК, чтобы, во-первых, превратить Эндо в корову, а заодно поменять ночь на день, дождь на солнце а гопников на девушек. Такая могущественная у Эндо ДНК.

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

ДНК фуунов изменяет фууна (и мир вокруг него) в два этапа:
1. ДНК компилируется в РНК.
2. РНК исполняется, и получается картинка.

Корабль передал организаторам ДНК Эндо (7 с половиной мегабайт). Если скомпилировать этот ДНК, получатся ночь и гопиники. Менять ДНК нельзя. Но можно дописать к нему что-нибудь, причём чем меньше - тем лучше (у корабля садятся батарейки от длинных ДНК).

Процесс превращения РНК в картинку несложен - по крайней мере, у нас проблем не возникло. Это просто написание интерпретатора семибайтных команд по отрисовке.

Вся закавыка была в первом этапе. ДНК превращается в РНК следующим образом:
1. Считывается закодированный в ДНК паттерн - кусок строки с "дырками".
2. Считывается закодированный в ДНК шаблон - кусок строки со "слотами".
3. Считывается ещё немного данных. Если они подходят под паттерн (то есть буквы совпадают с буквами паттерна, а там, где у паттерна "дырки", может быть что угодно) - всё, что прочитано, отбрасывается, а вместо этого к ДНК слева приписывается считанный шаблон, в котором "слоты" заполняются совпавшими кусками данных.

Например.
Паттерн: (ABCD____EF)
Шаблон: (TEXT * TEXT)
Данные: ABCDKLMNEFGHIJKL
Результат: TEXT ABCDKLMNEF TEXT GHIJKL

Примерно так, только раз в пять запутанней. После выполнения этих операций, догадайтесь, что?

Правильно - повторить.
Примерно два миллиона раз.

Написать парсер этого чуда было несложно. Основная проблема была в скорости. Тупое "копирование" строк приводило к невероятно медлительной обработке, поскольку паттерны в большинстве своём были такие:
AB__...(семь мегабайт пропусков)..._CD
Соответственно, если паттерн совпадает, мы должны вставить его в шаблон. То есть, скопировать семь мегабайт данных в памяти. Один раз это, может, и ничего, но два миллиона раз скопировать по семь мегабайт - результата не дождёшься. А ведь это только одна компиляция, а в процессе поиска решения компиляции идут одна за другой.

Решение, которое пробовал реализовать я, сделано на связанных списках. Вкратце смысл его в следующем: мы работаем не со строкой, а с набором пар:
...
(начало, длина)
(начало, длина)
(начало, длина)
...
Когда мы пытаемся прочитать очередной символ, мы смотрим, какая пара у нас выбрана "текущей", и читаем из неё. Дойдя до её конца, мы переходим на следующую пару.
В таком случае, чтобы "скопировать" семь мегабайт данных, достаточно просто найти их начало в этом списке, найти их конец, и скопировать только цепочку списка между ними (а она "лёгкая", там же нет данных - только указатели на них).
Например:
...
(начало1, 5 мегабайта)
(начало2, 2 мегабайта)
(начало3, 3 мегабайта)
...
Копируем:
...
(начало1, 5 мегабайта)
(начало2, 2 мегабайта)
(начало1, 5 мегабайта)
(начало2, 2 мегабайта)
(начало3, 3 мегабайта)
...
Казалось бы, скопировано 7 мегабайт, но на самом деле мы просто сделали копию указателей на данные - а это примерно 32 байта.

Реализовывать эту гадость было ужасно неудобно (ДНК фуунов совершенно не рассчитывалась под такие извращения), но я, плакая от усталости, всё-таки сделал это. И что бы вы думали?
Уже на двадцатой итерации длина цепочки ссылок была порядка нескольких тысяч элементов.
То есть, длина цепочки росла даже не линейно.
То есть, ДНК фууна устроено таким образом, что этот подход просто неэффективен. Он действительно чудовищно быстр на первых итерациях (где цепочка ещё маленькая), но с каждым следующим проходом получается так:
1. Была цепочка длины 3.
2. Скопировали, получили цепочку длины 6.
3. Скопировали её, получили цепочку длины 12.
...ну и так далее.
При этом длина суммарных данных в цепочке близка к первоначальной. Когда мы работаем со строкой, мы тратим много времени на копирование символов, но в итоге строчка получается примерно того же размера, и доступ к ней очень быстр. Когда мы работаем с моим списком, мы моментально копируем огромные блоки, но ДНК написан так, что дробление информации на кусочки неограниченно растёт. В результате с некоторого момента всё работает ещё хуже, чем в "наивной" схеме.

Ну и как они предполагали решать эту задачу?
(UPD: Оказывается, всё-таки можно сделать хорошую реализацию двусвязного списка. Ну что ж, значит я попросту облажался )

ДНК фууна был любопытен ещё и тем, что в нём скрывалась куча приколов.
Например, добавив к РКН маааленький префикс из инструкции, можно было заставить его генерить не картинку "грустного Эндо около сломанного звездолёта", а инструкцию:

Если вы видите эту картинку, значит носитель этой ДНК потерпел крушение на неизвестной планете. Пожалуйста, ничего не трогайте в ДНК, и вызовите службу поддержки с Альфа Центавры.

Если вы совсем-совсем никак не в состоянии связаться со службой поддержки, используйте следующий префикс, чтобы получить руководство пользователя ДНК:
[небольшой префикс]

Если носитель ДНК находится вдали от искуственных источников освещения, а естественный источник сейчас освещает противоположную сторону планеты, активируйте этот префикс, чтобы развернуть планету к Солнцу нужной стороной:

И самое главное:
НЕ ПАНИКУЙТЕ

Ещё существовали префиксы на DNA Self-Test (картинка с текстом "Checking memory read... OK; Checking memory write... OK; Checking integer overflow... OK ", причём ДНК на полном серьёзе всё это тестировала, а в картинку выводились результаты тестов - 25 штук).

Самое интересное обнаружилось незадолго до окончания соревнования. Кое-кто из нашей команды нашёл в исходном коде ДНК строчку "Portable Network Graphics". Дампнув содержимое в файл, он убедился, что это действительно встроенный PNG-файл. В нём на белом фоне было написано:
Human Audio follows.

И действительно, дамп следующего куска ДНК оказался wav-файлом. Голос в нём произнёс:
"IICIFPCCI...."
Похоже, это был ещё один префикс.

Единственная проблема со всеми этими префиксами, как я уже сказал, в том, что за отсутсвием эффективного компилятора большинство из них просто невозможно было запустить. Не говоря уже о, собственно, сборке Эндо (ведь именно в этом было задание). Для сравнения, полная сборка Эндо - два миллиона итераций, тогда как парсивший один из префиксов всю ночь мой компьютер успел сделать только 490 тысяч итераций. Самый короткий префикс тратил 130 итераций - то ли Self-Test, то ли страничка "НЕ ПАНИКУЙТЕ".

Надо бы подвести всем этим рассуждениям какую-то черту...
Играть было увлекательно. Тяжело, но увлекательно.

А теперь я, пожалуй, вернусь к ever17, и посвящу ему следующий пост.