ICFPC 2011 - новый виток
Для многих людей новый виток жизни начинается с Нового Года. Для кого-то, может быть, с Рождества. Кому-то собственный день рождения служит таким счетчиком.
У меня все по-другому. Главное событие года - международный конкурс ICFP Programming Contest.
Каковое и состоялось с 17 по 20 июня.
Сразу скажу, что положительные эмоции переполняют через край) Сравнивая нынешний контест с прошлогодними, многие мои знакомые отмечают прекрасно продуманное увлекательное задание, почти полное отсутствие всякого рода неприятных неожиданностей, таких как внезапное падение сервера, изменение спецификаций задачи из-за обнаруженных ошибок, или притянутую за уши проблему, о которой все забудут через пару дней, как страшный сон.
Нас ждало примерно следующее:
О технических подробностях "для посвященных" очень подробно рассказал sannysanoff в нашем блоге http://thirteen.kharkov.ru/2011/06/20/icfp-contest-2011-otchet-writeup-san
Итак, попытаюсь изложить задачу простым человеческим языком.
Грядет битва сил Света и Тьмы. С обеих сторон вышли две армии и выстроились "стенка на стенку". В каждой армии по 256 искусных магов. Казалось бы, силы равны! Кто же победит?
В мире магии есть свои законы, не менее строгие и незыблемые, чем законы всемирного тяготения или сохранения энергии.
У каждого из магов есть важные характеристики - жизненная сила (изначально она у всех одинакова, и равна 10000 единиц, и не может превышать 65535), и мана - способность творить заклинания. Перед каждым ходом мана восстанавливается до 1000 единиц.
Заклинания бывают как простейшие, так и очень сложные, состоящие из многих подготовительных этапов и включающие в себя совместные силы нескольких магов. Маги "ходят" по очереди - один из светлых, затем один из темных, и снова, и снова... Высшие силы строго следят за порядком, ибо ставки в этой битве высоки!
Теперь мы подобрались к самому главному - к собственно магии. В те далекие времена, когда вселенная только возникала, и даже само понятие "время" имело мало смысла, Тот, Кто Создал Все, соткал из самой ткани мироздания Карты, числом 15. Когда пришло время, Он явил их мудрейшим представителям рода человеческого.
Каждая Карта может по-своему управлять силами Вселенной. А если маг соберет несколько карт в нужном порядке,- мощь его будет воистину устрашающей!
Никто не помнит, как выглядели изначальные Карты - века изменили язык человека, равно как и язык магов. Мы знаем лишь, что их смысл сохранен в точности и изложен на вышеприведенном рисунке в виде сухой математики.
Итак, попробуем разобраться, как можно с минимальными затратами разгромить противника. Есть одна карта, которая при определенных условиях может за один ход уничтожить сразу двоих вражеских магов. Это карта help. А условия таковы. Заклинание help должны исполнять не мы сами, а созданный нами фантом, управляющий одним из поверженных чародеев неприятеля, или, иначе говоря, зомби. Как зомбировать врага - это отдельная задача, которую мы чуть позднее рассмотрим.
Представим себе следующую функцию на псевдо-C:
DoubleSuicide(n)
{
help(n, (n+1), 10000);
DoubleSuicide(n+2);
}
Если n - это порядковый номер вражеского мага, то help отнимет 10000 здоровья у него, 11000 здоровья у его соседа, после чего указанная последовательность применится к следующей паре врагов, и опять, и опять. Если предположить, что жизненной силы у всех по 10000, то эти действия будут последовательно уничтожать всех магов противника (по крайней мере, пока не закончатся 1000 единиц маны).
Попробуем теперь построить такую конструкцию в терминах наших Карт.
Для начала нам понадобится сформировать help n (n+1) 10000. Мы хотим, чтобы n была переменной, поэтому нам придется ее передать внутрь функции, причем передать дважды - один раз непосредственно, и еще раз - с инкрементом. К счастью, у нас есть подходящий инструмент - это карта S. Запись S help succ n раскроется как раз в:
help n (succ n), или help n (n+1).
Теперь что касается константы 10000. Мы не можем записать ее непосредственно, так как help-конструкция тут же сработает, а у нас есть причины отложить срабатывание до самого последнего момента, когда все сопутствующие заклинания тоже будут готовы. Для такой "задержки" прекрасно подходит карта K, которой можно скормить произвольный второй параметр, при этом она вернет свой первый параметр (который в нашем случае и будет числом 10000). Итак, у нас получается следующее:
S help succ n
K 10000 x
Поскольку для x выбор произвольный, мы можем использовать и в этой строке ту же переменную n:
S help succ n
K 10000 n
Следующий шаг очевиден (мы такое уже проделывали) - обрамить две вышеприведенные строчки картой S, вынеся n "за скобки":
S (S help succ) (K 10000) n
Итак, первая часть функции DoubleSuicide сформирована. Нам остается лишь вызвать самих себя еще раз с новым аргументом (n+2). Звучит страшно? На самом деле ничего "военного" здесь нет - мы ведь можем заранее подготовить тело функции DoubleSuicide и хранить его у одного из наших магов, а в нужный момент взять и скормить телу функции нужный нам параметр (n+2). А как взять-то, ведь все, о чем мы говорили выше, происходит не у нас, а в стане врага, где хозяйничает наш фантом-зомби? И на этот случай имеется соответствующая Карта - copy! Пусть наш маг-хранитель имеет номер m, тогда команда copy m, выполненная на стороне врага, сделает всю нужную работу. Не забываем, что исполнение copy m надо отложить, чтобы оно сработало сразу после help. Мы уже умеем пользоваться для этого Картой K:
(K copy) (K m)
А чтобы эти выражения в нужный момент раскрыть, передадим каждой карте K произвольный параметр x, проще всего вот так:
S (K copy) (K m) x
Нам остается только передать аргумент (n+2), а для этого не обойтись без двух succ.
Можно было бы завернуть их в нечто вроде такого:
S (S (K succ) (K succ)) I n ,
но это слишком накладно по количеству необходимых карт. Гораздо изящнее будет применить succ последовательно. Пусть x (несколькими строчками выше) будет равно n+1 (почему бы и нет):
S (K copy) (K m) (n+1)
succ (n+1)
Выносим (n+1) "за скобки":
S (S (K copy) (K m)) succ (n+1)
Чтобы можно было записать финальное succ n, естественно будет обернуть вышеприведенную строчку Картой K:
K (S (S (K copy) (K m)) succ) n
succ n
И, наконец:
S (K (S (S (K copy) (K m)) succ)) succ n
Итак, обе строки DoubleSuicide записаны, и обе принимают своим аргументом n. Мы уже знаем, что делать дальше :)
S (S help succ) (K 10000) n
S (K (S (S (K copy) (K m)) succ)) succ n
равносильно
S
(S (S help succ) (K 10000))
(S (K (S (S (K copy) (K m)) succ)) succ)
n
Итак, мы вплотную подошли к моменту запуска нашей зомби-программы. По Правилам, перед каждым "сознательным" ходом армии высшие силы проверяют, нет ли среди павших магов тех, кто получил проклятие Зомби. Если таковые найдены, то заклинание, которое им навязал противник, тут же будет исполнено с параметром I (Identity). Чтобы наша конструкция DoubleSuicide при этом сработала и получила на вход n, достаточно обернуть ее в:
S (K (DoubleSuicide)) (K n) I
Таким образом, полное тело зомби выглядит так:
S (K (S (S (S help succ) (K 10000)) (S (K (S (S (K copy) (K m)) succ)) succ)))
причем мы должны передать сюда параметром (K n), а Identity придет автоматически.
Теперь рассмотрим саму процедуру "зомбирования". Синтаксис Карты zombie таков: zombie i ZombieBody, где i - порядковый номер мага-жертвы. В качестве i проще всего взять 0, нулем же стартовать все наше накопленное мегазаклятие, и у нулевого собственного мага хранить число n, которое нам требуется (см. выше). Для извлечения n воспользуемся Картой get
имеем:
zombie 0 (ZombieBody (K n)). Оборачиваем ZombieBody и "выносим" n:
zombie 0 (
(K(ZombieBody) n)
(K n)
)
zombie 0 (
S (K(ZombieBody)) K n
)
Наконец, заменим n на get 0:
zombie 0 (
K (S (K (ZombieBody)) K) 0
get 0
)
и вынесем 0 "за скобки":
zombie 0 (
S (K (S (K (ZombieBody)) K)) get 0
)
и еще раз вынесем 0:
S zombie (S (K (S (K (ZombieBody)) K)) get) 0
Подставив сюда ZombieBody, получим в окончательном виде нашу функцию, которая будет зомбировать вражеского мага (нулевого в нашей системе отсчета, или 255-го с точки зрения врага) некоей функцией-проклятием, которое накроет, словно эпидемия, целую толпу вражеских магов, начиная с номера n (который хранится у нашего нулевого мага):
S zombie (S (K (S (K (S (K (S (S (S help succ) (K 10000)) (S (K (S (S (K copy) (K m)) succ)) succ))))) K)) get)
(запускается Картой zero)
(Продолжение следует)
У меня все по-другому. Главное событие года - международный конкурс ICFP Programming Contest.
Каковое и состоялось с 17 по 20 июня.
Сразу скажу, что положительные эмоции переполняют через край) Сравнивая нынешний контест с прошлогодними, многие мои знакомые отмечают прекрасно продуманное увлекательное задание, почти полное отсутствие всякого рода неприятных неожиданностей, таких как внезапное падение сервера, изменение спецификаций задачи из-за обнаруженных ошибок, или притянутую за уши проблему, о которой все забудут через пару дней, как страшный сон.
Нас ждало примерно следующее:
О технических подробностях "для посвященных" очень подробно рассказал sannysanoff в нашем блоге http://thirteen.kharkov.ru/2011/06/20/icfp-contest-2011-otchet-writeup-san
Итак, попытаюсь изложить задачу простым человеческим языком.
Грядет битва сил Света и Тьмы. С обеих сторон вышли две армии и выстроились "стенка на стенку". В каждой армии по 256 искусных магов. Казалось бы, силы равны! Кто же победит?
В мире магии есть свои законы, не менее строгие и незыблемые, чем законы всемирного тяготения или сохранения энергии.
У каждого из магов есть важные характеристики - жизненная сила (изначально она у всех одинакова, и равна 10000 единиц, и не может превышать 65535), и мана - способность творить заклинания. Перед каждым ходом мана восстанавливается до 1000 единиц.
Заклинания бывают как простейшие, так и очень сложные, состоящие из многих подготовительных этапов и включающие в себя совместные силы нескольких магов. Маги "ходят" по очереди - один из светлых, затем один из темных, и снова, и снова... Высшие силы строго следят за порядком, ибо ставки в этой битве высоки!
Теперь мы подобрались к самому главному - к собственно магии. В те далекие времена, когда вселенная только возникала, и даже само понятие "время" имело мало смысла, Тот, Кто Создал Все, соткал из самой ткани мироздания Карты, числом 15. Когда пришло время, Он явил их мудрейшим представителям рода человеческого.
Каждая Карта может по-своему управлять силами Вселенной. А если маг соберет несколько карт в нужном порядке,- мощь его будет воистину устрашающей!
Никто не помнит, как выглядели изначальные Карты - века изменили язык человека, равно как и язык магов. Мы знаем лишь, что их смысл сохранен в точности и изложен на вышеприведенном рисунке в виде сухой математики.
Итак, попробуем разобраться, как можно с минимальными затратами разгромить противника. Есть одна карта, которая при определенных условиях может за один ход уничтожить сразу двоих вражеских магов. Это карта help. А условия таковы. Заклинание help должны исполнять не мы сами, а созданный нами фантом, управляющий одним из поверженных чародеев неприятеля, или, иначе говоря, зомби. Как зомбировать врага - это отдельная задача, которую мы чуть позднее рассмотрим.
Представим себе следующую функцию на псевдо-C:
DoubleSuicide(n)
{
help(n, (n+1), 10000);
DoubleSuicide(n+2);
}
Если n - это порядковый номер вражеского мага, то help отнимет 10000 здоровья у него, 11000 здоровья у его соседа, после чего указанная последовательность применится к следующей паре врагов, и опять, и опять. Если предположить, что жизненной силы у всех по 10000, то эти действия будут последовательно уничтожать всех магов противника (по крайней мере, пока не закончатся 1000 единиц маны).
Попробуем теперь построить такую конструкцию в терминах наших Карт.
Для начала нам понадобится сформировать help n (n+1) 10000. Мы хотим, чтобы n была переменной, поэтому нам придется ее передать внутрь функции, причем передать дважды - один раз непосредственно, и еще раз - с инкрементом. К счастью, у нас есть подходящий инструмент - это карта S. Запись S help succ n раскроется как раз в:
help n (succ n), или help n (n+1).
Теперь что касается константы 10000. Мы не можем записать ее непосредственно, так как help-конструкция тут же сработает, а у нас есть причины отложить срабатывание до самого последнего момента, когда все сопутствующие заклинания тоже будут готовы. Для такой "задержки" прекрасно подходит карта K, которой можно скормить произвольный второй параметр, при этом она вернет свой первый параметр (который в нашем случае и будет числом 10000). Итак, у нас получается следующее:
S help succ n
K 10000 x
Поскольку для x выбор произвольный, мы можем использовать и в этой строке ту же переменную n:
S help succ n
K 10000 n
Следующий шаг очевиден (мы такое уже проделывали) - обрамить две вышеприведенные строчки картой S, вынеся n "за скобки":
S (S help succ) (K 10000) n
Итак, первая часть функции DoubleSuicide сформирована. Нам остается лишь вызвать самих себя еще раз с новым аргументом (n+2). Звучит страшно? На самом деле ничего "военного" здесь нет - мы ведь можем заранее подготовить тело функции DoubleSuicide и хранить его у одного из наших магов, а в нужный момент взять и скормить телу функции нужный нам параметр (n+2). А как взять-то, ведь все, о чем мы говорили выше, происходит не у нас, а в стане врага, где хозяйничает наш фантом-зомби? И на этот случай имеется соответствующая Карта - copy! Пусть наш маг-хранитель имеет номер m, тогда команда copy m, выполненная на стороне врага, сделает всю нужную работу. Не забываем, что исполнение copy m надо отложить, чтобы оно сработало сразу после help. Мы уже умеем пользоваться для этого Картой K:
(K copy) (K m)
А чтобы эти выражения в нужный момент раскрыть, передадим каждой карте K произвольный параметр x, проще всего вот так:
S (K copy) (K m) x
Нам остается только передать аргумент (n+2), а для этого не обойтись без двух succ.
Можно было бы завернуть их в нечто вроде такого:
S (S (K succ) (K succ)) I n ,
но это слишком накладно по количеству необходимых карт. Гораздо изящнее будет применить succ последовательно. Пусть x (несколькими строчками выше) будет равно n+1 (почему бы и нет):
S (K copy) (K m) (n+1)
succ (n+1)
Выносим (n+1) "за скобки":
S (S (K copy) (K m)) succ (n+1)
Чтобы можно было записать финальное succ n, естественно будет обернуть вышеприведенную строчку Картой K:
K (S (S (K copy) (K m)) succ) n
succ n
И, наконец:
S (K (S (S (K copy) (K m)) succ)) succ n
Итак, обе строки DoubleSuicide записаны, и обе принимают своим аргументом n. Мы уже знаем, что делать дальше :)
S (S help succ) (K 10000) n
S (K (S (S (K copy) (K m)) succ)) succ n
равносильно
S
(S (S help succ) (K 10000))
(S (K (S (S (K copy) (K m)) succ)) succ)
n
Итак, мы вплотную подошли к моменту запуска нашей зомби-программы. По Правилам, перед каждым "сознательным" ходом армии высшие силы проверяют, нет ли среди павших магов тех, кто получил проклятие Зомби. Если таковые найдены, то заклинание, которое им навязал противник, тут же будет исполнено с параметром I (Identity). Чтобы наша конструкция DoubleSuicide при этом сработала и получила на вход n, достаточно обернуть ее в:
S (K (DoubleSuicide)) (K n) I
Таким образом, полное тело зомби выглядит так:
S (K (S (S (S help succ) (K 10000)) (S (K (S (S (K copy) (K m)) succ)) succ)))
причем мы должны передать сюда параметром (K n), а Identity придет автоматически.
Теперь рассмотрим саму процедуру "зомбирования". Синтаксис Карты zombie таков: zombie i ZombieBody, где i - порядковый номер мага-жертвы. В качестве i проще всего взять 0, нулем же стартовать все наше накопленное мегазаклятие, и у нулевого собственного мага хранить число n, которое нам требуется (см. выше). Для извлечения n воспользуемся Картой get
имеем:
zombie 0 (ZombieBody (K n)). Оборачиваем ZombieBody и "выносим" n:
zombie 0 (
(K(ZombieBody) n)
(K n)
)
zombie 0 (
S (K(ZombieBody)) K n
)
Наконец, заменим n на get 0:
zombie 0 (
K (S (K (ZombieBody)) K) 0
get 0
)
и вынесем 0 "за скобки":
zombie 0 (
S (K (S (K (ZombieBody)) K)) get 0
)
и еще раз вынесем 0:
S zombie (S (K (S (K (ZombieBody)) K)) get) 0
Подставив сюда ZombieBody, получим в окончательном виде нашу функцию, которая будет зомбировать вражеского мага (нулевого в нашей системе отсчета, или 255-го с точки зрения врага) некоей функцией-проклятием, которое накроет, словно эпидемия, целую толпу вражеских магов, начиная с номера n (который хранится у нашего нулевого мага):
S zombie (S (K (S (K (S (K (S (S (S help succ) (K 10000)) (S (K (S (S (K copy) (K m)) succ)) succ))))) K)) get)
(запускается Картой zero)
(Продолжение следует)