几个月前，Yandex博客上发表了一篇文章 ，讨论了采访算法部分的通过。 除其他外，在本文中，链接指向了一个特殊竞赛，其中包含类似于Yandex向其候选人提供的任务的任务。
在系统中注册后，解决Haskell问题的能力立即吸引了我的注意力。 事实是，尽管我喜欢用这种语言进行编程，但除了在各种在线教育平台课程中执行任务之外，我没有取得什么进步。 认为他们的解决方案可能是一个有趣的挑战，并将提高我作为开发人员的水平之后，我着手解决了它们。
谁在乎它的最终结果，欢迎来关注。
A.石头和珠宝
给出了两行小写拉丁字符：字符串J和字符串S。字符串J中包含的字符是“珠宝”，字符串S中包含的字符是“石头”。 有必要确定S中有多少个字符同时是“珠宝”。 简而言之，您需要检查J中有多少个S字符。
第一个任务是热身，我们将“在额头上”解决。 我们定义函数jewelleryCount :: String-> String-> Int ，该函数使用第二个参数传递的列表的卷积，对第一个列表中正在处理的项目的所有情况进行汇总。 为此，我们基于elem函数定义elemInt函数，与最后一个函数不同的是， elemInt函数将不返回True或False，而是返回数字0或1。在main函数中，您只需要读取两行，并将它们传递给相应的函数并打印结果即可。 测试系统的判定是可以的，我们转到第二项任务。
jeweleryCount :: String -> String -> Int jeweleryCount j = foldr ((+).(elemInt j)) 0 where elemInt sx = fromEnum $ elem xs main :: IO () main = do j <- getLine s <- getLine print $ jeweleryCount js
github存储库中也提供了用于解决此任务和其他任务的源代码。
B.连续单位
需要找到二进制向量中最长的单位序列并打印其长度。
为了解决这个问题，我们实现了一个递归函数，该函数将遍历传输的列表并计算所需序列的长度。 使用函数的参数，除了列表本身，我们还将传递当前的最大长度和当前调用中的连续单位数。 首先，我们基于空列表定义递归，然后递归步骤本身。
要读取输入，我们定义函数getUserInputs :: IO [Char] ，在该函数中，我们首先读取数字n-列表的大小，然后使用组合器plicateM获得一个函数，该函数将调用函数<< get> getLine n次，并将结果合并到列表中。
import Control.Monad (replicateM) onesCount :: [Char] -> Int onesCount xs = onesCount' xs 0 0 where onesCount' "" max curr | max > curr = max | otherwise = curr onesCount' (x:xs) max curr | x == '1' = onesCount' xs max $ curr + 1 | curr > max = onesCount' xs curr 0 | otherwise = onesCount' xs max 0 getUserInputs :: IO [Char] getUserInputs = do n <- read <$> getLine :: IO Int replicateM n $ head <$> getLine main :: IO () main = do xs <- getUserInputs print $ onesCount xs
我们发送决定，判决是可以的。 我们继续前进。
C.重复删除
32位整数数组以非降序排列。 您要从中删除所有重复项。
让我们从一个简单的实现开始。 我们定义一个初始函数，该函数读取一个数字，打印该数字，然后将其包装在IO monad中返回。 我们还定义了deleteDoubles :: Int-> Int-> IO（）函数，该函数读取一个数字并仅在它不等于第二个参数时才打印该数字（我们将在那里传递上一步中读取的数字）。 之后，该函数递归地调用自身，从而前进到输入流中的下一个数字。 递归基数是要读取的数字数，我们将其传递给第一个参数。
import Control.Monad initial :: IO Int initial = do a <- read <$> getLine print a return a deleteDoubles :: Int -> Int -> IO() deleteDoubles 0 _ = return () deleteDoubles ta = do b <- read <$> getLine unless (a == b) $ print b deleteDoubles (t-1) b main :: IO () main = do t <- read <$> getLine unless (t < 1) $ initial >>= deleteDoubles (t-1)
我们发送了解决方案，它通过了所有测试，似乎可以继续执行下一个任务，但是在我看来，在IO monad中运行的函数的递归调用比简洁更为令人困惑。 让我们尝试改善它。
请注意，通常来讲，您可以首先读取整个数字列表（我们将使用已经熟悉第二个任务的copyM组合器），然后将其传递给一个纯函数，该函数过滤掉所有重复项，最后打印结果。
import Control.Monad deleteDoubles' _ [] = [] deleteDoubles' prev (x:xs) | prev /= x = x:(deleteDoubles' x xs) | otherwise = deleteDoubles' x xs deleteDoubles (x:xs) = x:deleteDoubles' x xs getUserInputs :: Int -> IO [Int] getUserInputs t = replicateM t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ (deleteDoubles <$> getUserInputs t) >>= mapM_ print
我提出了一个解决方案，但让我失望的是该程序由于超出了已用内存的限制而没有通过193测试。 主要错误是将整个列表读入整个内存。 我们将尝试避免这种情况，并将实现第一版和第二版的某种混合形式。
请注意，删除重复项的任务在某种程度上让人联想到左联想卷积：在每一步中，我们计算一个函数，该函数根据读取的当前项及其某些结果，在上一步决定打印，然后继续进行下一对值。
一个函数根据其参数打印或不打印结果，然后返回包装在IO monad中的第二个参数，该函数非常简单，我们将其称为步骤：
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd
我们根据传递的值确定了是否要打印，但是如何组织读数？ 为此，我们使用单子卷积函数foldM ::（可折叠t，单子m）=>（b-> a-> mb）-> b-> ta-> mb ，它适用于读取函数列表。
通过函数foldM的类型，我们注意到在每个步骤中，函数的先前应用的结果的“拆包”都发生在foldM本身的内部。 因此，在每一步中，我们只需要使用bind运算符（ >> = ）对当前列表项进行单子计算（实际上，读取下一个数字），并将其与前一个数字一起传递给步骤。 结果，我们得到以下程序
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd initial :: IO Int initial = do a <- read <$> getLine print a return a getUserInputs t = replicate t $ read <$> getLine main :: IO () main = do t <- read <$> getLine unless (t < 1) $ do init <- initial foldM_ ((=<<) . step) init $ getUserInputs (t-1)
D.括号序列的生成
给定整数n。 需要导出所有正确的长度为2⋅n的括号序列，按字典顺序排序（请参阅https://ru.wikipedia.org/wiki/Lexographic_order ）。
任务中仅使用括号。
建议获得一个在与响应中正确的括号序列的总数成比例的时间内工作的解决方案，同时使用与n成比例的存储容量。
与许多其他任务一样，必须导出满足某些条件的序列（例如，可以在此处更详细地阅读交换硬币，安排八个皇后和其他女王的任务），该任务可以使用列表monad简洁地解决。 简而言之，此方法基于列表的单子绑定，其含义是将对列表的每个元素执行的一组操作结合在一起。
定义一个递归函数generate':: Int-> Int-> [[Char]] ，该函数将要放入括号的数目作为第二个参数，并将已经设置为第一个参数的开放括号的数目。 对于递归步骤，我们需要两个辅助功能： 可能 -返回可以在下一步中放置的括号列表，以及步骤 -使用必要的参数对generate'函数进行递归调用。
import Control.Monad(mapM_) generate :: Int -> [String] generate = generate' 0 where generate' _ 0 = [[]] generate' an = [x:xs | x <- possible, xs <- step x] where step '(' = generate' (a + 1) (n - 1) step ')' = generate' (a - 1) (n - 1) possible | n == a = ")" | a == 0 = "(" | otherwise = "()" main :: IO () main = do n <- read <$> getLine let result = generate $ n * 2 mapM_ putStrLn result
我们发送了解决方案，并且我们了解到我们没有考虑对程序使用的内存量施加的限制-由于超出了已用内存的限制，该解决方案未通过第14次测试。
我们修改了generate'函数，以便与其构建正确的括号序列的整个列表，不如将它们立即显示在屏幕上。 为此，我们将必须在函数中添加第三个参数-为当前步骤构建的序列的一部分。 我注意到在此实现中，我们将以相反的顺序构造序列-这将允许我们使用列表构造函数（ :)而不是更昂贵的串联运算符（ ++ ）。
import Control.Monad(mapM_) generate :: Int -> IO() generate = generate' "" 0 where generate' xs _ 0 = putStrLn $ reverse xs generate' xs an | n == a = step ')' | a == 0 = step '(' | otherwise = step '(' >> step ')' where step '(' = generate' ('(':xs) (a + 1) (n - 1) step ')' = generate' (')':xs) (a - 1) (n - 1) main :: IO () main = do n <- read <$> getLine generate $ n * 2
E.字谜
给出了两行，由小写拉丁字母组成。 需要确定这些行是否为字谜，即它们是否仅在字符顺序上有所不同。
为了解决这个问题，我们将计算每行中出现一个字母的次数并比较结果。 我们立即了解到标准列表不适合我们，因此有必要使用一种数据结构，该结构将允许我们通过其索引有效地访问该元素。 有几种类型的数据可以满足我们的条件，但是我们将使用标准的不可变数组Data.Array （仍然至少存在各种可变数组以及Data.Vector ）。
为了构造必要的数组，我们使用函数hist ::（Ix a，Num b）=>（a，a）-> [a]-> Array ab ，根据传递的元素列表和这些元素应属于的范围，该数组形成一个数组，它存储列表中元素的重复次数。 尽管未包含在Data.Array模块中，但此函数通常作为使用另一个已经存在的库函数accumArray的示例给出。 我们只能复制其实现并编写main-数组Char Int相等性比较的好处已经定义。 我将您的注意力吸引到一个不错的功能-作为索引，我们不仅可以使用整数，而且可以使用Ix类的任何代表。 就我们而言，Char在此角色中扮演着自然的角色。
import Data.Array hist :: (Ix a, Num b) => (a,a) -> [a] -> Array ab hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i] main = do arr1 <- hist ('a','z') <$> getLine arr2 <- hist ('a','z') <$> getLine if (arr1 == arr2) then print 1 else print 0
F.合并k个排序列表
给定k个以非降序排序的非负整数数组，每个数组不超过100。构造它们合并的结果是必需的：一个以非降序排序的数组，其中包含原始k数组的所有元素。
每个数组的长度不超过10⋅k。
如果我们假设输入数组的长度为n，则尝试使解决方案在时间k⋅log（k）⋅n上起作用。
合并两个排序的列表是一项经典的列表任务，在Haskell编程的许多课程中都有介绍。 例如，可以如下解决。
merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys
好吧，我们可以合并两个列表。 列表应该怎么做？ 使用此功能进行卷积！ 因此，我们将所有列表合并为一个列表，只需要打印即可。
解决方案 import Control.Monad merge :: [Int] -> [Int] -> [Int] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys mergeLists :: [[Int]] -> [Int] mergeLists = foldl merge [] getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do k <- read <$> getLine lists <- getUserInputs k let res = mergeLists lists mapM_ (putStrLn . show) res
但是，此解决方案有两个严重的问题-计算复杂度高于所需的-O（k ^ 2⋅n）而不是O（k⋅log（k）⋅n） ，并且它使用了大量的额外内存。 结果，此解决方案由于超出了已使用的内存限制-17.27Mb（而不是允许的10Mb）而无法通过测试编号17。
尽管我们不会关注提供给输入的数字属于有限范围的值的事实，但是我们将继续寻找更通用的解决方案。
下一步是尝试通过分析这些任务来实现原始文章中提出的方法。 让我提醒您，它基于数据结构的使用，该数据结构提供了提取最小元素的有效方法。 作为这种结构，请选择Data.Set 。 我们使用第一个元素的列表初始化Set，然后在每个步骤中提取并打印最小元素，然后从相应的列表中添加下一个元素。 另外，我们将需要一个Data.Sequence结构来存储列表本身。 选择它的原因是，在每个步骤中都需要通过其索引快速访问列表（列表无法提供），并且无需复制整个结构即可更改该元素的元素（通常不能提供不变的数据）。数组 ）。
因此，我们有以下程序：
解决方案 import qualified Data.Sequence as Seq import qualified Data.Set as Set import Control.Monad import Data.Foldable mergeLists :: Set.Set (Int, Int) -> Seq.Seq [Int] -> IO () mergeLists set seq | Set.null set = return () | otherwise = do let ((val, idx), set') = Set.deleteFindMin set print val if null (Seq.index seq idx) then mergeLists set' seq else mergeLists (Set.insert (head (Seq.index seq idx), idx) set') (Seq.adjust tail idx seq) getUserInputs :: Int -> IO [[Int]] getUserInputs t = replicateM t $ do n <- getLine return $ tail $ read <$> words n main :: IO () main = do t <- read <$> getLine lists <- getUserInputs t let init_seq = Seq.fromList (filter (not . null) lists) let init_heap = Set.fromList (zipWith (,) (toList (fmap head init_seq)) [0..]) mergeLists init_heap $ tail <$> init_seq
我们发送了解决方案，发现即使程序开始消耗更少的内存（10.26Mb代替了第17个测试中的17.27Mb），它仍然没有达到限制。 这样做的原因在于，通过这种决定，我们必须以一种或另一种方式将整个输入数据读入存储器。 让我们尝试在此问题的第三个解决方案的帮助下避免这种情况-通过计数排序。
解决上一个字谜问题时，我们已经计算了传入字符的数量。 同样，在解决问题时，我们将使用Data.Array 。 首先，我们实现addToArray :: Array Int Int-> [Int]-> Array Int Int函数，该函数通过增加与列表中的值相对应的索引处的值，基于现有数组形成数组。
addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]
然后，在消除重复的任务中，我们将使用已知的方法-使用单峰卷积，将addToArray函数依次应用于k个源数组。 在第17次测试中，我们得到了10.26Mb的相同结果。 然后是时候记住， foldl （其类似物为foldM ）根据公认的归约顺序将首先扩展嵌套表达式的整个链，然后才进行它们的主动计算。 如您所知，为了解决这个问题， Data.List模块实现了foldl'函数，该函数使用函数seq :: a- > b-> b ，该函数首先将第一个参数转换为弱头范式，即将其简化为外部-函数或构造函数的值，然后返回第二个（ https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ）。 我们别无选择， 只能独立实现foldM'功能。
foldM' :: (Monad m) => (a -> b -> ma) -> a -> [b] -> ma foldM' _ z [] = return z foldM' fz (x:xs) = do z' <- fzx z' `seq` foldM' fz' xs
结果，第17次测试的已用内存量几乎减少了一半，达到5.64Mb！ 尽管成功地通过了第17和第18个测试，但是由于超出了内存限制-10.25Mb的相同原因，此实现未通过第19个测试。
好的，继续-我们还没有尝试过Data.Array.Unboxed。 值得注意的是，这种类型的数组与标准不同，它可以自己存储值，而不是指向它们的指针（ https://wiki.haskell.org/Arrays#Unboxed_arrays ）。 因此，此类阵列占用的存储空间更少，效率更高。 为了使用它们，我们只需要更改导入和函数类型，因为Data.Array和Data.Array.Unboxed实现了不可变IArray数组的一个接口。
我们正在发送一个解决方案-内存消耗减少了4.5倍，达到2.26 MB，但尚未超过时间限制-执行时间为1.09秒。 这可能与什么有关？ 从其余测试的执行时间保持不变的事实来判断，我认为原因并不是未装箱的阵列比装箱的阵列慢，而是特别是测试系统。 似乎一旦违反其中一项限制，任务就会中断。 但是，在极少数情况下，此实现仍以0.98秒的结果通过第19次测试，但由于超过了时间限制，因此未通过20号测试。
之后，我尝试使用Accum函数的不安全模拟，从理论上讲它应该更快，各种缓冲方法（ hSetBuffering :: Handle-> BufferMode-> IO（）函数），可变的IOArray数组，但是这些方法均未产生任何结果。
我不倾向于认为Haskell的限制设置得太紧，我希望仍然有一种解决方案能够通过所有测试。 在项目存储库中，我发布了用于解决此问题的几种不同版本的代码（使用Array和IOArray），也许这将是通过所有测试的解决方案的起点。
结论
尽管事实上只有六分之五的任务要我完成，但我还是完成了我的主要任务-练习函数式编程。 程序消耗的资源受到严格限制，这至少发挥了作用，这迫使我们寻找越来越多的新方法来解决问题。 我希望他们的描述对刚开始函数式编程之旅的人有用。
功能方法是否方便解决此类问题？ 老实说，我有双重印象。 一方面，解决大多数问题的方法非常简洁，Haskell本人的表达工具以及丰富的标准库在其中发挥了重要作用。 另一方面，人们不得不承认，在大多数情况下，消耗资源的管理可能是一个特定的问题，这将无法在给定的限制下解决该问题。