Пользователь
0,1
рейтинг
22 июня 2010 в 16:33

Разное → Отчёты ICFP Contest 2010

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

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

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

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

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

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

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

См. также: Отчёты ICFPC'09.
nzeemin @nzeemin
карма
62,2
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

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

Самое читаемое Разное

Комментарии (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

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