Игра в «кошки — мышки», поиск минимальной стратегии
Наступил 2013 год, и мы успешно провели первый в этом году конкурс по функциональному программированию под эгидой ФП(ФП). В 2013 году конкурсы стартуют всё так же традиционно на первой длинной неделе месяца, но уже не каждого, а один раз в два месяца. Так что в 2013 году запланировано проведение шести конкурсов по ФП: в феврале (который мы сегодня и опишем), в апреле, в июне, в августе, в октябре и в декабре.Задачу на февральский конкурс подготовил наш добрый коллега Александр Лебедев, за что ему низкий поклон, всяческие благодарности и занесение имени в Скрижали Славы ФП(ФП). Задача была из серии игр один-на-один, которую мы назвали «кошки — мышки»:
Есть ящик, состоящий из пяти ячеек, последовательно соединённых друг с другом, то есть у каждой ячейки ровно две соседние, кроме крайних, у которых по одной соседней (другими словами, ящик — это линия из пяти сегментов). В какой-то ячейке сидит мышь, и кошка не знает, в какой именно. Игра состоит из набора ходов до победы кошки. Один ход в игре описывается двумя полуходами:
- Кошка кладёт лапу на какую-то ячейку ящика. Если под лапой оказывается мышь, то игра окончена, и кошка победила.
- Если кошка не положила лапу на ячейку с мышью, то мышь перебегает в соседнюю ячейку (даже может перебежать в ту ячейку, на которую кошка клала лапу). В какую именно, кошка не знает.
Задача: написать программу, которая рассчитывает для кошки победную стратегию, и желательно содержащую наименьшее число ходов.
Если кому-то интересна реализация решения этой задачи на языке Haskell, то добро пожаловать под кат.
Ознакомиться с решением
