Отчёты ICFP Contest 2010

    С пятницы 18 июня 2010 с 16:00 МСК по понедельник 16:00 МСК — в течение ровно 3 суток — проходил ежегодный конкурс ICFP Programming Contest.

    В этот раз задание, безусловно, было весьма интересным и уступало разве что заданию 2007 года (строки ДНК и изображения).

    Немого о задании. Участникам предлагалось создавать машины и топлива для них. При этом конструкция машины — информация открытая, а конструкция топлива — закрытая. Желательно получить топливо для как можно большего количества машин, и сделать машины, для которых трудно подобрать топливо. Чем раньше передано решение на сервер, тем больше очков оно в итоге приносит.

    В основе кодирования машин и топлива лежат триты — единицы информации, принимающие одно из трёх значений (0, 1, 2). И машины и топлива — это цепочки тритов. Но при этом топливо нельзя передать непосредственно — нужно построить фабрику для его производства. А для этого нужно сначала догадаться о способе кодирования фабрики и внутреннем устройстве её элементов…

    Здесь собраны русскоязычные отчёты команд-участников:

    Ссылки на англоязычные отчёты можно найти здесь.

    После окончания конкурсного времени, от организаторов было выложено объяснение истоков задания.

    См. также: Отчёты ICFPC'09.
    Поддержать автора
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 23

      +2
      Добавлю в копилку интересных отчетов: команда thiscodeismade, 19 место.
      (sic: мотороллер не мой)
        +1
        Спасибо, добавил.
      • НЛО прилетело и опубликовало эту надпись здесь
          +2
          codingmonkeys, кратко: juick.com/xcr/772082
          tbd, у которых все тащили код: github.com/cail/icfpc2010-tbd
          0.000, зато с картинками: nzeemin.livejournal.com/303872.html
          vidmich.livejournal.com/15104.html

          Ну я тоже 0, коротко тут: jerom.livejournal.com/161481.html
            +1
            Может, перенести в блог icfpc: habrahabr.ru/blogs/icfpc/?
              +1
              Перенёс, но меня смущает что тему не плюсуют — хаброжителей это не интересует?
              Ещё непонятно за что минусуют.
                +5
                Ну а в персональном никто не прочитает. Тут есть хотя бы шанс.

                В целом же, спортивное программирование — спорная вещь, которую очень не любят те, кто не умеет. Это как с загадками на собеседованиях :)

                А что я дал ссылку на nzeemin — так я не глядя решил, что это murkt опубликовал, как в прошлом году.
                  0
                  спортивное программирование — вещь, которую очень не любят те, кто не умеет

                  Вот так целиком согласен :)
              +1
              Спасибо.

              > 0.000, зато с картинками: nzeemin.livejournal.com/303872.html
              8-) улыбнуло
                0
                Слава кратко описал. Постараюсь сегодня-завтра поподробнее о Coding Monkeys рассказать :)
                0
                Спасибо, жаль пропустил прошлую тему с анонсом ICFPC :(
                  +2
                  Кстати говоря.
                  Какие существуют в природе контесты в стиле ICFPC? Помню только Sapka Contest, проводившийся год назад под первый CodeCamp, но его так и не повторили.

                  Интересует именно такой принцип «головоломка с решением нестандартной проблемы, каким-то реверс-инжинирингом, командной работой и т.д.», а не обычные ACM-олимпиады.
                    +5
                      +4
                      Я учавствовал с другом, вся помощь которого свелась к определению функций гейтов в первые полчаса (отличный математик!) и первых 17 символов ввода сервера (привет, X::X).

                      Далее я построил эмулятор фабрики и на нём, видимо, довольно оригинальный генератор топлив. Эта штука использовала некоторое подобие генетики для перебора. Начальное поколение содержало два генератора из одного гейта. Затем генерировалось новое поколение с помощью операций swap, менявшей местами два случайных линка, add, добавлявшей зацикленный на себя гейт, и remove, удалявшей случайный гейт, и исправляющий линки. Затем мы полчаса задавали всем окружающим вопрос «как скрещивать схемы функциональных элементов с задержкой», но так и не добились ответа. Весовой функцией был выбрано хэммингово расстояние 17 первых символов ввода до нужной последовательности * 1024 + число гейтов.

                      Ночь работы (пт-сб) этой штуки принесла нам схему длины 26, которая решала простые машины. Поэтому к середине дня мы поднялись на 15 место. Затем я сел писать авточекер и автоаплоадер новых схем. Однако, из-за неимения опыта в сабже, пока я написал и отладил авточекер, сервер начал лагать так, что отлаживал автоаплоадер я до 2 ночи вс.

                      В итоге, мы не заливали фабрик 1,5 дня, что, безусловно было ошибкой, т.к. К в середине субботы генетический генератор фабрик нашёл решение для простых фабрик длины 15, разослав которое вручную на все новые машины можно было бы рассчитывать на огромный профит в субботу. Получил бы место повыше 70-ого.
                        +1
                        Прошу заметить, что мы так и не выяснили ни кодировку топлива, ни кодировку машин.
                          +1
                          А что за команда?
                            +1
                            Я пытался сделать брутфорс, но безуспешно. Потом посчитал варианты и понял что это тупиковый путь. В нашей команде фактически всё один человек разрулил. Он же написал генератор фабрик, который генерил нужный вывод вне зависимости от входных данных. Я пробовал придумать построение фабрики на основании входа, но не осилил — матана не хватило.

                            Все очки принесло топливо 111111, или как-то так. Очень много времени потратили (я в основном) на бессмысленные поиски зависимостей. Я ещё пол-дня убил пытаясь сделать фабрику-генератор нулей, которая вообще не была нужна. Ну, я же опять протупил поставить автосабмитер топлива для новых машин на ночь — может поднялись бы повыше 84-го. Другая ошибка — стоило кому-то пытаться узнать кодировку машин и топлива, сразу после того, как получили возможность засабмитать свою машину. В конце на это уже не было времени, да и толку было бы немного.
                            +1
                            Мы из 7 человек к 2 ночи остались вдвоем, когда уже почти подошли к ключу. Но брутфорсить или подбирать экспериментально посчитали неинтересным и не очень спортивным, решили, что мы что-то не понимаем и пошли с остальными в покер играть. Жаль, похоже, брутфорс помог бы.
                              +1
                              Oroborus, 51 место — murkt.livejournal.com/61477.html
                                0
                                Кстати, спасибо вам за анонс конкурса на Хабре — благодаря ему многие вовремя вспомнили, в том числе и я.
                                  0
                                  Потому и постил, так как в прошлом году я точно так же узнал за пару дней :)
                                +1
                                Погоняв (уже после окончания контеста) свою брутилку фабрик, обнаружил любопытные результаты:
                                — генератор любой константы делается на четырех гейтах (в первые часы контеста у нас было 6 гейтов для нуля, 7 для двойки и 14 для единицы. И только на второй день заимплементили самогонный аппарат 1.66 гейта на трит)
                                — линия задержки на 1 такт делается на трех гейтах, а на 2 такта — никак не менее шести
                                — требуемый 17-тритовый ключ генерится шестью гейтами (четырьмя способами)
                                — полный перебор для 7 гейтов занимает у меня сутки. На обычной машине, никаких там кластеров. Думаю, у сотрудников гугла были все шансы насчитать результаты, начинающиеся с 17-тритового ключа минут за 10. Если им разрешают юзать ресурсы, разумеется :)

                                В целом остался доволен контестом. Учитывая всю совокупность проблем, могло быть и хуже…
                                // THIRTEEN
                                  0
                                  ube, 45 место — alf13.livejournal.com/1016.html

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое