Запоздало спешу представить на суд внимательного читателя отчёт о проведении конкурса по функциональному программированию под эгидой Фонда Поддержки Функционального Программирования ФП(ФП) в июне месяце сего года. Всем желающим была предложена задача, которую предложил на конкурс один наш добрый коллега, участвовавший в своё время в разработке решения задачи про полубезумного Доктора Х (см. отчёт на Хаброхабре «Поиск скрывающегося Доктора X среди пациентов — решение более сложных логических задач»). Условие задачи было таково…
Необходимо было написать программу, которая осуществит расшифровку представленного ниже в виде кодограммы послания. На конкурс принимались, как обычно, программы на любых языках программирования, но предпочтение отдавалось функциональной парадигме. По замыслу, после запуска программа должна выполнить подбор и поиск решения, после чего вывести его на экран. А вот и сама кодограмма:
Один восточный мудрец проникся духом Олимпийского движения и послал барону Пьеру де Кубертену ребус-шараду, в котором закодировал послание всем добрым людям мира:
Но мудрец не был бы самим собой, если бы не сделал всё это в виде математической головоломки. Как вы видите, здесь у нас есть диаграмма Венна, показывающее пересечение пяти множеств. Каждый сектор, образуемый пересечением, помечен буквой или каким-то иным символом, в том числе пробелом. Необходимо расставить числа от 1 до 15 в секторах таким образом, чтобы суммы чисел в каждом из пяти множеств, помеченных цветными кольцами, были равными друг другу. Это даст ключ к расшифровке послания.
Не совсем понятно почему, но задача оказалась не совсем уж и интересной. В конкурсе приняло участие всего только два человека, а ещё несколько вполне успешно «навангавали» правильный ответ, что, впрочем, за участие и тем более решение не засчитывалось. Ну а я сам, как обычно, предлагаю ознакомиться с кратким отчётом, описывающим решение поставленной задачи на прекрасном языке Haskell.
Решение задачи
Не мудрствуя лукаво, я начал решать поставленную задачу в лоб. Что для этого нужно? Немного, а именно взять все возможные перестановки чисел от 1 до 15 (ведь именно 15 символов в закодированном сообщении), каждую перестановку проверить на соответствие критерию на равенство сумм по всем кольцам, затем сопоставить каждому числу букву из кода, отсортировать по числам и вывести полученную фразу на экран. Вот простая реализация всего, что написано:
main :: IO ()
main = mapM_ putStrLn $
map (map fst . sortBy (compare `on` snd) . zip encoding . fst) $
filter (allEqual . snd) $
map (l -> (l, rings l)) $
permutations ([1..15] :: [Int])
Надо отметить, что на программном уровне не происходит выбора правильного ответа, его необходимо искать вручную среди всех выводимых на экран последовательностей. И надо отметить, что таких последовательностей всего около 40 тысяч, так что такое автоматизированное решение задачи в большей степени негодно, чем годно.
В этой функции используются две специально написанные функции — rings
и allEqual
. Первая возвращает список сумм чисел в кольцах, вторая — предикат, который проверят факт того, что все суммы в пяти кольцах равны друг другу. Вот так выглядит определение первой функции:
rings :: Num a => [a] -> [a]
rings [n01, n02, n03, n04, n05, n06, n07, n08, n09, n10, n11, n12, n13, n14, n15]
= [sum [n01, n02, n06, n07],
sum [n02, n03, n04, n07, n08, n09, n10, n11],
sum [n04, n05, n11, n12],
sum [n06, n07, n08, n09, n13, n14],
sum [n09, n10, n11, n12, n14, n15]]
Достаточно негибкая функция, которая работает только со списками, содержащими 15 и только 15 числовых значений. Из этих пятнадцати значений функция формирует список из пяти сумм в соответствии с вхождением чисел в олимпийские кольца в кодограмме. Реализация тупа до безобразия. Зато работает.
А вот предикат:
allEqual :: Eq a => [a] -> Bool
allEqual [] = True
allEqual [x] = True
allEqual (x:xs) = x == head xs && allEqual xs
Тоже ничего мудрёного — возвращает значение True
тогда и только тогда, когда все значения в заданном списке одинаковы. Вдумчивому читателю рекомендуется подумать на тему того, как реализовать эту функцию через свёртку foldl
. Ну и константная функция с перечнем символов кодограммы:
encoding :: String
encoding = "ИР,П!РТ ОСТМ-ОЫ"
Заключение
Несмотря на то, что решение в целом негодно, оно вполне операционно — правильное решение можно найти. Например, можно перенаправить вывод в файл, а потом пройтись по этому файлу каким-нибудь статистическим анализатором на N-граммах русского языка. Впрочем, надо отметить одну оплошность автора задачи. Оказалось, что есть ровно две подходящих по критерию осмысленные фразы на русском языке. Они не сильно различаются, но тем не менее: «о, спорт, ты — мир!» и «о, спорт, ты — рим!». Экая незадача.
Участники конкурса, успешно справившиеся с задачей, подошли к её решению с другой стороны. Например, добрый коллега afiskon перебирал не перестановки чисел от 1 до 15, а буквы, выискивая в них фразы, а потом проверяя на соответствие критерию. Тут, впрочем, имеется небольшой «грязный хак» — поскольку речь идёт о спорте, резонно предположить, что в закодированной фразе есть последовательность «спорт». Неспортивно, вышло, но опять же, позволило коллеге занять первое место. С его отчётом об участии в конкурсе каждый может ознакомиться здесь.
Ну а я, как обычно, буду благодарен всем за комментарии и всякие хорошие пожелания.
Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
- Конкурсы в 2011 году: Альманах конкурсов по ФП за 2011 год
- Конкурсы в 2012 году: Альманах конкурсов по ФП за 2012 год
- Игра в «кошки — мышки», поиск минимальной стратегии
- Немного стеганографии: о подготовке апрельского конкурса по ФП
Автор: Darkus