Сегодня я с большим опозданием спешу отчитаться о втором конкурсе по функциональному программированию в 2013 году, который проходил под эгидой ФП(ФП) в течение первой недели апреля. Конкурс проходил в течение недели и нескольких дней и был объявлен в новом официальном блоге ФП(ФП) ^[1], а ссылки на него распространялись по всем старым блогам.

Однако сразу скажу, что то ли я перемудрил с организацией и задачей, то ли ещё по каким-то причинам, но в конкурсе приняло участие только двое конкурсантов, которые и так обычно принимают участие во всех мероприятиях ФП(ФП). Так что можно констатировать, что в этот раз конкурс не то, чтобы совсем не удался, но совсем не достиг тех целей, которые я перед ним ставил. А у меня было довольно много радужных надежд именно на этот конкурс, ведь я посвятил ему довольно много времени в качестве организатора.

Замысел

На этот раз я хотел сделать нечто необычное. На ум мне пришёл метод, которым пользовался великолепный Френсис Бекон (уже не помню, для каких именно целей, но пользовался). Это был один из первых, если не самый первый метод применения стеганографии, то есть метода сокрытия информации. Стеганография является, если можно так выразиться, родной сестрой криптографии. Однако если в криптографии имеется задача сделать невозможным раскодирование информации, то в стеганографии упор делается на сокрытии информации, то есть представлении ситуации таким образом, как будто бы ничего значимого не передаётся.

Итак, тот метод, который задумал я, основан на применении некоторых ординарных свойств символов для дополнительного кодирования информации в обычном тексте. Пусть есть некоторый текст. На каждый сивол этого текста можно, по сути, повесить огромное количество битов дополнительной информации, задействовав различные войства символа. Например, если буква написана шрифтом с засечками, то это бит 1, а если рубленым шрифтом, то это бит 0. Так же можно пользоваться любям бинарным свойством — полужирный символ или нет, курсивный или нет. По идее, в одном и том же тексте можно закодировать огромное количество скрытых посланий. Главное, чтобы символов хватило, ведь для кодирования одного символа скрытого текста требуется несколько символов обычного текста, поскольку каждый символ обычного текста несёт один бит скрытой информации.

Я решил взять формулировку какой-либо незначительной и очень распространённой задачи и закодировать в этой формулировке нечто необычное. Однако простой кодировке мне показалось мало. В 2013 году я предложил конкурсантам искать в окружающем их мире волшебные слова, и поэтому решил закодировать в скрытом сообщении первое волшебное слово 2013 года. Этим словом стало слово «НЕЙТРОН», которое и обнаружили двое конкурсантов, успешно справившиеся с заданием конкурса. Но ведь не просто так это слово было скрыто.

Смотрите. Везьмём русский алфавит. В нём 33 буквы, то есть практически 32, что есть 2 в степени 5, то есть 5 бит. Если принять два допущения, что буквы Ё и Е кодируются одним и тем же кодов, равно как и буквы Ь и Ъ, которые семантически несут одно и то же значение, то мы получим 31 символ. Добавим к этому набору пробел, и мы получим простой телеграфный код, включающий пробел и все основные буквы русского алфавита. Ни регистров, ни знаков препинания нет, но они и не нужны для простой передачи скрытого послания. Так что можно ограничиться пятью битами и при помощи них закодировать послание в тексте достаточной длины.

Если закодировать волшебное слово, то получится некоторый бинарный код: 01110001100101010011100010111101110. Здесь мы принимаем простейший пятибитовый код: пробел будет кодироваться последовательностью 00000, буква А — последовательностью 00001 и так далее до буквы Я, которая кодируется последовательностью 11111. Но для сокрытия такой короткой последовательности требуется всего лишь 35 символов, а сложно найти задачу, чья формулировка состояла бы и такого незначительного числа букв. Поэтому я взял и преобразовал это двоичное число в десятичное, из чего получилось ничто иное, как: 15244838382.

Это число можно подвергнуть различным преобразованиям. Я решил поступить таким образом — мы представим это число в виде некоторого арифметического выражения, достаточно сложного, которое описшем на естественном языке. Это длинную фразу на естественном языке мы снова подвергнем кодированию тем же пятибитовым кодом, который уже и спрячем за формулировкой незначительной задачи. Это показалось интересным, осталось придумать, как для заданного числа придумать достаточно сложное арифметическое выражение.

В голову ничего не пришло, кроме разложения на множители. Однако число оказалось не очень для этого хорошим, поэтому от него пришлось отнять некоторое слагаемое, и уже результат подвергнуть разложению на множители. В итоге число представлено как произведение степеней простых множителей, к которому добавлен волшебное слагаемое. Получилось что-то типа такого: «Взять число два и возвести его в шестую степень результат умножить на три в квадрате результат умножить на пять результат умножить на одиннадцать результат умножить на девятнадцать в квадрате результат умножить на тридцать один результат умножить на сорок три и к результату прибавить десять тысяч пятьсот сорок два».

Здесь, как видно, не используются запятые по уже понятным причинам. Эту странную фразу я закодировал и спрятал в тексте задачи на конкурс ^[2]. Моей задумкой было то, что конкурсант, увидев такое необычное задание и способ его представления (в особенности), не кинется сразу писать или гуглить куин, а поразмыслит и подумает. В итоге его размышлений родится программа, которая берёт HTML-код, разбирает его и преобразует в бинарный код, а потом бинарный код преобразует в слова на русском языке. Тут мне показалось, что вышеприведённой фразы недостаточно для статистического анализа, поэтому я решил внедрить в описание задачи ещё одно скрытое послание, а именно описание протокола — если взять красные символы, то они составят простую фразу: «пять бит. пробел, а… я. ё это е. ъ это ь.». Но даже красные символы не навели некоторых на размышления…

В итоге, у конкурсантов была зацепка в виде описания протокола и исходного кода в виде последовательностей полужирных и обычных символов. Если применить протокол к этой последовательности, то можно было бы получить приведённую выше фразу, описывающую арифметическое действие. Затем действие необходимо было выполнить, и я планировал, что для этого напишут специальный парсер, чтобы выполнить его автоматически. Ну а по результатам выполнения полученное число надо было бы перевести к двоичному представлению и снова применить к нему известный протокол. В итоге было бы получено первое волшебное слово.

Однако без подсказок никто этого так и не сделал. Оба участника конкурса смогли найти число, при этом выполнив все арифметические действия вручную, но что с этим числом делать дальше придумать не смогли — мне пришлось подсказывать. Так что, в итоге, я считаю, что эксперимент по сокрытию информации даже и удался. Можно было бы принять в качестве правильных ответов набросанные в комментариях куины, а потом написать эту статью, чтобы повеселить праздную публику.

Но перейдём к описанию того, как я готовил конкурс…

Реализация

Перед тем, как перейти собственно к описанию решения, необходимо написать пару слов на такую тему. Изначально я хотел определить функцию, которой на вход подавалось бы волшебное слово и текст, в котором это волшебное слово необходимо спрятать, а на выходе выдавалась бы HTML-разметка для публикации где бы то ни было. Однако в процессе подготовки я столкнулся с такой проблемой. Если разложить указанное ранее число 15244838382 на множители, то получится нечно совсем неинтересное: 2 * 3 * 2540806397. Любой согласится, что такое произведение слишком просто. Именно для этих целей я и задумал иметь некое волшебное слагаемое, которое надо добавлять в конце. Но вот вопрос — как выбрать такое волшебное слагаемое? Перебирать все и просматривать одно за другим?

Я решил пойти иным путём. Перенесём проблему перебора на некий более высокий уровень абстракции. Что мы хотим получить в итоге? Более сложное арифметическое выражение. В нём заведомо будет одно слагаемое, большее нуля. А вот сколько будет множителей? И какие будут степени у множителей? По этим критериям я и решил искать волшебное слагаемое. Проделав несколько экспериментов, я остановился на том, что множителей в разложении числа на простые множители должно быть не менее 7, а при этом сумма степеней у множителей должна быть не менее 12. Но мы, как настоящие программисты, конечно же параметризуем эти числа, в результате чего получится функция поиска волшебного слагаемого:

findMagicAddend :: Int -> Integer -> Integer
findMagicAddend n m = head $
                        map ((d, _, _) -> d) $
                        filter ((_, l, s) -> l >= n && s >= m)
                             [(k, length fct, sum $ map snd fct) |
                               k <- [2..], let fct = factors $
                                                       createDefinition k $
                                                       binToInteger $
                                                       encode magicWord]

Здесь всё достаточно просто. Мы берём волшебное слово (для простоты я определил его в виде константной функции magicWord, кодируем его, переводим из двоичной системы в десятичную и создаём определение числа в виде арифметического выражения, причём волшебное слагаемое подбираем при помощи генератора списка от 2 до самой бесконечности. В списке, получаемом из генератора, мы собираем волшебное слагаемое, количество множителей в разложении числа на простые множители, сумму степеней простых множителей. Далее мы фильтруем этот список троек на основании изложенных ранее критериев — количество множителей должно быть не меньше первого аргумента, а сумма степеней — не меньше второго. Далее список троек превращаем в список волшебных слагаемых (длина и сумма нам больше не нужны) и берём первый элемент. Всё.

Модуль для кодирования и декодирования

Начнём, как всегда, сверху вниз. Вот определение функции main, которая готовит стеганограмму для заданных в виде константных функций волшебного слова и текста, в котором оно прячется:

main = let magicAddend  = findMagicAddend 7 12
           code         = encode $ show $ createDefinition magicAddend $ binToInteger $ encode magicWord
           neededZeroes = ((-) `on` length) text code
           code'        = code ++ replicate neededZeroes '0'
       in  collideTags $ concat $ zipWith htmlEncode code' text

Функция написана в стиле языка OCaml, скорее, нежели в стиде языка Haskell, но здесь это целесообразно по той причине, что для сборки HTML-разметки, которую необходимо вернуть в результате работы функции, необходимо иметь в наличии множество промежуточных результатов, которые и подготавливаются в образцах выражения let. Конечно, можно было бы обойтись и без них, но каждый может себе представить, каким многоэтажным было бы тогда выражение, возвращаемое функцией main.

Образец magicAddend получает значение волшебного слагаемого, которое найдено по той самой технологии, как было описано ранее. Именно здесь и использованы те две найденные в результате экспериментов константы — 7 и 12. Результат — число 10 542. Затем в образец code заносится двоичный код арифметического выражения, полученного при помощи применения функции createDefinition к десятичному представлению кода для волшебного числа. Указанная функция как раз строит разложение числа на множители, а функция show в данном случае переводит такое разложение в естественно-языковой текст (мы посмотрим на это чуть позже).

Образец neededZeroes получает в качестве значения количество нулей после кода, которое необходимо добавить, чтобы сохранить длину текста, в котором прячется код волшебного слова. Соответственно, в образце code' сохраняется код с добавленными нулями. Ну и затем в выражении после слова in строится HTML-разметка. Сначала все символы кода и текста сливаются друг с другом посредством функции htmlEncode, которая принимает на вход два символа, а возвращает строку. Потом список строк конкатенируется в одну большую строку, а после этого из этой большой строки убираются все вхождения подстроки "</b><b>" (функция collideTags). Это необходимо для усложнения задачи по анализу HTML-разметки (хотя, какое уж тут усложнение)…

Рассмотрим функцию для кодирования текста. Вот её определение:

encode :: String -> String
encode = concatMap (fromJust . flip M.lookup alphabet) .
           filter (`elem` ('Ё':'Ъ':legalChars)) .
           map toUpper

Функция получает на возд строку и преобразует каждый её символ к верхнему регистру. Затем выфильтровывает из полученной строки символы, которые не входят в алфавит (это всякие пунктуационные символы, некириллические символы; в общем, остаются только пробел и символы русского языка в верхнем регистре). После фильтрации каждый символ строки подаётся на поиск в словаре alphabet, который содержит перевод символов кириллицы в пятибитовый код. Каждый символ, стало быть, преобразуется в строку из пяти нулей и единиц, поэтому в конце преобразования все строки сливаются в одну большую строку.

А вот так строится словарь для кодирования:

alphabet :: Map Char String
alphabet = M.insert 'Ё' (binary 5 6) $
             M.insert 'Ъ' (binary 5 28) $
             M.fromList $
             zip legalChars $
             map (binary 5) [0..31]

Строятся строки двоичных представлений чисел от 0 до 31, причём длина двоичных представлений должна быть не менее пяти символов. Далее эти двоичные представления сшиваются в пары с символами от пробела до 'Я', список пар преобразуется в словарь Data.Map, куда добавляются новые коды для символов 'Ъ' и 'Ё'. Итого в словаре получается ровно 32 символа, что полностью забирает пять бит для кодирования. А вот так строится список допустимых символов:

legalChars :: [Char]
legalChars = ' ' : delete 'Ъ' ['А'..'Я']

Буква Ё всё равно не входит в интервал ['А'..'Я'] в силу странностей кодирования Unicode, а вот твёрдый знак придётся удалить вручную. Потом к полученному списку просто добавляется пробел. Всё.

Рассмотрим определение функции для перевода заданного числа в двоичное представление:

binary :: Int -> Integer -> String
binary m d = if n < m
               then replicate (m - n) '0' ++ b
               else b
  where
    b = binary' d
    n = length  b
    
    binary' :: Integer -> String
    binary' 0 = "0"
    binary' 1 = "1"
    binary' d = ((++) `on` binary') (d `div` 2) (d `mod` 2)

Эта функция вполне обычна, но имеет только один нюанс — она добавляет лидирующие нули, если длина полученного представления меньше, чем заданная параметром m минимальная длина представления. Всё остальное просто — обратите внимание на определение замыкания binary', оно занятно.

Снова перейдём к определениям функций, которые вызываются из функции main. Вот определение функции binToInteger, которая используется для перевода двоичного представления, выраженного строкой, в десятичное:

binToInteger :: String -> Integer
binToInteger = sum .
                 map (uncurry (*) . (n, b) -> (n, read [b])) .
                 zip (map (2^) [0..]) .
                 reverse

Опять же всё очень просто, и я раз за разом поражаюсь выразительности языка Haskell. Здесь мы обращаем двоичное представление числа в виде строки, к каждому символу, который есть '0' или '1', добавляет в пару соответствующую степень двойки. Потом все пары преобразуем в произведение степени двойки на 0 или 1, после чего полученный список произведений складываем. Результат — требуемое число в двоичном представлении.

Далее — функция createDefinition, которая получает на вход волшебное слагаемое и число, из которого необходимо составить арифметическое выражение. Вот тако она это делает:

createDefinition :: Integer -> Integer -> Number Integer
createDefinition k n = Number (factorize (n - k)) k
  where
    factorize = map (head &&& fromIntegral . length) . group . primeFactors

Опять же, всё просто. Собирается определение Number (этот тип мы сейчас рассмотрим), в котором первым значением идёт разложение числа на множители, а вторым — волшебное слагаемое. Само собой разумеется, что на множители раскладывается исходное число за вычетом волшебного слагаемого. Ну а разложение на множители производится при помощи функции primeFactors, которая определена в модуле Data.Numbers.Primes. Далее все множители группируются, каждый список в группировке преобразуется в пару (оператор (&&&)), в которой первым элементом является простой множитель, а вторым — их количество в группе, то есть степень. Длина списка выражается типом Int в целях оптимизации, поэтому мы преобразуем его к типу Integer, как того требует наш тип Number, определение которого следует:

data Number a = Number
                {
                  factors :: [(a, a)],
                  addend  :: a
                }

Собственно, чего-либо иного ожидать было сложно. Число состоит из списка множителей, к каждому из которых приписан показатель степени, а также волшебного слагаемого. Весь цимес этого типа в определении экземпляра для класса Show, который преобразует значения данного типа в строку, описывающую арифметическое выражение на естественном языке:

instance (Eq a, Integral a) => Show (Number a) where
  show (Number [] a) = russianNumberName a
  show (Number fs a) = showFirstFactor (head fs) ++
                         foldl showOtherFactors "" (tail fs) ++
                         showAddend a
    where
      showFirstFactor (n, 1) = "Взять число " ++ russianNumberName n ++
                                 " в качестве результата"
      showFirstFactor (n, d) = "Взять число " ++ russianNumberName n ++
                                 " и возвести его в " ++ powerName d
        where
          powerName 2 = "квадрат"
          powerName 3 = "куб"
          powerName 4 = "четвёртую степень"
          powerName 5 = "пятую степень"
          powerName 6 = "шестую степень"
          powerName 7 = "седьмую степень"
          powerName 8 = "восьмую степень"
          powerName 9 = "девятую степень"
          powerName _ = error "Неизвестный показатель степени в функции powerName."
      
      showOtherFactors s (n, 1) = s ++ " результат умножить на " ++
                                         russianNumberName n
      showOtherFactors s (n, d) = s ++ " результат умножить на " ++
                                         russianNumberName n ++ " в " ++ powerName' d
        where
          powerName' 2 = "квадрате"
          powerName' 3 = "кубе"
          powerName' 4 = "четвёртой степени"
          powerName' 5 = "пятой степени"
          powerName' 6 = "шестой степени"
          powerName' 7 = "седьмой степени"
          powerName' 8 = "восьмой степени"
          powerName' 9 = "девятой степени"
          powerName' _ = error "Неизвестный показатель степени в функции powerName'."
      
      showAddend 0 = ""
      showAddend a = " и к результату прибавить " ++ russianNumberName a

Описывать что-либо тут особого смысла нет, поскольку код говорит сам за себя. Здесь есть пара упрощений, которые перечислены в заключении этой статьи. Но в целом код позволяет решить подавляющее больщиинство задач.

Остались только утилитарные функции для кодирования текста в HTML-разметку. Их определения не составляют какой-либо особенности или сложности:

htmlEncode :: Char -> Char -> String
htmlEncode c t | c == '0'  = "<b>" ++ [t] ++ "</b>"
               | otherwise = [t]

collideTags :: String -> String
collideTags s = if tag `isInfixOf` s
                  then collideTags (prefix ++ suffix)
                  else s
  where
    tag = "</b><b>"
    tl  = length tag
    
    prefix  = take (length prefix' - tl) prefix'
    prefix' = fst $ head $ filter snd $ map (l -> (l, tag `isSuffixOf` l)) $ inits s
    suffix  = drop tl suffix'
    suffix' = fst $ head $ filter snd $ map (l -> (l, tag `isPrefixOf` l)) $ tails s

На этом всё. Переходим к рассмотрению модуля, который предназначен для преобразования числа в его наименование на естественном языке. Модуль RussianNumbers, функции из которого используются для определения экземпляра класса Show для типа Number.

Модуль для именования чисел на русском языке

В экземпляре класса Show для типа Number использовалась функция russianNumberName. Эта функция импортирована из модуля RussianNumbers, в котором определено всё для того, чтобы для заданного числа получить его наименование на русском языке (порядковое числительное в именительном падеже). Модуль этот не слишком интересен и больше наполнен техническими элементами, нежели интересными находками.

Проблема с числительными в русском языке имеется только одна: наименование второй триады — «тысяча» имеет женский род в отличие от прочих триад, а потому необходимо дублирование функций для обработки грамматической категории рода и атавизмов двойственного числа, дошедшего до современного русского языка из языка древнерусского, а именно различные падежи/числа у наименований триад для чисел, заканчивающихся на 1, заканчивающихся на 2, 3 или 4, а также заканчивающихся на прочие цифры. Ну и ещё есть небольшая странность в том, что для чисел от 11 до 19 действуют иные правила падежного сопряжения. В итоге получается просто муторное кодирование несложных правил.

Перво-наперво необходимо иметь список для наименования триад (триадой называем три разряда, имеющие определённое наименование — «миллион», «квинтиллиард» и т. д.). Возьмём столько наименований, сколько сможем:

triadeNames :: [String]
triadeNames = ["", "тысяча", "миллион", "миллиард", "биллион", "биллиард",
               "триллион", "триллиард", "квадриллион", "квадриллиард",
               "квинтиллион", "квинтиллиард", "секстиллион", "секстиллиард",
               "септиллион", "септиллиард", "октиллион", "октиллиард",
               "нониллион", "нониллиард", "дециллион", "дециллиард"]

На самом-то деле названий там ещё больше, но ограничимся этими. Кто желает, сможет скачать модуль и дополнить его. Ну а мы двинемся дальше и начнём с определения главной функции модуля:

russianNumberName :: (Eq a, Integral a) => a -> String
russianNumberName = trimSpaces . foldl nameTriade "" . reverse . zip triadeNames . triades
  where
    nameTriade s (t, n) = s ++ tnDeclination t n
    
    tnDeclination t n | n == 0        = ""
                      | t == ""       = rnn999  n
                      | t == "тысяча" = rnn999' n ++ " " ++ init t ++ femininumEnding  n
                      | otherwise     = rnn999  n ++ " " ++      t ++ masculinumEnding n
    
    masculinumEnding n | n `mod` 100 >= 11 && n `mod` 100 <= 19 = "ов "
                       | n `mod` 10 == 1 = " "
                       | n `mod` 10 >= 2 && n `mod` 10 <= 4 = "а "
                       | otherwise = "ов "
    
    femininumEnding n | n `mod` 100 >= 11 && n `mod` 100 <= 19 = " "
                      | n `mod` 10 == 1 = "а "
                      | n `mod` 10 >= 2 && n `mod` 10 <= 4 = "и "
                      | otherwise = " "

Записанная в бесточечной нотации функция работает просто. Мы берём число и разбиваем его на триады. Далее каждую триаду ставим в пару с её наименованием. После этого список пар обращается, поскольку в русском языке наименование числа начинается с самой старшей триады. Итого — у нас есть обращённый список пар триад и их наименований. Этот список мы сворачиваем при помощи функции nameTriade, которая определена локально. Рассмотрим её.

Функция nameTriade получает на вход уже имеющуюся строку и пару. Она добавляет к строке полное наименование новой триады, полученное из пары. Полное наименование даёт функция tnDeclination. Она собирает слова русского языка — берёт наименование числа от 0 до 999 и добавляет к нему наименование триады в нужном падеже и числе. Тут-то и видно, как надо разбирать все эти безобразия русского языка: отделять тысячи, распознавать в женском и мужском родах различные варианты падежей. В общем, технические подробности.

После свёртки списка пар мы убираем лишние пробелы, которые всяко получаются при соединении слов друг с другом. Можно было бы обойтись и без этого, однако в таком случае пришлось бы много внимания и дополнительных условий с ветвлениями уделять в глубинах функций rnn999 и rnn999'. Ну а всякий вдумчивый читатель уже понял, что эти две функции отвечают за наименование числа от 0 до 999. Рассмотрим первую:

rnn999 :: (Eq a, Integral a) => a -> String
rnn999 0   = "ноль"
rnn999 1   = "один"
rnn999 2   = "два"
rnn999 3   = "три"
rnn999 4   = "четыре"
rnn999 5   = "пять"
rnn999 6   = "шесть"
rnn999 7   = "семь"
rnn999 8   = "восемь"
rnn999 9   = "девять"
rnn999 10  = "десять"
rnn999 11  = "одиннадцать"
rnn999 12  = "двенадцать"
rnn999 13  = "тринадцать"
rnn999 14  = "четырнадцать"
rnn999 15  = "пятнадцать"
rnn999 16  = "шестнадцать"
rnn999 17  = "семнадцать"
rnn999 18  = "восемнадцать"
rnn999 19  = "девятнадцать"
rnn999 20  = "двадцать"
rnn999 30  = "тридцать"
rnn999 40  = "сорок"
rnn999 50  = "пятьдесят"
rnn999 60  = "шестьдесят"
rnn999 70  = "семьдесят"
rnn999 80  = "восемьдесят"
rnn999 90  = "девяносто"
rnn999 100 = "сто"
rnn999 200 = "двести"
rnn999 300 = "триста"
rnn999 400 = "четыреста"
rnn999 500 = "пятьсот"
rnn999 600 = "шестьсот"
rnn999 700 = "семьсот"
rnn999 800 = "восемьсот"
rnn999 900 = "девятьсот"
rnn999 n   = if n > 999
               then error "Некорректный аргумент функции rnn999."
               else let h  = (n `div` 100) * 100
                        h' = n `mod` 100
                        d  = (h' `div` 10) * 10
                        i  = n `mod` 10
                    in  tryH h h' d i
  where
    tryH h h' d i | h == 0    = tryH' h' d i
                  | otherwise = rnn999 h ++ " " ++ tryH' h' d i
    tryH' h' d i | h' == 0            = ""
                 | h' < 10            = tryI i
                 | h' > 10 && h' < 20 = rnn999 h'
                 | otherwise          = tryD d i
    tryD d i | d == 0    = tryI i
             | otherwise = rnn999 d ++ " " ++ tryI i
    tryI i | i == 0    = ""
           | otherwise = rnn999 i

Как видно, в этой функции даются наименования для всех тех чисел, у которых есть собственные наименования. Это делается при помощи специальных образцов. Если на вход подано число, у которого нет специального наименования, то его наименование собирается из имеющихся. Для этого число раскладывается на сотни, десятки и единицы, но при этом проверяется, не входит ли число в заветный перечень от 11 до 19. Таким образом, если у нас есть число XYZ, то в образце h получается число X00, в образце h' получается число YZ, в образце d получается число Y0 и в образце i получается число Z. Всё довольно просто. А затем производится наименование числа.

Если число сотен нулевое, то сразу переходим к наименованию десятков. Если же нет, то берём название сотни и переходим к наименованию десятков. Если десятки равны 0, то тут вообще всё число равно нулю, а потому мы возвращаем пустую строку (если число 0 в принципе, то мы именуем его на уровне выше). Если число лесятков меньше 10, то переходим к именованию единиц, если число десятков находится в интервале от 11 до 19, то именуем его в соответствии с правилом для этого интервала. В противном случае именуем десяток и единицу по отдельности, делая это в двух различных функциях.

Абсолютно так же устроена функция rnn999', за исключением только лишь двух слов — «одна» и «две» в применении к тысячам. В остальном производится вызов функции rnn999, и тут даже есть большое количество пересечения кода, которое можно было бы свести в одну функцию. Но не вышло.

В общем, вот такой получился модуль. Может поименовать практически любое число на русском языке. Если что, можно использовать для различных нужд в бухгалтерии и прочих местах, где требуется оформление бумаг, в которых числа пишутся прописью. Я уже начал использовать :).

Идеальное решение

В процессе подготовки конкурса я предполагал, что кто-нибудь из самых яростных адептов функционального программирования возьмёт и напишет идеальное решение этой задачи. Под идеальным решением я понимаю такое, которое берёт на вход URL страницы со стеганограммой, а возвращает найденное волшебное слово. При этом, конечно же, оно должно быть в меру универсальным — пусть в нём программно заложен описанный красными символами протокол, однако универсальность в данном случае заключалась бы в синтаксическом анализе естественно-языковой фразы с описанием арифметического выражения, результатом которого было бы вычисленное число. Конечно, если кто-либо смог бы предоставить программу, которая не пользовалась бы «красным протоколом», а производила частотный анализ по комбинациям битов различной длины, на основании которого делала бы определённого рода заключения, то это было бы ещё круче, но в данном случае длины арифметического выражения не хватило бы для более или менее полноценного статистического анализа.

В общем, я ожидал, что кто-нибудь да сможет. Но никто не смог. Даже несмотря на то, что конкус в итоге был продлён на неделю. Так что теперь я могу заявить, что выдам приз тому, кто первым в комментариях к данной заметке даст ссылку на свой исходный код, представляющий идеальное решение. Сам же я такую ссылку не предоставлю, ибо идеального решения не писал в силу тех же самых причин, что заставили меня в этом году перейти на более щадящий для меня режим запуска конкурсов один раз в два месяца.

В общем, дерзайте…

Заключение

В заключение хотелось бы сказать, что с начала 2013 года в жизнедеятельности Фонда Поддержки Функционального Программирования ФП(ФП) произошёл ряд существенных изменений:

Во-первых, ФП(ФП) переехал на официальный блог, который расположен по адресу haskell98.blogspot.ru ^[1]. Прошу заносить этот новый адрес в свои RSS-читалки. Там публикуются в основном рассказы на тему функционального программирования, но бывает и что-то иное. В любом случае, все рассказы жёстко категоризованы метками, так что каждый сможет себе отфильтровать по интересу.

Во-вторых, у ФП(ФП) появился блог на английском языке. В основном там дублируется информация из блога на русском языке, но бывает и что-то особенное, равно как и пропускаются некоторые не особо интересные записи из русского блога. Если кому-то интересно, то вот адрес: haskell98eng.blogspot.ru ^[3]. Ну и ежели вы расскажете своим англоязычным друзьям про этот блог, я буду безмерно благодарен.

В-третьих, как я уже упомянул, в 2013 году конкурсы стали проводиться реже — один раз в два месяца, то есть по чётным месяцам года. Связано это с безумной загрузкой на текущем месте работы, ну и надрыв на этом поприще в прошлом году тоже нельзя сбрасывать со счетов. Ну и, кстати, по результатам конкурсов в 2012 году уже выпущен новый номер Альманаха ^[4].

Ну а в чётвёртых, в этом году все конкурсы связаны между собой, и теперь за участие в конкурсах и других околоконкурсных делах под эгидой ФП(ФП) даются баллы, звания, ордена и медали (картонные погоны и сабли из оргстекла, привет Zert ^[5]). Так что прошу принимать участие, в конце года подведём итоги и выявим самых активных участников с награждениями и всеобщим чествованием. Ещё не поздно заработать звание Великого Магистра ФП.

А вот некоторые недочёты, которые хорошо бы устранить в более полноценной версии подготовки этого конкурса:

1. В функции main образец neededZeroes может получить отрицательное значение. Этот случай необходимо отслеживать, поскольку в данном случае выйдет, что длины текста недостаточно для сокрытия кода. Конечно, хорошо бы выводить диагностическое сообщение. Не было сделано из-за отсутствия желания заниматься с монадой IO.
2. Экземпляр класса Show для типа Number написан немного некорректно с точки зрения естественного языка, если список множителей пуст. Необходимо, конечно, добавить дополнительную проверку.
3. Также в этом же экземпляре имеется слишком жёсткое ограничение на то, что показатель степени у множителя не может быть более 9. Однако для пущей универсализации программы необходимо предусмотреть возможность наличия произвольного показателя степени. Его необходимо, конечно же, делать через модуль RussianNumbers, но для этого данный модуль необходимо дополнять огромным количеством дополнительных определений, в том числе и всякими зависимостями от падежей, чисел, типов числительных (порядковое или нет).
4. Дополнить список наименований триад до наиболее возможно полного, а ещё лучше закодировать правило наименования триад на основе греческих названий чисел — оно простое и вполне формализуемое.
5. В модуле RussianNumbers можно сократить дублирующийся код в двух местах. Хорошо бы это сделать.
6. Да и вообще, весь модуль RussianNumbers после внесения всех улучшений желательно перенести в проект NLSynthesis ^[6]. Там ему самое место.

А вот по следующим адреса всякий желающий может скачать исходные тексты приведённых в статье модулей (кстати, там есть ещё и другие определения, не описанные в статье, но которые также представляют некоторый интерес для вдумчивого читателя):

• Модуль Steganography ^[7].
• Модуль RussianNumbers ^[8].

Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:

• Конкурсы в 2011 году: Альманах конкурсов по ФП за 2011 год ^[9]
• Конкурсы в 2012 году: Альманах конкурсов по ФП за 2012 год ^[10]
• Игра в «кошки — мышки», поиск минимальной стратегии ^[11]

Автор: Darkus

Источник ^[12]