Current music:

Forest Of Shadows - Eternal Autumn (Where Dreams Turn To Dust (MCD))

ICFPС'07 аточод
ICFPC'2007 == ICFP Programming Contest 2007 года, десятый по счёту (а ICFP == International Conference on Functional Programming). Описание и исходные данные — по ссылке. Под катом аточод об участии и ссылки на всякое.

Мою команду организовывал Дима mindszenty (ака mantycore), помимо меня подписав ещё Игоря Русских (автора Colorer) и _zee_, причём было это меньше чем за неделю до эвента. Где-то посередине мы потестили вебдванольное общение в basecamp (отстой), потом за день до Игорь попытался найти рациональное зерно в алгоритме шифрования картинкок из блога (которого там не было). Плюс сделал нам svn repository на гуглокоде (из него, кстати, любой желающий может невозбранно понатырить Наше Всё и ужаснуться. И картинки.), гуглогруппу и поднял жабберовского бота, симулирующего конференцию. Я отчаянно прокрастинируя написал на С интерпретатор виртуальной машины 2006 года и попытался срочно доделать Универсальный Интерфейс на C#, позволяющий вызывать произвольные методы через рефлекшен, но не успел, зато жутко невыспался.

Кстати, если кто вдруг не читал _adept_'овский аточод про ICFP'2006, это стОит сделать, ибо объясняет наше исходное восприятие всего.

Собственно, таймлайн (в моём GMT+2, у Зи и Димы было +3, у Игоря -6)
13:00 пятницы, открывается описание задачи и исходное ДНК. Мы с Димой его читаем.
14:40, просыпается Игорь (проспав, насколько я понял, четыре часа или около того), мы как раз вдумчиво доперечитываем описание. Я начинаю писать интерпретатор ДНК на шарпе, Дима -- интерпретатор РНК на руби (но собирается куда-то поехать), Игорь читает описание и тоже собирается поехать на работу.

---

Лирическое отступление для тех, кому влом самостоятельно читать этот ужос на крыльях. Дана семимегабайтная ДНК потерпевшего крушение прешельтса (случайно собранного Intergalactic Garbage Collector, ужасная судьба!), построенная Разумным Создателем (FuunCorp, inc.). Состоит из четырёх оснований -- I, C, F, P. Интерпретируется так: на каждом шаге её начало декодируется как паттерн для чего-то вроде простенького регулярного выражения, в котором могут быть закодированные основания, инструкции skip (пропустить количество оснований, закодированное дальше Особым Образом), search (пропустить всё до закодированной дальше подстроки) и кепчурящие скобочки, плюс команда "III", выводящая следующие семь оснований в виде кодона РНК, но никак не влияющая на строящийся паттерн. Если в процессе кончилась ДНК, программа завершается. Декодированное от ДНК откусывается. Дальше аналогичным образом строится темплейт, состоящий опять же из оснований, невлияющих команд вывода РНК, подстановок n-ого кэпчура (с опциональным L раз применённым обратным кодированием) или закодированной длины n-го кэпчура. И тоже всё декодированное от ДНК откусывается. Дальше производится Match, если неуспешный, то повторяем всё с самого начала, если успешный, то всё заматченное тоже откусывается от ДНК, а на его место вставляется темплейт (с подставленными кэпчурами, естественно) и опять-таки всё повторяется с самого начала.

Полученные семиосновные куски РНК подаются на вход Рисовалки, которая интерпретирует их как инструкции для рисования цветной картинки 600х600 пикселей, вроде "сдвинуться вперёд на пиксель", "повернуться по/против часовой стрелки", "добавить в аккумулятор цвет", "нарисовать пиксель цветом из аккумулятора", бла бла бла. Плюс up to 10 backbuffers, с соответствующими командами их порождения и совокупления (с учётом прозрачности!).

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

---

Так вот, я начинаю писать интерпретатор на шарпе и со мной немедленно играет злую шутку описание предыдущего контеста. Там же как всё было — тоже виртуальная машина, её строишь, запускаешь, она входит в диалоговый режим, выдаёт как бы задачки, ты их решаешь, за выполнение получаешь Кодовые Строчки, которые посылаешь организаторам, которые начисляют тебе очки. Само то есть собой кодовые строчки зашифрованы страшным образом и сама машина тоже совершенно непознаваема. Я наивно предположил, что и в этот раз будет что-то такое, мы это всё построим и запустим, введём строчку, данную в описании (про которую сказано, что случается что-то странное), а дальше она как-то даст нам какие-то задания, инструкции по вводу решений етс. Поэтому я сразу сказал, что нам следует отбросить все мысли о дебаггинге происходящего, это бред, этого не может быть, потому что не может быть никогда, ну и прогал соответствующим образом (впоследствии сполна вкусив последствия premature optimization).

19:00 опять появляется Дима, Игорь говорит, что уже довольно далеко продвинулся в деле написания интерпретатора РНК (тоже на руби), я неуклонно приближаюсь к завершению своего интерпретатора ДНК, мы немножко разговариваем о перспективах выкидывания исходного ДНК нафиг и тупой генерации длинного префикса для рисования.

20:00 Игорь обнаруживает, что в начале исходного ДНК валяется длинная последовательность чистой генерации РНК, использует её для тестирования своего интерпретатора, получает картинку с каким-то префиксом.

20:30 Я, собственно, дописываю код, но он глючит, потому что я пишу всё поверх обычного динамического массива, в котором ДНК лежит задом-наперёд, чтобы можно было быстро удалять и добавлять всякие штуки в начало, но в процессе подстановки кэпчурей в темплейт надо генерить всё в естественном порядке, а потом инвертить и дописывать, короче я запутываюсь и не могу распутаться, потому что начинаю жутко хотеть спать. Вдобавок, продолжительная медитация на строчку "skips and unquoted capture substitutions should be performed faster than in linear time" из описания наводит меня на мысль, что их любимое занятие — это сделать скип на пару миллионов оснований и записать обратно заскипленное плюс что-нибудь ещё (вставляя таким образом это что-нибудь ещё в середину ДНК), так что мне нужна специфическая структура данных: список (чтобы можно было быстро вставлять) с каким-то древовидным индексом поверх (чтобы можно было быстро делать скипы).

Нахожу у себя Wintellect PowerCollections (у них замечательная лицензия, кстати, BSD но с явным запрещением распространять на код требование предоставления кода, то есть анти-GPL как он есть), в нём обнаруживается BigList, который решает обе моих проблемы — теперь я храню ДНК в естественном порядке (и поэтому не запутываюсь!) с логарифмическими вставкой/доступом/удалением.

Переписываю, разбираюсь с SVN и начинаю ловить баги, периодически используя Диму в качестве толкователя описания.

2:00 Заработало наконец. Заливаю текущую версию и РНК, предположительно рисующую начальную картинку. Рассказываю, как компилить шарп из командной строки в отсутствие вижуальной студии ("MSBuild someProject.csproj", ага =)). Игорь начинает ловить баги в своём интерпретаторе РНК. Я качаю руби и ImageMagick под неё, дописываю к своему интерпретатору вызов с префиксом.

4:00 При запуске с префиксом из мануаля обнаружилось ещё немножко глюков, поправил, залил, залил получающуюся РНК — предполагая, что это SelfCheck, про который что-то писали в их списке рассылки.

4:40 Неожиданно появляется Зи. Игорь наконец рендерит селфчек (это был он) и начинает изъясняться междометиями, потому что странно и удивительно видеть, как это всё действительно работает.

5:00 Игорь рендерит с префиксом с картинки из начала ДНК и выкладывает результат. Междометиями начинают изъясняться все.

5:30 Игорь рендерит хелп по гайду, воспользовавшись новым префиксом. Тогда он, кстати, выглядел немножко по-другому, ибо в Игоревском интерпретаторе не было поддержки clip, fill и ещё каких-то функций. Немножко ещё говорим и я иду спать.

---

Cуббота Я просыпаюсь, завтракаю, читаю в мейле что Зи написал полный и быстрый рендерер РНК на жаве, синхронизируюсь с SVN и выхожу в наш типа чат в 15:20. Там мы некоторое время общаемся, я тренируюсь запускать рендерер, который действительно довольно быстрый — на отрисовку начальной картинки на моей машине уходило порядка 160 секунд на ДНК->РНК и меньше минуты на, собственно, отрисовку РНК.

17:30 ручками расшифровав префиксы для первой картинки (с Don't Panic!) и второй, с правилами пользования гайда, я наконец понимаю, что они имеют в виду:
// Guide preface
Pattern: ( ? IFPCFFP ) I
Template: %0:0 C
// Guide navigation
Pattern: ( ? IFPCFFP ) II
Template: %0:0 IC
(%L:N -- вставить N-ый кэпчур, зашифрованный L раз)
То есть оно ищет вот такую вот метку и несколько I после неё, откусывает и вставляет обратно всё до метки включительно и "С" или "IC", что подозрительно похоже на двоичную запись чисел 1 и 2 в их внутреннем формате. То есть фактически в определённом месте памяти нолег (все I) меняется на ненолег. Перевожу 1337 в двоичку, запускаю, получаю оглавление гайда, yay!

Тем временем Зи идёт спать, а Дима едет на деньрожденья к девушке.

19:50 Мы с Игорем наперегонки пишем выдиралку для страниц гайда, я успеваю раньше и выдираю все, указанные в оглавлении. Внимательно дочитываем недочитанное, в том числе и первую страницу таблицы функций, параллельно обсуждая Всякое. При мысли о том, что это всё, по видимому, придётся вызывать при помощи этого ужасного ассемблера, у меня начинается эмокодерская депрессия. Чтобы избавиться от чёрных мыслей я проверяю, что Fuun Sequrity Features действительно зашифрованы rot13 и начинаю ручками вбивать бред в дешифратор, после третьего абзаца скидывая задачу на плечи Игоря, который занимался тем же самым.

20:30 Просыпается Зи.

21:00 Автоматизирую перебор, нахожу в гайде страницы номер 3, 9 и 100, не указанные в оглавлении, дальше искать влом. Ффтыкаем. Игорь замечает, что характерные "стеганографические" пятнышки есть и на странице Most Wanted, и что вообще говоря это просто прозрачные дырки, сквозь которые просвечивает фон.

23:30 Я ковыряюсь в стеганографии. Обнаруживаю, что если одну 24битную разложить в 8*3 однобитных, то на картинке с Е.Т. видно какое-то число и вообще Странное в младшем разряде. Однако понять, как работает алгоритм в целом, не удаётся. Происходит длительный депрессивный тупняк, потому что я всё ещё цепляюсь за призрак надежды на то, что хакать машину всё-таки не придётся. Игорь ручками вызывает разные функции и смотрит на результат.

1:55 Я понимаю, что ошибался, о чём и сообщаю Игорю. Рефакторю нафиг интерпретатор, делаю отдельные процедуры декомпиляции кода в паттерн и темплейт и начинаю писать компиляцию паттерна и темплейта (на своём ассемблере) в код. И поиск подстроки в ДНК. UI решаю пока не писать, а завожу специальный файлег на шарпе, в котором можно писать всякий временный код и который не лежит в SVNe.

3:00 Опять появляется Зи и начинает ломать Alien Virus Alert.

5:46 Игорь замечает, что запись AAA_GeneTablePageNr имеет длину 18h, так что это, наверное, не код, а данное. Прописывает туда код двойки, прямо в файле с ДНК, вызывает префикс для демонстрации гайда на 42 второй странице (Gene Table) и видит вторую страницу (из 14), ура. Тут же появляется грустный Зи, поломавший Alien Virus Alert — там оказывается совершенно беспонтовый "рекламный текст". Причём в процессе ломания Зи чуть ли не OCR написал на коленке, чтобы самому ручками не вбивать символьчеги.

8:00 Я дописываю ассемблер, неоднократно испытывая Просветление по пути. Наконец-то понимаю, что язык виртуальной машины на самом деле очень мощный и даже удобный, начинаю понимать, как оно всё на самом деле работает. Общаюсь с Игорем, с ним та же фигня. Очень жалко потерянного времени, нужно было с самого начала плотно изучить язык и разобрать все префиксы.

Зи тем временем ковыряется в стеганографии, без особых успехов.

9:00 Оформляю компилятор ассемблера в виде отдельной проги (с одной строчкой кода -- вызовом соответствующих методов у интерпретатора). Ещё через полчасика -- с поддержкой бинарных и шестнадцатеричных констант. Игорь вытаскивает все 14 страниц адресов. Зи пытается приспособить свой OCR для распознавания этой таблицы. В десять я иду спать.

---

Воскресенье Я просыпаюсь в четыре с минутами, завтракаю, сажусь за комп, в конференции живой Дима, в пять появляется Игорь. Остаётся 20 часов до дедлайна. Мы что-то делаем, я нахожу у себя fineReader и пытаюсь распознать таблицу функций, но безуспешно, Дима принимает эстафету стеганографии.

18:00 Игорь вызывает функции ImpDocNN, обнаруживает что это более детальное описание местных функций в сишном синтаксисе, даже с параметрами.

19:30 Игорь вызывает printGeneTable с параметром enableIntegrityChecks = true, получает ту же табличку генов, но ещё и с помеченными неисправным функциями (очевидно, проверяется контрольная сумма). Я заливаю первую версию интерактивного дебаггера.

21:45 Игорь достаёт все картинки про историю ICFP (предыдущие соревнования, бла бла бла). Там явно виден Стеганографически Зашифрованный Префикс (некоторые буковки жёлтые).
22:00 Он же обнаруживает, что рядом с повреждённой функцией рисования коровьего пятна лежит её Error Correction Code (хемминговский, судя по описанию). Мы с ним долго общаемся на тему дальшейших действий: повреждённых функций много, их бы надо бы починить бы, однакож страничка мануаля с описанием процесса починки немножко зашифрована, её бы надо бы расшифровать бы. Ситуация с расшифровкой осложняется тем, что в тексте из гайда (который был зашифрован rot13) говорится, что процедуре расшифровки нужно скармливать Purchase Code (24-acid sequence), а в ИмпДоке ей скармливается наоборот Int24 (которое 23-битное на самом деле) — зашифрованное неизвестным ключом нулевое значение. Нифига не понятно кому верить и что делать.

23:00 Я отвлекаюсь от дебаггера и достаю зашифрованный префикс из описаний предыдущих соревнований. При применении он превращает стандартную картинку в зелёную и полупрозрачную, с какими-то линиями. Нафига нужно — непонятно. Параллельно выясняется, что Игорь правил зишный рендерер, внёс туда баг, закоммитил, пофиксил баг и НЕ закоммитил =) Да, так вот, этот префикс взводит в true какой-то неописанный флажок сразу перед vmu_Mode (что-то со старым алгоритмом мутации). На рисование гайда он не влияет (а я надеялся, что если его вдруг выставить и отрисовать картинку со стеганографией, то что-нибудь произойдёт!)

0:00 Игорь успешно применяет CorrectErrors к повреждённому коровьему пятну. Я замечаю, что ECC для той функции лежит сразу после неё самой, с отступом 24 байта, и имеет ту же длину, что она сама, однако другие корраптнутые функции так вот вслепую не чинятся. Дима обнаруживает, что каждый ген при запуске первым делом выводит уникальный кусок junk RNA, так что можно смело писать трейсер -- если бы табличку бы распознать всё-таки.

2:00 Игорь замечает таблицы фонтов и решает подставить другой фонт и вывести character table им (так она выводится точками). Я тем временем делаю дебаггер совсем-совсем клёвым, с консольным юзер-интерфейсом, командами трансляции ДНК в ассемблер и наоборот ассемблера в ДНК (в том числе и из файла), пошаговым исполнением, поиском подстроки, выводом текущих адресов и размеров зон, командами дампа памяти (относительно начала ДНК/зелёной зоны (immutable кода и переменных)/синей зоны (стека)), добавляю в транслятор файлов распознавание комментариев.

3:00 Игорь успешно заменяет фонт перед вызовом хелпа с char table, Дима замечает, что это разновидность EBCDIC.

3:50 Игорь экспериментировал с biomorph и научился превращать Эндо в верблюда (OCamel) или слона (MLephant). Я дописал к дебаггеру брейкпоинт по выводу определённой РНК, взял РНК putChara, научился доставать из стека его параметр и добавил дамп этого всего в отдельный файлег.

5:00 Дима написал декодер задампленных кодов из EBCDIC в аски, сдампил gene table и начал писать разбиралку результатов (оно ж непрерывным потоком дампится, а из него нужно выделять имена, адреса и длины функций). Я заметил, что на исходной картинке есть Летучайа Тарелка, а на результирующей — нет, и попытался наваять префикс, который бы вписал в начало кода процедуры рисования оной код возврата.

7:00 Дима собрался уходить на работу и составил Жизнеутверждающий Списог того, что нам маза попробовать. Оставалось шесть часов, у нас с Игорем нарастал пессимизм и предчувствие неминуемого прососа, ибо исследовать всякое, конечно, очень интересно, но очки дают немножко не за это, а у нас в активе был только самый первый код из гайда, для включения дня. С таблицей очков, кстати, всё очень забавно было: в первые два дня там подавляющее большинство команд не сделало вообще ничего, а где-то пятьдесят шли вровень с этим самым кодом. Затем кто-то обнаружил, что код можно соптимизить на одно основание. Затем этого кого-то выкинуло из топ15, все остальные увидели, что у него префикс на единицу короче и тоже срочно бросились оптимизить. Ну и на момент -6 часов до дедлайна была толпа совсем лузеров, затем толпа людей, включивших солнце, затем толпа людей, оптимизённо включивших солнце (и мы среди них на 70 месте), а затем совсем немножко команд, сделавших что-то ещё. И нам было грустно находиться среди одинаковой толпы людей!

Так вот, одной из вещей, о которых напомнил Дима, было загадочное поле "hitWithTheClueStick", очень длинное, но не функция. Ну я быстренько дебаггером дампнул кусок из начала и увидел совершенно явную аски-графику, какие-то буквы. Вот жеж! Тогда я срочно дампнул всё в файлег и попытался подобрать ширину экрана, по совету Димы поставил 16 и О Чюдо! прочёл что-то вроде "Achtung! Image in portable network graphics format follows". Окей, там дальше действительно шли какие-то явно бинарные данные, но немножко, а потом ещё много бинарных данных (разделялось оно основанием "P", как положено числам). Посмотрел на хедер произвольной png-шки в шестнадцатеричке, посмотрел на начало первого куска, а там и вправду оно. Конвертировал, скинул в файл, а там картинка с текстом про то, что дальше идёт звук. Сказал конвертеру скинуть следующий кусог в mp3, а там голос быстро-быстро читает основания. Выложил в svn, попытался на слух записать, однако что-то не удалось, а Игорю удалось, вбили префикс, получили расшифрованную страничку гайда Beautiful Numbers.

Что с ней делать было как-то непонятно, я ещё немножко потыкался кругом, поставил брейкпоинт на вызов crypt (это уже совсем просто было, запускаешь дебаггер, дампаешь начало интересующей функции, там первая инструкция — вывод уникальной junk RNA, ставишь на неё брейкпоинт и запускаешь), посмотрел в стек, обнаружил что вместо заявленных int9[128] (сто двадцать восемь байт ключа) идёт int9[8] и какая-то фигня непонятная, видимо упомянутый где-то способ передачи укороченных параметров. Но нам это всё как-то совершенно бесполезно было.

10:46 Дима уехал на работу. Игорь попытался позапускать крякалку с разными числами, безуспешно. Я ещё несколько раз пытался убрать тарелочку, безуспешно. Решил, что мой код корраптит стек. Нашёл себе функцию colorBlack, она маленькая, всего 172h оснований, и начал смотреть, как она вообще работает. Оставалось два часа до конца эвента.

Вообще фантастика, конечно — по идее, это в первую очередь надо было сделать. Редкостный идиотизм. Ну вот смотрю, значицо, смотрю и вижу Странное — оно как-то очень уверено доступается явно в зелёную зону посредством скипа на константу (а не поиска кода начала зелёной зоны и потом скипа на константу, как это делали мы). Смотрю дальше — а там всё странней и странней, идёт явно возврат из функции, который точно так же доступается к синей зоне (стеку то есть). И тут я понимаю, что моё исходное представление о красной зоне как о стеке выполнения функций попросту неверно, в красной зоне функция всегда одна, текущая. А возврат из функции выглядит так:

Extracting pattern : !75 ( !7509409 ) ( !24 ) ( !24 )
Extracting template : IIPIP %0:1 IIPIP %0:2 IICIICIICIPPPIPPCPIIC %0:0

!75 — это прыжок до начала зелёной зоны, там ещё кусок функции оставался, его нужно было Зохавать
!7509409 — это прыжок через всю зелёную зону с записыванием её в нулевой кэпчур
а дальше вытаскиваются два int24 — адрес возврата типа.

И подставляются внутрь этого вот кода в темплейте, а потом идёт закэпчуренная зелёная зона. На следующем шаге код со свежеподставленными параметрами раскрывается:
Extracting pattern : ( !x ( !y ) )
Extracting template : %0:0 %0:1
Где x и y — это те подставленные числа (адрес и длина, по ходу). В нулевом кэпчуре (они по закрывающим скобкам нумеруются) оказывается какой-то код, в первом -- всё зохаванное в процессе матча, которое возвращается на место.

И всё.

11:48 Я получаю префикс, убирающий летучую тарелку.
Pattern: ( ?IFPICFPPCFFPP !4406230 ) !161
Template: %0:0 IFFCPICCFPICICFPPICICIIPIPIICICIICCICICIICICIICCCPIICIIPIPIIICCPIICIIPIPIIICCPIICIICCCICCICIPPCPCCICCICIPPICPCCFCCFCCFCICICICCICICFICCCFCPICCFPICICFPPICICIPPPIIC
Маркер начала зелёной зоны, адрес функции минус 13 (длина маркера начала зелёной зоны), длина того, что я собираюсь вставить в начало функции. В темплейте уже закодированный код возврата, описанный выше.

И ТАРЕЛКА ИСЧЕЗАЕТ!

Оставшийся час мы очень суматошно и глупо решаем, что будем убирать, периодически коммитим, думаем как бы это соптимизить (чтобы уменьшить длину префикса, за неё очки отнимают). Оказываемся на тридцатом месте, последний коммит не проходит, потому как за три минуты до конца падает их сервер =) Правда, я прикинул, выше 28 места не поднялись бы всё равно таким образом, так что и так неплохо получилось.



Мысли по поводу следующего года тут.