Традиционный конкурс по функциональному программированию состоялся в июле. Судя по количеству участников, большинство апологетов программирования на этот раз убыли на отдых, либо не стали участвовать в конкурсе, экономя силы и готовясь к ICFPC, который в этом году состоялся через неделю после моего мероприятия. Тем не менее, в конкурсе на этот раз приняли участие девять человек, из которых семеро дали в той или иной степени правильные ответы. Распределение по языкам программирования: Haskell — 4 решения, из которых 2 некорректные; C++, Clean, F#, Java и Perl — по одному решению.
Задача на этот раз была из области автоматического управления. Конечно, она всё также сводилась к поиску на графе, для чего всяко можно использовать алгоритм A*. Тем не менее, большинство участников выбрали реализацию ad hoc, в том числе и победитель. Вот примерное условие:
На улице генерала Белова стоит четырнадцатиэтажный дом.
На первом этаже живет Митя. На втором — Петя, Тёма и Саша. На третьем — Витя, а на четвёртом — Маша и Паша. Кто живёт выше — никто не знает.
Митя и Витя собираются в гости к своему однокласснику Тёме. Паша позвонил Пете и попросил его вернуть конспект по ОБЖ. Сашина кошка снова улизнула из квартиры и наверняка греется у батареи на третьем этаже. Саша полон решимости вернуть её домой. Маша, тем временем, хочет сходить в магазин за новым велосипедным звонком.
В начальный момент времени лифт находится на первом этаже. Одновременно в лифте может находится не более двух человек, а пользоваться лестницей нельзя из-за ремонта. «Шагом» считается перемещение лифта между парой соседних этажей. В начале каждого шага ученики могут свободно перемещаться между лифтом и лестничной площадкой.
Необходимо было написать программу, которая составляет программу для лифта. Само собой разумеется, поощрялось обобщённое программирование, то есть создание изначально наиболее общей программы — под произвольное количество этажей и лифтов. Не все это восприняли, но тем не менее. Ну а далее в этой статье будет представлена авторская интерпретация решения этой задачи.
Читать полностью »
