?

Log in

No account? Create an account
dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
Participating in ICFPC-2006 for fun and profit :) 
26th-Jul-2006 06:05 pm
Как я участвовал в ICFPC-2006

Это первая часть рассказа. Тут вторая часть, а тут - окончание.

Короткое вступление для тех, кто не в теме.

Каждый год случается международная конференция ICFP - International Conference on Functional Programming. К этой конференции приурочен програмерский contest под названием ICFPC. Несмотря на название конференции, участвовать в контесте может любой желающий, и пользоваться можно любыми языками, не только функциональными, кроме того - участники могут объединяться в команды. Contest отличается от соревнований типа ACM и topcoder тем, что он менее "заточен" под какие-то конкретные языки или наборы навыков, а задачи в нем прикольные и позволяют получить удовольствие не только от победы, но и от участия.

Это третий ICFPC, в котором я принимал участие. Короткий отчет о ICFPC-2005 можно прочитать тут, отчета об ICFPC-2004 у меня. к сожалению, нет.

Подготовка

Опыт предыдущих лет показал, что одному тягаться достаточно тяжело. В прошлом году я предпринял попытку создать команду, но занялся этим слишком поздно, и команда распалась на ходу. В этом году я примкнул к одной из "сборных irc-канала #haskell", куда кроме меня вошли Lemmih (Дания), vincenz и jyp (оба - Бельгия).

Где-то за два-три месяца до начала соревнования мы уже обговорили возможные пути организации нашего сотрудничества, имели централизованный репозиторий, несколько средств для удаленного общения и вообще были серьезно настроены на победу :) Как оказалось, собирать команду загодя - хорошая идея, т.к. все неуверенные в себе участники имели достаточно времени на "подумать" и отпали задолго до старта соревнования.

Примерно в это же время стало известно, что тема в этом году - "computational archaeolinguistics". Гугл подсказал, что это - исследование древних или забытых языков и средств, использовавшихся для проведения вычислений.

За два дня до старта. Среда, 19-го июля

За несколько дней до начала contest-а организаторы выложили на официальном сайте странный бинарный файл "codex.umz"(2 mb). Тщательное разглядывание файла показало, что внутри встречаются ссылки на всевозможные заговоры и мистификации - в частности, были найдены слова Fnord, "Paul is dead","so dark the con of man" и "societas eruditorium" и "Evan Chan was murdered". Все это наводило на мысль, что файл - тщательно спланированная мистификация, тем более, что частотный анализ, сделанный одним из будущих участников, показал, что распределение байт в файле близко к нормальному.

Старт. Пятница, 21-го июля, 19:00 EET

В 18:45 мы создали skype-конференцию и стали ждать, когда на сайте организаторов откроется ссылка на текст задания.

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

Пришлось тщательно читать вводную, которую мы все пролистали по диагонали, сразу кинувшись читать спецификацию.

Вводная говорила, что codex - это древний манускрипт, найденный археологами, а спецификация описывает древний компьютер (под названием "Универсальная Машина", UM) с памятью на плитах песчаника, который может интерпретировать кодекс и раскрыть секреты тайного общества, существовашего в 200 г. до н.э. В частности, нам предлогалось искать "научные статьи" этого общества, которые для экономии места (на плитах песчаника) записывались очень лаконично. Например, вот так: "PUZZL.TSK=100@1001|14370747643c6d2db0a40ecb4b0bb65". Найденные "публикации" прелагалось submit-ить на сайт организаторов. Больше никакой полезной информации мы не нашли.

Мы еще 5 минут поскрипели мозгами, и решили сначала реализовать Универсальную Машину, а там - будет видно. Мы разделили работу на I/O, emeory management и CPU принялись реализовывать UM на Haskell.

Помощь извне. Пятница, 21-го июля, 20:20

А в это время Алексей Щепин, один из авторов tkabber, активный участник jabber community и вообще хороший человек, собирался ехать в США на XMPP Interoperability Event. Эта поездка мешала ему принять участие в ICFPC, но он собирался "активно болеть". Очевидно, болеть он решил более чем активно, т.к. в 20:15 в одной из jabber-конференций он сказал, что успешно превратил виртуальную машину разрабатываемого им языка metaerl в Universal Machine, дал ссылку на код и любезно разрешил его использовать.

В 20:45 код был совместными усилиями от-debug-ен и настал долгожданный момент:
# ./vm codex.umz
self-check succeeded!
enter decryption key:


Как оказалось, код нам прислали организаторы 15-ю минутами ранее. Кстати, кто захочет самостоятельно поиграться с кодексом - вот наш код: "(\b.bb)(\v.vv)06AAbsqu51UUMkQBGh". После нескольких минут пожирания CPU кодекс сообщил:
self-check succeeded!
enter decryption key:
(\b.bb)(\v.vv)06AAbsqu51UUMkQBGh
decrypting...
ok
LOADING: 9876543210

 == CBV ARCHIVE ==
    VOLUME ID 7

 Choose a command:

 p) dump UM data
 x) exit

? 


По нажатию на "p" в stdout вылезло МНОГО бинарных данных. Повторный запуск с перенаправлением stdout показал, что запуск кодекса генерирует 15 мб данных, которые ... являются еще одной программой для UM!

Код Алексея в спешном порядке суется в репозиторий, остальные члены команды бросают работу над реализацией UM на Haskell (к этому моменту было сделано уже процентов 70 работы) и мы начинаем изучать то, что получилось в результате "раскручивания" кодекса.

UMIX guest login. Пятница, 21-го июля, около 21:00

Запуск дампа (который мы окрестили "stage2.um") привел к появлению вот такой вот любопытной надписи:
12:00:00 1/1/19100
Welcome to Universal Machine IX (UMIX).

This machine is a shared resource. Please do not log
in to multiple simultaneous UMIX servers. No game playing
is allowed.

Please log in (use 'guest' for visitor access).
;login: 


"Ни фига себе!", - сказал я себе, и попробовал залогиниться guest-ом:
12:00:00 1/1/19100
Welcome to Universal Machine IX (UMIX).

This machine is a shared resource. Please do not log
in to multiple simultaneous UMIX servers. No game playing
is allowed.

Please log in (use 'guest' for visitor access).
;login: guest
logged in as guest
INTRO.LOG=200@1964|ce2132eae5a539cf97838e766eabac7


You have new mail. Type 'mail' to view.


Ага! Вот и первый "publication", который мы тут же засабмитили на сайт организаторов, который бодро сообщил нам, что у мы заработали 200 очков!

Наверняка хотя бы часть моих читателей решит самостоятельно "попробовать на зуб" задачи этого года. Чтобы не портить вам удовольствие от самостоятельного исследования потрохов UMIX, я рекомендую всем желающим перестать читать прямо сейчас, скачать codex.umz, написать свой эмулятор UM или взять готовый (реализация команды Freaks Unidos) и не читать мой текст дальше. Я не смогу адекватно передать все те мелкие детали и "художественные штрихи", которыми насыщен ICFPC этого года. Не слушайте, как я "напеваю вам Страдивари", а попробуйте сами.

Spoilers ahead!

Все дальнейшее повествование описывает нашу борьбу с задачами, найденными внутри UMIX, и я буду ссылаться на файлы и артефакты внутри UMIX так, как будто это натуральный настоящий unix.

BASIC - выбор настоящего хакера. Пятница, 21-го июля, 21:10-21:30

Быстрый осмотр показал, что внутри UMIX есть не только пользователь guest:
% ls /home
ftd/
guest/
gardener/
ohmega/
yang/
howie/
hmonk/
bbarker/


В почте обнаружилось письмо от "администраторов", журящих guest-пользователей за попытки ломать чужие account-ы. В ~guest/code обнаружились следы этих попыток в виде (неоконченной) программы hack.bas на QBASIC-е :)

Отрезав от программы мусор и "скомпилировав" ее с помощью /bin/qbasic я получил "hack2.exe", с помощью которого взломал два account-а (в этом месте я роняю и подбираю свою челюсть, осознав, что я работаю в виртуальной unix-машине, реализованной на виртуальной UM-машине, и в этой дважды виртуальной машине есть компилятор бейсика, который работает).

Доступ к двум поломанным account-ам быстро дает нам пароли еще к четырем (они встречаются в различных файлах в plaintext или близком к нему видах), и к 22:00 у нас остается только один account, к которому у нас нету доступа - ftd.

Прошло 2,5 часа из отведенных трех суток, у нас 230 очков (see scoreboard), мы одни из четырех команд, "открывших счет". Настроение более чем радужное.

А теперь со всей этой фигней мы постараемся взлететь. Пятница, 21-го июля, 21:30-00:00

Исследование открытых account-ов показывает, что почти все они принадлежали людям, занимающимся исследованиями в области языков программирования. Еще один account принадлежит исследователю-биоинформатику, который изучает муравьев(я тут же вспомнил icfpc 2004), а еще один - содержит text-mode игрушку под названием adventure. Запустив ее и увидев "You are staying in the Room with a Door. In from of you there is a note lying on the floor ...", я прослезился от ностальгии :)

Два часта пролетают, как пять минут, за чтением файлов, почты и изучением программ, найденных во всех открытых account-ах. Остается вопрос - что курили авторы? :)

Один из acount-ов принадлежит автору единственного в мире языка программирования, программы на котором рисуются блок-схемами в ASCII art, второй - автору компьютера "Инь-и-янь" (и языка для него), который умеет исполнять всего четыре инструкции, зато каждая из них выполняет сразу по два действия, причем команды перехода нет, а вместо нее instruction pointer умеет двигаться как вперед, так и назад. Третий account принадлежит исследователю rewrite rules, помешанному на миниатюризации своих программ. Четвертый ученый придумал язык для описания .... детских игрушек типа "проведи шарик через лабиринт". Ученый-биоинформатик моделирует поведение муравьев с помощью чего-то, отдаленно напоминающего игру life Дэвида Конвея.

Все account-ы содержат описание нескольких (от трех до 15) головоломок, за решение которых мы, предположительно, получим какие-то очки. Что делать с adventure - пока непонятно.

BASIC - выбор настоящего хакера. Часть вторая. Суббота, 22-го июля, 00:11-00:58

Итак, у нас остался один неломаный account - ftd. Воспользовавшись комментариями в hack.bas, я дописываю его так, чтобы он перебирал не только пароли из прилагаемого словаря, но и дописывал к ним числа от 00 до 99 и проверял и такие пароли тоже. Реализация осложнялась тем, что местный qbasic ... не знает арабских цифр, а использует только римские! Строки программы, метки для переходов, метки циклов - все только римскими числами. Попробуйте без подготовки написать "490 FOR I=0 to 99 DO" с использованием римских цифр ;)

Быстрый поиск ("apropos roman") в моем "большом" linux-е показал, что я являюсь счастливым обладателем пакета "math::roman" для Tcl. С помощью xemacs, Tclsh и такой-то матери за примерно пол-часа я получаю работающий hack3.bas, который перебирает "пронумерованные" пароли и ftd был сломан :) Мы получаем +100 очков! (тогда это казалось большим достижением на фоне наших 230)

С часу до двух ночи у нас совещание по стратегии на завтра. Lemmih забирает себе задачу по программированию с помощью ascii art, jyp - волшебный компьютер "Инь и янь", vincenz возится с adventure, а я решаю взять тайм-аут до завтра. В 02:00 я ложусь спать.

Кидая в машину шарики, слушай звуки, из нее раздающиеся, иначе это кидание будет пустою забавою. День второй, суббота, 22-го июля, 09:00-00:00

В девять утра, как и договаривались, у нас strategy meeting. Vincenz настаивает, что мне надо попробовать сделать "BLACKS" (это головоломки по созданию детских игрушек) и я соглашаюсь. Изучение scoreboard показывает, что несколько команд, которые работали в то время, пока мы спали, успешно решили все головоломки BLACKS и получили за это .... 1000 очков!

Суть задачи такова: дан черный ящик с N дырками на входе и N - на выходе. В дырку-вход можно кинуть шарик, и он выпадет из какой-то дырки на выходе. Пока шарик катится через машину, она несколько раз издаст звук "дзынь!". Номер выхода, соответствующих каждому из входов, и кол-во "дзыньков" - известны. Задача: восстановить внутренности черного ящика, если известно, что внутри шарик катится либо по прямой, либо переходи на соседнюю "дорожку" влево или вправо, причем "дзыньк" раздается только при переходе вправо.

На первый взгляд, blacks похоже на простую переборную задачу, но размер головоломок быстро растет, и решать ее перебором для ящика с 500-и входами (т.е. перебирать все перестановки вектора из 500 элементов => 500! вариантов) как-то не очень хочется. Поиск в глубину с отсечениями тоже справляется плохо, т.к. отсекать почти что нечего и пространство решений все равно растет достаточно сильно с ростом входных данных. Перебор со случайной генерацией следующего шага тоже не дает результатов (хотя какая-то команда впоследствии и утверждала, что нашла решения именно таким путем. Возможно, им повезло с генератором случайных чисел :). За перебором вариантов решения незаметно проходит 6-7 часов.

Я начинаю думать, что эта задача - перепевка какой-то известной проблемы из какой-то сопредельной области. В гугле находятся задачи из области схемотехники по построению т.н. обратимых функций с помощью swap-гейтов и "гейтов Тоффоли", которые подозрительно похожи на то, что мне надо решить. Еще два часа проходит за продиранием сквозь статьи по схемотехнике, прежде чем я решаю забить.

К этому моменту я уже умею быстро строить черный ящик с нужным соответствием входов и выходов (в кои-то веки пригодился метод пузырьковой сортировки!), но количество "дзыньков", которые она издает, меньше требуемого. С подачи моей жены я начинаю искать способ "достроить" получающийся у меня черный ящик до нужного. С ее же подачи обнаруживается, что существует способ создать черный ящик, у которого выходы находся строго под входами, а вектор соответствия числа "дзыньков" номеру входа имеет вид (0,0,..,0,N,1,1,1,1,1,1,0,0,....,0), где сумма всех единиц равна N. В таких терминах уже можно решать задачу тупым перебором, и к полуночи 22-го числа у меня есть готовый генератор и набор решений. провереный верификатором, живущих в UMIX. Чтобы засунуть решения в UMIX, пришлось также написать оптимизатор полученных решений, т.к. выяснилось, что copy-paste в виртуальную машину ~17000 строк текста занимает где-то 15 минут :)

Юлька, спасибо тебе большое!

Мы получаем +1000 очков и выходим на третье место!

To Be Continued

Это первая часть из трех. Тут вторая часть, а тут - окончание.
Comments 
26th-Jul-2006 03:20 pm (UTC)
Продолжай! ;)
6th-Dec-2006 04:15 pm (UTC) - про супер виртуализацию
Anonymous
"hack2.exe", с помощью которого взломал два account-а (в этом месте я роняю и подбираю свою челюсть, осознав, что я работаю в виртуальной unix-машине, реализованной на виртуальной UM-машине, и в этой дважды виртуальной машине есть компилятор бейсика, который работает).
^^^^^^^^^^

нет тут никакой вируальной unix-машины. А есть одна большая adventure на functional language (просто в квест включили якобы работу на unix).

А в 15 Мегабайтном файле должно было быть куча текста, но он скрыт. Если бы дещифровать (вытащить) из него сообщения, то и играть было бы гораздо легче
26th-Jul-2006 03:26 pm (UTC)
пиши, читается замечательно.
да, а команда-то ваша как называется?
26th-Jul-2006 03:26 pm (UTC)
С большим интересом прочитал. Увлекательно.

Бьюсь головой о стену. Люблю задачи такого рода...

P.S. Извиняюсь, что записался, но так и не учавствовал... Ненормальный у меня графак последнее время.. Но нет мне оправдания. :(
26th-Jul-2006 04:25 pm (UTC) - show must go on
дочитал :-) продолжать! а как команда-то называлась?
26th-Jul-2006 06:13 pm (UTC)
Ой, вовремя ты сказал, что спойлер! Я как раз хотел в самолётах попробовать порешать :-)
26th-Jul-2006 08:51 pm (UTC)
Продолжай обязательно
26th-Jul-2006 09:05 pm (UTC)
Офигеть. Здорово как, оказывается.
27th-Jul-2006 04:53 am (UTC)
Продолжай! =)
28th-Jul-2006 09:41 am (UTC)
давай еще! интересно!
28th-Jul-2006 12:28 pm (UTC)
Ну так уже ... В первых строчках - ссылка на продолжения.
28th-Jul-2006 09:45 am (UTC)
Очень интересно.
продолжайте, plz
28th-Jul-2006 12:27 pm (UTC)
Дык это ... В первых строчках - ссылка на продолжение
28th-Jul-2006 09:56 am (UTC)
Очень интересно :)
28th-Jul-2006 11:33 am (UTC)
Anonymous
Прикольно! В миллион раз интереснее, чем АСМ.
28th-Jul-2006 10:34 am (UTC)
>12:00:00 1/1/19100

Ржал. В следующий раз меня пни - я про контест регулярно забываю :)
28th-Jul-2006 12:27 pm (UTC)
Там, кстати, таких easter eggs - несколько в каждой задаче. Типа, спам от пользователя Donald Nut, тонкие намеки на предыдущие icfpc в adventure и задаче про муравьев, и т.п.

По поводу пнуть - заметано.
28th-Jul-2006 10:55 am (UTC)
Вах.. когда продолжение? ;)
28th-Jul-2006 10:59 am (UTC)
Нашел уже %)
28th-Jul-2006 11:49 am (UTC) - +1
Интересно.
Я не регистрировался, поэтому на enter decription key все закончилось.
28th-Jul-2006 04:22 pm (UTC)
Дочитал, классно :)
31st-Jul-2006 05:22 pm (UTC)
дочитал, читается взахлёб
4th-Aug-2006 04:21 pm (UTC)
Очень-очень интересно!
Спасибо
5th-Aug-2006 05:40 am (UTC) - Universal Machine Emulator
мы написали свой эмуль для этой ВМ, кто хочет поиграть - http://community.livejournal.com/ru_unpacking/1892.html

там же сорцы на C.
8th-Aug-2006 09:30 pm (UTC)
... скачать codex.umz, написать свой эмулятор UM или взять готовый (реализация команды Freaks Unidos) ...

как интересно они что-то на нем делали, если он не работает :)

kst:~/um% ./um-32 second.um 
File size is 15923865
ERROR. We didn't read the program: 1 bytes left

11th-Aug-2006 07:42 am (UTC)
Странно, у меня ничего подобного не наблюдается
9th-Aug-2006 01:01 am (UTC)
вот мы тут обсуждали это дело в одном укромном месте, возник вот такой вопрос, не проясните ли:


вобщем, я вот что не понимаю, следите за руками:

1. люди, принимающие участие в этом деле -- это сказочные чудовища (с) -- команда аффтора заняла 10+ место, при том что аффтор, я думаю, находится на другом эволюционном уровне просто, по сравнению, скажем, со мной. (вообще же, жизнь прожита зря =(, но "сейчас не об этом")

2. кто же тогда организаторы этого конкурса? боги из параллельной вселенной? Если они вот такое устраивают раз в год, да так тихо -- такого размера шило -- как утаить в том маленьком мешке, что называется "коммьюнити функц. программирования"?

3. где эти люди, и почему мы о них ничего не знаем? может, все они пишут на джаве в гугле? может, их выкрадывают инопланетяне, и в заоблачных высотах они прилаживают новые фичи к нашей матрице? (а потом физики эти фичи косвенным образом обнаруживают)
11th-Aug-2006 07:47 am (UTC)
1)Не, сказочные чудовища - это те, кто займет первое место :)

2)Организаторы этого конкурса - каждый год новые (какой университет хостит конференцию ICFP, тот и организовывает конкурс), соответственно с притоком свежих идей проблем нет. Да и с количеством тоже - студентов/аспирантов пруд пруди. Судя про CREDITS, в этом году над подготовкой работали 20+ человек, из них минимум три (молодых) профессора.

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

А мы потом наблюдаем эхо от их трудов в виде generics в яве, mapReduce в гугле, и т.п.
(no subject) - Anonymous - Expand
uvm - Anonymous - Expand
15th-Aug-2006 04:57 pm (UTC) - монстры среди нас
я правда предпочитаю неспешный способ программирования - лучше сутки-другие подумать, а потом за 2 часа все написать :-)
хотя интересно было бы поучавствовать в таком состязалище
16th-Aug-2006 02:10 pm (UTC) - Re: монстры среди нас
Я в следующем году месяца за три буду предупреждать :)
16th-Aug-2006 03:55 pm (UTC)
Anonymous
Отличный рассказ! Жалею, что сам не программист.
17th-Aug-2006 07:21 pm (UTC)
"распределение байт в файле близко к нормальному"
к равномерному наверное
18th-Aug-2006 06:51 am (UTC)
:(((

Вот они, первые признаки подбирающегося маразма.

Конечно, к равномерному.
18th-Aug-2006 06:26 am (UTC)
С римскими цифрами порадовало. Прям прочувствовал как люди старались. Читаю дальше.:)
Page 1 of 2
<<[1] [2] >>
This page was loaded Sep 20th 2017, 6:17 pm GMT.