ICFPC — ежегодное соревнование для программистов. Оно проходит в онлайне и длится 72 часа. ICFPC 2017 начнётся в пятницу 4 августа в 12:00 (UTC) и закончится в понедельник.
Я расскажу, почему нельзя пропускать ICFPC и дам серию советов. Освободи следующие выходные, собери команду и участвуй!
Соревнование для вдумчивых хакеров
ICFPC — командное соревнование. Соревнований для одиночек много: например, Facebook Hacker Cup и Google Code Jam. Если вам нравятся AI для игр, то codingame.com проводят отличные челенджы раз в 2-3 месяца. В одиночных соревнованиях топ обычно забит какими-то гениями, а в командных можно хорошо выступить за счет упорства и хорошей организации.
Команда может быть любого размера. Обычно задачи на ICFPC можно решать несколькими способами. Попробовать все способы и выбрать лучший — это большая работа. В 2011 году я играл в команде из двух человек. У нас не было недостатка идей, но мы остро чувствовали недостаток рук.
Соревнование для вдумчивых. Соревнование длится трое суток, поэтому не нужно быть быстрым, как олимпиадный программист. Есть время, чтобы подумать над задачей, разобраться и реализовать любой алгоритм.
Задачи небанальные. Организатор соревнования меняется каждый год. Обычно это университет, поэтому они добавляют в задачи отсылки к научным проблемам и классике computer science (скажем, в 2014 была отсылка к SECD-машинам). Кроме того, ICFPC приурочен к научной конференции по функциональному программированию ICFP, и это влияет на задачи. Через раз приходится читать описания на функциональном псевдоязыке (не бойтесь, понятном для обывателей!), а потом программировать виртуальные машины и компиляторы.
Задача одна! За 72 часа команда неограниченного размера должна решить всего одну задачу. Но многогранную и трудную. Её нельзя решить оптимально, но можно решить лучше других команд. Самыми необычными и яркими задачами считаются задачи 2006 и 2007 годов, в которых балом правили виртуальные машины внутри виртуальных машин и а также реверс-инжениринг виртуальных машин.
У меня юбилей )
Я, xoposhiy, участвовал в ICFPC 9 раз. И каждый раз было что-то новенькое:
- в 2007 была задача на редактирование ДНК пришельца и структуру данных rope string,
- в 2009 — вывод спутников на орбиту с помощью программы для виртуальной машине симулятора,
- в 2010 — ни на что не похожая задача про машинки и топливо,
- в 2011 — карточная игра Lambda the Gathering про SKI-комбинаторы,
- в 2012 — бот для Boulder Dash с изменяющимися в процессе игры требованиями,
- в 2013 — подбор арифметической функции по примерам входов и выходов,
- в 2014 — боты для Pac-Man на двух виртуальных машинах,
- в 2015 — гексагональный тетрис с заклинаниями,
- в 2016 — решение и составление трудных оригами.
В последние годы наша команда стабильно попадает в десятку лучших:
- в 2016 — 6 место,
- в 2015 — 7 и 13 место (было две команды),
- в 2014 — 7 место,
- в 2013 — 3 место,
- в 2012 — 13 место,
- в 2011 — не вышли в финальный раунд,
- в 2010 — 22 место.
Интересно, что третье место в 2013 году выиграла команда из 8 человек. А в прошлом году 6 место заняла команда аж из 12 человек. Тут нормальный человек должен удивиться, как мы способны такой толпой трое суток продуктивно трудиться всего над одной задачей? Рассказываю!
Как мы боремся с мифическим человеко-месяцем
Закон Фредерика Брукса: «Если проект не укладывается в сроки, то добавление рабочей силы задержит его ещё больше»
Расскажу на примере задачи с прошлогоднего ICFPC 2016.
Дан силуэт плоского оригами, собранного из квадратного листа бумаги 1×1. Нужно восстановить развертку оригами, то есть отметить на листе линии сгибов и описать для каждой вершины на развертке, куда она переходит на силуэте. В начале есть 100 силуэтов от организаторов. Через сутки участники смогут сабмитить свои задачи для соперников.
Как решать?
Используйте дуальность задачи. Нужно решать оригами. А ещё нужно придумывать оригами, которые не смогут решить соперники. Это первая возможность для параллельной работы. Дуальные задачи — обычное дело в ICFPC. В 2010 и 2014 году были похожие задачи.
Решайте задачи разными способами. Мы сразу придумали два способа решать оригами: собирать квадрат 1×1 из полигонов, видимых на силуэте, и наоборот, разгибать силуэт так, чтобы получился квадрат 1×1. Было непонятно, какой из этих способов лучше, поэтому мы разделились и начали делать их параллельно.
Потом заметили, что много силуэтов — выпуклые фигуры. А они решаются тривиально — загибанием краёв квадрата. Поэтому мы написали ещё один решатель выпуклых оригами.
Потом мы заметили несколько трудных задач от команды WILD BASHKORT MAGES (привет, ripatti), которые принесли бы много баллов, и написали решатель именно для них. (В конце мы узнали, что MAGES тоже написали специализированный решатель для наших оригами)
Потом мы написали визуальный решатель, который помог справиться с несколькими десятками оригами вручную. В итоге у нас было 5 различных решателей для одной задачи.
В 2013 году мы тоже заняли третье место благодаря тому, что у нас было два разных решателя для разных типов задач. В ICFPC специализация и дублирование решений помогают.
Начните со вспомогательного кода. Перед тем, как программировать решатели, нужно закодировать структуры данных, описывающие предметную область. Запрограммировать ввод-вывод. Протестировать. Попрофайлить и оптимизировать. Пока одна группа занимается этими задачами, остальные думают над алгоритмами.
Визуализируйте. Оригами были описаны числами, но мы хотели посмотреть на них, поэтому сразу взялись за визуализатор. В каждом ICFPC нужно делать какой-нибудь визуализатор или визуальный отладчик. Вот наш:
А вот так выглядит визуализация в решателе команды-победителя Unagi:
Вложитесь в инфраструктуру. Как только начальный хаос и спешка закончатся, автоматизируйте рутинные задачи. Мы сделали автоматическое скачивание новых задачек. Сложили решенные оригами в Git, чтобы они были доступны всей команде. В других ICFPC писали систему для тестирования финального качества решения, чтобы экспериментировать и понимать, полезны наши доработки или вредны.
Тестируйте. Несложно наколбасить много кода. Сложнее заставить его корректно работать. Ошибки есть всегда, поэтому обязательно пишите тесты, особенно на низкоуровневый код, которым пользуются вся команда. Если не писать тесты, то два из трех дней уйдут на отладку. Мы проходили этот урок многократно. Однако говорить про тесты легко, сложнее в пылу соревнования не забить на них.
Поделите на два. 12 человек превращаются в 6, если работают в парах. Пара даёт более качественное решение. Пара может в любой момент разделиться, причем каждый участник будет хорошо разбираться в общем коде. Например, можно начать делать визуализатор в паре, заложить правильную архитектуру, а потом спланировать фичи и разойтись делать их параллельно. Ещё в паре веселее кодить, но это не точно.
Избегайте merge-конфликтов. История в репозитории большой команды получается ветвистой. При любом неаккуратном движении случаются merge-конфликты, которые портят нервы и отнимают время. Поэтому навык бережного отношения к истории изменений очень полезен на ICFPC. Договоритесь об оформлении кода, добавьте файл с настройками IDE в репозиторий, используйте автоформатирование.
Соберите команду мечты. Задача не известна заранее, её нужно будет декомпозировать «на лету». Поэтому в ICFPC полезны люди, способные быстро ориентироваться в обстановке, генерировать идеи и продавать их другим членам команды, вкладывать свои силы в самую полезную задачу, читать кучу чужого кода и не ломать его своими правками.
Организуйте научный отдел. Часть команды может читать научные статьи, искать готовые инструменты, расшифровывать подсказки от организаторов и других участников. Как любая наука, это не даёт мгновенный выхлоп. Но в прошлом году мы таким образом отыскали пару полезных мыслей.
Не забудьте выспаться. Вас ждёт 72-часовой марафон, и свежие головы будут на вес золота.
Команда kontur.ru
В этом году в нашей команде [пока] 14 человек. Мы постараемся следовать всем своим советам и показать лучшую игру.
Во время соревнования попробуем писать интересное в наш канал в Телеграме. Подписывайтесь и болейте за нас.
Настоящие джедаи не смогут просто наблюдать, верно? Тем более, что играть в ICFPC интересно и увлекательно вне зависимости от финального результата. Так что собирайте команду и участвуйте. И да пребудет с вами сила :)
- Сайт соревнования (там традиционно минимум информации до начала!)
- Твиттер организаторов
Автор: xoposhiy
