Конкурс "Программист месяца": сезон гастролей открыт!

Тем, кто познал изящность и красоту программистских головоломок, "научив" компьютер решать хоть одну хитрую задачу, можно позавидовать - немногим дано испытать то состояние, близкое к нирване, которое охватывает творца программы в момент, когда его детище благополучно проходит каверзные тесты. Но гораздо логичнее было бы пожалеть этих людей. Ибо миг торжества недолог - и творческий зуд опять толкает на поиски новых задач. Воистину нет покоя вставшему на эту стезю. Пока одни ищут задачи на книжных полках и в глубинах Сети, другие в то же самое время выставляют их на своих страницах и проводят самые разнообразные конкурсы. И как приятно порой бывает наткнуться на такой "оазис" в сетевой пустыне, где тебя приветливо встретят и любезно "озадачат" прямо с порога. Об одном из таких уголков, постоянно живущем сетевом конкурсе "Программист месяца" (Programmer Of The Month - POTM), и пойдет далее речь. А обнаружил я его по адресу www.cs.washington.edu/homes/corin/POTM.PAGES/.

"Зубры" программирования, вероятно, оценят разместившийся на этом сервере богатый архив с условиями задач прошлых первенств. Первоначально они проводились в недрах компании AT&T, но со временем доросли до планетарных масштабов. За пять лет участникам было предложено два с лишним десятка самых разнообразных задач. Некоторые из них за это время стали классическими и пополнили всевозможные сетевые архивы. С какими только проблемами не приходилось сталкиваться завсегдатаям конкурса! Это и программирование логических игр с несколькими участниками (бои обычно велись по олимпийской системе с выбыванием, все захватывающие результаты финальных поединков доступны здесь же, на сервере), и решение математических головоломок (в том числе знаменитой игры в "пятнадцать", а также криптарифмов, так хорошо знакомых постоянным читателям "КТ"). Особого внимания заслуживают и "тяни-толкаи" - гибриды нескольких хорошо известных задач - например, задачи обхода доски шахматным конем с "задачей коммерсанта", предложенной в POTM три года назад. Нужно признать, что за время проведения первенства уровень задач постепенно возрастал, так что будущим призерам, вероятно, придется изрядно попотеть. Зато слава обеспечена: помимо получения титула POTM и чести лицезреть свою фамилию в "галерее славы", триумфатор награждается также переходящим призом - роскошной "доской почета" от генерального спонсора - компании AT&T (см. рис. 1), на которой отныне гордо значится и его собственное имя. Правда, заморским (неамериканским) победителям, похоже, придется довольствоваться лишь ee живописным изображением в формате GIF…

_В качестве решений принимаются исходные коды программ на C/С++, Java, а также таких экзотических для российских программистов языках, как, например, Perl и Python. Тексты на Pascal и Fortran в принципе принимаются тоже, но перед компиляцией транслируются на C, что заранее дает фору "сишникам" и "джавистам".

"И почему я связался с этими вещами? - недоумевает про себя Фред Хайсинбозем (Fred Hicinbothem) - основатель и бессменный ведущий конкурса. И тут же отвечает на свой вопрос. - Очевидно, по той же самой причине, по которой вы участвуете в них, - это весело!" И его мнение разделяют около двух тысяч человек по всему свету, регулярно получающих по e-mail донесения о ходе очередного первенства. Чтобы попасть в список рассылки POTM, достаточно послать письмецо с соответствующей просьбой по адресу fah@potm.ffast.att.com. И тогда уж, будьте уверены, известие о новом конкурсе вас не минует. Если же вы настроены куда как более решительно и хотите непосредственно быть в курсе всех основных событий последнего тура, пошлите письмо по этому же адресу, набрав в качестве Subj слово "Enter".

Интересно, что в качестве второй причины своего начинания лукавый "отец-основатель" называет ни больше ни меньше как производственную необходимость: часть конкурсных заданий представляют собой самые настоящие злободневные задачи, с которыми он, ведущий программист компании AT&T с двадцатипятилетним стажем, неоднократно встречался в своей практике. Добавим к этому, что некоторые из них до сих пор, возможно, не имеют эффективного решения. С другой стороны, чем черт не шутит? Может быть, кто-то из читающих эту заметку возьмет и напишет программу, которая затмит все, когда-либо присланные на этот конкурс… Тем более что фамилий российских программистов в "галерее славы" пока что-то не наблюдается.

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

Итак, задача нынешнего, весенне-летнего первенства, достаточно нетривиальная при внешне традиционном условии, носит название "Scenic Tour", что на русский переводится как "Гастроли" (хотя, по-моему, тут больше бы подошло толкиеновское "Туда и обратно"). Суть ее сводится к нахождению оптимального циклического пути внутри квадратной сетки размером SIZEхSIZE клеток (при этом SIZE не превосходит 256), который задается последовательностью координат клеток, через которые он пролегает. Путь должен начинаться и заканчиваться в левой верхней клетке с координатами (0,0), при этом он обязательно должен включать правую нижнюю клетку с координатами (SIZE-1, SIZE-1), которая делит его на два участка - прямой и обратный. При этом из каждой клетки за один ход можно переместиться в ее "соседку" (имеющую с ней общую сторону или вершину). В каждой клетке вписано натуральное число от 0 до 255, выражающее ее "высоту". Расстояние между двумя соседними клетками определяется как модуль разности их "высот" (иначе говоря, на сколько нужно "подняться" или "опуститься", чтобы попасть в соседнюю клетку). Таким образом, длина пути между любыми двумя клетками находится как сумма расстояний между соседними клетками на каждом шаге, входящем в этот путь.

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

1. Ни одна клетка, кроме начальной, не может посещаться дважды, хотя путь может петлять и самопересекаться как угодно; выходить за границы сетки при этом категорически запрещается!
2. Отношение длин частичных путей "обратно" и "туда" должно быть максимальным; то есть выигрывает программа, нашедшая путь с максимальным значением показателя LONG_SCORE/SHORT_SCORE, где SHORT_SCORE - длина "обратного" пути между клетками (SIZE-1,SIZE-1) и (0,0), а LONG_SCORE - длина "прямого" пути между (0,0) и (SIZE-1,SIZE-1). При этом во избежание деления на нуль по крайней мере у двух этих крайних клеток "высоты" различны.
3. Путь может состоять не более чем из LIMIT ходов; при этом LIMIT не менее 4хSIZE и не более 20хSIZE (что, в свою очередь, дает нам некоторую свободу для маневра по обходу "нежелательных" клеток). В качестве примера на рис. 2 приведен удовлетворяющий условиям путь для сетки 4х4, показатель которого равен 34/8=4,25.

Для всех программ, участвующих в конкурсе, действуют также ограничения на размер исходного кода - 25 Кбайт, исполнимого кода - 1 Мбайт, а также ограничение на объем используемой динамической памяти, которое можно назвать чисто символическим, - 50 Мбайт (!). Ограничено и время расчета каждого теста: не более десяти минут на "малютке" SPARCStation, используемой для финального тестирования, что, в общем-то, тоже немало. Здесь же, на сервере, можно скачать программу-таймер для оценки того, удается ли вашей программе "уложиться" в заданное время.

Заметим, что каждую неделю на сервере POTM публикуются сводки с места событий, где фиксируются все присланные решения и результаты, показанные программами на предварительных тестах. Впрочем, еще не вечер - официальные итоги будут подведены в полночь 26 июня, после того как все присланные программы "обкатают" на тройке контрольных тестов и победитель определится по сумме полученных значений критерия. Если же (о, чудо!) эти значения у нескольких участников все-таки совпадут, то в расчет будет браться время решения. Пока же у всех участников достаточно времени, чтобы "утяжелить" свои решения каким-нибудь новым, нетривиальным алгоритмическим ходом.

Напоследок мне остается лишь пожелать удачи всем потенциальным лауреатам. Успешных вам "гастролей", эффективных алгоритмов и остроумных решений!