Задача конкурса ICFPC-2012: робот и λ

[jerom]

Дописал, что задача NP-полна даже без усложнений.

[mechmind]

За собранную λ в момент достижения выхода +50

Это как?

[blueboar2]

Чтобы тот кто собрал 5 лямбд и вышел был круче чем тот кто собрал 5 лямбд и не вышел

[blueboar2]

За каждую собранную в процессе лямбду при полном выполнении задания

[janatem]

За собранную λ в момент выполнения команды A +25
За собранную λ в момент достижения выхода +50

Точнее сказать: «за каждую собранную ранее лямбду...».

[mariofag]

Ну вот, а сказку вы перевести поленились :(
В общем, прологом к задаче является история о том, что из-за возросшей популярности функциональных ЯП, многие языки начали перенимать различный функционал ФЯП, вроде лямбда-функций. Это привело к тому, что мировые запасы лямбд крайне быстро истощаются, и, по прогнозам аналитиков, закончатся уже к октябрю. Однако, организаторы обнаружили огромнейшие природные запасы лямбд в Lomond Hills в Шотландии и даже составили карты подземных шахт. Соответственно, ваша задача: спасти мир от лямбда-кризиса, запрограммировав робота.
Вот такое вот веселье.

[tagir_valeev]

Это ж Supaplex!

[Grammarnazi]

Кажется, я знаю кто победит.

[powder96]

Я думаю, что единственный «правильный» способ — это перебрать все возможные ходы, отсекая последовательности, не изменяющие никак ситуацию в игре или приводящие к проигрышному положению (например, когда на карте есть лямбды/открытые выходы, до которых нельзя добраться), и выбирая выигрышные решения с наименьшим числом ходов. Но это потребует ужасно много ресурсов, в то время, как имеется только 150сек.

Интересно было бы посмотреть программы победителей, когда конкурс закончится.

[burjui]

Эвристики тут нужны, а не полный перебор. А вообще, Стенфордский курс по AI вам в помощь.

[Sild]

Я только выход из лабиринта делал, волновой алгоритм тут не канает, да?=(

[bootch]

Почему не канает? Как способ найти лямбду — вполне.

[Kilew]

Если бы не камни можно было бы и его использовать — а так ;) То попадаешь в состояние «слишком много вершин» в следующей волне, то в состояние «почему там мало вершин» в следующей волне ;)