Наступил 2013 год, и мы успешно провели первый в этом году конкурс по функциональному программированию под эгидой ФП(ФП). В 2013 году конкурсы стартуют всё так же традиционно на первой длинной неделе месяца, но уже не каждого, а один раз в два месяца. Так что в 2013 году запланировано проведение шести конкурсов по ФП: в феврале (который мы сегодня и опишем), в апреле, в июне, в августе, в октябре и в декабре.
Задачу на февральский конкурс подготовил наш добрый коллега Александр Лебедев, за что ему низкий поклон, всяческие благодарности и занесение имени в Скрижали Славы ФП(ФП). Задача была из серии игр один-на-один, которую мы назвали «кошки — мышки»:
Есть ящик, состоящий из пяти ячеек, последовательно соединённых друг с другом, то есть у каждой ячейки ровно две соседние, кроме крайних, у которых по одной соседней (другими словами, ящик — это линия из пяти сегментов). В какой-то ячейке сидит мышь, и кошка не знает, в какой именно. Игра состоит из набора ходов до победы кошки. Один ход в игре описывается двумя полуходами:
- Кошка кладёт лапу на какую-то ячейку ящика. Если под лапой оказывается мышь, то игра окончена, и кошка победила.
- Если кошка не положила лапу на ячейку с мышью, то мышь перебегает в соседнюю ячейку (даже может перебежать в ту ячейку, на которую кошка клала лапу). В какую именно, кошка не знает.
Задача: написать программу, которая рассчитывает для кошки победную стратегию, и желательно содержащую наименьшее число ходов.
Если кому-то интересна реализация решения этой задачи на языке Haskell, то добро пожаловать под кат.
Решение
Для начала определим модуль:
> module MouseAndCat where
И импортируем дополнительные модули, которые потребуются в процессе написания программы:
> import Control.Monad
> import Control.Monad.State.Lazy
Самой важной функцией в этой задаче является функция для проверки решения, поскольку само решение ищется вообще тривиально (и это будет видно позже). Проверка решения в данном случае — это доказательство минимальности стратегии кошки.
Пусть поведение кошки описывается некоторой функцией behaviour :: Int -> [Int], которая возвращает список клеток, которые кошка должна накрывать лапой, чтобы поймать мышь. Как проверить, что это поведение правильное?
Поскольку кошке ничего неизвестно о местоположении мыши, то примем на вооружение вероятностный подход и будем брать в учёт все альтернативные положения мыши и её возможные ходы. Так для N = 4 имеем:
1) 1 1 1 1
2) 1 2 2 1
3) 2 3 3 2
4) 3 5 5 3
Здесь видно, что на втором ходе мышь могла прийти во вторую ячейку двумя способами (из первой и из третьей ячеек), а на четвёртом ходе в первую ячейку она могла придти тремя способами:
1. Выйти из второй клетки, пойти в первую, затем во вторую и обратно в первую:
[2,1,2,1].
2. [2,3,2,1].
3. [4,3,2,1].
Число способов попасть в ячейку с номером p на шаге (k + 1) определяется следующей функцией:
> ability :: Num a => a -> a -> a
> ability p k = ability (p - 1) (k - 1) +
> ability (p + 1) (k - 1)
Когда в процесс вмешивается кошка, то у мышки становится меньше альтернатив для ходов. Каждый раз, когда кошка кладёт лапу на ячейку p, мы должны записать в неё 0, что означает, что эта ячейка не даёт вклада в будущие альтернативы мыши.
Например если игра идёт на четырёх ячейках, и кошка ходит так: [2,2,3,3,2], то после пятго хода у мыши нет альтернатив:
Было: 1 1 1 1
Кошка положила лапу на 2: 1 0 1 1
Мышь сделала ход: 0 2 1 1
Кошка положила лапу на 2: 0 0 1 1
Мышь сделала ход: 0 1 1 1
Кошка положила лапу на 3: 0 1 0 1
Мышь сделала ход: 1 0 2 0
Кошка положила лапу на 3: 1 0 0 0
Мышь сделала ход: 0 1 0 0
Кошка положила лапу на 2: 0 0 0 0
На последнем ходе альтернативы у мыши иссякли, и кошка определённо поймала мышь.
Теперь немного о моделировании поведения мыши.
> next :: Num a => [a] -> [a]
> next ps = zipWith(+) (0:ps) (tail ps ++ [0])
Функция next считает альтернативы для ходов мыши без учёта поведения кошки.
> catImpact :: Num a => Int -> [a] -> [a]
> catImpact i ps = let (as, (_:bs)) = splitAt (i - 1) ps
> in as ++ (0:bs)
Функция catImpact ставит ноль на i-ую позицию в списке альтернатив ходов мыши.
Игра моделируется функцией play, которая принимает на вход количество клеток N и список ходов кошки.
> play :: Num a => Int -> [Int] -> [a]
> play n ps = execState m $ replicate n 1
> where
> m = forM_ ps $ i -> modify $ catImpact i . next
Ну и, наконец, функция testGame проверяет поведение кошки:
> testGame :: (Int -> [Int]) -> Int -> Bool
> testGame beh n = play n (beh n) == replicate n 0
Теперь можно привести функцию, которая вычисляет один из возможных минимальных
ответов к задаче:
> answer :: (Enum a, Num a) => a -> [a]
> answer n = [2..(n - 1)] ++ reverse [2..(n - 1)]
Все заинтересованные смогут взять описанный модуль для моделирования здесь. Впрочем, если скопировать текст статьи в файл с расширением
.lhs, сохранить его в кодировке UTF-8 (без BOM) и скормить компилятору языка Haskell, то всё будет хорошо, поскольку эта статья представляет собой модуль на языке Haskell в литературном стиле.
Дополнительная информация о конкурсах и ФП(ФП)
В 2013 году в работе Фонда Поддержки Функционального Программирования ФП(ФП) произошли определённые изменения, о которых необходимо сказать:
- Официальным блогом ФП(ФП) становится блог haskell98.blogspot.ru, с чем я всех и поздравляю.
- Как уже было сказано, конкурсы проводятся один раз в два месяца (по чётным месяцам года), объявление о старте конкурса производится в первую «длинную» неделю месяца, то есть такую неделю, которая содержит не менее 4-ёх дней нового месяца (1-ое число должно быть в четверг или ранее). Сам конкурс проводится в выходные в соответствии с установленным ранее регламентом.
- В течение 2013 года все конкурсанты будут получать баллы за своё участие. Подробно баллах и правилах их начисления написано здесь. Апелляции на тему «я буду участвовать, но баллы мне не начисляйте» не принимаются — правила едины для всех.
- Чуть позже придумаю ещё что-нибудь более интересное: звания, всякие ордена, ещё что-нибудь.
- В конце года по итогам зарабатывания баллов будет составлен список победителей, которые будут награждены чем-нибудь хорошим.
Всем удачи. Участвуйте в конкурсах, копите баллы и получайте призы. Кстати, ссылки на эту статью также принесут баллы.
Да, и ещё. Альманах-2012 находится в процессе компиляции. Скоро выйдет в свет, о чём будет сообщено дополнительно. Неравнодушных прошу ждать.
Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
- Конкурсы в 2011 году: Альманах конкурсов по ФП за 2011 год
- Расшифровка кода на языке Haskell (конкурс по ФП в январе 2012)
- Шахматные задачи на мат в один ход: решение на языке Haskell
- Измерение объёмов при помощи двух заданных сосудов: решение на языке Haskell
- Трансмутации слов друг в друга: решение на языке Haskell
- Решение арифметических задач — вероятностный подход против регулярных выражений
- Поиск кратчайшего расстояния между точками в трёхмерном пространстве
- Управление лифтами: решение на языке Haskell
- Решение логических задач на языке Haskell: в своём ли уме Валет?
- Поиск скрывающегося Доктора X среди пациентов — решение более сложных логических задач
- Шарики и дырки — один из вариантов плотной упаковки на языке Haskell
- Раскрашиваем карту при помощи языка Haskell
- Алгоритм A* и кубик Рубика: реализация на языке Haskell
Автор: Darkus
