Alguns meses atrás, um artigo apareceu no blog da Yandex que discutia a passagem da seção algorítmica da entrevista. Entre outras coisas, neste artigo, foi fornecido um link para um concurso especial contendo tarefas semelhantes às oferecidas pelo Yandex aos seus candidatos.
Tendo me registrado no sistema, minha atenção foi imediatamente atraída pela capacidade de resolver problemas no Haskell. O fato é que, embora eu goste de programar nessa linguagem, não progredi além da implementação de tarefas de vários cursos de plataformas educacionais on-line. Tendo decidido que a solução deles pode ser um desafio interessante e aumentará meu nível como desenvolvedor, passei a resolvê-los.
Quem se importa com o que acabou por vir, bem-vindo ao gato.
A. Pedras e jóias
Duas linhas de caracteres latinos minúsculos são fornecidas: cadeia J e cadeia S. Os caracteres incluídos na cadeia J são “jóias” e incluídos na cadeia S são “pedras”. É necessário determinar quantos caracteres de S são simultaneamente "jóias". Simplificando, você precisa verificar quantos caracteres de S estão em J.
A primeira tarefa é um aquecimento, vamos resolvê-lo “na testa”. Definimos a função jeweleryCount :: String -> String -> Int , que, usando a convolução da lista passada pelo segundo argumento, resume todos os casos do item que está sendo processado na primeira lista. Para esses fins, definimos a função elemInt com base na função elem , que, diferentemente da última, retornará não Verdadeiro ou Falso, mas o número 0 ou 1. Na função principal, você só precisa ler duas linhas, passá-las para a função correspondente e imprimir o resultado. O veredicto do sistema de teste está OK, passamos para a segunda tarefa.
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
O código fonte para resolver esta e outras tarefas também está disponível no repositório do github.
B. Unidades consecutivas
É necessário encontrar a seqüência mais longa de unidades no vetor binário e imprimir seu comprimento.
Para resolver esse problema, implementamos uma função recursiva que percorre a lista transferida e calcula o comprimento da sequência necessária. Com os argumentos da função, além da própria lista, transmitiremos o comprimento máximo atual e o número de unidades consecutivas na chamada atual. Primeiro, definimos a base da recursão na lista vazia e, em seguida, a própria recursão.
Para ler a entrada, definimos a função getUserInputs :: IO [Char] , na qual lemos primeiro o número n - o tamanho da lista e, em seguida, usando o combinador replicateM , obtemos uma função que chama a função <<get> getLine n times e mescla os resultados em uma lista .
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
Nós enviamos a decisão, o veredicto está OK. Nós seguimos em frente.
C. Remoção duplicada
É fornecida uma matriz de números inteiros de 32 bits ordenados em ordem não decrescente. É necessário remover todas as repetições dele.
Vamos começar com uma implementação simples. Definimos uma função inicial que lê um número, o imprime e o retorna envolto na mônada de E / S. Também definimos a função deleteDoubles :: Int -> Int -> IO () , que lê um número e o imprime apenas se não for igual ao segundo argumento (passaremos o número lido na etapa anterior). Depois disso, a função se chama recursivamente e, assim, prossegue para o próximo número no fluxo de entrada. A base de recursão é o número de números a serem lidos; passaremos para o primeiro argumento.
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)
Enviamos a solução, ela passa em todos os testes e parece que podemos passar para a próxima tarefa, mas, na minha opinião, a chamada recursiva da função que trabalha na mônada de IO é mais confusa do que concisa. Vamos tentar melhorá-lo.
Observe que, de um modo geral, você pode primeiro ler a lista inteira de números (usaremos o combinador replicateM já familiarizado com a segunda tarefa), depois passá-lo para uma função pura que filtra todas as repetições e, finalmente, imprime o resultado.
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
Estou enviando uma solução e a primeira decepção é que o programa não passa no teste 193 devido a exceder o limite de memória usada. O principal erro é ler a lista inteira na memória completamente. Vamos tentar evitar isso e implementar um certo híbrido da primeira e da segunda versões.
Observe que a tarefa de remover duplicatas lembra um pouco a convolução associativa à esquerda: em cada etapa calculamos uma função que, dependendo do item atual lido e de alguns de seus resultados, na etapa anterior decide imprimir e prossegue para o próximo par de valores.
Uma função que imprime ou não imprime o resultado dependendo de seus argumentos, após o qual retorna seu segundo argumento, envolto na mônada IO, é bastante simples, vamos chamá-lo de etapa:
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd
Nós descobrimos se devemos ou não imprimir, dependendo dos valores passados, mas como organizar a leitura? Para fazer isso, usamos a função de convolução monádica foldM :: (Foldable t, Monad m) => (b -> a -> mb) -> b -> ta -> mb , aplicável à lista de funções de leitura.
Por tipo de função foldM, notamos que a cada passo a “descompactação” do resultado da aplicação anterior da função ocorre sob o capô da própria foldM. Assim, em cada etapa, precisamos apenas iniciar um cálculo monádico do item da lista atual (de fato, ler o próximo número) usando o operador de ligação ( >> = ) e passá-lo junto com o número anterior para a etapa. Como resultado, obtemos o seguinte programa
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. Geração de sequências de colchetes
Dado um número inteiro n. É necessário derivar todas as seqüências de colchetes corretas de comprimento 2 ⋅ n, ordenadas lexicograficamente (consulte https://ru.wikipedia.org/wiki/Lexographic_order ).
Somente parênteses são usados na tarefa.
É aconselhável obter uma solução que funcione em um tempo proporcional ao número total de seqüências de colchetes corretas na resposta e, ao mesmo tempo, use uma capacidade de memória proporcional a n.
Essa tarefa, como muitas outras, nas quais é necessário derivar seqüências que atendam a certas condições (por exemplo, a tarefa de trocar moedas, organizar oito rainhas e outras, pode ser lida com mais detalhes aqui ), é resolvida de forma sucinta usando a lista mônada. Em suma, essa abordagem é baseada na ligação monádica para listas, cujo significado é unir o conjunto de operações realizadas em cada elemento da lista.
Defina a função recursiva generate ':: Int -> Int -> [[Char]] , que leva o número de colchetes a serem colocados como segundo argumento e o número de colchetes de abertura não fechados já definido. Para a etapa de recursão, precisamos de duas funções auxiliares: possível - retorna uma lista de colchetes que podem ser colocados na próxima etapa e etapa - faz uma chamada recursiva para a função generate 'com os parâmetros necessários.
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
Enviamos a solução e entendemos que não levamos em conta a restrição que foi imposta à quantidade de memória usada pelo programa - a solução não passa no 14º teste por exceder o limite de memória usada.
Modificamos a função generate 'para que, em vez de construir toda a lista de sequências de colchetes corretas, ela as exiba imediatamente na tela. Para fazer isso, teremos que adicionar o terceiro argumento à função - um fragmento da sequência construída para a etapa atual. Observo que, nesta implementação, construiremos a sequência na ordem inversa - isso nos permitirá usar o construtor list ( :) em vez do operador de concatenação mais caro ( ++ ).
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. Anagramas
Duas linhas são dadas, consistindo em letras latinas minúsculas. É necessário determinar se essas linhas são anagramas, ou seja, elas diferem apenas na sequência de caracteres.
Para resolver esse problema, contaremos quantas vezes uma carta ocorre em cada linha e comparamos os resultados. Entendemos imediatamente que as listas padrão não são adequadas para nós e é necessário usar uma estrutura de dados que nos permita acessar efetivamente o elemento pelo seu índice. Existem vários tipos de dados que satisfariam nossas condições, mas usaremos a matriz imutável padrão Data.Array (ainda existem pelo menos várias matrizes mutáveis, bem como Data.Vector ).
Para construir as matrizes necessárias, usamos a função hist :: (Ix a, Num b) => (a, a) -> [a] -> Matriz ab , que, de acordo com a lista transferida de elementos e o intervalo ao qual esses elementos devem pertencer, forma uma matriz, que armazena o número de repetições de elementos da lista. Essa função, embora não esteja incluída no módulo Data.Array, geralmente é fornecida como um exemplo do uso de outra função já existente na biblioteca, o acumArray. Só podemos copiar sua implementação e escrever main - o benefício da comparação de igualdade para Array Char Int já está definido. Chamo sua atenção para um recurso interessante - como índice, podemos usar não apenas números inteiros, mas também qualquer representante da classe Ix . No nosso caso, Char desempenha um papel natural nesse papel.
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. Mesclar k listas ordenadas
Dadas k matrizes de números inteiros não negativos classificadas em ordem não decrescente, cada uma das quais não excede 100. É necessário construir o resultado de sua fusão: uma matriz classificada em ordem não decrescente contendo todos os elementos das matrizes k originais.
O comprimento de cada matriz não excede 10 k.
Tente fazer a solução funcionar pelo tempo k ⋅ log (k) ⋅ n, se assumirmos que as matrizes de entrada são de comprimento n.
Mesclar duas listas ordenadas é uma tarefa clássica da lista e é abordada em muitos cursos sobre programação Haskell. Por exemplo, pode ser resolvido da seguinte maneira.
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
Bem, podemos mesclar duas listas. E o que devemos fazer com a lista de listas? Convolva-o com esta função! Assim, combinaremos todas as listas em uma e teremos apenas que imprimi-las.
Solução 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
Entretanto, esta solução tem dois problemas sérios - a complexidade computacional é maior que a necessária - O (k ^ 2 ⋅ n) em vez de O (k ⋅ log (k) ⋅ n) , além de usar muita memória adicional. Como resultado, esta solução falha no número de teste 17 devido a exceder o limite de memória usada - 17,27 Mb em vez dos 10 Mb permitidos.
Embora não prestemos atenção ao fato de que os números fornecidos à entrada pertencem a um intervalo limitado de valores, continuamos a procurar soluções para um caso mais geral.
O próximo passo é tentar implementar a abordagem proposta no artigo original com a análise dessas tarefas. Deixe-me lembrá-lo de que é baseado no uso de uma estrutura de dados que fornece uma maneira eficiente de extrair o elemento mínimo. Como tal estrutura, selecione Data.Set . Inicializamos Set com a lista dos primeiros elementos; em cada etapa, extraímos e imprimimos o elemento mínimo e, em seguida, adicionamos o próximo elemento da lista correspondente. Além disso, precisaremos de uma estrutura Data.Sequence para armazenar as próprias listas. Foi escolhido por razões de que, em cada etapa, é necessário ter acesso rápido à lista por seu índice (que a lista não pode fornecer) e alterar o elemento desse elemento sem a necessidade de copiar toda a estrutura (que em geral não pode fornecer Dados imutáveis . Matriz ).
Assim, temos o seguinte programa:
Solução 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
Enviamos a solução e descobrimos que, embora o programa tenha começado a consumir muito menos memória (10,26 Mb em vez de 17,27 Mb no 17º teste), ele ainda não atingiu o limite. A razão disso está no fato de que, com essa decisão, de uma forma ou de outra, precisamos ler todos os dados de entrada na memória. Vamos tentar evitar isso com a ajuda da terceira solução para esse problema - classificando por contagem.
Já executamos a contagem do número de caracteres recebidos ao resolver o problema anterior do anagrama. Além disso, como para resolvê-lo, usaremos Data.Array . Primeiro, implementamos a função addToArray :: Array Int Int -> [Int] -> Array Int Int , que forma uma matriz com base na existente, aumentando os valores nos índices que correspondem aos valores da lista.
addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]
Em seguida, usaremos a abordagem conhecida por nós no problema de remover repetições - usando a convolução monádica, aplicando sequencialmente a função addToArray em k matrizes de origem. E ... obtemos o mesmo resultado de 10,26 Mb no 17º teste. E então é hora de lembrar que foldl (cujo análogo é foldM ) de acordo com a ordem de redução aceita primeiro expandirá toda a cadeia de expressões aninhadas e só então prosseguirá para o cálculo ativo. Como você sabe, para combater esse fato, o módulo Data.List implementa a função foldl ' , que usa a função seq :: a -> b -> b , que primeiro lança o primeiro argumento na forma normal da cabeça fraca, ou seja, reduz a parte externa - o valor da função ou construtor e, em seguida, retorna o segundo ( https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ). Não temos escolha a não ser implementar a função foldM 'independentemente .
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
Como resultado, a quantidade de memória usada no 17º teste quase caiu pela metade e totalizou 5.64Mb! Embora os testes 17 e 18 tenham sido aprovados com êxito, essa implementação não passou no 19º teste pelo mesmo motivo que o limite de memória foi excedido - 10,25Mb.
Ok, siga em frente - ainda não experimentamos o Data.Array.Unboxed. Esse tipo de matriz é digno de nota, pois, diferentemente do padrão, ele pode armazenar os próprios valores, em vez de apontar para eles ( https://wiki.haskell.org/Arrays#Unboxed_arrays ). Devido a isso, essas matrizes ocupam menos espaço de memória e são mais eficientes. Para usá-los, precisamos apenas alterar os tipos de importação e função, pois o Data.Array e o Data.Array.Unboxed implementam uma interface de matrizes imutáveis do IArray .
Estamos enviando uma solução - o consumo de memória diminuiu 4,5 vezes para 2,26 MB, mas não ultrapassou o limite de tempo - o tempo de execução foi de 1,09 segundos. Com o que isso poderia estar conectado? A julgar pelo fato de que o tempo de execução dos testes restantes permanece o mesmo, acho que o motivo não é que a matriz sem caixa tenha sido mais lenta que a caixa, mas em particular o sistema de teste. Parece que a tarefa é interrompida assim que uma das restrições é violada. No entanto, em casos muito raros, essa implementação ainda passa no 19º teste com um resultado de 0,98 segundos, mas falha no teste número 20 também devido ao excedente do prazo.
Depois disso, tentei usar o analógico inseguro da função acum, que em teoria deveria ser mais rápido, vários métodos de buffer (função hSetBuffering :: Handle -> BufferMode -> IO () ), matrizes mutáveis de IOArray , mas nenhum desses métodos produziu resultados .
Não estou inclinado a acreditar que os limites para Haskell são muito rígidos e espero que ainda exista uma solução que passe em todos os testes. No repositório do projeto, publiquei várias versões diferentes do código para resolver esse problema (com Array e IOArray), talvez este seja o ponto de partida para uma solução que passará em todos os testes.
Conclusão
Mesmo apesar de apenas cinco das seis tarefas terem me sucumbido, concluí minha tarefa principal - praticar a programação funcional. Não menos importante foi o papel de severas restrições aos recursos consumidos pelo programa, o que nos forçou a procurar cada vez mais novas abordagens para solucionar problemas. Espero que a descrição deles seja útil para aqueles que estão começando sua jornada na programação funcional
A abordagem funcional foi conveniente para resolver esses problemas? Honestamente, tenho uma dupla impressão. Por um lado, as soluções para a maioria dos problemas se mostraram muito concisas e as ferramentas expressivas do próprio Haskell, bem como de sua rica biblioteca padrão, tiveram um papel significativo nisso. Por outro lado, não se pode deixar de admitir que, na maioria dos casos, o gerenciamento de recursos consumidos pode ser um determinado problema, o que não permitirá solucionar o problema nas restrições especificadas.