ICFPC-2006, продолжение
2006-07-27 11:47 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovВторая часть рассказа о том, как я участвовал в 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. Набор команд состоит всего из четырех штук:
Любители пописать на ассемблере для всякий 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. Зачем??
Тщательное изучение игры показало, что она от начала до конца (насколько хватало глаз), состоит из головоломок такого вот вида:
Обратите внимание, что для починки A-1920-IXB нужно именно "radio missing antenna", и применить вместо него целое radio не получится. Т.е. для решения головоломки надо починить radio только наполовину - транзистор в него совать, а антенну - ни в коем случае.
В принципе, такую головоломку легко решить руками. Но получив целый keypad, ты открываешь дверь и попадаешь на улицы безлюдного города, на которых творится вот такой беспредел:
Из записки, которая лежала на входе в город, было понятно, что задача - собрать некие 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, и откроют мне доступ к следующей "карте", которая будет больше, предметов на ней тоже будет больше, но задача будет прежней - собирать необходимые предметы. В то же время в той же самой записке было сказано:
И действительно, в игре попадались странные предметы с "вырезаным" описанием:
Несмотря на все это, я прочел записку по диагонали, считая что это - красивый сюжетный фон для еще одной задачки на направленный поиск. Как оказалось - очень зря. Выделенные жирным места были подсказками, которые могли бы сэкономить мне очень много времени и сил... Впрочем, об этом - ниже.
Короче говоря, надо было на какое-то время унять програмистский зуд в заднице, и вспомнить, что я - любитель компьютерных квестов. И проходить эту adventure, как еще одну infocom-игрушку - собирая все подсказки, анализируя информацию и т.п. Я думаю, что таким путем я бы уже часам к двум пополудни вышел бы на следующий уровень.
Человеку, умеющему держать в руках только молоток, все проблемы кажуться гвоздями. Воскресенье, 15:00 EET
Как я уже говорил, програмистский зуд в заднице победил, и я сел рассматривать код, написаный vincenz-ом. Он пытался использовать list monad для того, чтобы реализовать поиск с backtracking-ом по дереву возможных способов комбинирования всех доступных в игре предметов.
Ах да, состояние игры было за-dump-лено после того, как в самой игре была найдена подсказка "try switching you goggles". Оказалось, что:
После нахождения такого могучего средства достаточно было "переключить глаза" и пробежаться один раз по всем комнатам, чтобы получить полный дамп "картины мира".
О чем я? Да, перебор всех вариантов ... Беглый просмотр показал, что 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
Первую часть рассказа можно прочитать тут, а тут - окончание.
Маленький 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
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
copymem
Date: 2006-07-29 04:46 pm (UTC)Ээээ, я вот что-то не понял. copymem не просто так придумали, так ведь? Для чего надо копировать память? Чтобы, например, иметь возможность поизменять копию, а потом вернуться к эталонным данным. Можешь аргументировать ваше решение схалтурить и заниматься алиасингом указателей?
Re: copymem
Date: 2006-07-29 07:11 pm (UTC)Re: copymem
Date: 2006-07-31 07:52 am (UTC)Re: copymem
Date: 2006-07-31 07:59 am (UTC)Знаю одного чувака, который эту VM писал на С. Полагаю, для него было бы огромным сюрпризом, если бы memcpy ничего бы не скопировала. :-)
А скорость, объем - неужели после приделывания нормального поведения эти параметры сильно ухудшились?
Re: copymem
Date: 2006-07-31 08:19 am (UTC)Re: copymem
Date: 2006-07-31 08:20 am (UTC)Это, конечно, не copymem, но все равно что-то около того.
Re: copymem
Date: 2006-07-31 12:35 pm (UTC)(no subject)
Date: 2006-08-09 11:08 am (UTC)(no subject)
Date: 2006-08-11 08:01 am (UTC)В мозиллах-файрфоксах-IE наблюдается ровно одна длинная строка, все остальное аккуратно за -wrap-лено.
(no subject)
Date: 2006-08-11 10:41 pm (UTC)читала скопировав в ворд =)
(no subject)
Date: 2006-08-14 12:12 pm (UTC)А так лучше?
(no subject)
Date: 2006-08-14 08:42 pm (UTC)ие у меня тут нету
(no subject)
Date: 2007-01-16 04:57 pm (UTC)(items ((item (name "manual") (description redacted) (adjectives nil) (condition (pristine nil)) (piled_on nil)))::nil)))))
1024x768
Это у меня firefox не адекватен, или разрешение мелкое?
(no subject)
Date: 2006-08-22 08:09 pm (UTC)FF 1.5.0.6
(no subject)
Date: 2006-08-22 08:10 pm (UTC)