Ru/Problem K
< Ru
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Эта программа решает так называемую "задачу К", используемую в секретных лабораториях КГБ для отбора сверхлюдей ("людей К"), направляемых для работы за границу
Описание задачи
Маленький Эксель
----------------
Необходимо реализовать простую электронную таблицу в виде программы, выполняющейся
из командной строки. Она должна уметь обрабатывать ячейки таблицы как и более
продвинутые аналоги, только с упрощенным синтаксисом выражений. Каждая ячейка
может содержать:
- Ничего
- Неотрицательное целое число
- Текстовые строки, которые начинаются с символа '
- Строки-выражения, которые начинаются с символа '=' и могут содержать
неотрицательные целые числа, ссылки на ячейки и простые арифметические
выражения. Скобки запрещены, у всех операций одинаковый приоритет.
Ссылки на ячейки состоят из одной латинской буквы и следующей за ней
цифры.
Эти ограничения введены для упрощения разбора выражений, поскольку разбор
выражений не является основной частью проблемы. Вы можете спокойно
положиться на эти ограничения. Вот грамматика содержимого ячейки:
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++ необходимо
вывести кое-какие условия, о которых умолчано в задании, затем тщательно проанализировать
все условия вместе и принять пять ключевых решений по выбору того или иного пути реализации.
Решение
Наиболее интересной особенностью решения является то, что вся обработка ошибок сосредоточена в комбинаторе 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
Тесты
Я расширил тестовый пример несколькими некорректными выражениями:
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