- PVSM.RU - https://www.pvsm.ru -
Наступил 2013 год, и мы успешно провели первый в этом году конкурс по функциональному программированию под эгидой ФП(ФП). В 2013 году конкурсы стартуют всё так же традиционно на первой длинной неделе месяца, но уже не каждого, а один раз в два месяца. Так что в 2013 году запланировано проведение шести конкурсов по ФП: в феврале (который мы сегодня и опишем), в апреле, в июне, в августе, в октябре и в декабре.
Задачу на февральский конкурс [1] подготовил наш добрый коллега Александр Лебедев, за что ему низкий поклон, всяческие благодарности и занесение имени в Скрижали Славы ФП(ФП). Задача была из серии игр один-на-один, которую мы назвали «кошки — мышки»:
Есть ящик, состоящий из пяти ячеек, последовательно соединённых друг с другом, то есть у каждой ячейки ровно две соседние, кроме крайних, у которых по одной соседней (другими словами, ящик — это линия из пяти сегментов). В какой-то ячейке сидит мышь, и кошка не знает, в какой именно. Игра состоит из набора ходов до победы кошки. Один ход в игре описывается двумя полуходами:
- Кошка кладёт лапу на какую-то ячейку ящика. Если под лапой оказывается мышь, то игра окончена, и кошка победила.
- Если кошка не положила лапу на ячейку с мышью, то мышь перебегает в соседнюю ячейку (даже может перебежать в ту ячейку, на которую кошка клала лапу). В какую именно, кошка не знает.
Задача: написать программу, которая рассчитывает для кошки победную стратегию, и желательно содержащую наименьшее число ходов.
Если кому-то интересна реализация решения этой задачи на языке 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 году в работе Фонда Поддержки Функционального Программирования ФП(ФП) произошли определённые изменения, о которых необходимо сказать:
Всем удачи. Участвуйте в конкурсах, копите баллы и получайте призы. Кстати, ссылки на эту статью также принесут баллы.
Да, и ещё. Альманах-2012 находится в процессе компиляции. Скоро выйдет в свет, о чём будет сообщено дополнительно. Неравнодушных прошу ждать.
Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
Автор: Darkus
Источник [18]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/igra/27448
Ссылки в тексте:
[1] февральский конкурс: http://haskell98.blogspot.ru/2013/02/2013.html
[2] здесь: http://hpaste.org/82495
[3] haskell98.blogspot.ru: http://haskell98.blogspot.ru/
[4] здесь: http://haskell98.blogspot.ru/2013/02/blog-post.html
[5] Альманах конкурсов по ФП за 2011 год: http://habrahabr.ru/post/155913/
[6] Расшифровка кода на языке Haskell (конкурс по ФП в январе 2012): http://habrahabr.ru/post/137116/
[7] Шахматные задачи на мат в один ход: решение на языке Haskell: http://habrahabr.ru/post/138464/
[8] Измерение объёмов при помощи двух заданных сосудов: решение на языке Haskell: http://habrahabr.ru/post/139659/
[9] Трансмутации слов друг в друга: решение на языке Haskell: http://habrahabr.ru/post/142551/
[10] Решение арифметических задач — вероятностный подход против регулярных выражений: http://habrahabr.ru/post/143954/
[11] Поиск кратчайшего расстояния между точками в трёхмерном пространстве: http://habrahabr.ru/post/148263/
[12] Управление лифтами: решение на языке Haskell: http://habrahabr.ru/post/149377/
[13] Решение логических задач на языке Haskell: в своём ли уме Валет?: http://habrahabr.ru/post/149945/
[14] Поиск скрывающегося Доктора X среди пациентов — решение более сложных логических задач: http://habrahabr.ru/post/151797/
[15] Шарики и дырки — один из вариантов плотной упаковки на языке Haskell: http://habrahabr.ru/post/154855/
[16] Раскрашиваем карту при помощи языка Haskell: http://habrahabr.ru/post/157573/
[17] Алгоритм A* и кубик Рубика: реализация на языке Haskell: http://habrahabr.ru/post/161913/
[18] Источник: http://habrahabr.ru/post/169671/
Нажмите здесь для печати.