Здравствуйте, konsoletyper, Вы писали:
K>Ну, я Язык — Nemerle Со мной — mаrvin (выдал человека, какой я нехороший). K>Если попадём в первую сотню — будем чрезвычайно рады
Страна (то бишь rsdn.decl) должна знать своих героев!
Мне вот интересно, после того впечатляющего! поста адепта, не окупирует ли Россия вcю верхушку icfp
Здравствуйте, Курилка, Вы писали:
A>>Мне вот интересно, после того впечатляющего! поста адепта, не окупирует ли Россия вcю верхушку icfp К>Ммм, ну если учесть, что он с Киева, то даж не знаю
Киев России — не помеха .
P.S. Ладно, ладно уговорили — пусть будут русскоязычные товарищи .
Здравствуйте, D. Mon, Вы писали:
DM>Отличная возможность местным фанатам Nemerle доказать реальное превосходство своего любимого языка!
Вряд ли это получится. В Nemerle есть определённые косяки, которые жить мешают. Причём, не в самом языке, а больше в стандартных библиотеках (в основном с коллекциями). Исправлению этих косяков мешает тот факт, что есть куча всего, что написано под Nemerle, и это придётся переписывать. Думаю, мои вспомогоательные библиотеки из BnfMacro немного делу помогут, но всё же...
Короче, с треском проваливаюсь на ICFP, после чего иду ругаться с Михалем и Камилом. Может, сумею убедить.
эх, жаль thesz в отпуске . Я поспрашиваю своих, может кто захочет учавствовать. Но там такие зубры, что без олимпиадного опыта no fuckin way, даже не спортивно.
Хотя, джо армстронг со своей командой смог занять первое место в лайтнинг дивижне решая задачу просто так, для удовольствия, без всякой подготовки, на убогом и тормозном эрланге . Посмотрим как выступит Da Nemerle Hackerz Crew, короче . Жаль только, что такие зубры как владд2 не хотят лично возглавить (на радость всему рсдн) самую крутую команду — MakrozRulezHuzkelSuxx.
Похоже, все что они пока засабмитили — это строчка-совет из описания задания. Так же поступили еще полторы сотни человек..
Я тоже участвую. Пока реализовал транслятор ДНК в РНК, но он работает довольно медленно (10 итераций в секунду)..
Нашел и расшифровал скрытые послания, засабмитил цепочку из послания, посмотрим что скажут..
Здравствуйте, Andir, Вы писали:
A>Страна (то бишь rsdn.decl) должна знать своих героев! A>Мне вот интересно, после того впечатляющего! поста адепта, не окупирует ли Россия вcю верхушку icfp
Ничего себе! Вот это задачи. Первая олимпиада по программированию, в которой хочется принять участие.
Блин, такое ощущение, что это конкурс не программистов, а телепатов. Ну сделал я генератор РНК, получил исходную картинку, картинку с self-test и какую-ту статью про соверщшенные числа на фоне лямбды. И что бы это значило?
Здравствуйте, D. Mon, Вы писали:
DM>Солнце-то включил?
Нет, я же говорю, всего три картинки видел: исходную, self-test и "красивые числа". Третью вытянул по префиксу, который достал из ДНК (39 символов). Типа, сделай то, назнаю что.
DM>Как команда называется?
Есть еще одна картинка с текстом, там даются две последовательности. Одна рисует картинку с лямбдой, вторая включает солнце.
Не знаю, как вышло через нее перепрыгнуть..
Здравствуйте, D. Mon, Вы писали:
DM>Есть еще одна картинка с текстом, там даются две последовательности. Одна рисует картинку с лямбдой, вторая включает солнце. DM>Не знаю, как вышло через нее перепрыгнуть..
Так это, причём тут ФП? Я думал, будут задачи. А тут — сплошная телепатия. Типа, догадайся, что было на уме у организаторов и найти картинку на n-том байте ДНК в кодировке X. Вообще не поняно, как это можно сделать программно. Я и achtung! portable network graphics follows -> human audio follows -> префикс и 39 симв нашёл совершенно случайно. Не понятно, как я мог бы для этого использовать Nemerle или Haskell.
Здравствуйте, D. Mon, Вы писали:
DM>Есть еще одна картинка с текстом, там даются две последовательности. Одна рисует картинку с лямбдой, вторая включает солнце. DM>Не знаю, как вышло через нее перепрыгнуть..
А, нашел. Но опять же непонятно. Всё это — случайная догадка. Как мне в этом мог помочь Haskell, ума не приложу.
Да не, имея оба транслятор ДНК и рисовалку РНК можно без телепатии, т.к. в начале ДНК идет отрисовка кода для следующего шага..
Собсно, то, что можно найти в аудио, рисует только "laziness", похоже.
Здравствуйте, D. Mon, Вы писали:
DM>Да не, имея оба транслятор ДНК и рисовалку РНК можно без телепатии
Блин, изначально были транслятор ДНК и рисовалка, которые очень даже быстро всё делают (минут 15 на основную картинку, и по 5 — на все 3 лямбды, что я нашёл). И всё равно не догоняю.
DM> т.к. в начале ДНК идет отрисовка кода для следующего шага.. DM>Собсно, то, что можно найти в аудио, рисует только "laziness", похоже.
Странно, у меня по префиксу из аудио файла нарисовалась beautiful numbers.
K>Блин, изначально были транслятор ДНК и рисовалка, которые очень даже быстро всё делают (минут 15 на основную картинку, и по 5 — на все 3 лямбды, что я нашёл). И всё равно не догоняю.
А как получилось так быстро исполнять?
Моя реализация копирует строки, оттого сильно медленная..
K>Странно, у меня по префиксу из аудио файла нарисовалась beautiful numbers.
Здравствуйте, D. Mon, Вы писали:
K>>Блин, изначально были транслятор ДНК и рисовалка, которые очень даже быстро всё делают (минут 15 на основную картинку, и по 5 — на все 3 лямбды, что я нашёл). И всё равно не догоняю.
DM>А как получилось так быстро исполнять?
Секрет фирмы . Вообще, в мануале в конце есть советы, как это делать. Типа, очень тонкий намёк. Моя первая реализация могла делать не более 50-ти итераций/сек, но потом marvin обратил моё внимание на раздел, и я пошёл по правильному пути. Если за 22 часа не воткнёшь, я тебе вышлю свой код, на Nemerle.
DM>Моя реализация копирует строки, оттого сильно медленная..
Правильно, моя тоже 26 часов назад копировала. Но мы пошли иным путём...
K>>Странно, у меня по префиксу из аудио файла нарисовалась beautiful numbers.
DM>Хм, интересно..
у меня есть: beautiful numbers, repair guide navigation, steganography, картинка из "чистого" РНК (с двумя префиксами, которую ты приводил), и Endo с включённым солнцем. Первые три — с лямбдой. А у тебя есть что-то ещё интересное?
K>Секрет фирмы . Вообще, в мануале в конце есть советы, как это делать. Типа, очень тонкий намёк. Моя первая реализация могла делать не более 50-ти итераций/сек, но потом marvin обратил моё внимание на раздел, и я пошёл по правильному пути. Если за 22 часа не воткнёшь, я тебе вышлю свой код, на Nemerle.
Я тоже не сразу заметил там нужную фразу. Сейчас сделал быструю реализацию (3000 итераций в секунду).
K>у меня есть: beautiful numbers, repair guide navigation, steganography, картинка из "чистого" РНК (с двумя префиксами, которую ты приводил), и Endo с включённым солнцем. Первые три — с лямбдой. А у тебя есть что-то ещё интересное?
Здравствуйте, D. Mon, Вы писали:
K>>Секрет фирмы . Вообще, в мануале в конце есть советы, как это делать. Типа, очень тонкий намёк. Моя первая реализация могла делать не более 50-ти итераций/сек, но потом marvin обратил моё внимание на раздел, и я пошёл по правильному пути. Если за 22 часа не воткнёшь, я тебе вышлю свой код, на Nemerle.
DM>Я тоже не сразу заметил там нужную фразу. Сейчас сделал быструю реализацию (3000 итераций в секунду).
Спросил у Адепта. Их машина даёт 100-200К итераций в секунду. Надо потом вопросами засыпать. Кстати, ты получившуюся блочную структуру (ты так, я понимаю, сделал?) дефрагментируешь периодически? А скорость на исходном изображении не падает после 900К?
K>>у меня есть: beautiful numbers, repair guide navigation, steganography, картинка из "чистого" РНК (с двумя префиксами, которую ты приводил), и Endo с включённым солнцем. Первые три — с лямбдой. А у тебя есть что-то ещё интересное?
DM>Пока нет.
Блин, обидно. Самое интересное, что тут не надо быть семи пядей во лбу. Просто кому-то повезло больше и они поняли, как запустить Guide. Может, заметили какую-то тонкость. Даже и поучаствовать толком не получилось (если вообще можно битие лбом об стену назвать участием). В общем, я где-то с 18.00 — пас (последняя надежда на брутфорс + везение пропала). Может, marvin что-то родит. Но мы сесь день с утра думали — ничего. Так что надежды мало...
K>>>Странно, у меня по префиксу из аудио файла нарисовалась beautiful numbers.
Все правильно, там сначала laziness, потом долго ничего не пишет, и если прервать, то только то слово и увидишь. А если дождаться, то про числа и индуса.
K>у меня есть: beautiful numbers, repair guide navigation, steganography..
А как steganography получили? Я пытаюсь делать, как сказано в repair guide, заменяю нужную часть, но результирующая днк рисует исходную картинку..
Здравствуйте, D. Mon, Вы писали:
K>>у меня есть: beautiful numbers, repair guide navigation, steganography..
DM>А как steganography получили? Я пытаюсь делать, как сказано в repair guide, заменяю нужную часть, но результирующая днк рисует исходную картинку..
А что меняешь-то в префиксе? Ты его разобрал на шаблон/трафарет? Тамо получается, что ни в одном из префиксов числа нет. Типа, в шаблоне ищется определённая последовательность, а трафарете она клеится в начало, а дальше добавляется последовательность и I/C. Мы предположили, что потом эта последовательность (которая в самом префиксе состоит из C и F соотв) интерпретирутется, как число. Но попытка заменить на что-то другое не увенчалась успехом. Даже брутфорс сделали для той, которая beautiful numbers рисует, который не изменяя количества цифр перебирает все числа от 0..127. С тем префиксом, который рисует navigation это сделать проще — там всего два бита. На FF (т.е. число CC — 3), вылезает steganography.
Хитро.
А я пыался число 1337 вставить. В нем 11 бит, а в префиксе как раз есть последовательность из ровно 11 C и I. Заменив их на бвоичное представление 1337 получил тоже корректную команду, но результат ее незаметен.
Здравствуйте, D. Mon, Вы писали:
DM>Хитро. DM>А я пыался число 1337 вставить. В нем 11 бит, а в префиксе как раз есть последовательность из ровно 11 C и I. Заменив их на бвоичное представление 1337 получил тоже корректную команду, но результат ее незаметен.
Может это не для средних умов, но какие-то замученные задания . Слишком уж на квест похоже.
Здравствуйте, Константин Л., Вы писали:
КЛ>Может это не для средних умов, но какие-то замученные задания . Слишком уж на квест похоже.
Имхо, это и отличает данный контест от всех остальных. Т.е. можно быть уверенным, что тут побеждают настоящие Хакеры. =) Т.е. люди, которые готовы думать головой, находить изощренные способы решения задач и для них по настоящему интересно осваивать новое и неизведанное. Эдакие цифровые искатели приключений. =) ИМХО.
Здравствуйте, Константин Л., Вы писали:
DM>>А я пыался число 1337 вставить. В нем 11 бит, а в префиксе как раз есть последовательность из ровно 11 C и I. Заменив их на бвоичное представление 1337 получил тоже корректную команду, но результат ее незаметен.
КЛ>Может это не для средних умов, но какие-то замученные задания . Слишком уж на квест похоже.
Ага. ИМХО, на подобных конкурсах не должно быть стен, в которые упираешься. Типа, если в одну уперся,можешь повозиться в другой области, и хоть что-то получишь. Ну а сели человек не дагадался. Я выведал у Адепта, как получить доступ к repairing guide. Всё оказалось очень даже просто. Но мне не повезло — не пришла нужная мысля вот и всё. Хотя не нужно было быть семя пядей во лбу, чтобы этот префикс составить.
Короче, действительно, очень похоже на квест. А квест он не содержит вообще никакой логики или соображения — бейся во все щели, пока не повезёт и не ударишься в нужную. Это не спортивно и вообще непонятно, зачем такие ловушки ставить. Я побщался с Адептом. Он в своей статье на организаторов будет ругаться.
Лично у меня негативное впечатление от конкурса. Было весело в самом начале, когда я делал симулятор ДНК, потом оптимизировал его. А дальше началось бите об стену. Думаю, мало кто получает удовольствие от сего процесса. Прошлый конкурс был на порядок интереснее.
Здравствуйте, Plague, Вы писали:
КЛ>>Может это не для средних умов, но какие-то замученные задания . Слишком уж на квест похоже.
P>Имхо, это и отличает данный контест от всех остальных. Т.е. можно быть уверенным, что тут побеждают настоящие Хакеры. =) Т.е. люди, которые готовы думать головой, находить изощренные способы решения задач и для них по настоящему интересно осваивать новое и неизведанное. Эдакие цифровые искатели приключений. =) ИМХО.
Всё это буллшит! Понимаешь, в любой такой ситуации есть миллионы способов решить задачу. А нужно найти единственно верный. Это в корне неверно. Это не проверка твоей способности осваивать новое и неизведанное, а лишь твои способности к телепатии. Хорошая задача не должна содержать единственно верного ответа. Даже если оптимальный ответ — единственно верный, то должна быть куча почти идеальных ответов. А не так, что упираешься в стену и сидишь в безысходности.
Здравствуйте, D. Mon, Вы писали:
DM>Хитро. DM>А я пыался число 1337 вставить. В нем 11 бит, а в префиксе как раз есть последовательность из ровно 11 C и I. Заменив их на бвоичное представление 1337 получил тоже корректную команду, но результат ее незаметен.
Как ты нашёл префикс из 27 симв.? Тебе пошёл на пользу мой совет? Блин, бьюсь головой об стену: как же мне самому такое в голову не пришло?
Здравствуйте, konsoletyper, Вы писали:
КЛ>>>Может это не для средних умов, но какие-то замученные задания . Слишком уж на квест похоже.
P>>Имхо, это и отличает данный контест от всех остальных. Т.е. можно быть уверенным, что тут побеждают настоящие Хакеры. =) Т.е. люди, которые готовы думать головой, находить изощренные способы решения задач и для них по настоящему интересно осваивать новое и неизведанное. Эдакие цифровые искатели приключений. =) ИМХО.
K>Всё это буллшит! Понимаешь, в любой такой ситуации есть миллионы способов решить задачу. А нужно найти единственно верный. Это в корне неверно. Это не проверка твоей способности осваивать новое и неизведанное, а лишь твои способности к телепатии. Хорошая задача не должна содержать единственно верного ответа. Даже если оптимальный ответ — единственно верный, то должна быть куча почти идеальных ответов. А не так, что упираешься в стену и сидишь в безысходности.
Ну что, судя по тону, Немерле у нас, я вижу, проигрывает? У инженера должна быть развита интуиция и креативность, дружище . Этот конкурс не для тех, кто привык лопатой махать. Что до задач — все математические задачи содержат единственно верный ответ, и ничего, никто не жалуется.
ЗЫ: Я прекрасно знаю, что я бы этот конкурс слил бы по чорному — не силен я в олимпиадных условиях, так что ничего личного. Хотя...
ЗЗЫ: Вот, кстати, прикольная команда в топе: "jabber-ru". Интересно, кто это, и на чем пишут.
Здравствуйте, Gaperton, Вы писали:
G>Ну что, судя по тону, Немерле у нас, я вижу, проигрывает? У инженера должна быть развита интуиция и креативность, дружище . Этот конкурс не для тех, кто привык лопатой махать. Что до задач — все математические задачи содержат единственно верный ответ, и ничего, никто не жалуется.
Блин, ты не понял. Понимаешь, мат. задачи и квесты — это совершенно разные вещи. Да и лопатой я не махаю, привык думать и т.д. Ты бы просто вникнул в задачу и понял, в чём подвох.
Что по поводу мат. задач. Некоторые вообще не имеют решения, но от участнков требуется найти приближение получше. Короче, вы с Plague не правы. Если бы вы участвовали в 2006 и 2007, вы бы ощутили разницу. Кстати, тот же adept собирается написать отчёт о прошедшем конкурсе. Посмотрим, что он там напишет.
Кстати, и Немерле тут не при чём. Я застрял на вещи, к программированию мало относящейся. Так что объективно об этом говорить нельзя. Вот если бы я нашёл этот чёртов префикс, тогда ещё можно было бы о чём-то судить.
Здравствуйте, konsoletyper, Вы писали:
K>Здравствуйте, Gaperton, Вы писали:
G>>Ну что, судя по тону, Немерле у нас, я вижу, проигрывает? У инженера должна быть развита интуиция и креативность, дружище . Этот конкурс не для тех, кто привык лопатой махать. Что до задач — все математические задачи содержат единственно верный ответ, и ничего, никто не жалуется.
K>Блин, ты не понял. Понимаешь, мат. задачи и квесты — это совершенно разные вещи. Да и лопатой я не махаю, привык думать и т.д. Ты бы просто вникнул в задачу и понял, в чём подвох.
Я смотрел условие. Быстро прочтя документ, нихрена не понял. Увидев псевдокоды — ужаснулся — раз они тут есть, значит, надо их читать, в них наверняка какой-то подвох. Понял, что надо сам мануал тока курить внимательно несколько часов. Восхитился хитростью авторов задачи — это все еще придумать надо было. Остатки желания учавствовать рассеялись как дым от свежего ветерка, пнимаешь . Тем более пятница была, мозг в ожидании вечернего пива был в suspend mode. И не только у меня, у всего офиса.
K>Что по поводу мат. задач. Некоторые вообще не имеют решения, но от участнков требуется найти приближение получше. Короче, вы с Plague не правы. Если бы вы участвовали в 2006 и 2007, вы бы ощутили разницу. Кстати, тот же adept собирается написать отчёт о прошедшем конкурсе. Посмотрим, что он там напишет.
K>Кстати, и Немерле тут не при чём. Я застрял на вещи, к программированию мало относящейся. Так что объективно об этом говорить нельзя. Вот если бы я нашёл этот чёртов префикс, тогда ещё можно было бы о чём-то судить.
Чо, поподкалывать уже низя, штоли? Я видел тут вашу переписку, прекрасно все понимаю. Но надо же у своей РСДНовской команды тонус-то поддерживать .
K>Ага. ИМХО, на подобных конкурсах не должно быть стен, в которые упираешься. Типа, если в одну уперся,можешь повозиться в другой области, и хоть что-то получишь...
K>Короче, действительно, очень похоже на квест. А квест он не содержит вообще никакой логики или соображения — бейся во все щели, пока не повезёт и не ударишься в нужную. Это не спортивно и вообще непонятно, зачем такие ловушки ставить.
Не соглашусь. Это квест, только если подходить к нему как к квесту. Но с другой стороны, была задана модель вычислений и дана задача по построению или дорисовке картинки. Можно было вообще не проходить этапы квеста (ну разве что свет включить очень полезно), а заниматься тем, где свобода творчества и решений не ограничена — написанием программы-ДНК, которая сделает то, что надо.
Я, например, только за счет такого подхода в первую полсотню и пробился — придумал некий метод дорисовки, генератор нужной последовательности действий, потом компилятор ее в РНК/ДНК, который еще и сжатием занимается..
Где-то за час до конца соревнования получил картинку про стегагнографию. Что с ней делать, так и не понял, конечно.
K>Всё это буллшит! Понимаешь, в любой такой ситуации есть миллионы способов решить задачу. А нужно найти единственно верный.
Здесь не было единственно верного. Об этом организаторы предупреждали еще в мае, когда описывали основные принципы, которыми руководствовались:
1 the programming task should not be easily solvable
2 the programming task should not be solvable by using a lot of computing power
3 a solution to the programming task should not be lying around (or for sale) somewhere
4 we have to think about how to deal with the fact that contestants are going to use many programming languages and compilers
5 the solution space of the programming task should be large: we don't want many teams to submit the same, correct or best, solution
6 there should be a clear way to determine the winner of the contest: the solution space of the programming task should have a total ordering without a top (or bottom)
Т.е. не должно быть такого волшебного префикса, который можно найти в квесте и получить требуемую картинку один в один.
Просто увидел, что другие сабмитят префикс из 27 символов, который делает в точности ту же картинку (по очкам видно). Т.е. можно имеющийся из 28 как-то оптимизировать. Оказалось, это просто: там искалась строка, у которой можно было один символ убрать без изменения результата поиска.
K>Тебе пошёл на пользу мой совет?
Да, даже несколько: спасибо за подсказку со стегенографией и за идею дефрагментации (ее реализовал, скорость трансляции перестала падать).
Здравствуйте, Andir, Вы писали:
A>Признавайтесь, кто-нибудь участвует?
Эх, порешал я эту задачку
И как обычно в таких случаях, застрял на каком-то ньюансе и так не смог реализовать DNA 2 RNA ... Причём судя по проверке на трейсе из FAQ — ньюанс нетривиальный, потому как трейс совпадает один в один. Почему-то self-test у меня обрывается на примерно 36 тыс. команд (заканчивается dna) и соответственно нифига не работает правильно, хотя картинка и вполне правильная получается, но выводит результаты только первых двух тестов.
С нетерпением жду когда выложат хоть какие-нибудь варианты решения, чтобы отловить эту злобную багу
А вообще задачка мне понравилась, особо если представить себе как это придумывалось.
P.S. Судя по напору на производительность первого преобразователя, я так понимаю что императив для реализации dna2rna опять рулит неимоверно (хотя описание алгоритмов и выдано в сугубо функциональном виде).
Уф, замкнули двадцатку. Теперь можно нормально есть и спать.
Очень уж сложное задание в этом году было. Начали получать нормальные результаты только в ночь с воскресенья на понедельник (а потом проспали утро понедельника ). Обидно, что больше суток не могли придумать, как менять страницы в repairing guide, хотя оказалось все довольно просто. Нам бы эти сутки, может быть результат какой нормальный был. А то 4% — это почти ничего.
Вот наш результат. После того, как "включили солнце", сумели только повернуть лопасти мельницы, и нарисовать уток и кита, правда, без сетки поверх. Больше ничего не успели.
Вообще, море впечатлений, куча всякой добытой информации из dna, но некая неудовлетворенность тем, что слишком было сложно набирать хоть какие-то баллы сначала, а когда начало что-то получаться, то закончились отведенные три дня.
Извиняюсь за некий сумбур. Если кому будет интересно, как мы участвовали, расскажу.
_DA>Извиняюсь за некий сумбур. Если кому будет интересно, как мы участвовали, расскажу.
Да, очень интересно!
Вот, что пока пишет еще товарищ:
Мы были Tibetian Biodiversity Display (условно-случайно подобранный акроним к tbd, как-то так пошло) и заныкались аж на тридцатое место путём грязных хаканий. Прозреваю, что если бы последний сабмит прошёл (а он не прошёл, потому что у меня гпрс и двадцать часов не спал и ваще), то могло бы быть и лучше.
; ufo with smoke 4406243 1805 (just subtract 13 from teh baze offs and yay)
( ?IFPICFPPCFFPP !4406230 ) !161
%0:0
<compiled payload>
Для тех, кто понимает. И так далее для всех объектов, недостойных занимать место.
Сам удивляюсь, каким идиотом нужно быть, чтобы решить посмотреть наконец на маленькую процедурку вида чо-то-там-колор и узнать, как эта херня работает и как правильно возвращаться из функции, за два часа до конца. А потом стремаясь и плющась считать оффсеты и запускать дебаггер.
Вообще стрёмное какое-то получилось всё. Если б участнеги не имели опыта 2006, намного лучше все пошли бы, я думаю. Как бы я вначале думал, что виртуальную машину дебагать бессмысленно в принципе, как это было в 2006, что нам будут выдавать префиксы за квесты и всё такое. А тут вдруг выяснилось, что это самое основное занятие и есть. Пришлось переписывать немножко кода и впадать в длительную депрессию.
Я зопрогал на шарпе виртуальную машину и потом построил поверх неё дебаггер и компилятор ассемблера (ну типа такая вот запись паттернов/темплейтов) в коды. И декомпилятор, соответственно. И ваще!
Игорь запрогал транслятор РНК в картинки, который был глючной, но зато он мог в него смотреть и трейсить всячески. На руби. Потом он ещё писал что-то более высокоуровневое для трансляции, но я к тому моменту был уже совершенно категорически нерасположен изучать руби вообще и его транслятор в частности. Ну и, собственно, изучал Всякие Штуки он исключительно плодотворно, например, сумел подставить в Character Set произвольный шрифт вместо точег. Ну и вообще — открытия в основном его, насколько я помню.
Зи появился ночью с пятницы на субботу и запрогал на жаве правильный и сравнительно быстрый транслятор РНК, который я потом только и использовал. Ещё зи прогал типа ОЦР для распознавания мессаги Alien Virus Alert, которая оказалась совершенно беспонтовой, а ОЦР нам потом не пригодился вообще потому что я научился ловить вызовы drawChar и дампить код.
Микал появлялся изредка и иногда чота прогал. Это специфика соревнования — оно не распараллеливается вообще. Если человек вдруг отстал на полсуток, то максимум на что он может надеятся — что ему дадут какую-нибудь задачку. Вот в конце он вполне замечательно запрогал расшифратор задампленного кода, после чего кое-как распознал таблицу функций. Правда, это было уже где-то в семь утра понедельника... Тоже руби.
DM>Я зопрогал на шарпе виртуальную машину и потом построил поверх неё дебаггер и компилятор ассемблера (ну типа такая вот запись паттернов/темплейтов) в коды. И декомпилятор, соответственно. И ваще!
Может я че не понимаю, но вот сделать это за несколько часов Либо я не осознаю сложность задачи, либо я младенец по сравнению с ними Послушаешь, так они вм'ы клепают в нотепадах в перерыве между затяжкой сигареты и глотком пива
Здравствуйте, D. Mon, Вы писали:
K>>Короче, действительно, очень похоже на квест. А квест он не содержит вообще никакой логики или соображения — бейся во все щели, пока не повезёт и не ударишься в нужную. Это не спортивно и вообще непонятно, зачем такие ловушки ставить.
DM>Не соглашусь. Это квест, только если подходить к нему как к квесту. Но с другой стороны, была задана модель вычислений и дана задача по построению или дорисовке картинки. Можно было вообще не проходить этапы квеста (ну разве что свет включить очень полезно), а заниматься тем, где свобода творчества и решений не ограничена — написанием программы-ДНК, которая сделает то, что надо.
Понимаешь, реально на это расчёта не было. Если кто-то так и делал, то в последние часы от отчаяния (freaks unidos, например). Как я понял, интересность и нестандартность задач повышалась экспоненциально с нахождением новых префиксов. И то, где многие застряли — самое начало, т.к. организаторы перестарались с шифрованием начальных префиксов. Вот собственно, какие у меня претензии к ним.
DM>Я, например, только за счет такого подхода в первую полсотню и пробился — придумал некий метод дорисовки, генератор нужной последовательности действий, потом компилятор ее в РНК/ДНК, который еще и сжатием занимается..
Воистину респект! Знаешь, собрать таких как ты человек 5, было бы первое место! Я тоже задумывался над этим, но как представил ЧТО нужно сделать, понял, что утону. Да и не нашёл способа преодолеть одну трудность: должна рисоваться сначала картинка, а потом твои собственные РНК. Я не понял, как такое сделать. Была мысля делать pattern и template, которые переставляют местами свой собственный РНК и исходный ДНК. Но не было уверенности, что в конце программы ДНК не делает просто skip этак на 1млрд симв.
Ещё можно было написать собственный рендерер и кодировать не РНК, а некоторую векторную картинку, которая рисуется этим рендерером. Но это — вообще нечто недостижимое (в смысле, за 12 часов, а так — вполне можно посидеть, голову на досуге поломать).
DM>Где-то за час до конца соревнования получил картинку про стегагнографию. Что с ней делать, так и не понял, конечно.
Может, это фейк? Кстати, а где на правой картинке скрыта левая?
Здравствуйте, Andir, Вы писали:
A>С нетерпением жду когда выложат хоть какие-нибудь варианты решения, чтобы отловить эту злобную багу
Баги могут быть из-за того, что не учитываются всякие там break/return/finish(). Я и сам вначале вольно трактовал подобные вещи, а потом, как обломался, всё внимательно пересмотрел. В итоге угробил 24 на отладку + оптимизацию.
A>P.S. Судя по напору на производительность первого преобразователя, я так понимаю что императив для реализации dna2rna опять рулит неимоверно (хотя описание алгоритмов и выдано в сугубо функциональном виде).
Ну, вопрос спорный. Лучше всего тут подходит ИП + ФП. Например, всякие там nat/asnat лучше вручную в цикл разворачивать, а вот хранение/обработку ДНК лучше делать в функционально-иммутабельном стиле, иначе рискуем получить жуткие тормоза.
Здравствуйте, _DAle_, Вы писали:
_DA>Уф, замкнули двадцатку. Теперь можно нормально есть и спать. _DA>Очень уж сложное задание в этом году было. Начали получать нормальные результаты только в ночь с воскресенья на понедельник (а потом проспали утро понедельника ). Обидно, что больше суток не могли придумать, как менять страницы в repairing guide, хотя оказалось все довольно просто. Нам бы эти сутки, может быть результат какой нормальный был. А то 4% — это почти ничего. _DA>Вот наш результат. После того, как "включили солнце", сумели только повернуть лопасти мельницы, и нарисовать уток и кита, правда, без сетки поверх. Больше ничего не успели. _DA>Вообще, море впечатлений, куча всякой добытой информации из dna, но некая неудовлетворенность тем, что слишком было сложно набирать хоть какие-то баллы сначала, а когда начало что-то получаться, то закончились отведенные три дня. _DA>Извиняюсь за некий сумбур. Если кому будет интересно, как мы участвовали, расскажу.
Да, только сейчас начинаю понимать, как на самом деле всё в этом году здорово было (наконец, нашёл способ посмотреть остальные страницы repairing guide и дальше стало интереснее). Правда, организаторы перестарались с запрятыванием первоначальных префиксов, что всё испортило. Это не дало участникам хорошенько полазить в кишочках ДНК, а ведь это так интересно!
Здравствуйте, konsoletyper, Вы писали:
A>>С нетерпением жду когда выложат хоть какие-нибудь варианты решения, чтобы отловить эту злобную багу K>Баги могут быть из-за того, что не учитываются всякие там break/return/finish(). Я и сам вначале вольно трактовал подобные вещи, а потом, как обломался, всё внимательно пересмотрел. В итоге угробил 24 на отладку + оптимизацию.
Не-е, если эти ньюансы не учитывать то self-test должен обрываться на первых итерациях, там чётко видно что проверяются все скипы, сёрчи и т.д. Думаю, что я где-то неверно интерпретировал спецификацию, причём в таком месте, где редко бывает исполнение.
A>>P.S. Судя по напору на производительность первого преобразователя, я так понимаю что императив для реализации dna2rna опять рулит неимоверно (хотя описание алгоритмов и выдано в сугубо функциональном виде).
K>Ну, вопрос спорный. Лучше всего тут подходит ИП + ФП. Например, всякие там nat/asnat лучше вручную в цикл разворачивать, а вот хранение/обработку ДНК лучше делать в функционально-иммутабельном стиле, иначе рискуем получить жуткие тормоза.
Ну оно понятно, что совмещать и т.д., я к тому что если реализовывать эту часть например на Хаскеле, то ясен пень по производительности можно попасть в хорошую ловушку, из которой никакими оптимизациями не выбраться (запускать то надо много и часто). Отсюда предпочтение лучше делать на императивные языки, чтобы, как это сказать бы, увеличить оптимизационный потенциал.
Здравствуйте, Andir, Вы писали:
A>Здравствуйте, _DAle_, Вы писали:
_DA>>Извиняюсь за некий сумбур. Если кому будет интересно, как мы участвовали, расскажу.
A>Конечно интересно! На чём писали? Работу параллелили?
A>С Уважением, Andir!
Попробую немножко рассказать.
Итак, в прошлом году я и несколько моих знакомых участвовали в ICFP06 по одиночке. Очень понравилось, но решили, что без команды участвовать практические нереально — видна только верхушка айсберга. В этом году изначально собрались командой: crem, DAle, HeaDacHe, pinc (ники с topcoder.com). За неделю где-то завели svn у crem'a на компе, следили за блогом. Так как в блоге были картинки, решили написать примитивный binary -> greyscale picture просмотрщик, чем я и занялся после приезда в Минск с концерта Металлики К началу контеста просмотрщик был почти написан, но в будущем не пригодился. Общение было в основном в irc, иногда разговаривали по телефону.
Кратко об условии. Участникам предоставлялся ДНК код некой инопланетной зверушки, представляющей из себя строку из символов I C F P, длиной 7.5 мегабайт. Затем был приведен алгоритм, превращающий ДНК в РНК. РНК же из себя представлял набор команд для отрисовки картинки (довольно изощренными методами). Даны были две картинки: текущее состояние зверушки и желаемое. Сделать надо всего ничего: добавить к текущей ДНК префикс так, чтобы картинка в результате была как можно более похожа на желаемую (точное совпадение пикселов), ну и префикс для этого надо было использовать желательно как можно короче.
Дальше хронологически
20.07
13:30 Появилось условие. 22 страницы. Нас только трое.
13:30 crem разобрался с RNA->IMG частью, собирается писать на perl.
13:50 Решили послать префикс из условия. Увидели, что можно на сайте посмотреть, что это за картинка получается. Там был selfcheck.
14:00-15:00 Начали писать DNA->RNA. pinc на ruby, я на С++, независимо друг от друга.
16:00 crem вроде уже дописал свой конвертор, появился HeaDacHe.
19:00 HeaDacHe написал несколько алгоритмов поиска подстроки для моего DNA->RNA на с++. Версию на ruby решили не развивать из-за тормозов.
20:00 Я дописал DNA->RNA, правлю ошибки, в это время уже написаны какие-то скрипты для отрисовки.
.. 00:00 DNA->RNA все еще не заработал, вместе с HeaDacHe'ом ищем ошибки. crem и pinc за это время улучшили рисовалку, появилась возможность дампить картинки при отрисовке RNA с нужной частотой и еще куча полезных мелочей.
21.07
01:00 crem наваял компаратор картинок для сравнения наших результатов с target.png. Мы наконец-то завели DNA->RNA, выдает какой-то RNA, вроде что-то рисуется, но на selfcheck пока вылетает.
03:00 Наконец-то прошел selfcheck. Теперь у нас есть вроде правильно работающий DNA->RNA. Работает, правда, медленно. Иду спать.
...
11:00 Пока я спал, народ уже получил картинку с repair guide. На ней два префикса. Подставив второй префикс ("солнце") получили картинку, которая похожа на начальную, но с цветами, которые были в конечной. Послали. Оказалось, что эта картинка дала нам результат в 1.27%. Поднялись выше в табличке, место на 30. Картинка совпадает на 67% c конечной.
12:00 Прогнали профайлером DNA->RNA. string::operator+=, поиск, как оказалось, вызывается не так уж и часто, так что KMP-алгоритм был похоже лишним.
14:00 Храню теперь ДНК в статическом буфере, убрал почти все STL-приблуды, заменил на memcpy, убрал рекурсию из части функций. Заработало раз в 10 быстрее, но все равно слишком медленно. Явно видно, что тормозят копирования кусков ДНК. Префикс из условия c selfcheck'ом преобразовывался за несколько секунд, но с пустым префиксом преобразоавние длилось очень долго.
15:00 HeaDacHe'у удается соптимизировать еще раза в 2.
17:00 К этому времени получили картинки для первого префикса с полученной утром картинки. Это был repair guide navigation..
...00:00 Тут мы просто застряли. DNA->RNA дальше практически не оптимизируется в таком варианте. Я пробовал переписать часть кода, но наткнулся на ошибку в рассуждениях. Понятно было, что надо не копировать строки, а хранить что-то вроде пар (смещение, длина) и с ними оперировать, но виделось достаточно много проблем с таким подходом. С подстановкой же числа страницы было вообще глухо. Появилось бесчисленное количество идей, но ни одна из них не прошла, да еще и картинки из префиксов получались слишком долго...
DM>>Я зопрогал на шарпе виртуальную машину и потом построил поверх неё дебаггер и компилятор ассемблера (ну типа такая вот запись паттернов/темплейтов) в коды. И декомпилятор, соответственно. И ваще!
КЛ>Может я че не понимаю, но вот сделать это за несколько часов Либо я не осознаю сложность задачи, либо я младенец по сравнению с ними Послушаешь, так они вм'ы клепают в нотепадах в перерыве между затяжкой сигареты и глотком пива
да, где-то так оно и есть но если хочешь попробовать, есть такая книжка "writing your Scheme interpreter in 48 hours", где в эти 48 часов вмещается изучение Scheme (это почти Лисп), написание её интерпретатора, и изучение хаскела на уровне достаточном чтоб это сделать. можешь попробовать — потом расскажешь нам
Здравствуйте, Andir, Вы писали:
A>Ну оно понятно, что совмещать и т.д., я к тому что если реализовывать эту часть например на Хаскеле, то ясен пень по производительности можно попасть в хорошую ловушку, из которой никакими оптимизациями не выбраться (запускать то надо много и часто). Отсюда предпочтение лучше делать на императивные языки, чтобы, как это сказать бы, увеличить оптимизационный потенциал.
Ну, Ocaml и Nemerle — тоже функциональные. Так что...
02:00 Прошло много времени с того момента, как мы послали префикс, но наше место в таблице с тех пор практические не изменилось. Было видно, что тормозим не одни мы. Надо еще сказать, что в irc сети freenode.net был канал #oasis, посвященный ICFP. В нем участники разных команд иногда рассказывали свои проблемы и всколзь упоминали о своих достижениях. В основном жаловались на медленный DNA->RNA конвертор. У кого-то было несколько итераций в секунду. У нас было 250. Кто-то хвалился 30000. Хотя многие не напиали еще даже транслятор.
...
11:00 Когда я проснулся, оказалось, что у crem'a умер основной комп. svn был на другом.
12:00 Сделал нормальный лог в конверторе, чтобы можно было посмотреть, что происходит на итерациях.
14:00 Наконец-то мы догадались. На первой итерации обработки repair guide префикса где-то далеко происходила замена I на С. Наконец-то мы додумались посмотреть, что же лежит за этим I, там лежало много символов I, а затем P, то есть число 0, и менялось оно на число 1. Для перехода на другую страницу надо было всего лишь менять 0 не на 1, а на другое число. Сформировали быстренько вот такой IIPIFFCPICFPPICIICCCCCCCCCCCCIICIPPPFCCFFFCCFCFIIC
префикс для 1337.
15:00 HeaDacHe начал переписывать DNA->RNA без копирований. В это время мы наконец-то получили 1337 страницу.. Стало ясно, что нам нужно намного быстрее получать картинки. Но это был наконец-то первый прогресс за много часов.
16:30 Я наваял маленький генератор префиксов для страниц, стали ждать конвертацию. Тут нам привалила большая удача в лице Zis'a, который начал участвовать один, а теперь примкнул к нам. Его DNA->RNA, написанный на С++, работал с фантастической скоростью примерно в 50000 итераций в секунду. Тем временем мы уже опустились на 38 место.
17:30 Теперь у нас была куча новых страниц с кучей разрозненной информации. Оказалось что ДНК состоит из трех частей: красной, зеленой и синей. Синяя часть представляла собой стек, куда передавались параметры, зеленая же никогда не меняла своих размеров. Также появилась у нас и первая страница списка функций, которые были зашиты в ДНК. Выглядела она так. Также нашелся Intergalactic character set. Еще была очень важная страница, где описывалось, как можно вызывать отдельные функции из ДНК с помощью адаптера. Часть страниц была с какой-то информацией, одна с закодированным текстом, одна про Lindenmayer-systems... Есть еще картинки пустые. Похоже — закодированная РНК. В общем, загрузились новой информацией.
18:00 'Закодированный' текст оказался совсем просто закодированным, но пока был нам не сильно нужен. Zis начал писать на python'e вызов функций по смещению с помощью адаптера.
19:00 Вызовы функций давно готовы, по инициативе pinc'a пробуем получить другие страницы списка функций с помощью вызова функции AAA_geneTablePageNr. Что-то не получается.
21:00 Обнаруживаем, что в табличке вместо top-20 стало top-15 и у верхних префикс просто на единицу короче, делаем тоже самое Тот же результат, но формально 22 место.
21:45 pinc'у удается вызвать функцию отрисовки земли. Сдвинулись с места.
22:00 Есть уже набор разных спрайтов, рисующих части картинки, что с ним делать не сильно понятно.
23:00 crem придумал, как получить остальные страницы со списком функций. Оказалось, что AAA_geneTablePageNr — это не функций, я переменная, и туда надо всего лишь записать номер нужной нам страницы. Сгенерили все 14 страниц, куча различных функций от сложения чисел до рисования начальной картинки с солнцем. Решаем, что надо всю эту таблицу функций собрать в текстовый файл. Начинаем втроем руками набивать смещения и названия функций, автоматически не распозналось.
00:00 Пока мы набивали функции Zis занимался раскодированием текстов.
23.07
00:15 Zis нашел шуточное послание:
Help! We are a group of computer scientists held prisoner on the remote planet of Utrecht in the Orion nebula by the evil Fuun The Fuun have already conquered thousands of worlds, and it appears that Earth is next Their modus operandi is always the same: they organize a fake `programming contest' on the victim world to repair a supposedly disabled Fuun This enables them to identify that planet's best and brightest minds, who are then eliminated in advance of the actual invasion, leaving the planet defenseless against the Fuun's superior weaponry You must not, under any circumstances, repair the Endo creature, as he when reactivated will surely destroy his `rescuers' and give the attack signal to the Fuun invasion force massing near Sullust Do not give in to the lure of rewards, monetary or otherwise! It is too late for us, but in the unlikely event that Earth manages to stave off the Fuun invasion, we would appreciate a monument of some sort to honour us especially since we sabotaged the Fuun DNA by swapping some parabolas We are: Alexey Rodriguez Andres Loeh Arie Middelkoop Bastiaan Heeren Chris Eidhof Clara Loeh Eelco Dolstra Eelco Lempsink Jeroen Leeuwestein Johan Jeuring John van Schie Jurriaan Hage Maaike Gerritsen Mark Stobbe Martijn van Steenbergen Stefan Holdermans
piтс в это же время нашел 3 странички с описанием параметров части функций.
01:00 Построили список "дыр", которые есть в таблице функций. Думаем, как отрисовывать нужную нам картинку. К этому времени можно было уже писать скрипты на питоне, вызывающие функции по имени, устанавливающие значения переменных и т.д. (не зря же руками 14 страниц набивали). Чтобы сгенерировать префикс, рисующий дерево и заканчивающий работу надо было всего лишь написать что-то вроде print call('appletree') + quit(). Осталось 12 часов, у нас еще никакого результата.
01:30 Баловались с разными функциями. set_bool('ocamlrules', True) + call('ocaml') + quit() рисует верблюда вместо коровы это нам не нужно.
01:40 Zis откуда-то нашел еще штук 10 страниц с документацией по функциям.
02:30 Только у 23 команд пока результаты лучше нашего. Что-то организаторы не рассчитали со сложностью. Zis вытянул из дырок между функциями еще кучу картинок сомнительной пользы (хотя скорее всего просто мы не знаем для чего некоторые из них нужны). Вот одна из них.
02:40 Рассмотрели среди функций setOrigin.
03:30 Получилось отрисовать уток и холмы недалеко от их расположения, но непонятно как поверх них нарисовать сетку, которая присутсвует на картинке, да и холмы что-то совсем плоххо рисуются. Похоже все спят кроме нас с crem'ом.
04:00 Отрисовали уток поверх солнечной картинки, сравнили, не так уж плохо даже без сетки, половина пикселов где-то совпадает. Отослали — 1.33%, 19 место, наконец-то мы сдвинулись.
04:20 Отрисовали уток на 2 пиксела выше. 18 место, 1.4%. С солнцем и облаками так просто ничего не выходит. Возможно закодированы.
04:50 Нарисовали кита в нужном месте (на самом деле ошиблись на пиксел) 1.44%, опять поднялись на 18.
05:30 Больше ничего так тупо отрисовать не получается. Иду спать на три часа.
11:45 pinc будит меня телефоном, crem оказывается тоже проспал и его до сих пор нет. Остается час. Оказывается утром народ понял как повернуть лопасти мельницы. Это нужно было делать с помощью команды setGlobalPolarRotation, вызванной до всего. Посылаем. 4.66%, 17 место.
13:00 Лихорадочно пробовали (в основном crem пробовал) что-нибудь еще отрисовать, ничего не успеваем. Финиш. 20 место, неплохо.
Итоговый питоновский скрипт, генерирующий префикс выглядел вот так
Думаю, что видели мы достаточно мало. Там еще и закодированные РНК и композиции функций и еще черт знает что есть, множество всяких полунамеков... Но это все было круто
Здравствуйте, konsoletyper, Вы писали:
A>>С нетерпением жду когда выложат хоть какие-нибудь варианты решения, чтобы отловить эту злобную багу
K>Баги могут быть из-за того, что не учитываются всякие там break/return/finish(). Я и сам вначале вольно трактовал подобные вещи, а потом, как обломался, всё внимательно пересмотрел. В итоге угробил 24 на отладку + оптимизацию.
От блин, судя по всему бага у меня в отрисовке rna2bmp, а не dna2rna проверил чужие реализации — выход дают такой же, а вот рисовалка у меня рисует только часть картинки ... А я убил всё время на поиск багов в ДНК
Здравствуйте, konsoletyper, Вы писали:
K>Понимаешь, реально на это расчёта не было. Если кто-то так и делал, то в последние часы от отчаяния (freaks unidos, например).
По крайней мере один дурак нашелся.
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, D. Mon, Вы писали:
КЛ>[]
КЛ>
DM>>Я зопрогал на шарпе виртуальную машину и потом построил поверх неё дебаггер и компилятор ассемблера (ну типа такая вот запись паттернов/темплейтов) в коды. И декомпилятор, соответственно. И ваще!
КЛ>Может я че не понимаю, но вот сделать это за несколько часов Либо я не осознаю сложность задачи, либо я младенец по сравнению с ними Послушаешь, так они вм'ы клепают в нотепадах в перерыве между затяжкой сигареты и глотком пива
Помню, на втором курсе универа я за двое суток сделал SQL-сервер . С виртуальной машиной, компилятором в нее подмножества SQL (что требовалось условием задачи), и все такое. Причем, он умел много клиентов обслуживать. Как вспомню — так вздрогну, ужас какой-то. Сейчас так не смогу.
На самом деле, стековую "виртуальную машину" я сделал где-то за час с небольшим (парсер грамматики SQL рекурсивным спуском и генерация кода тоже заняла немного времени). Все перечисленное реально очень просто, здесь нет никакого креатива — тут надо тупо знать некоторые вещи, и все. У меня получилось сделать машину за час потому, что я знал язык ФОРТ, а это знание позволяет делать "виртуальные машины" на языках типа С/С++ чрезвычайно быстро. Это некоторый угол зрения на проблему, под которым все становится очень просто — ключевое слово "шитый код". Собственно, при таком подходе код состоит из адресов, а интерпретатор тупо передает управление по текущему адресу и инкрементирует счетчиу команд. Язык ФОРТ показывает, как при таком подходе сделать чрезвычайно компактную и гибкую "виртуальную машину". Это знание меня не раз выручало, кстати.
Вот тебе интерпретатор "шитого кода" — код не очень хороший, но иллюстрирует идею:
while( *context.PC ) // останавливаемся на команде с кодом 0
{
context.PC -> Execute( context ); // команда — это указатель на класс-наследник базового класса "команда", с виртуальной функцией execute
context.PC++; // контекст мы передали, чтобы команда могла менять PC. Так делаются команды условных переходов, например.
}
[]
G>На самом деле, стековую "виртуальную машину" я сделал где-то за час с небольшим (парсер грамматики SQL рекурсивным спуском и генерация кода тоже заняла немного времени). Все перечисленное реально очень просто, здесь нет никакого креатива — тут надо тупо знать некоторые вещи, и все.
[]
ну может быть. А то у меня уже комплекс неполноценнсоти развился
G>Помню, на втором курсе универа я за двое суток сделал SQL-сервер .
недавно, когда отдельные товарищи стали меня уверять какая это сложная вещь — GUI-программирование я сделал за час файл-менеджер. на delphi. 7 строчек кода, всё остальное — натасканные из палитры готовые компоненты
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, Gaperton, Вы писали:
КЛ>[]
G>>На самом деле, стековую "виртуальную машину" я сделал где-то за час с небольшим (парсер грамматики SQL рекурсивным спуском и генерация кода тоже заняла немного времени). Все перечисленное реально очень просто, здесь нет никакого креатива — тут надо тупо знать некоторые вещи, и все.
КЛ>[]
КЛ>ну может быть. А то у меня уже комплекс неполноценнсоти развился
Никаких "может быть". Держи ссылку, здесь пример кода на С++. Реализован интерпретатор "байт-кода" и три команды. Строчек 30 кода примерно . http://rsdn.ru/Forum/message/638235.1.aspx
Здравствуйте, konsoletyper, Вы писали:
K>Секрет фирмы . Вообще, в мануале в конце есть советы, как это делать. Типа, очень тонкий намёк. Моя первая реализация могла делать не более 50-ти итераций/сек, но потом marvin обратил моё внимание на раздел, и я пошёл по правильному пути. Если за 22 часа не воткнёшь, я тебе вышлю свой код, на Nemerle.
Здравствуйте, Mckey, Вы писали:
M>А можно посмотреть на ваш код н Nemerle?
А зачем тебе? Хочешь узнать, как вообще можно оптимизировать симуляцию ДНК? Тогда лучше посмотри код на C#, который я написал уже после контеста и который очень сильно оптимизирован. Если же просто хочешь посмотреть какой-нибудь код на Nemerle, то здесь, только он жутко криво написан да ещё и жутко тормозной.
Здравствуйте, konsoletyper, Вы писали:
K>А зачем тебе? Хочешь узнать, как вообще можно оптимизировать симуляцию ДНК? Тогда лучше посмотри код на C#, который я написал уже после контеста и который очень сильно оптимизирован. Если же просто хочешь посмотреть какой-нибудь код на Nemerle, то здесь, только он жутко криво написан да ещё и жутко тормозной.
Просто тоже пробовал кое-что написать (уже после окончания).. Но все равно тех цифр про которые тут говорили достич не удаеться... хотелось бы посмотреть как можно решить проблему...
Здравствуйте, Mckey, Вы писали:
K>>А зачем тебе? Хочешь узнать, как вообще можно оптимизировать симуляцию ДНК? Тогда лучше посмотри код на C#, который я написал уже после контеста и который очень сильно оптимизирован. Если же просто хочешь посмотреть какой-нибудь код на Nemerle, то здесь, только он жутко криво написан да ещё и жутко тормозной.
M>Просто тоже пробовал кое-что написать (уже после окончания).. Но все равно тех цифр про которые тут говорили достич не удаеться... хотелось бы посмотреть как можно решить проблему...
А что тут непонятного? В мануале в конце есть раздел с несколькими советами. Там делается намёк на то, что чаще всего производятся операции skip на много шагов и protect большого кучка ДНК, но с protection-level = 0 (т.е. просто копирование). Вместо копирования мегабайтных кусков можно просто делать блочный ДНК, и при копировании создавать блоки, указывающие на кусок уже ранее существующего ДНК. Но таким макаром через несколько итераций получается уж очень длинная цепочка блоков, что опять же замедляет работу. Так что время от времени нужно делать дефрагментацию, т.е. склеивание многих маленьких блоков в один.
Как раз от периодичности срабатывания дефрагментатора очень многое зависит. В том симуляторе, что я написал для контеста, дефрагментация делается просто с определённым периодом. Однако, это не дало хорошего результата. После контеста я примел другой подход: дефрагментатор вызывается настолько часто, насколько необходимо для поддержания "оптимального" количества блоков. Если же количество блоков растёт быстро, то время от времени производится более агрессивная дефрагментация (это даёт некоторый прирост в худших случаях).
Но вообще можно было на форум для этого не лезть. См. ссылку на discussion на сайте ICFP Contest. Там есть посты, объясняющие, как правильно пишется симулятор ДНК. Заодно некоторые команды дают ссылки на собственные реализации.
А из-за чего код на Nemerle тормозной? Вроде с блоками работает, строки не копирует..
И с какой скоростью работают оба варианта? (у меня компилятора N нет, не на чем проверить)
Здравствуйте, D. Mon, Вы писали:
DM>А из-за чего код на Nemerle тормозной? Вроде с блоками работает, строки не копирует..
Ну, во-первых, в коде на Nemerle, как я уже объяснял, я не сильно заморачивался с дефрагментацией, в результате, она происходила слишком часто, когда не нужно, и слишклм редко, когда нужно. Во-вторых, в C# я занялся элементарным битовыжиманием. Например, в Nemerle сдуру сделал два вида блоков, и match'ил их, а pattern matching разворачивается в цепочку if'ов с проверкой is, что не очень быстро. Ещё неслобое ускорение получилось заменой if'ов (или match'а) на case'ы, последовательным чтением-проверкой при распозвнавании pattern'ов и template'ов, использовании, где возможно, не списков, а массивов, unchecked и т.д. На Nemerle практически всю эту оптимизацию можно сделать, за искл. case, аналогов которого я не нашёл, а match не разворачивается в case'ы в тривиальных случаях (потому что времени ни у кого нет эту фичу добавить).
DM>И с какой скоростью работают оба варианта? (у меня компилятора N нет, не на чем проверить)
С какой скоростью работал вариант на Nemerle, точно сказать не могу. Выводил время только после каждых 10К итераций, а общее время было особо не нужно. Тестировал неа двух компах. На одном пиковая скорость была 3000 и/с, наименьшая — 300 и/с. Исходная картинка генерилась где-то полчаса, так что скорость была приблизительно немногим более 1К и/с. На втором компе всё было быстрее примерно в 3 раза, а исходная картинка генерилась 12 минут. Мне, честно говоря, было не до хардкорных оптимизаций, тем более, что за время конкурса я нашёл только 4 префикса, и оптимизации были просто не актуальны.
Вариант на C# на медленном компе исходную картинку генерит 1.5 минуты, со средней скоростью примерно 20К и/с. На быстром компе — чуть меньше 40 секунд, со скоростью около 50 и/с.
Компилятор N вместе с интеграцией с VS периодически выкладывают в форуме "Интеграция Nemerle", в топиках с соотв. названием.
нет. я вообще считаю, что в моих собственных программах алгоритмики не меньше, чем в ICFP. там имхо развлекаются те, у кого основная работа связана с более скучными вещами
Здравствуйте, BulatZiganshin, Вы писали:
BZ>нет. я вообще считаю, что в моих собственных программах алгоритмики не меньше, чем в ICFP. там имхо развлекаются те, у кого основная работа связана с более скучными вещами
Ага, писать компилятор для камла — такая тоска!
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>нет. я вообще считаю, что в моих собственных программах алгоритмики не меньше, чем в ICFP. там имхо развлекаются те, у кого основная работа связана с более скучными вещами Т>Ага, писать компилятор для камла — такая тоска!
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, BulatZiganshin, Вы писали:
Т>>>Ага, писать компилятор для камла — такая тоска!
BZ>>вот-вот. неужели тебе работы не хватает?
Т>Да я не про себя. Я про Ксавье и Ко.
Здравствуйте, BulatZiganshin, Вы писали:
P>>А jabber-ru это не BulatZiganshin?
BZ>нет. я вообще считаю, что в моих собственных программах алгоритмики не меньше, чем в ICFP. там имхо развлекаются те, у кого основная работа связана с более скучными вещами
Ну, в ICFP этого года алгоритмики то никакой вообще заметно не было. А вообще, для многих участников всяческих алгоритмических соревнований — это прежде всего состязание с другими людьми, своеобразный спорт. И особой корреляции со скучностью работы я что-то не замечал. За себя скажу, что какая бы у меня ни была работа — вряд ли это повлияет на мое участие/неучастие в том же топкодере. Это мое хобби.
BZ>>нет. я вообще считаю, что в моих собственных программах алгоритмики не меньше, чем в ICFP. там имхо развлекаются те, у кого основная работа связана с более скучными вещами
_DA>Ну, в ICFP этого года алгоритмики то никакой вообще заметно не было. А вообще, для многих участников всяческих алгоритмических соревнований — это прежде всего состязание с другими людьми, своеобразный спорт. И особой корреляции со скучностью работы я что-то не замечал. За себя скажу, что какая бы у меня ни была работа — вряд ли это повлияет на мое участие/неучастие в том же топкодере. Это мое хобби.
Our report about the ICFP programming contest 2007 is now online. The
report contains many details about the contest: how to solve it, how
we made it, who participated, and who won it, amongs others.
Здравствуйте, konsoletyper, Вы писали:
K>Ну, во-первых, в коде на Nemerle, как я уже объяснял, я не сильно заморачивался с дефрагментацией, в результате, она происходила слишком часто, когда не нужно, и слишклм редко, когда нужно. Во-вторых, в C# я занялся элементарным битовыжиманием. Например, в Nemerle сдуру сделал два вида блоков, и match'ил их, а pattern matching разворачивается в цепочку if'ов с проверкой is, что не очень быстро. Ещё неслобое ускорение получилось заменой if'ов (или match'а) на case'ы, последовательным чтением-проверкой при распозвнавании pattern'ов и template'ов, использовании, где возможно, не списков, а массивов, unchecked и т.д. На Nemerle практически всю эту оптимизацию можно сделать, за искл. case, аналогов которого я не нашёл, а match не разворачивается в case'ы в тривиальных случаях (потому что времени ни у кого нет эту фичу добавить).
А зачем тогда на шарпе переписывал? Почему просто немерловый код не оптимизировал? Ты вель вроде бы ансэйф не использовал... А без него существенного увеличения быстродействия сменой языка не получишь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>А зачем тогда на шарпе переписывал? Почему просто немерловый код не оптимизировал? Ты вель вроде бы ансэйф не использовал... А без него существенного увеличения быстродействия сменой языка не получишь.
Ансейф не использовал. А использовал switch. Я предлагал оптимизацию вариантов. Надо сделать у базового класса варианта какой-нибудь метод, который возвращает число, а у наследников его определить так, чтобы он возвращал константу. И при паттерн-матчинге делать не последовательность if (v is A.B) а switch по значению, которое вернул данный метод. Ну и ещё надо бы посмотреть реализацию match для enum'ов. В общем, тогда (а это было 2 года назад) только из-за использования цепочек if'ов вместо switch'а, всё работало в 10 раз медленнее. Не знаю, сделали в последних версиях компилятора такую оптимизацию, или нет.
Здравствуйте, konsoletyper, Вы писали:
K>Здравствуйте, VladD2, Вы писали:
VD>>А зачем тогда на шарпе переписывал? Почему просто немерловый код не оптимизировал? Ты вель вроде бы ансэйф не использовал... А без него существенного увеличения быстродействия сменой языка не получишь.
K>Ансейф не использовал. А использовал switch.
Есть достоверная (с учетом только ускорения от применения свитча) информация о том, что это дало?
K>Я предлагал оптимизацию вариантов. Надо сделать у базового класса варианта какой-нибудь метод, который возвращает число, а у наследников его определить так, чтобы он возвращал константу.
Это было реализовано исходно. Более того в ранних версиях Немерле использовал свитчи (мсильные), но код их генерации писал какой-то олух и он там накосячил. Камил и Москаль провили какие-то тесты (со слов Камила) и пришли к выводу, что если выбросить свитчи, то скорость не уменьшится, а реализация станет в разы проще и чище.
K> И при паттерн-матчинге делать не последовательность if (v is A.B) а switch по значению, которое вернул данный метод. Ну и ещё надо бы посмотреть реализацию match для enum'ов. В общем, тогда (а это было 2 года назад) только из-за использования цепочек if'ов вместо switch'а, всё работало в 10 раз медленнее. Не знаю, сделали в последних версиях компилятора такую оптимизацию, или нет.
Оптимизаций нет. Но Камил настаивает том, что выигрыша в скорости от этого не будет.
ЗЫ
В общем, я тоже за то чтобы вставить генерацию свитчей, но это не так просто как кажется. Прийдется менять логику работы построителя дерева решений и затем уже только саму генерацию мсила.
У меня план по доработкам забит на месяц вперед. Было бы здорово если бы кто-то взялся за эту фичу. Я бы ему помог советами.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Язык — Nemerle 
. 
. Слишком уж на квест похоже.
Либо я не осознаю сложность задачи, либо я младенец по сравнению с ними 
