ICFPC'2011, часть 1: задание.
Задолго до начала контеста в блоге организаторов появилась картинка с традиционной лямбдой, и подписью "What's in an image?", которая как бы говорит нам. Разумеется, antilamer принял это как руководство к действию, и довольно быстро обнаружилось, что в картинке имеется jar-файл, при запуске которого получилось вот такое чудо:
Это была мощнейшая подсказка. К сожалению, мало кто предположил, что подсказка будет настолько явной. _adept_ даже высказал мнение, что это очередная мистификация, наподобие тех, что были в 2006 году. (Блджад! Сколько раз уже его команда прокалывалась на том, что подсказки - это подсказки, а не мистификации! 2006 год был один раз!) Тем не менее, мы правильно рассудили, что, наверное, придётся играть в какой-то аналог Magic: The Gathering с лямбдами и аспирантками ВМК (if any). Зато никто не обратил внимание на нарисованный на второй карте расходящийся омега-комбинатор. А зря - эта проблема не преминула всплыть ближе к середине контеста.
Итак, опубликовали задание. Контест проводится в виде серии дуэлей между программами, написанными участниками. У каждой программы есть в распоряжении 256 слотов, каждый из которых может содержать число или функцию. Каждому слоту также сопоставлена «жизненная сила» (целое число от -1 до 65535), при утере которой со слотом ничего больше сделать нельзя, кроме как «воскресить» его. Есть фиксированный набор действий, называемых «картами» (типа карт в MtG), которые можно осуществлять с живыми слотами, причём двояко: либо функцию с карты применять к слоту, либо со слота к карте (в случае невозможности такого применения вылезает еггог и дуэль заканчивается). Результат применения функции (это может быть число или другая функция) перезаписывается обратно в слот.
Дуэлянты ходят по очереди. «Ходить» можно следующими «картами»:
1) zero - константа 0 (её можно записать в любой свой слот);
2) succ - увеличивает числовое значение в слоте на 1;
3) dbl - удваивает числовое значение в слоте. Если результат больше 65535, записывается 65535;
4) get - что-то вроде косвенной адресации. Если в слоте лежит число 0-255, мы ищем слот с этим номером и записываем его содержимое в исходный слот.
5) put - записывает в указанный слот identity function;
6-8) S,K,I - комбинаторы из SKI calculus. Да, это там где Unlambda. Что, страшно? Вот и нам было страшно. Но зато они позволяют строить в слотах вполне себе turing-complete функции из этих базовых блоков - с ветвлениями, циклами и рекурсией. Не без извращений, конечно;
9) attack - функция трёх аргументов (каррированная, разумеется) i, j, n, уменьшает жизненную силу в своём i-том слоте на n, а у противника, в (255-j)-том слоте - на 9/10n. То есть себе она наносит больше вреда, чем противнику - зато если слот «убит», то он выбывает из игры;
10) help - аналогичная функция трёх аргументов. Уменьшает жизненную силу в своём i-том слоте на n, и увеличивает её в своём же j-том слоте на 11/10n.
11) copy - тырит содержимое некоторого слота оппонента (адресованного числом в своём слоте) к себе.
12) revive - вносит оживляж. Если свой (косвенно адресуемый, как всегда) слот мёртв, т.е. его жизненная сила меньше или равна нулю - устанавливает её в 1, и перезаписывает его содержимое identity function.
13) zombie - вот это жесть. Каррированная функция о двух аргументах (i и x), которая записывает в (255-i)-тый слот противника то, что есть x (обычно это какая-то функция), и, чтобы жизнь мёдом не казалась, заодно убивает собственный слот и записывает туда identity function.
В начале каждого хода функции во всех мёртвых слотах применяются автоматически по порядку, при этом их семантика меняется: inc уменьшает, dec увеличивает, attack лечит, help уменьшает жизненную силу. Бааальшая подлянка для противника, если уж удалось засадить ему зомби. Только нужно его ещё сконструировать.
Цель дуэли, понятно - убить все слоты противника (или хотя бы больше, чем он). Очевидно, что с таким богатым набором средств можно составить туеву хучу стратегий для достижения задачи. Это если разобраться со SKI-исчислением, конструированием функций, комбинаторами, и прочей анлямбдой. Практически никто из нас такими извращениями не занимался, поэтому заметную часть времени участники торчали в википедии, лихорадочно накачивая себя новыми знаниями.
Ознакомившись с заданием (и википедией) и изрядно от всего охренев, участники легли спать, чтобы наутро ринуться в бой.
Это была мощнейшая подсказка. К сожалению, мало кто предположил, что подсказка будет настолько явной. _adept_ даже высказал мнение, что это очередная мистификация, наподобие тех, что были в 2006 году. (Блджад! Сколько раз уже его команда прокалывалась на том, что подсказки - это подсказки, а не мистификации! 2006 год был один раз!) Тем не менее, мы правильно рассудили, что, наверное, придётся играть в какой-то аналог Magic: The Gathering с лямбдами и аспирантками ВМК (if any). Зато никто не обратил внимание на нарисованный на второй карте расходящийся омега-комбинатор. А зря - эта проблема не преминула всплыть ближе к середине контеста.
Итак, опубликовали задание. Контест проводится в виде серии дуэлей между программами, написанными участниками. У каждой программы есть в распоряжении 256 слотов, каждый из которых может содержать число или функцию. Каждому слоту также сопоставлена «жизненная сила» (целое число от -1 до 65535), при утере которой со слотом ничего больше сделать нельзя, кроме как «воскресить» его. Есть фиксированный набор действий, называемых «картами» (типа карт в MtG), которые можно осуществлять с живыми слотами, причём двояко: либо функцию с карты применять к слоту, либо со слота к карте (в случае невозможности такого применения вылезает еггог и дуэль заканчивается). Результат применения функции (это может быть число или другая функция) перезаписывается обратно в слот.
Дуэлянты ходят по очереди. «Ходить» можно следующими «картами»:
1) zero - константа 0 (её можно записать в любой свой слот);
2) succ - увеличивает числовое значение в слоте на 1;
3) dbl - удваивает числовое значение в слоте. Если результат больше 65535, записывается 65535;
4) get - что-то вроде косвенной адресации. Если в слоте лежит число 0-255, мы ищем слот с этим номером и записываем его содержимое в исходный слот.
5) put - записывает в указанный слот identity function;
6-8) S,K,I - комбинаторы из SKI calculus. Да, это там где Unlambda. Что, страшно? Вот и нам было страшно. Но зато они позволяют строить в слотах вполне себе turing-complete функции из этих базовых блоков - с ветвлениями, циклами и рекурсией. Не без извращений, конечно;
9) attack - функция трёх аргументов (каррированная, разумеется) i, j, n, уменьшает жизненную силу в своём i-том слоте на n, а у противника, в (255-j)-том слоте - на 9/10n. То есть себе она наносит больше вреда, чем противнику - зато если слот «убит», то он выбывает из игры;
10) help - аналогичная функция трёх аргументов. Уменьшает жизненную силу в своём i-том слоте на n, и увеличивает её в своём же j-том слоте на 11/10n.
11) copy - тырит содержимое некоторого слота оппонента (адресованного числом в своём слоте) к себе.
12) revive - вносит оживляж. Если свой (косвенно адресуемый, как всегда) слот мёртв, т.е. его жизненная сила меньше или равна нулю - устанавливает её в 1, и перезаписывает его содержимое identity function.
13) zombie - вот это жесть. Каррированная функция о двух аргументах (i и x), которая записывает в (255-i)-тый слот противника то, что есть x (обычно это какая-то функция), и, чтобы жизнь мёдом не казалась, заодно убивает собственный слот и записывает туда identity function.
В начале каждого хода функции во всех мёртвых слотах применяются автоматически по порядку, при этом их семантика меняется: inc уменьшает, dec увеличивает, attack лечит, help уменьшает жизненную силу. Бааальшая подлянка для противника, если уж удалось засадить ему зомби. Только нужно его ещё сконструировать.
Цель дуэли, понятно - убить все слоты противника (или хотя бы больше, чем он). Очевидно, что с таким богатым набором средств можно составить туеву хучу стратегий для достижения задачи. Это если разобраться со SKI-исчислением, конструированием функций, комбинаторами, и прочей анлямбдой. Практически никто из нас такими извращениями не занимался, поэтому заметную часть времени участники торчали в википедии, лихорадочно накачивая себя новыми знаниями.
Ознакомившись с заданием (и википедией) и изрядно от всего охренев, участники легли спать, чтобы наутро ринуться в бой.