Personal tools

Ru/Problem K

From HaskellWiki

< Ru
Jump to: navigation, search

Эта программа решает так называемую "задачу К", используемую в секретных лабораториях КГБ для отбора сверхлюдей ("людей К"), направляемых для работы за границу

Contents

1 Описание задачи

Маленький Эксель
----------------

Необходимо реализовать простую электронную таблицу в виде программы, выполняющейся
из командной строки. Она должна уметь обрабатывать ячейки таблицы как и более
продвинутые аналоги, только с упрощенным синтаксисом выражений. Каждая ячейка
может содержать:
 - Ничего
 - Неотрицательное целое число
 - Текстовые строки, которые начинаются с символа '
 - Строки-выражения, которые начинаются с символа '=' и могут содержать
   неотрицательные целые числа, ссылки на ячейки и простые арифметические
   выражения. Скобки запрещены, у всех операций одинаковый приоритет.
   Ссылки на ячейки состоят из одной латинской буквы и следующей за ней
   цифры.

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

      expression ::= '=' term {operation term}*
      term ::= cell_reference | nonnegative_number
      cell_reference ::= [A-Za-z][0-9] -- 
      operation ::= '+' | '-' | '*' | '/'
      text ::= '\'' {printable_character}

Процесс обработки:
 - Все выражения должны быть заменены на вычисленный результат.
 - Все вычисления выполняются с помощью целочисленной арифметики со знаком.
 - Ячейки с текстом должны быть вычислены как соответствующий текст без
   префикса '.
 - Операции над строками текста запрещены.
 - В случае любой ошибки вычисления формулы, вычисляемая ячейка должна содержать
   слово-сообщение об ошибке, начинающееся с символа '#'. Используйте короткие,
   ясные сообщения. Не надо предоставлять подробности об ошибках в выводе.

Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.


Ввод и вывод
------------

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


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

Пример данных:
3            4
12          =C2       3       'Sample
=A1+B1*C1/5 =A2*B1    =B3-C3  'Spread
'Test       =4-3      5       'Sheet

Ожидаемый вывод:
12      -4      3       Sample
4       -16     -4      Spread
Test    1       5       Sheet


Указания по решению
-------------------
Необходимо промышленное качество кода. Более короткое и читаемое решение
предпочтительней. Решение должно содержать тестовые примеры и код, использованные
в процессе создания решения. Не забудьте откомментировать код в ключевых
местах. Код должен быть устойчив к ошибкам.

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

Вам необходимо будет указать, какие изменения необходимо сделать для
реализации второй фазы проекта.

Вот. С этой задачей в одной конторе не справился ни один из тех, кому ее давали.
Точнее, не справился в полном объеме. После более или менее успешного ее решения
проводилось интервью. Задача использовалась для выявления потенциальных архитекторов.

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


2 Решение

Наиболее интересной особенностью решения является то, что вся обработка ошибок сосредоточена в комбинаторе reliable, остальная часть программы написана в безнадёжном стиле

-- чистое время решения задачи - 8 часов
import Prelude hiding (catch)
import Control.Exception
import Data.Char
import Data.Graph
import Data.List
import Data.Function (on)
import Data.Ord (comparing)
 
-----------------------------------------------------------------------------------------------
-- Мини-библиотека ----------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------
 
mapSnds         = map.mapSnd
mapSnd  f (a,b) = (a,f b)
groupOn f       = groupBy ((==) `on` f)
sortOn  f       = sortBy  (comparing f)
a.$b = b a
 
-- Вычислить (f x), возвращая вместо ошибок при вычислении errValue
reliable :: (x->y) -> y -> x -> IO y
reliable f errValue x  =  (evaluate$ f x) `catch` (\_ -> return errValue)
 
 
 
-----------------------------------------------------------------------------------------------
-- Типы данных --------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------
 
-- Таблица, содержимое ячеек которой представлено типом a
type Sheet a = [NamedCell a]
-- Отображение содержимого ячеек
mapSheet  f = mapSnds f
mapSheetM f = mapM (\(a,b) -> do fb <- f b; return (a,fb))
 
-- Поименованная ячейка
type NamedCell a = (CellName,a)
 
-- Имя ячейки (такое, как "a1")
type CellName = String
 
-- Содержимое ячейки: пусто/строка/выражение/ошибка
--   a = Expr Int   до вычислений по формулам
--   a = Int        после вычислений
data Cell a  =  EmptyCell | StringCell String | ExprCell a | ErrorCell String
 
-- AST выражения, имеющего тип a
data Expr a  =  BinOp (BinOp a) (Expr a) (Expr a)
             |  RefCell CellName
             |  Const a
 
-- Бинарная операция
type BinOp a  =  a->a->a
-- Превращение строковой записи в бинарную операцию
cvt "+" = (+)
cvt "-" = (-)
cvt "*" = (*)
cvt "/" = div
 
-- Список ячеек, на которые ссылается Expr
refs (BinOp   _ x y)  =  refs x++refs y
refs (RefCell name)   =  [name]
refs (Const   _)      =  []
 
 
-----------------------------------------------------------------------------------------------
-- Программа ----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------
--main = interact$ fromSheet.mapSheet showCell.calcSheet.removeCycles.mapSheet parseCell.toSheet
 
 
main = do
    input <- getContents
    -- Конвертирует входной формат данных в таблицу строк
    let inputSheet      = toSheet input                   :: Sheet String
    -- Проводит парсинг содержимого каждой ячейки
    parsedSheet <- mapSheetM (reliable parseCell (ErrorCell "#PARSING")) inputSheet
                                                          :: IO (Sheet (Cell (Expr Int)))
    -- Заменяет формулы в циклически зависящих ячейках на сообщения об ошибке
    let acyclicSheet    = removeCycles parsedSheet        :: Sheet (Cell (Expr Int))
    -- Вычисляет формулы в ячейках
    let calculatedSheet = calcSheet acyclicSheet          :: Sheet (Cell Int)
    -- Заменяет результат вычисления в каждой ячейке его текстовым представлением
    outputSheet <- mapSheetM (reliable showCell "#EVAL") calculatedSheet  :: IO (Sheet String)
    -- Конвертирует таблицу строк в выходной формат данных
    putStrLn (fromSheet outputSheet)
 
 
 
-- Превращает входные данные в список пар (имя ячейки, её содержимое):
--   [ ("a1", "2"), ("a2", "=a1+1"),  ("b1", "=a2+1"), ("b2", "=b1") ]
toSheet :: String -> Sheet String
toSheet input  =  enumSheet xs  where
   -- xs - тексты ячеек, разбитые построчно
   xs :: [[String]]
   x:xs = map words$ lines input
   -- число строк/столбцов в таблице, записанное в первой строке ввода
   -- [rows,cols] = map read x
   -- Перенумеровать все ячейки таблицы
   enumSheet :: [[a]] -> Sheet a
   enumSheet = concat . zipWith enumRow [1..]
   -- Перенумеровать ячейки строки num
   enumRow :: Int -> [a] -> [NamedCell a]
   enumRow num = zipWith (enumCell num) ['a'..]
   -- Занумеровать ячейку столбца letter строки num
   enumCell :: Int -> Char -> a -> NamedCell a
   enumCell num letter cell = (letter:show num, cell)
 
 
 
-- Парсит содержимое ячейки, превращая входную строку во внутреннее представление
parseCell :: String -> Cell (Expr Int)
parseCell "\"\""                      =  EmptyCell
parseCell ('\'':xs)                   =  StringCell xs
parseCell ('=':xs)                    =  ExprCell$ parseExpr xs
parseCell xs        | all isDigit xs  =  ExprCell$ Const (read xs)
 
-- Парсит выражение (начинающееся с '=')
parseExpr :: (Integral a, Read a) =>  String -> Expr a
parseExpr = build.reverse.split where
  -- разбивает строку на список строк [терм,операция,терм,операция...терм]
  split xs | null rest  =  [xs]
           | otherwise  =  x:op:split rest1
    where (x,rest)   = span isAlphaNum xs
          (op,rest1) = break isAlphaNum rest
  -- строит Expr из списка термов/операций (заменить на вызов fold*!)
  build (x:op:xs)  =  BinOp (cvt op) (build xs) (term x)
  build [x]        =  term x
  -- парсит терм = число | имя ячейки
  term xs | all isDigit xs  =  Const (read xs)
          | otherwise       =  RefCell (map toLower xs)
 
 
 
-- Заменяет циклически зависимые ячейки на сообщения об ошибке
removeCycles :: Sheet (Cell (Expr Int)) -> Sheet (Cell (Expr Int))
removeCycles  =  concatMap replaceCycles . topSort  where
  -- Выделить группы ячеек с циклическими зависимостями
  topSort :: Sheet (Cell (Expr Int)) -> [SCC (CellName, Cell (Expr Int))]
  topSort = stronglyConnComp . map f
                where -- f вычисляет, на какие ячейки ссылается эта
                      f x = (x, fst x, refs1 (snd x))
                      refs1 (ExprCell e) = refs e
                      refs1 _            = []
  -- Заменить содержимое циклически зависимых ячеек на сообщения об ошибке
  replaceCycles :: SCC (CellName, Cell (Expr Int)) -> [(CellName, Cell (Expr Int))]
  replaceCycles (AcyclicSCC cell)   =  [cell]
  replaceCycles (CyclicSCC  cells)  =  mapSnds (const$ ErrorCell "#CYCLE") cells
 
 
 
-- Заменяет формулы в ячейках на результаты их вычисления
calcSheet :: Sheet (Cell (Expr Int)) -> Sheet (Cell Int)
calcSheet sheet = result  where
  -- Таблица, в которой формулы заменены результатами их вычислений
  result :: Sheet (Cell Int)
  result = mapSnds calcCell sheet
  -- Замена формулы в ячейке на результат её вычисления
  calcCell :: Cell (Expr Int) -> Cell Int
  calcCell EmptyCell       =  EmptyCell
  calcCell (StringCell s)  =  StringCell s
  calcCell (ExprCell   e)  =  ExprCell   (calc e)
  calcCell (ErrorCell  s)  =  ErrorCell  s
  -- Вычисление значения выражения
  calc :: Expr Int -> Int
  calc (Const x)       =  x
  calc (BinOp op x y)  =  op (calc x) (calc y)
  calc (RefCell x)     =  answer
                            where Just (ExprCell answer) = lookup x result
 
 
 
-- Выводит текстовое представление вычисленной ячейки
showCell :: Cell Int -> String
showCell EmptyCell       =  "\"\""
showCell (StringCell s)  =  s
showCell (ExprCell x)    =  show x
showCell (ErrorCell s)   =  s
 
 
-- Конвертирует таблицу строк в выходной формат данных
fromSheet :: Sheet String -> String
fromSheet xs = xs.$ sortOn  (tail.fst)          -- Разбить ячейки на rows
                 .$ groupOn (tail.fst)          -- ..
                 .$ map (unwords.map snd.sort)  -- Текстовое представление каждого row
                 .$ unlines                     -- Слить текстовые представления rows

3 Тесты

Я расширил тестовый пример несколькими некорректными выражениями:

7 4
12 =C2 3 'Sample
=A1+B1*C1/5 =A2*B1 =B3-C3 'Spread
'Test =4-3 5 'Sheet
"" =A9 =1/0 =A5
=B5 =1+C6+1 =5A =A1++A1
=1+ x =A5 =A6+B6
=a1 =a3 =a4 =a5 

Вывод программы должен быть:

12 -4 3 Sample
4 -16 -4 Spread
Test 1 5 Sheet
"" #EVAL #EVAL #EVAL
#CYCLE #CYCLE #EVAL #EVAL
#EVAL #PARSING #CYCLE #EVAL
12 #EVAL #EVAL #EVAL

4 Ссылки