thedeemon: (office)
As you surely know, Bashkortostan is the world leader in technology,
computer science and algebraic topology. With this submission, we expect to
cement the positions of our motherland in the exciting new field of
computational geometry. Don't worry: resistance is very obviously futile.

From young age, our children are trained in the art of convex decomposition
of polyhedra, computing barycenters of weighted point sets, and triangulated
surface mesh skeletonization; hoping, that one day they'd be tasked with a
crucially important problem of...

https://github.com/cakeplus/icfp-2016-wild-bashkort-mages
Самый суперский отчет (точнее, readme к исходникам) с нынешнего ICFPC. Почитайте целиком, не пожалеете.

В этом году контест был очень классным, и очень суровым.

Hextris

Aug. 11th, 2015 11:59 pm
thedeemon: (office)
В эти выходные прошло соревнование ICFPC - волшебная пора, когда все функциональные программисты мира (все 800!) могут оторваться от своей дневной работы на джаве, С++ или РНР и на три дня представить, что их любимый язык все-таки где-то применим.

В этом году надо было сделать свой решатель тетриса, но хексагонального, с занятной неевклидовой геометрией (движение фигуры по прямой не сохраняет взаимное расположение частей в их координатах относительно друг друга, движения и повороты работают по-разному в зависимости от места происходящего).
gif, 1.6 MB )
К этому сверху был прилеплен поиск и использование волшебных заклинаний ("ктулху фхтагн бешельме чернмернда") - каждый ход кодируется одним из нескольких возможных символов, если из этих символов в решении складывается какое-нибудь заклинание, за это дают дополнительные очки, и, видимо, много. Я как обычно участвовал без ансамбля, поэтому на заклинания совсем забил, занимался только тетрисом. За первый день сделал логику игры (загрузка данных, движения фигур, сжигание рядов, подсчет очков) с визуализацией и ручным управлением, можно было играть самому, а также прогнать пример от организаторов и убедиться, что все работает. Все получалось довольно гладко, разве что на поворот фигур потратил неожиданно много времени: гуглить готовые подходы не стал, хотя понимал, что наверняка известны какие-нибудь красивые подходы с трехмерными координатами. Стал придумывать сам, но формулу для преобразования координат при повороте не придумал, вместо этого сделал табличку (отображение разных координат при повороте), заполнявшуюся индуктивно: точка, вокруг которой идет поворот, не меняется, ее ближайшие 6 соседей меняются местами циклично, а дальше если для какой-то клетки знаешь, как при повороте двигается ее ближайший сосед, то ее движение состоит из такого же ровно сдвига (вместе с тем соседом) плюс поворот вокруг этого ближайшего соседа, такой поворот уже известно как делается.

На второй день стал придумывать стратегию для игры, и в течение второго и третьего дней ее постепенно реализовал (как-то не очень быстро каменный цветок выходил). Работало все следующим образом. Когда очередная фигура появляется на поле, понятно, что остановиться ей надо будет или где-то непосредственно рядом с уже имеющимися заполненными клетками, или рядом со стеной (краем уровня). Очки дают за сжигание полностью заполненных горизонтальных рядов, поэтому нас интересует соседство горизонтальное прежде всего. Поэтому в самом начале игры для каждой фигуры, для всех ее поворотов, были составлены списки точек, которыми она может касаться горизонтально. Когда фигура появляется на поле, надо пройтись по всем пустым горизонтальным соседям уже имеющихся на поле объектов и примерить к ним текущую фигуру по тем спискам потенциальных точек соприкосновения, т.е. перебирать все-все возможные ее положения не нужно, лишь те, где ожидаются касания. Для каждой такой потенциальной позиции приземления оценивается ее привлекательность: приведет ли ее занятие к полному заполнению каких-нибудь горизонтальных рядов (и их количество), если нет, то для каждого горизонтального ряда занимаемой позиции оценивается наибольшее количество получающихся заполненных подряд клеток (больше - лучше), плюс поправка на высоту: сжигать ряды лучше те, что выше, а вставать на пока еще незаполненные лучше пониже. Чуть позже был добавлен еще один фактор: сравнивалось количество "пузырей" (недостижимых сверху пустых клеток, т.к. фигуры могут двигаться лишь вбок и вниз, но не вверх) до и после занятия позиции, образование новых "пузырей" пенализируется, снижает оценку привлекательности позиции. Оценив все эти потенциальные позиции для приземления фигуры и отсортировав их по привлекательности, первая версия брала первую достижимую из них (для которой найдется путь от исходного положения фигуры). Это дало смешной результат: т.к. часто вращение фигуры на некоторые углы отображает ее в себя, позиции с такими углами поворота получают одинаковую оценку, и после сортировки по оценке первой часто попадалась позиция повернутая, в результате фигура перед ее занятием делала ненужные вращения, что по условиям задачи чревато обнулением очков. Поэтому вместо первой достижимой позиции из отсортированного списка брался набор позиций с одинаковыми оценками и из них выбирался вариант с кратчайшим путем, это отсекало ненужные вращения. Поиск пути был простым А* в трехмерном пространстве (x,y,угол), в процессе поиска строится множество достижимых позиций, в котором для каждой клетки сказано, как туда попали. Если для какой-то интересующей нас позиции путь не нашелся, то значит поиск пути перебрал все достижимые клетки карты, и при поиске путей для других позиций уже ничего еще раз строить не нужно: если позиция достижима, она уже в нашем множестве достижимых, и путь к ней уже известен, а если ее там нет, то путь не существует. В итоге все работало мгновенно, как-то еще оптимизировать или усложнять поиск не понадобилось. Памяти процесс ел меньше 3 МБ на маленьких задачах и около 20 МБ на больших.

В последний день к описанной схеме был еще добавлен look-ahead: последовательность фигур известна заранее, поэтому вместо принятия решений лишь по текущей фигуре был сделан рекурсивный перебор на пару шагов вперед. Вместо того, чтобы брать наиболее привлекательную достижимую позицию, составлятся список из 5 лучших достижимых (с разными оценками, чтобы отсечь те, что отличаются лишь поворотами), для каждой из них моделируем что получится при ее выборе, рекурсивно ищем решение для следующей фигуры, так на несколько фигур вглубь (в будущее), в этом дереве вариантов для листьев выбирается максимум, он возвращается наверх и складывается с оценкой узла-родителя, из его таких сложенных вариантов выбирается максимум и передается наверх.. В итоге для текущей фигуры выбирается такое положение, которое дает максимальную сумму оценок для этой и нескольких следующих фигур. Например, если текущей фигурой можно сжечь один ряд и следующей можно будет сжечь еще один, но если сейчас один не сжигать, то следующая сможет сжечь оба, то будет выбран именно последний вариант, ибо за сжигание двух рядов сразу дают больше очков, чем за два сжигания по одному ряду. С таким look-ahead'ом все стало ощутимо медленнее, но все равно большинство задач обсчитывалось меньше чем за минуту, и чтобы обновить все решения мне понадобилось менее получаса. Писал на D, исходники на битбакете, 1200 строк включая гуй.

Вот, получилось довольно интересно, на мой взгляд. Поскольку заклинаниями не занимался, очков набрал не очень много, в общем зачете из 300+ зарегистрированных команд на 103 месте (в этот раз назвался Dr. Zoidberg).
thedeemon: (office)
ICFPC еще торт, скажу я вам! В этом году нам предложили поиграть в пакмэна, где вместо колобка был Лямбдамэн (куда ж без Вадлера), а привидения выглядели как знаки присваивания, квинтессенция императивщины. Лямбдамэн и его враги управлялись программами, исполняющимися двумя различными виртуальными машинами. У привидений-присавиваний была императивная машина с регистрами, данными в виде массива и программами, его мутирующими и вызывающими прерывания для выполнения сайд-эффектов. У Лямбдамэна был вариант SECD-машины, где (за исключением одной ненужной операции) все довольно чисто и функционально. Программа - это функция, принимающая свое прошлое состояние и состояние мира на вход, и возвращающая выбранное ей направление движения вместе с обновленным своим состоянием.
Помимо описания виртуальных машин организаторы выложили и референсную реализацию (мегабайты непролазного джаваскрипта, полученного компиляцией хаскеля).

Read more... )

ICFPC '13

Aug. 16th, 2013 06:20 pm
thedeemon: (Digby)
"The story so far: As usual, Ginger and I are engaged in our quest to find out what the hell is going on and save humanity from my nemesis, some bastard who is presumably responsible."

В этом году соревнование ICFPC организовывали в RiSE Group из Microsoft Research, где активно занимаются солверами вроде Z3 и синтезом программ, системами доказательств и верификации, вроде Dafny и Boogie, а также исследовательскими языками вроде F*. Поэтому их задание совершенно не удивило. Сводилось оно к тому, что они загадали множество небольших функций на описанном в условии простеньком языке, и нам надо было отгадать, что это за функции. Каждая такая функция принимает на вход 64-битное целое число, и такое же возвращает. Для каждой загаданной функции можно было попросить их сервер вычислить ее на некотором наборе входных значений, и сервер отдавал результаты. После чего у игрока было 5 минут, чтобы догадаться по этим результатам и свойствам функции (для каждой загаданной функции было описано число и множество операций в ней использованных), что это за функция, и прислать текст догадки. Полного совпадения не требовалось, достаточно было эквивалентной загаданной, но только если их система будет способна понять, что загаданная и присланная функции эквивалентны. Посылать числа на вычисление и догадки можно много раз, но не чаще 5 запросов за каждые 20 секунд, и не более 5 минут между первым запросом и последней догадкой.

В моем часовом поясе соревнование начиналось (и заканчивалось!) в 7 утра, так что начало я благополучно проспал. Почитав утром задание, понял, что это классическая задача для SMT-солверов, но я с ними никогда дела не имел, и сейчас освоить не успею, поэтому буду придумывать что-то сам. Всего разных возможных функций из UInt64 в UInt64 - (264)(264) штук, но возможных функций на том языке заданного размера (по условию там было не более 30 операций) - менее 2100 штук, что для полного перебора все равно дофига, но, теоретически, задавая правильные вопросы серверу, достаточно было получить от него 100 бит информации, чтобы понять, какая функция там загадана.Read more... )
thedeemon: (Digby)
"On a lonely planet spinning its way to damnation amid the fear and despair of a broken human race, who is there to fight for all that is good and pure and gets you smashed for under a fiver? Yes, it's the surprising adventures of me, Sir Digby Chicken Caesar."

Одна из главных сложностей нынешнего ICFPC - заставить себя заняться улучшением текущего решения или даже придумыванием нового, в то время как твоя программа работает себе, накапливая очки. Хочется просто сидеть и наблюдать за ее прогрессом (screenshot).
thedeemon: (office)
Программистское рождество, как известно, бывает летом, но лето было давно, и следующее придет еще не скоро, а праздника хочется, посему предлагаю по аналогии с зимними олимпийскими играми устроить маленький зимний контест. Задача у меня практически готова, так что это не столько предложение, сколько анонс. Я попытался выдержать дух хороших образцов ICFPC, потому:
- Играть можно командой или в одиночку. Задачка не шибко сложная, так что наличие команды не будет большим преимуществом.
- Писать можно на чем угодно.
- Никаких бинарников под определенную систему собирать не нужно.
- Никаких сетевых взаимодействий и жестких рилтаймовых ограничений.
- С первой минуты контеста будет доступен scoreboard, где сразу можно будет видеть свой прогресс и успехи других участников (очки).
- Соответственно, победитель четко определяется по очкам и времени, никаких субъективных судейских закидонов.
- Результатов не придется ждать до осени!
- Это НЕ очередной AI для очередной игры.
- Это НЕ очередной поиск пути в графе.
- Надеюсь, будет интересно и весело. Многие смогут кое-чему научиться.

В честном соревновании мы выясним наконец какой язык лучше, и на чем пишут настоящие хакеры. Правда ли, что дельфи лучше эрланга, написанного на хаскеле, а кложа на порядок продуктивнее 1С. :)

Начать чад кутежа предлагаю в пятницу 14-го декабря в 11:00 UTC, ну или можете меня переубедить на другую дату/время. В назначенное время ссылка на задание появится у меня в журнале. С завершением сложнее: можно формально выделить традиционные 72 часа, но скорее всего победители определятся раньше - по мере заполнения таблицы результатов именами команд, набравшими максимум очков.

Update: дата не изменилась, начинаем в пятницу 14-го в 11 UTC.
thedeemon: (Default)
Как-то я пропустил объявление результатов ежегодного соревнования по функциональному программированию. А они довольно забавные:
1-е место - С++.
2-е место - Окамл (мои поздравления jabber.ru!)
Lightning division - Java.
Судейский приз достался команде, писавшей на Хаскеле, Паскале и Питоне, употребившей на троих 22 литра пива. :)

Supaplex!

Jul. 13th, 2012 04:36 pm
thedeemon: (Default)
Была когда-то такая замечательная игрушка под ДОС. Реинкарнацию под Win/Mac/Lin можно взять тут:
http://www.newsupaplex.pp.ru/sup_download.html
Нынешний ICFPC, похоже, слизан с нее. Стоит ожидать появления догоняющих героя врагов!
thedeemon: (Default)
В минувшие выходные прошло ежегодное 72-часовое соревнование ICFP Contest. В этом году его организовывали японцы (судя по выложенному ими бинарнику, пишущие на окамле). На мой взгляд, задание получилось очень хорошим, лучше нескольких предыдущих (2008-2010). Условие повторять не буду, его можно прочитать в оригинале на английском c красивыми картинками или в подробном пересказе по-русски.

К огранизации японцы тоже подошли грамотнее предшественников: чтобы обезопасить себя от падений официального сервера, задействовали гугловские сервисы - blogger для вывешивания условия и spreadsheets для приема ссылок на решения. Сами решения скачивались уже после контеста и теперь неспеша будут запускаться и сражаться.

Read more... )

ICFPC'10

Jun. 23rd, 2010 02:52 pm
thedeemon: (Default)
Назвался груздем - пиши отчет о полезании в кузов.
В понедельник завершилось ежегодное программистское соревнование ICFPC, в котором я традиционно участвую с 2007 года (мои предыдущие отчеты: 2007, 2008, 2009).

Если в прошлом году задание было очень четким, понятным, и оттого немного скучным, то в этом году оно было очень непонятное. Участникам предлагалось состязаться на рынке машин и топлив, где команды выпускают разные машины и производят для своих и чужих машин топливо. У кого лучше топливо и кто больше машин им обеспечил, тот больше денег (очков) заработал. В задании было описано, как в машинах бывают устроены двигатели, и как определяется, подходит ли им топливо. При этом сами машины и топлива кодировались последовательностью троичных цифр, но как именно - не сообщалось (разве что была подсказка, что там есть списки, туплы и числа произвольной длины). Более того, недостаточно просто придумать и закодировать топливо для машины, нужно создать фабрику для производства этого топлива, и ее уже посылать на сервер. Про фабрику было сказано, что она состоит из соединяющихся друг с другом гейтов, у каждого гейта два входа и два выхода. От выходов ко входам бегают троичные цифры (триты), какой-то неизвестный их поток подается на вход фабрики, и на выходе фабрики получается некий поток тритов, он-то и должен кодировать топливо. Устройство гейтов не уточнялось, формат фабрики - тоже, разве что был дан один пример:
Read more... )
thedeemon: (Default)
Порадовала история про судейский приз на ICFPC этого года. В топ-10 по очкам вошла команда с лаконичным названием "when i was 4 years old i was maimed by a giant pig". Приложенное к их исходникам readme выглядело примерно так:



Т.е. в графе "используемый язык" у этой команды стоят сразу 6 языков, все они так или иначе ипользовались:



Например, PHP использовался для генерации кода на С++. Java для визуализатора орбит. Решение очень впечатлило судей, однако по правилам соревнования для судейского приза нужно было выбрать один язык, который будет вписан в объявление "XX is the tool of choice for extremely cool hackers". Они долго чесали репу, и в конце концов выдали такую формулировку:



Так-то. :)

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:25 am
Powered by Dreamwidth Studios