Отчёты ICFP Contest 2010

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

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

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

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

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

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

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

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

    Подробнее
    Реклама
    Комментарии 23
    • +2
      Добавлю в копилку интересных отчетов: команда thiscodeismade, 19 место.
      (sic: мотороллер не мой)
    • НЛО прилетело и опубликовало эту надпись здесь
      • +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

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