В эту пятницу начинается ICFPC-2016.
Может, и поздновато, но хочется размять кости.
Собирается неплохая команда, всего трое.
Может, ещё кто?

13-16 июля.
Днепровцы, кто отдаст три (четыре) дня жизни?
Ну или не-днепровцы?
Java? Groovy? Scala?

14е место на #icfpc2011
Я рассчитывал на меньшее, около 28го - слишком мало успели %)

Окончание. Начало здесь, вторая часть здесь.

Часть третья

Получили невероятное удовольствие. Оно было бы ещё больше, если бы мы на второй день таки-вывели и написали универсальный компилятор в LtG — но увы :D

Читал я как-то годную фэнтезю — Бэккера, "Князь пустоты". Там есть сцена поединка магов.
Клан первого из них, "Завет" — владел магией высших порядков, хотя всегда жил крайне скромно. Другой маг был большим человеком в самом богатом магическом клане "Багряных Шпилей" — но вот беда, никто, кроме Завета, высшей магией не владел. Все прочие кланы строили свою карьеру на заклинаниях, подобранных наугад, Завет же владел теорией.

Маг Шпилей вызвал самого сильного духа, какого мог, своими эмпирически подобранными заклятиями (сильнейшими в клане, заметьте). И до смерти удивился, когда полуживой маг Завета с помощью заклинаний-Абстракций (они и правда так назывались!), без усилий размазал духа и соперника тонким слоем по окрестностям.

Примерно таким же тонким слоем чувствовали себя мы перед чемпионами, потому что:

• надо было овладеть новым, "магическим" языком;
• он почти что так и назывался - только слово Magic заменили словом Lambda;
• мы тыкались в темноте, оттачивая комбинации наших примитивных эмпирических "заклинаний";
• те, кто освоил теорию, в мгновение ока (от 200 до 900 ходов) выносили "в ноль" наш тщательно, вручную подобранный раш.

Не отпускало нас потом ещё два дня.

• Браузнуть сырца можно тут: http://svn.victorsergienko.com/icfpc2011/trunk/domain-model/
• Итого — примерно 71К на Груви + 35К юнит-тестов на нём же.
• Нам не хватало как минимум одного, третьего программиста. И вообще, два программиста и два математика — это в четыре раза слабее, чем четыре программиста-математика. У японцев-Atomic-ов, которые, наверняка, станут чемпионами, как раз столько и было :)
• Команда Ciklum бултыхается где-то в полупроходниках со своими 21-23 победами из 30 на неофициальном сервере.

А как оно было у японцев...

Четыре японских хаскеллиста:

• собирали части пушки в разных словах (потом оказалось, что иначе в этом SKI-исчислении никак);
• авто-компилировали все стратегии;
• умели, если им что-то сломали, оживлять ячейку и продолжать любую (!) старую стратегию с того места, на которое возможно откатиться (!!!), и собирали подходящие запчасти по разным слотам (!);
  • У меня самовосстанавливаться умеют только две очень частных стратегии - dec() слабой ячейке врага, и revive() своей.
• ещё они написали свой тестовый-контестовый сервер — от нечего делать, надо полагать.
• эти монстры научились убивать "sitting duck" в 165 ходов.

Вот у меня недавно dima_kender спрашивал старый вопрос — какой язык программирования лучше для быстрой разработки :D

Я ответил старый ответ — язык, который хорошо знает команда. Ну и смотря чего разработка — десктоп, простой веб, рич веб, сложная логика или CRUD, с БД или без.

И дал свои предварительные ответы, при прочих равных:
Для веба — Rails, для десктопа — Windows.Forms.

Но если программисты и задача пыц-пыц какие умные, то Haskell, как показали последние дни.

Если добавить зомби, всё становится круче.
Мила Йовович

Пока японская трава не отпускает, надо писать.
Наша команда, кста, прославляет своим названием (и, надеюсь, бе-ме результатом) компанию Ciklum.

Последние три дня прошли в зомбическом угаре.
Задание на очередное соревнование ICFPC японцы придумали на редкость удачное, хотя и слишком умное для нас :D

В этом году програмы участников должны играть друг с другом в некую Lambda: the Gathering - гибрид Magic: the Gathering, SKI-исчисления (вот пример готового языка) и машины Тюринга.

Правила

Если вкратце, у двух игроков есть:

• 15 видов "карт", каждая из которых - это функция;
• игровое поле из 256 ячеек. У ячейки есть "жизнь" (в начале игры - 10000) и "значение" (число или функция), в начале - функция I(x)=x.

Вот примеры карт-функций:

• I(x) возвращает x
• succ(x) возвращает x+1
• copy(i) возвращает значение i-й ячейки врага
• attack(i, j, n) бьёт (255-j)-ю ячейку врага на 9n/10 жизней, ценой убавления n жизней у нашей i-й ячейки;
• zombie(i x) садит в (обязательно мёртвую) (255-i)-ю ячейку врага шпиона-зомби с функцией x, который будет делать на поле врага всё, на что запрограммирован; там есть нюансы, о них позже;
• revive(x) оживляет мёртвую ячейку и даёт ей 1 очко жизни.

Ходы. Игроки ходят по очереди. Каждый ход:

• сначала наступает "час зомби", когда подсаженные врагом зомби ("см. рис. 1") автоматически вылазят из могил и делают своё дело, противное всему живому;
• потом игрок применяет (вычисляет) одну из 15 "карт"-функций к значению одной своей ячейки,
• или же наоборот, применяет значение (тоже функцию) из одной "ячейки" к "карте".
• если функция вычислилась без ошибки, то результат записывается в ту же ячейку;
• в любом случае, у вычисления функции может быть побочный эффект, который остаётся.

Некоторые карты-функции могут возвращать в результате другие функции. Таким образом в ячейке можно накапливать длинные формулы, а потом "запускать" их "на раскрутку". Это, собственно, Тюринг-полная машина. Или не совсем полная, как мы заподозрили позже.

Например, функция K(x, y), применённая к x, вернёт другую функцию - Kx - которая, применённая к любому y, вернёт x ("запомнит" x, а y выбросит). Таким образом, K позволяет отложить вычисление x столько раз, сколько K мы навесим на x.

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

Победа. Выигрывает тот, кто убьёт оппоненту все ячейки, или, по истечении 100 тыс. ходов — тот, у кого больше живых ячеек. Возможна ничья.

В "час зомби" функции, меняющие здоровье, работают "наоборот": inc() уменьшает на 1 нашей, а dec() увеличивает вражеской ячейке; attack() всё так же платит здоровьем нашей, чтобы увеличить (!) здоровье вражеской, а help() не "переливает" из одной нашей в другую, а уменьшает здоровье обеим. Собственно, help() в функции зомби — самое мощное атакующее оружие.

День первый

Вот сели мы за это задание...

Продолжение здесь, окончание здесь

Если кто-то хочет в ICFPC - я готов договориться с конторой, чтобы в помещение с интернетом пустили несколько команд, в т.ч. на пятницу.

Организовываться можно через меня, я сведу желающих вместе :)

Можно потренироваться на Google Code Jam. Следующий матч у них через 4 дня :) Но можно потренироваться в любой момент, на старых.

Немного утешает мысль, что мы делали честную орбитальную механику, без переборов по импульсам и без заглядывания в будущее.

Какой-нибудь бинарный поиск с "машиной времени" по силе/времени импульса не запрещён правилами и FAQ-ом, но СЛЕГКА похож на чит. Хотя, если бы мне в голову пришла такая идея - сделал бы, не задумываясь.

Fells like "Глупо, но честно".

Этим летом на ICFPC team Grobocode вышла в виде нас с sanyok_ua.
Хорошо помог vbayda. nataly_scheg помогала отлаживать математику.
Выступала команда в основном из посёлка Морское под Судаком.

Надо было управлять космическим кораблём! Круто! Пришлось срочно осваивать орбитальную механику.
Подробно условия задачи можно прочесть в отчёте _adept_-а; в двух словах - надо было переходить с орбиты на орбиту, в т.ч. для встречи со спутниками, экономить топливо, корректироваться, а потом - даже дозаправляться.

Чтобы получить доступ к кораблю, его надо было запустить в виртуальной машине, на которую дали только спеки. Хорошая традиция.

День первый

( кому интересно )

Наконец-то я пишу, как мы (team Grobocode) играли в ICFPC.

Содержание.
Задача
Команда
Инструменты
Решение
  Рулёжка к заданной точке
  Поиск пути
  Поиск пути-2
  Заносы: считаем инерцию и трение
  Как не попасть в жертву Барзуму
Как вообще было дело
Наши ошибки
Итог

Задача

Задачу вы наверняка читали у _adept_-а; если нет, напою совсем кратко.
Луноход с Марса передаёт по сокету поток телеметрии, в котором есть его координаты-скорость, и координаты-скорость препятствий и марсиан, попадающих в поле зрения. Все объекты - круги, заданные на плоскости в вещественных координатах.
Мы ему передаём команды "влево-вправо-газ-тормоз". Линейное и угловое ускорения заранее неизвестны.
Задача - как можно быстрее доехать до базы, не упасть в кратер и не попасться марсианам, которые хотят принести мерс-о-ход в жертву богам Барзума.

Команда

Команду собрали более-менее заранее. За неделю до начала сделали тренировку, проверили матобеспечение - доступ к SVN и вики, решили три задачки с топкодера и расползлись. Как и следовало ожидать, пара часов ушла только на подключение к сети/клиентский софт/логины/IDE.

Собирались участвовать 8 человек, а к началу туров нас осталось пятеро, в алфавитном порядке:
al_dragon
gabriel_irk
kontiky
sanyok_ua
singalen

( Далее ещё много... )

Итог

Полную версию не дотянули до более-менее рабочей программы, но вариант 2-го дня, "нос на центр и тапочку в пол", засабмитили.
Получилось, плохо, но, думаю, мы тоже не в худшей половине.