Решение арифметических задач — вероятностный подход против регулярных выражений

Как всегда в начале месяца состоялся конкурс ^[1] по функциональному программированию, который проводится на ежемесячной основе под эгидой Фонда Поддержки Функционального Программирования. В мае на суд конкурсантов была предложена задача, которая планировалась в качестве задачи для Большого Ежегодного Конкурса по ФП, который пока так и не состоялся. Изначальная концепция задачи была переосмыслена, в результате чего появилась такая формулировка:

В файле, находящемся по известному адресу, записано 100 тысяч условий арифметических задач на четыре действия: сложение, вычитание, умножение и деление. Условия записаны на естественном языке. В качестве результата необходимо представить файл с ответами на задачи — по одному ответу в виде натурального числа на каждой строке (итого 100 тысяч строк).

В конкурсе приняло участие 23 человека, которые использовали такие языки, как Bash, C++, C#, Clojure, F#, Haskell, Nemerle, Perl, Python, Racket и Shell. В этом конкурсе впервые за историю проведения самым часто используемым языком стал не Haskell, а другой язык — Perl.

В конкурсе впервые разыгрывался приз зрительских симпатий ^[2]. Это было весело.

В данной заметке я опишу то, как готовился конкурс (в том числе и при помощи одной из моих техник организации времени), с какими проблемами я столкнулся в процессе подготовки и организации, а также будет дан ответ на вопрос о пресловутом пороге в 55 %.

Генерация условий задач

Перво-наперво надо было нагенерировать кучу естественноязыковых условий арифметических задач. Меня предупреждали коллеги, что конкурс будет из-за этого неинтересным, поскольку мой генератор (более или менее детальное описание и применение см. здесь ^[3]) не сможет выдать достаточное разнообразие ЕЯ-текстов, а потому с лёгкостью и непринуждённостью вся его работа покроетая регулярными выражениями. Это и произошло в итоге, но об этом чуть позже.

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

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

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

Сначала определим некоторые типы данных, которые нам потребуются для работы:

type Task a = (TaskModel a, String)

data TaskModel a = Addition
                   {
                     operandX :: a,
                     operandY :: a,
                     result   :: a
                   }
                 | Substraction
                   {
                     operandX :: a,
                     operandY :: a,
                     result   :: a
                   }
                 | Multiplication
                   {
                     operandX :: a,
                     operandY :: a,
                     result   :: a
                   }
                 | Division
                   {
                     operandX :: a,
                     operandY :: a,
                     result   :: a
                   }

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

Далее две служебные функции:

fstOperand :: String
fstOperand = "%x"

sndOperand :: String
sndOperand = "%y"

Их можно было бы и не определять, но подобные определения, вроде как, позволяют избежать некоторых неприятных ошибок. К тому же, компилятор будет проверять правильность использования. Однако одну пренеприятнейшую ошибку, связанную с этими функциями, я всё же совершил. В одном терме порождающей грамматики я два раза указал функцию fstOperand, что породило ровно 1556 некорректных описаний задач. В итоге максимальным числом правильных ответов стало не 100 000, а 98 444. Обнаружил я эту досадную оплошность только в процессе проведения конкурса, когда исправлять что-либо было уже поздно. Но в этой статье даются уже исправленные исходники.

Вот списки термов для генерации задач на четыре арифметических действия:

addition = rule addition'
  where
    addition' = [kidsHaveItemsA, kidsInClassesA, kidsAgesA, kidsBuyItemsA,
                 kidsPlayA, kidsMakeItemsA, servedTableA, birdsAtWaterA,
                 plantsInCityA, bonbonsA, kidGetsGiftA, bulbsA, textbooksA,
                 kidPlantsA, toolsAtTableA, driverDrivesA]

substraction = rule substraction'
  where
    substraction' = [kidsHaveItemsS, kidsInClassesS, kidsAgesS, kidsBuyItemsS,
                     kidsPlayS, kidsMakeItemsS, servedTableS, birdsAtWaterS,
                     plantsInCityS, bonbonsS, kidGetsGiftS, bulbsS, textbooksS,
                     kidPlantsS, toolsAtTableS, driverDrivesS]

multiplication = rule multiplication'
  where
    multiplication' = [kidsHaveItemsM, kidsInClassesM, kidsAgesM, kidsBuyItemsM,
                       kidsPlayM, kidsMakeItemsM, servedTableM, birdsAtWaterM,
                       plantsInCityM, bonbonsM, kidGetsGiftM, bulbsM, textbooksM,
                       kidPlantsM, toolsAtTableM, driverDrivesM]

division = rule division'
  where
    division' = [kidsHaveItemsD, kidsInClassesD, kidsAgesD, kidsBuyItemsD,
                 kidsPlayD, kidsMakeItemsD, servedTableD, birdsAtWaterD,
                 plantsInCityD, bonbonsD, kidGetsGiftD, bulbsD, textbooksD,
                 kidPlantsD, toolsAtTableD, driverDrivesD]

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

Я не буду здесь приводить определения всех этих функций в количестве 64, а также дополнительных к ним, используемых для порождения синонимов различных объектов. Это было бы слишком громоздко — там общим объёмом порядка 475 LOC на языке Haskell. Кому интересно — всегда сможет обратиться непосредственно к исходникам.

Более интересной является функция порождения одного ЕЯ-описания задачи. Рассмотрим её внимательно:

task :: IO (Task Int)
task = do n <- randomRIO (1, 4) :: IO Int
          case n of
            1 -> do x <- randomRIO (1, 100)
                    y <- randomRIO (1, 100)
                    desc <- generate addition [Substitution fstOperand (show x),
                                               Substitution sndOperand (show y)]
                    return (Addition x y (x + y), desc)
            2 -> do x <- randomRIO (1, 100)
                    y <- randomRIO (1, 100)
                    desc <- generate substraction [Substitution fstOperand (show $ x + y),
                                                   Substitution sndOperand (show x)]
                    return (Substraction (x + y) x y, desc)
            3 -> do x <- randomRIO (1, 100)
                    y <- randomRIO (1, 100)
                    desc <- generate multiplication [Substitution fstOperand (show x),
                                                     Substitution sndOperand (show y)]
                    return (Multiplication x y (x * y), desc)
            4 -> do x <- randomRIO (1, 100)
                    y <- randomRIO (1, 100)
                    desc <- generate division [Substitution fstOperand (show $ x * y),
                                               Substitution sndOperand (show x)]
                    return (Division (x * y) x y, desc)

Что здесь происходит? Перво-наперво случайным образом выбирается арифметическое действие, одно из четырёх. Можно было бы написать более заумно, но тут мы просто воспользовались банальным множественным выбором case. В самой генерации тоже ничего необычного нет. Опять же случайным образом выбираются два операнда из интервала от 1 до 100, а генерация ЕЯ-описания задачи производится посредством подстановки этих операндов в тело ЕЯ-описания на места, определяемые функциями fstOperand и sndOperand. Конечно, здесь что-то 6 лишних строк, и их надо бы убрать, но это мы сделаем потом. А для начала надо отметить, что для вычитания и деления подстановка операндов в задачу производится хитрым образом. Это сделано для того, чтобы остаться в множестве натуральных чисел, а не вылезти из него в отрицательные и рациональные.

Функция generate и конструктор Substitution определены в библиотеке с генератором ЕЯ-текста.

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

saveTasks :: Integer -> String -> IO ()
saveTasks n fn = do ts <- mapM (_ -> task) [1..n]
                    tsk <- openFile (fn ++ "_tsk.txt") WriteMode
                    hSetEncoding tsk utf8
                    hPutStrLn tsk $ intercalate "n" $ map snd ts
                    hClose tsk
                    writeFile (fn ++ "_slv.txt") $ intercalate "n" $ map (show . result . fst) ts

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

Напоследок традиционная диаграмма вызовов:

Напоминаю легенду:

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

Проверка решений

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

compareSolutions :: FilePath -> FilePath -> IO ()
compareSolutions et sl = do etalon   <- readData et
                            solution <- readData sl
                            print $ length $ filter (== 0) $ zipWith (-) etalon solution
  where
    readData fn = withFile fn ReadMode (h -> do cnt <- hGetContents h
                                                 length cnt `seq` return (map read $ lines cnt))

Поскольку эталонный файл с решениями у нас есть, то надо просто считать его и присланный участником файл, построить списки чисел, отнять одно от другого и подсчитать количество полученных нулей. Именно это данная функция и делает, после чего выводит результат на экран.

Её диаграмма вызовов такова:

Реализация вероятностного решателя

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

1. Если максимальное из двух чисел больше 200, то тут однозначно задача на деление — большее число делится на меньшее.
2. Если максимальное из двух чисел находится в интервале от 100 до 200 включительно, то тут либо вычитание, либо деление, причём деление только в случае, если большее делится на меньшее без остатка. Так что во втором случае надо выбрать одну из двух операций, а в первом — только одну, то есть вычистание.
3. Если оба числа находятся в интервале от 1 до 100 включительно, то здесь может быть любая операция, но деление может быть только в случае возможности деления большего на меньшее без остатка. Так что либо выбираем одну операцию из трёх, либо из четырёх случаным образом.

Если сосчитать вероятность получения правильного ответа на основании таких правил, то получится где-то совсем рядом с 55 %. Быстрая реализация функции:

solve :: (Int, Int) -> IO Int
solve (x, y) = solve' (max x y) (min x y)
  where
    solve' x y | x > 200   = return (x `div` y)
               | x > 100   = if x `mod` y == 0
                               then getRandomElement [x - y, x `div` y]
                               else return (x - y)
               | otherwise = if x `mod` y == 0
                               then getRandomElement [x + y, x - y, x * y, x `div` y]
                               else getRandomElement [x + y, x - y, x * y]

Показала, что именно столько в процентном отношении данный подход и даёт правильных ответов. В итоге в качестве минимального порога и была принята волшебная цифра в 55 %, и отдельные особо умудрённые конкурсанты даже объяснили, откуда она взялась.

Другие функции из модуля для решения задач таковы:

main :: FilePath -> IO ()
main fn = loadData fn >>= mapM solve >>= saveSolutions ("Solve_" ++ fn)

loadData :: FilePath -> IO [(Int, Int)]
loadData fn = withFile fn ReadMode loadData'
  where
    loadData' h = hGetContents h >>= (cnt -> seq (length cnt) (return $ map (([x, y] -> (x, y)) .
                    map read . words . filter (c -> isDigit c || isSpace c)) $ lines cnt))

saveSolutions :: FilePath -> [Int] -> IO ()
saveSolutions fn xs = withFile fn WriteMode (h -> mapM_ (hPrint h) xs)

Надеюсь, что читатели уже достаточно умудрены, чтобы им не надо было подробно объяснять смысла этих определений. Если кому-то что-то не понятно — милости прошу в комментарии.

Ну и напоследок диаграмма вызовов функций:

Заключение

Сперва напомню, чтобы не было лишних вопросов — все диаграммы нарисованы вручную в MS Visio. Их смысл простой — наглядное представление того, как устроены внутренности функций. Я их рисую для понимания, какие метрики можно применять для расчёта сложности функциональных программ. Пока эта идея всё ещё лежит у меня на задворках подсознания, мозг ^[6] её переваривает, а для того, чтобы легче переваривал — рисую вот такие диаграммы. Но и, надеюсь, добрым людям тоже интересно и полезно.

В качестве всяких недочётов хотелось бы отметить следующие:

1. Необходимо убрать 6 повторяющихся строк из определения функции task.
2. Для генерации заданного количества ЕЯ-описаний задач надо использовать функцию replicateM, а не mapM с использованием списка в качестве счётчика.
3. Упросить код для записи строк в файл: intercalate "n" = unlines.
4. Поскольку генератор основан на контекстно-свобоных порождающих грамматиках, его очень сложно использовать для порождения правильных длинных текстов, в которых разные части, расположенные далеко друг от друга, согласованы. Для этого либо надо использовать очень громоздкие правила, либо вводить в DSL различные конструкции и переменные. Но чем тогда такой DSL будет отличаться от самого языка Haskell?
5. Тем не менее, в DSL для генерации можно вставить условные конструкции, а также оператор для случайной перестановки элементов списка. Это позволит в некоторых случаях упростить правила порождающей грамматики и одновременно с этим увеличить разнообразие генерируемых текстов.

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

Все желающие могут невозбранно скачать полные модули с приведёнными в данной статье программными сущностями здесь ^[7] и здесь ^[8].

Не могу не напомнить, что у Фонда Поддержки Функционального Программирования ФП(ФП) теперь есть свой официальный форум, на котором невозбранно зарегистрироваться и пообщаться с единомышленниками можно здесь ^[9].

Ну и если вы хотите дополнительно отблагодарить автора, но не знаете как, то можете ознакомиться с возможностями по данной ссылке ^[10].

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

• Решение задачи о перегорающих лампочках на языке Haskell ^[11]
• Фреймворк для решения задач о переправах на языке Haskell ^[12]
• Конструирование и вычисление арифметических выражений на языке Haskell ^[13]
• Расшифровка кода на языке Haskell (конкурс по ФП в январе 2012) ^[14]
• Шахматные задачи на мат в один ход: решение на языке Haskell ^[15]
• Измерение объёмов при помощи двух заданных сосудов: решение на языке Haskell ^[16]
• Трансмутации слов друг в друга: решение на языке Haskell ^[17]

Автор: Darkus