?

Log in

dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
ICFPC-2006, продолжение 
27th-Jul-2006 11:47 pm
Вторая часть рассказа о том, как я участвовал в ICFPC-2006, и что из этого получилось

Первую часть рассказа можно прочитать тут, а тут - окончание.

Маленький flashback на подготовку

Инициатором собрать команду с #haskell был vincenz. Желающих с самого начала было довольно много - человек пятнадцать, не меньше. Причем - со всего шарика. Из европы, из штатов, из австралии и новой зеландии. И была у нас мысль создать non-stop команду, которая будет морщить мозг 24 часа в сутки, без перерывов на сон и еду.

Идея организовываться сильно загодя (мы начали аж за 3 месяца) себя оправдала на все 100% (записываем в положительные lessons learned). Ближе к контесту народ стал потихоньку отпадать. Кто подался в другие команды, кто - не нашел времени, кто - просто ушел с радара. За три дня до начала в IRC собрался "kick-off meeting", на который явились аж пятеро человек, причем один из них не был в себе уверен, а остальные четверо - давно и активно занимались подготовкой. По результатам обсуждения было решено выступать командой из четырех человек, претендовать таким образом на первое место, всех непришедших из команды вычеркнуть, и в последнюю минуту никого на борт не брать, чтобы не портили весь фен-шуй.

После того, как решили вопрос с составом, стал вопрос не менее сложный - как назвать команду? Общеизвестно, что как вы команду назовете, так она и поплывет, поэтому вопросу выбора названия было уделено много времени и сил. Поскольку language of choice у всех был Haskell, считалось, что в названии в том или ином виде должно быть слово lazy. Дальше мы пытались подобрать достойные продолжения такому началу, экспериментировали с анаграммами из наших nick-ов, и т.д. и т.п. Выдохшись, мы признались самим себе, что зашли в тупик.

Тупик, он же - non-terminating computation, имеет в Haskell и в теории вычисления характерное название - bottom. Тут же вспыхнула искра синергетики, и название команде было придумано за 10 секунд.

Называться мы стали "Lazy Bottoms".

(fast-forward на 5 суток вперед, возвращаемся к contest-у)

Чем выше взлетаешь - тем большее падать. Воскресенье, 23-го июля, 10:00 EET

Мы - на четвертом или пятом месте, 1500+ очков. (к сожалению, не догадались сохранять странички scoreboard-а).

Очередной strategy meeting показывает следующую диспозицию:

0)В нескольких категориях мы или набрали возможный максимум очков (INTRO, BLACKS, BASIC - тут спасибо любимому мне) (тут и далее заглавными буквами даны заголовки колонок из scoreboard), или же держим первое место по набранным очкам (ADVIS - тут спасибо vincenz).

1)Нас догоняют серьезные конкуренты. Во-первых, Team Smartass, ветераны ICFPC, которые, похоже, работают в то время, пока мы спим, и наоборот. В результате, предыдущие два дня мы регулярно обставляли их вечером, а они нас - утром. Во-вторых - подтягиваются конкуренты с #haskell - Duncomloolump, победители ICFPC 2004. Нагоняют и Caml Riders, которые, по-моему, сильно выступили в ICFPC-2002.

2)У нас есть потенциал для рывка. Lemmih практически закончил CIRCS - генератор "двумерного ascii-кода", который может дать нам сразу +1200 очков. В ADVTR (игре adventure) мы можем "прикупить" еще +600-700, если доделать "решатель", который весь предыдущий день писал vincenz. В области написания программ для компьютера инь-янь (BLNCE) несколько продвинулся jyp, но и там можно найти еще где-то +600. Плюс, у нас еще и конь не валялся в области мутагенных муравьев (ANTWO), а это - верные +400. Цифры не совсем точные - мы ориентируемся на максимум очков в каждой категории, и считаем, на сколько еще мы можем "подняться".

3)Есть и отрицательный момент - организаторы выложили обновленную версию кодекса, в которой пофиксили ряд косметических багов, и один серьезный - в "муравьях". К сожалению, организаторы расширили набор тестов на соотвествие реализации UM ее спецификации, и наша реализация, которая "срезает углы" в области выделения памяти, теперь не проходит self-check. Организаторы решили проверить, действительно ли мы по команде "copymem" честно выделяем и копируем память. Мы, конечно, такой фигней не страдаем, и тупо alias-им указатели. На чем нас и попалили.

Диспозиция на первую половину дня определяется следующая:

1)Lemmih доделывает CIRCS, ETA - 14:00

2)vincenz, который раньше занимался оптимизацей систем управления памятью для embedded-устройств(!), чинит реализацию UM. ETA - 12:00

3)Я поднимаю из слабеющих рук vincenz-а флаг борьбы с adventure, и где-то до 16:00 борюсь с ней, после чего переключаюсь на муравьев

4)jyp продолжает бороться с BLNCE, а после 14:00 к нему подключается Lemmih

Меня сверлит подлая мыслишка о том, что jyp не "впрягается" достаточно сильно. Вчера он ушел спать где-то в 18:00, сославшись на жесткий недосып. Сегодня с утра тоже не выглядит достаточно активным. За сутки работы - около 150 баллов. На фоне vincenz (400+, плюс - хороший задел в adventure), Lemmih (100 в CIRCS, плюс - задел еще на 1200+), меня (1200+ - повезло, что за BLACKS дали сразу 1K) это выглядит несколько слабовато. В слух, впрочем, я ничего не говорю.

Низкий старт, отмашка, поехали!

Лирическое отступление про единство и борьбу противоположностей в задаче BALANCE

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

Краткое описание: имеется комьютер с линейно организованой памятью. Операции берут значения прямо из памяти, результаты тоже пишутся прямо в память. Для того, чтобы адресовать операнды и место размещения результата используются 4 "source" регистра (S0,S1,S2,S3) и 2 "destination" регистра (D0,D1), причем source и destination регистры не содержат непосредственных адресов. Вместо этого source и destination регистры содержат адреса, по которым выбираются значения, которые, в свою очередь, используются как адреса. Другими словами, адресация всегда косвенная!. Типичный набор действий для получения value из памяти такой - из опкода берем номер source-регистра, берем его значение, трактуем его как адрес, по этому адресу вычитываем слово, его трактуем как адрес, по нему вычитываем, собственно, value. Набор команд состоит всего из четырех штук:

MATH
                 MATH  performs addition  and  its dual,  subtraction.

                 M[ dR[D+1] ] <- M[ sR[S1+1] ]  -   M[ sR[S2+1] ]
                 M[ dR[D]   ]    <- M[ sR[S1]   ]    +  M[ sR[S2]   ]

                 Т.е. какую-то пару значений (например, адресованную через S0 и S1) в памяти складываем,
                 а какую-то (адресованую через S2 и S3) - вычитаем.

 LOGIC
                 LOGIC performs bitwise 'and' as well as its perfect
                 dual, bitwise 'exclusive or.'

                 M[ dR[D+1] ]  <- M[ sR[S1+1] ]  XOR  M[ sR[S2+1] ]
                 M[ dR[D]   ]     <- M[ sR[S1]   ]    AND  M[ sR[S2]   ]

                Аналогично предыдущей команде.

 SCIENCE
                 SCIENCE tests  a hypothesis and  determines the speed
                 at  which the program  progresses.

                 if M[ sR[0] ] = 0 then (nothing)
                 otherwise IS <- IMM

                 if IS = 0 then HALT
                 else (nothing)

                 Т.е. это странный гибрид "exit if ..." и мега-goto, поскольку IS - это значение,
                 на которое изменяется instruction pointer после каждой команды.

 PHYSICS
                 PHYSICS changes what the registers reference, in both
                 a linear  and angular  way. 

                 Описание очень длинное, но своими словами получается примерно так: 
                 из памяти вычитывается слово, засовывается в S0. Младшие пять бит этого значения
                 используются для того, чтобы определить, значения каких регистров из списка (S1,S2,S3,D0,D1)
                 будем менять. Регистры, значения которых мы будем менять, передают свое значение в регистры,
                 стоящий в списке слева, и получают новое значение из регистра, стоящего в списке справа.
                 Т.е. такой безумный циклический swap значений между несколькими регистрами.


Любители пописать на ассемблере для всякий ZX80 и 8051 должны быть в либо в кайфе, либо в тихом шоке ;)

И вот на таком чудо-компьютере предлагалось реализовать задачки, которые в типичном курсе теории вычислений решают на машине Тюринга: "обнулить кусок памяти", "скопировать кусок памяти", "заполнить кусок памяти возрастающими значениями", "остановиться ровно после 127 команд" и т.п.

Оценка напрямую зависит от размера программы - чем меньше команд, тем выше бал.

Так вот, за первый день jyp реализовал эмулятор этого компьютера и руками решил 7 легких задач из 14-и. Я рассчитывал, что можно реализовать какой-то более высокоуровневый (или более примитивный) язык, транслируемый в этот ужасный ассемблер, а потом оптимизировать полученный результат. Lemmih, который имел определенный опыт построения компиляторов (и даже где-то хачивший ghc) собирался заняться этим после того, как разберется с CIRCS.

Meanwhile, я игрался с adventure.

You have been eaten by the grue, или Иногда adventure - это всего лишь adventure. Воскресенье, 23-го июля, 10:00-23:59 EET

Приняв из рук vincenz все "приборы и материалы" по задаче ADVNTR, я обнаружил, что кроме пошагового решения части головоломок в darcs присутствует достаточной большой кусок кода на Haskell. Зачем??

Тщательное изучение игры показало, что она от начала до конца (насколько хватало глаз), состоит из головоломок такого вот вида:
Room With a Door

You are in a room with a mechanical door. You will probably need
to use a keypad to unlock it. A hallway leads north. 
There is a pamphlet here. 
Underneath the pamphlet, there is a manifesto. 

>: north
Junk Room

You are in a room with a pile of junk. A hallway leads south. 
There is a bolt here. 
Underneath the bolt, there is a spring. 
Underneath the spring, there is a button. 
Underneath the button, there is a (broken) processor. 
Underneath the processor, there is a red pill. 
Underneath the pill, there is a (broken) radio. 
Underneath the radio, there is a cache. 
Underneath the cache, there is a blue transistor. 
Underneath the transistor, there is an antenna. 
Underneath the antenna, there is a screw. 
Underneath the screw, there is a (broken) motherboard. 
Underneath the motherboard, there is a (broken) A-1920-IXB. 
Underneath the A-1920-IXB, there is a red transistor. 
Underneath the transistor, there is a (broken) keypad. 
Underneath the keypad, there is some trash. 

>: look keypad
The keypad is labeled "use me". 
Also, it is broken: it is a keypad missing a motherboard and a
button. 

>: look motherboard
The motherboard is well-used. 
Also, it is broken: it is a motherboard missing a A-1920-IXB and
a screw. 

>: look A-1920-IXB
The A-1920-IXB is is an exemplary instance of part number
A-1920-IXB. 
Also, it is broken: it is (a A-1920-IXB missing a transistor)
missing (a radio missing an antenna) and a processor and a bolt.

>: look radio
The radio is a hi-fi AM/FM stereophonic radio. 
Also, it is broken: it is a radio missing a transistor and an
antenna.


Обратите внимание, что для починки A-1920-IXB нужно именно "radio missing antenna", и применить вместо него целое radio не получится. Т.е. для решения головоломки надо починить radio только наполовину - транзистор в него совать, а антенну - ни в коем случае.

В принципе, такую головоломку легко решить руками. Но получив целый keypad, ты открываешь дверь и попадаешь на улицы безлюдного города, на которых творится вот такой беспредел:
>: north
53th Street and Harper Avenue

You are standing at the corner of 53th Street and Harper Avenue.
A sign reads, "No access east of Lakeshore Blvd (incl. Museum of
Science and Industry) due to construction." From here, you can
go north, south, or west. 
There is a (broken) raw-umber T-0010-BQH here. 
Underneath the T-0010-BQH, there is a (broken) foreign
V-9247-KMI. 
Underneath the V-9247-KMI, there is a (broken) imaginary
T-0010-BQH. 
Underneath the T-0010-BQH, there is a (broken) snow X-1623-GTO. 
Underneath the X-1623-GTO, there is a (broken) prussian-blue
T-0010-BQH. 
Underneath the T-0010-BQH, there is a (broken) gray-tea-green
T-0010-BQH. 
Underneath the T-0010-BQH, there is a (broken) miniature
V-9247-KMI. 
Underneath the V-9247-KMI, there is a (broken) ivory X-1623-GTO.

Underneath the X-1623-GTO, there is a (broken) steel-blue
V-9247-KMI. 
Underneath the V-9247-KMI, there is a (broken) indigo
T-0010-BQH. 
Underneath the T-0010-BQH, there is a (broken) EPROM burner. 
Underneath the EPROM burner, there is a (broken) brass
X-1623-GTO. 
Underneath the X-1623-GTO, there is a (broken) old-gold
T-0010-BQH. 
Underneath the T-0010-BQH, there is a (broken) foreign
T-0010-BQH. 

>: look ivory X-1623-GTO 
The X-1623-GTO is an exemplary instance of part number
X-1623-GTO. Interestingly, this one is ivory. 
Also, it is broken: it is (a X-1623-GTO missing a T-0010-BQH and
a T-0010-BQH) missing (a T-0010-BQH missing a F-9887-QAE and a
X-1623-GTO and a B-4292-LWV and a F-9887-QAE and a X-1623-GTO
and a X-1623-GTO) and (a T-0010-BQH missing a X-1623-GTO and a
X-1623-GTO) and ((a X-1623-GTO missing a T-0010-BQH and a
T-0010-BQH) missing a B-4292-LWV and (a T-0010-BQH missing a
X-1623-GTO and a X-1623-GTO) and (a T-0010-BQH missing a
F-9887-QAE and a X-1623-GTO and a B-4292-LWV and a F-9887-QAE
and a X-1623-GTO and a X-1623-GTO) and (a J-6458-VDL missing a
T-0010-BQH and a F-9887-QAE) and a F-9887-QAE) and (a J-6458-VDL
missing a T-0010-BQH and a F-9887-QAE) and a B-4292-LWV and a
F-9887-QAE.


Из записки, которая лежала на входе в город, было понятно, что задача - собрать некие uploader и downloader, каждый из которых требует для сборки 5-и запчастей. Запчасти (типа EPROM burner, USB cable, status LED, и т.п.) разобраны на составные части, перемешаны с мусором и разбросаны по улицам города. Задача по сборке, напомню, осложнялась тем, что в inventory влезает не более шести предметов, класть на землю предметы нельзя, освобождать место в inventory можно двумя путями - сжигая ненужные предметы, или комбинируя два поломаных предмета в один "более целый".

Явно направшивалось написание автоматического "собирателя" нужных предметов.

И вот тут я капитально, образцово-показательно, непростительно ПРОТУПИЛ:

* Во-первых, в записке (достаточно длинной) было сказано, что " I've left two useful items for you here, but I've had to disassemble them and scatter the pieces. Each piece may be assembled from the items at a single location.". Я умудрился пропустить выделенную жирным часть, и думал, что предметы прийдется собирать по всей карте. Ограничение на "сборку предмета в пределах комнаты" сразу уменьшало search space в 12 раз!

* Во-вторых, я думал, что собрать uploader и downloader - это либо и есть цель adventure, либо же они - вариации на тему keypad, и откроют мне доступ к следующей "карте", которая будет больше, предметов на ней тоже будет больше, но задача будет прежней - собирать необходимые предметы. В то же время в той же самой записке было сказано:
Dear Self,
I've had to erase our memory to protect the truth. The
Municipality has become more powerful than we had feared. Its
Censory Engine has impeded the spread of information throughout
our ranks. [...] Recover the blueprint from the Museum of Science and
Industry; it will show you how to proceed. If you have trouble
reading the blueprint, know that the Censory Engine blocks only
your perception, not your actions. Have courage, my self, the
abstraction is weak


И действительно, в игре попадались странные предметы с "вырезаным" описанием:
>: w
52nd Street and Blackstone Avenue

You are standing at the corner of 52nd Street and Blackstone
Avenue. From here, you can go east, south, or west. 
There is a manual here. 

>: look manual
The manual is [______REDACTED______]. 
Also, it is in pristine condition. 


Несмотря на все это, я прочел записку по диагонали, считая что это - красивый сюжетный фон для еще одной задачки на направленный поиск. Как оказалось - очень зря. Выделенные жирным места были подсказками, которые могли бы сэкономить мне очень много времени и сил... Впрочем, об этом - ниже.

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

Человеку, умеющему держать в руках только молоток, все проблемы кажуться гвоздями. Воскресенье, 15:00 EET

Как я уже говорил, програмистский зуд в заднице победил, и я сел рассматривать код, написаный vincenz-ом. Он пытался использовать list monad для того, чтобы реализовать поиск с backtracking-ом по дереву возможных способов комбинирования всех доступных в игре предметов.

Ах да, состояние игры было за-dump-лено после того, как в самой игре была найдена подсказка "try switching you goggles". Оказалось, что:
>: help switch
switch: Switch your Insta-Read(tm) Goggles to another mode. The
goggles are marked with the following settings: 'English',
'XML', 'sexp', 'ML', 'ANSI'. Synonyms include sw.

>: switch goggles ML
(success (command (switch "ML")))

look
(success (command (look (room (name "52nd Street and Blackstone Avenue") 
(description "You are standing at the corner of 52nd Street and Blackstone Avenue. From here, you can go east, south, or west. ") 
(items ((item (name "manual") (description redacted) (adjectives nil) (condition (pristine nil)) (piled_on nil)))::nil)))))


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

О чем я? Да, перебор всех вариантов ... Беглый просмотр показал, что vincenz допустил в коде ряд небольших ошибок в логике, я решил их поправить, получил почти правильный результат, решил поправить что-то еще, обнаружил, что надо бы изменить парочку datatype-ов и .. Короче, меня засосала опасная трясина reckless programming. Очнулся я где-то в 14:00, наконец-то осознав, что я пытаюсь написать на haskell самодельный, неполноценный и глючный prolog.

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

Решено! Выкидываем haskell, берем prolog! Делаем "apt-get install swi-prolog", из темных глубин памяти выползают ошметки полученых где-то на пятом курсе знаний пролога, и уже через час мне кажется, что дело движется вперед семимильными шагами.

Впрочем, естественно, что на пути прогресса оказывается пару досадных ухабов - не описал еще один сценарий возможного поведения при take, допустил ошибку при написании предиката, определяющего, нужен ли будет хоть где-то/когда-то такой-то предмет, и т.п. и т.п.

Цикл debug-hack-debug-hack превращается в водоворот, который засасывает меня с головой. Кажется, что еще чуть-чуть - и золотой ключик у меня в кармане.

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

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

Тут я делаю вторую ошибку (из упрямства) и пытаюсь придумать быстрое решение. Где-то в 04:00 становится понятно, что быстрого решения не будет, и я ложусь спать - а сделать это надо было еще часа три-четыре тому назад.

To Be Continued
Comments 
29th-Jul-2006 04:46 pm (UTC) - copymem
> Мы, конечно, такой фигней не страдаем, и тупо alias-им указатели. На чем нас и попалили.

Ээээ, я вот что-то не понял. copymem не просто так придумали, так ведь? Для чего надо копировать память? Чтобы, например, иметь возможность поизменять копию, а потом вернуться к эталонным данным. Можешь аргументировать ваше решение схалтурить и заниматься алиасингом указателей?
29th-Jul-2006 07:11 pm (UTC) - Re: copymem
скорость
31st-Jul-2006 07:52 am (UTC) - Re: copymem
скорость. объем занимаемой памяти. Что характерно, двое суток нам это сходило с рук :)
31st-Jul-2006 07:59 am (UTC) - Re: copymem
Я, честно сказать, даже удивлен, что вам это сходило с рук. :-)
Знаю одного чувака, который эту VM писал на С. Полагаю, для него было бы огромным сюрпризом, если бы memcpy ничего бы не скопировала. :-)
А скорость, объем - неужели после приделывания нормального поведения эти параметры сильно ухудшились?
31st-Jul-2006 08:19 am (UTC) - Re: copymem
Чисто визуально - потребление памяти выросло раза в три. top говорит, что в два с половиной :)
31st-Jul-2006 08:20 am (UTC) - Re: copymem
Я, кстати, не поленился поглядеть, как называется команда, в которой мы схитрили. Команда называется "Load Program" (которая должна делать копию массива, на который указывает B, и загружать ее (копию) в массив 0). Вот тут у нас просто было переприсваивание указателей.

Это, конечно, не copymem, но все равно что-то около того.
31st-Jul-2006 12:35 pm (UTC) - Re: copymem
Нам явный баг сходил с рук - сэндмарк вылетал, а умикс работал :)
9th-Aug-2006 11:08 am (UTC)
Очень интересно, но вот эту часть читать не ясно как -- скроллится по горизонтали крайне неудобно, а строки беспредельной длины.
11th-Aug-2006 08:01 am (UTC)
Мнэээ. А в каком браузере?

В мозиллах-файрфоксах-IE наблюдается ровно одна длинная строка, все остальное аккуратно за -wrap-лено.
11th-Aug-2006 10:41 pm (UTC)
Firefox 1.5, IE 5.5 - все горизонтальное
читала скопировав в ворд =)
14th-Aug-2006 12:12 pm (UTC)
(/me немножко правит пост)

А так лучше?
14th-Aug-2006 08:42 pm (UTC)
да, в фаерфоксе теперь все хорошо
ие у меня тут нету
16th-Jan-2007 04:57 pm (UTC)
Все портит в ff 1.5.0.8 следующая строчка:
(items ((item (name "manual") (description redacted) (adjectives nil) (condition (pristine nil)) (piled_on nil)))::nil)))))
1024x768

Это у меня firefox не адекватен, или разрешение мелкое?
22nd-Aug-2006 08:09 pm (UTC)
Вернулся из отпуска :)
FF 1.5.0.6
22nd-Aug-2006 08:10 pm (UTC)
Да, теперь всё в порядке :)
This page was loaded Jun 26th 2017, 9:09 pm GMT.