ICFPC-2011: Lambda: the Gathering

[singalen]

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

Пока японская трава не отпускает, надо писать.
Наша команда, кста, прославляет своим названием (и, надеюсь, бе-ме результатом) компанию 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() в функции зомби - самое мощное атакующее оружие.

День первый

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

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