Конкурс POTM и его братья

В последнее время жизнь в "спортивном секторе" программирования бьет ключом: растет число участников прежних соревнований, а новые появляются как грибы после дождя. Что предпочесть на досуге алгоритмисту-любителю? Согласно мудрой присказке, "у каждого свой вкус"…

В последнее время жизнь в «спортивном секторе» программирования бьет ключом: растет число участников прежних соревнований, а новые появляются как грибы после дождя. Что предпочесть на досуге алгоритмисту-любителю? Согласно мудрой присказке, «у каждого свой вкус»…

В программировании, как и в спорте, есть свои «спринтеры», стремительно щелкающие типовые задачки-«хрящики» во время быстротечных командных «блицев», и «стайеры», предпочитающие неподъемные «арбузы», над которыми порой можно биться месяцами. Нетрудно заметить, что «спринтерские» соревнование даже в русскоязычной сети проводятся сейчас часто («законодателем мод» тут является всемирное командное студенческое первенство, проводимые под эгидой авторитетнейшей Ассоциации по вычислительной технике - Association for Computing Machinery). В последнее время о них немало пишут. Программистам-«стайерам» в этом смысле везет гораздо меньше. Однако нынче праздник на их улице: недавно стартовало новое состязание для любителей копаться в нетривиальных алгоритмах - «именной» конкурс братьев Уваровых по программированию (Uvarov Brothers Programming Contest, UBPC). И об этом событии стоит рассказать подробнее.

Так уж вышло, что в рождении нового конкурса оказалась замешана «Компьютерра», а точнее, опубликованная три года назад в «Кнопках» (см. «КТ» #246) статья о POTM («Programmer Of The Month») - конкурсе, проводимом американским энтузиастом программирования Фредом Хайсинботемом (Fred Hicinbothem) из компании AT&T. Как в свое время отметил Фред, эта заметка здорово обострила турнирную борьбу: не секрет, что «закрома Родины» на редкость богаты сильными программистами и математиками. В числе «новобранцев», замахнувшихся на престижный трофей, был и наш соотечественник, студент Павел Уваров, который в сентябре 1999 года в тандеме с опытным «POTM’ером», бельгийцем Фредериком ван дер Планке наконец-то добился своего: лучше всех программно «распилил» прямоугольную доску на куски одинакового размера и стал победителем.

К сожалению, в последние годы легендарный POTM несколько сдал: свежие задания стали появляться нерегулярно (так что конкурс из «программиста месяца» впору было переименовать в «квартального программиста»). А где-то с полгода назад отец-основатель турнира вообще отправил свое детище в бессрочный отпуск. Впрочем, жива и здравствует домашняя страничка конкурса - уникальная библиотека, хранящая «правила игры» и имена победителей всех 26 соревнований, а также листинги присланных со всех концов света программ-участниц и письма соискателей, снабженные ироничными и проницательными комментариями самого Фреда.

Так что же - POTM умер? Нет, скорее, да здравствует UBPC! Ибо свято место пусто не бывает: подхватив эстафетную палочку легендарного турнира, экс-чемпион POTM’а Павел Уваров на пару со своим братом Андреем основал новый, «семейный» конкурс. Воспользовавшись правом участника турнира «тормошить» его организаторов по различным оргвопросам, я связался с Павлом по электронной почте, результатом чего стало это своеобразное блиц-интервью.

- Хоть мы и придерживаемся многих традиций POTM, наш конкурс не задумывался как его замена или продолжение. Мы планировали создать некоторую альтернативу POTM, взяв за основу многие из замечательных идей этого конкурса и добавив свои. Но получилось так, что, узнав о нас, Фред разослал письма всем бывшим участникам его конкурса и повесил на своей страничке ссылку на наш сайт, назвав ее «The New POTM Site».

- При разработке первого задания мы руководствовались тем, что оно должно быть понятным, интересным и не слишком сложным. Было приятным сюрпризом, что о нас (благодаря Фреду) сразу узнало так много людей и что лучшие программисты со всего мира (в том числе победители различных POTM’ов) прислали нам свои программы. Я мечтаю о том, чтобы выиграть в конкурсе мог только высококлассный программист.

- «POTM Trophy» продолжает пребывать в ведении Фреда, и, вероятно, стоит сейчас в квартире у последнего победителя. Большим недостатком этого приза является то, что его могут забрать к себе домой только жители Америки (и это понятно, так как изначально POTM не выходил даже за пределы AT&T). Если мы попытаемся организовать что-нибудь подобное у себя, то наверняка столкнемся с теми же проблемами и тем самым дискриминируем всех, кто живет не в России. Материальные призы (например, деньги) мы давать пока не можем - за неимением материальной базы. Но эта проблема, возможно, со временем будет решена (Ау! Где вы, меценаты образования? - Д.К.). От себя хочу сказать, что лично для меня было важно не столько завоевать какой-нибудь приз, сколько увековечить свое имя в списке победителей.

- Обязанности между нами распределяются по принципу: кто что лучше знает, тот то и делает. Я, как участник нескольких POTM’ов и заядлый «юниксоид», взял на себя то, чем занимается Фред: составление и перевод заданий на русский язык и последующее компилирование программ. Андрей, как вебмастер, взял на себя разработку и поддержку сайта, общей линии дизайна и т. д. Нам никто не помогает - все держится на наших четырех плечах.

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

Единственной возможностью влиять на траекторию движения «машинки» является контроль за ускорением: скорость может оставаться постоянной, а также увеличиваться или уменьшаться на единицу за один ход (то есть «средство передвижения» разгоняется или тормозит). Целью игрока является как можно более точное попадание «машинки» в конечную клетку при заданном лимите ходов. Следует также учесть, что трасса может быть усеяна стенами, встреча с каждой из которых (попадание в одну «забетонированную» клетку или соприкосновение с ней при «проезде») может оказаться для «шофера» роковой. Так что алгоритм под кодовым названием «газуй!», применимый в условиях степи, может привести к летальному исходу на замысловатой трассе «Формулы 1».

На рисунке показана внесенная в «протокол соревнований» карта путешествия машинки из начального пункта (1,8) в конечный (1,4) за 16 ходов. Примечательно, что во время путешествия она едва не поцарапала левый борт о верхнюю горизонтальную стену, но благодаря осторожности «водителя», своевременно сделавшего поворот, финишировала точно у финального флажка. Такой результат был достигнут благодаря следующей последовательности ускорений: (1;1) - (1;-1) - (1,0) - (-1,0) - (0;-1) - (0;0) - (-1;-1) - (-1;1) - (-1;-1) - (-1;1) - (-1;1) - (1;0) - (1;0) - (-1;1) - (1;0) - (0;0). Вывод подобной цепочки и должен быть результатом работы программы-участницы конкурса.

Как подчеркивают сами организаторы, «игра в машинки» является лишь «пробным камнем» турнира. Дальше пойдут другие, не менее (а скорее, более) сложные задания.Подробнее со всеми тонкостями «правил дорожного движения» можно ознакомиться на официальном сайте UBPC. Напоследок хочу пожелать участникам (коих на текущий момент зарегистрировалось уже две сотни с гаком!) успешных стартов, а самому турниру - долгой и счастливой судьбы. И пусть после первой «финальной отмашки» (а состоится она в начале августа) последуют новые, не менее интересные старты.

[i40258]