Так уж вышло, что на февральский конкурс по функциональному программированию в 2014 году была предложена очень смешная и совершенно неполиткорректная задача, которая, однако же, привлекла небывалое для последних времён количество конкурсантов. В итоге на конкурс было подано 10 решений, а участвовало 9 конкурсантов (то есть один из участников решил задачу на двух языках программирования). Из представленных языков программирования же в порядке убывания были следующие: Haskell (4 решения), Erlang (2 решения), Clojure, JavaScript, Prolog и Scala (по 1 решению). Что, собственно, очень радует.
Победитель получит книгу «Квантовые вычисления и функциональное программирование» с автографом автора, когда она будет написана и опубликована. Собственно, победители всех конкурсов в 2014 году получат именно этот приз, а те, кто займёт второе место — какую-нибудь из имеющихся в библиотечном фонде ФП(ФП) книгу. Ну а теперь, кому интересно, можно ознакомиться с решением конкурсной задачи на языке Haskell.
Постановка задачи
На этот раз в качестве разминки для ума конкурсантам была дана следующая задача, найденная в анналах этих ваших интернетов:
На суднѣ находится 20 человѣкъ, между ними одинъ негръ. Вслѣдствiе недостатка въ продовольствiи одинъ изъ команды долженъ быть выброшенъ за бортъ. Рѣшено отсчитывать по семи и каждаго седьмого освобождать; дойдя до конца ряда, переходить къ его началу, не прерывая счёта. Оставшийся послѣдним долженъ умереть. Негръ (обозначенный перевёрнутой спичкой) можетъ стать на любое мѣсто въ ряду. Съ кого слѣдует начинать счётъ, чтобы негръ оставался всегда послѣднимъ?
Само собой разумеется, что в рамках конкурса надо было написать универсальное решение, которое в качестве входных параметров принимало бы количество человек на борту, количество отсчитываемых людей и местоположение негра в ряду.
В такой постановке задача является вариантом вполне известной задачей Иосифа Флавия, о которой можно почитать в Википедии, равно как и узнать там алгоритм её решения. То есть участникам оставалось только переложить этот алгоритм на выбранный ими язык программирования.
Так что теперь нам остаётся посмотреть, как задача Иосифа Флавия может быть решена на языке программирования Haskell.
Решение
Для реализации задачи необходимо написать всего лишь две функции. Первая рассчитывает то, какой человек останется последним, если в изначальных n людях отсчитывать по k. Вот её определение:
lastman :: Integral a => a -> a -> a
lastman 1 _ = 1
lastman n k = 1 + (lastman (n - 1) k + k - 1) `mod` nЗдесь просто закодировано то рекуррентное соотношение, которое дано в математическом алгоритме решения задачи. Вторая же функция, собственно, решает поставленную на конкурс задачу, поскольку она для заданного l, то есть позиции того, кто должен остаться последним, возвращает позицию того, с кого надо начинать счёт. Вот её определение:
solve :: Integral a => a -> a -> a -> a
solve n k l = 1 + (l + n - lastman n k) `mod` n
Для красоты реализации можно написать функцию main, которая обеспечивает диалог с пользователем:
main :: IO ()
main = do putStr "Сколько человек на борту: "
n <- getLine
putStr "На каком месте стоит негр: "
l <- getLine
putStr "Какой по счёту человек спасается: "
k <- getLine
putStrLn ("Начинать счёт надо с " ++
show (solve (read n) (read k) (read l)) ++
"-го человека.")Всё.
Заключение
Вот такой получился расистский конкурс. Прошу не судить строго, ибо конкурс на этот раз выдался вполне интересным для участников, раз было подано 10 решений. Ну а описанное в этой статье решение всякий желающий может получить здесь.
Прошу не забывать о моей новой инициативе: «Квантовые вычисления и функциональное программирование».
Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
- Конкурсы в 2011 году: Альманах конкурсов по ФП за 2011 год
- Конкурсы в 2012 году: Альманах конкурсов по ФП за 2012 год
- Конкурсы в 2013 году: Альманах конкурсов по ФП за 2013 год
Автор: Darkus
