Il y a quelques mois, un article a paru dans le blog de Yandex qui parlait du passage de la section algorithmique de l'interview. Entre autres choses, dans cet article, un lien a été établi vers un concours spécial contenant des tâches similaires à celles proposées par Yandex à leurs candidats.
Ayant enregistré dans le système, mon attention a été immédiatement attirée par la capacité de résoudre des problèmes sur Haskell. Le fait est que bien que j'aime la programmation dans cette langue, je n'ai pas progressé plus loin que la mise en œuvre des tâches de différents cours de plateformes éducatives en ligne. Ayant décidé que leur solution pouvait être un défi intéressant et augmenterait mon niveau en tant que développeur, j'ai procédé à leur résolution.
Peu importe ce qui en est finalement arrivé, bienvenue au chat.
A. Pierres et bijoux
Deux lignes de caractères latins minuscules sont données: la chaîne J et la chaîne S. Les caractères inclus dans la chaîne J sont des «bijoux» et inclus dans la chaîne S sont des «pierres». Il est nécessaire de déterminer combien de personnages de S sont simultanément des «joyaux». Autrement dit, vous devez vérifier le nombre de caractères de S dans J.
La première tâche est un échauffement, nous allons le résoudre «sur le front». Nous définissons la fonction jewelleryCount :: String -> String -> Int , qui, en utilisant la convolution de la liste passée par le deuxième argument, résume tous les cas de l'élément en cours de traitement dans la première liste. À ces fins, nous définissons la fonction elemInt en fonction de la fonction elem , qui, contrairement à la dernière, ne renverra pas True ou False, mais le nombre 0 ou 1. Dans la fonction principale, il vous suffit de lire deux lignes, de les passer à la fonction correspondante et d'imprimer le résultat. Le verdict du système de test est OK, nous passons à la deuxième tâche.
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
Le code source pour résoudre cette tâche et d'autres tâches est également disponible dans le référentiel github.
B. Unités consécutives
Il est nécessaire de trouver la plus longue séquence d'unités dans le vecteur binaire et d'imprimer sa longueur.
Pour résoudre ce problème, nous implémentons une fonction récursive qui parcourra la liste transférée et calculera la longueur de la séquence requise. Avec les arguments de la fonction, en plus de la liste elle-même, nous passerons la longueur maximale actuelle et le nombre d'unités consécutives sur l'appel en cours. Tout d'abord, nous définissons la base de récursivité sur la liste vide, puis l'étape de récursivité elle-même.
Pour lire les données d'entrée, nous définissons la fonction getUserInputs :: IO [Char] , dans laquelle nous lisons d'abord le nombre n - la taille de la liste, puis en utilisant le combinateur replicateM nous obtenons une fonction qui appellera la fonction <<get> getLine n fois et fusionner les résultats dans une liste .
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
Nous envoyons la décision, le verdict est OK. Nous continuons.
C. Suppression des doublons
Un tableau d'entiers 32 bits classés dans l'ordre non décroissant est donné. Il est nécessaire d'en supprimer toutes les répétitions.
Commençons par une implémentation simple. Nous définissons une fonction initiale qui lit un nombre, l'imprime et le renvoie enveloppé dans la monade IO. Nous définissons également la fonction deleteDoubles :: Int -> Int -> IO () , qui lit un nombre et l' affiche uniquement s'il n'est pas égal au deuxième argument (nous passerons le nombre lu à l'étape précédente). Après cela, la fonction s'appelle récursivement et passe ainsi au numéro suivant dans le flux d'entrée. La base de récursivité est le nombre de nombres à lire, nous lui passerons le premier argument.
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)
Nous envoyons la solution, elle passe tous les tests, et il semblerait que nous pouvons passer à la tâche suivante, mais à mon avis, l'appel récursif de la fonction travaillant dans la monade IO est plus déroutant que concis. Essayons de l'améliorer.
Notez que, d'une manière générale, vous pouvez d'abord lire la liste complète des nombres (nous utiliserons le combinateur replicateM déjà familier avec la deuxième tâche), puis la passer à une fonction pure qui filtre toutes les répétitions, et enfin imprimer le résultat.
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
J'envoie une solution, et la première déception est que le programme ne passe pas le test 193 en raison du dépassement de la limite de mémoire utilisée. L'erreur principale est de lire la liste entière dans la mémoire dans son ensemble. Nous allons essayer d'éviter cela et implémenterons un certain hybride des première et deuxième versions.
Notez que la tâche de suppression des doublons rappelle quelque peu une convolution associative de gauche: à chaque étape, nous calculons une fonction qui, en fonction de l'élément lu et de certains de ses résultats, à l'étape précédente décide d'imprimer, puis passe à la paire de valeurs suivante.
Une fonction qui imprime ou n'imprime pas le résultat en fonction de ses arguments, après quoi elle retourne son deuxième argument, enveloppé dans la monade IO, est assez simple, appelons-la étape:
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd
Nous avons compris s'il fallait imprimer ou non, selon les valeurs transmises, mais comment organiser la lecture? Pour ce faire, nous utilisons la fonction de convolution monadique foldM :: (T pliable, Monade m) => (b -> a -> mb) -> b -> ta -> mb , qui s'applique à la liste des fonctions de lecture.
Par type de fonction foldM, on note qu'à chaque étape le «déballage» du résultat de l'application précédente de la fonction se produit sous le capot de foldM lui-même. Ainsi, à chaque étape, il suffit de commencer un calcul monadique de l'élément de liste actuel (en fait, lire le numéro suivant) à l'aide de l'opérateur de liaison ( >> = ) et de le transmettre avec le numéro précédent à l'étape. En conséquence, nous obtenons le programme suivant
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. Génération de séquences de parenthèses
Étant donné un entier n. Il est nécessaire de dériver toutes les séquences de parenthèses correctes de longueur 2 ⋅ n, ordonnées lexicographiquement (voir https://ru.wikipedia.org/wiki/Lexographic_order ).
Seules les parenthèses sont utilisées dans la tâche.
Il est conseillé d'obtenir une solution qui fonctionne dans un temps proportionnel au nombre total de séquences de parenthèses correctes dans la réponse, et utilise en même temps une capacité de mémoire proportionnelle à n.
Cette tâche, comme beaucoup d'autres, dans laquelle il est nécessaire de dériver des séquences qui remplissent certaines conditions (par exemple, la tâche d'échanger des pièces de monnaie, d'organiser huit reines et d'autres, peut être lue plus en détail ici ), est résumée succinctement en utilisant la liste monade. En bref, cette approche est basée sur la liaison monadique pour les listes, dont le sens est de réunir l'ensemble des opérations effectuées sur chaque élément de la liste.
Définissez une fonction récursive generate ':: Int -> Int -> [[Char]] , qui prend le nombre de parenthèses à mettre comme deuxième argument, et le nombre de parenthèses ouvertes qui sont déjà définies pour être définies comme premier argument. Pour l'étape de récursivité, nous avons besoin de deux fonctions auxiliaires: possible - retourne une liste de crochets qui peuvent être placés dans l'étape suivante, et étape - fait un appel récursif à la fonction générer avec les paramètres nécessaires.
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
Nous envoyons la solution, et nous comprenons que nous n'avons pas pris en compte la restriction qui a été imposée sur la quantité de mémoire utilisée par le programme - la solution ne passe pas le 14e test en raison du dépassement de la limite de mémoire utilisée.
Nous modifions la fonction generate pour qu'au lieu de construire la liste entière des séquences de parenthèses correctes, elle les affiche immédiatement à l'écran. Pour ce faire, nous devrons ajouter le troisième argument à la fonction - un fragment de la séquence construite pour l'étape en cours. Je note que dans cette implémentation, nous allons construire la séquence dans l'ordre inverse - cela nous permettra d'utiliser le constructeur de liste ( :) au lieu de l'opérateur de concaténation plus cher ( ++ ).
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. Anagrammes
Deux lignes sont données, composées de lettres latines minuscules. Il est nécessaire de déterminer si ces lignes sont des anagrammes, c'est-à-dire si elles diffèrent uniquement dans la séquence de caractères.
Pour résoudre ce problème, nous comptons le nombre de fois qu'une lettre apparaît dans chaque ligne et comparons les résultats. Nous comprenons immédiatement que les listes standards ne nous conviennent pas, et il est nécessaire d'utiliser une structure de données qui nous permettrait d'accéder efficacement à l'élément par son index. Il existe plusieurs types de données qui satisferaient nos conditions, mais nous utiliserons le tableau immuable standard Data.Array (il existe encore au moins divers tableaux mutables, ainsi que Data.Vector ).
Pour construire les tableaux nécessaires, nous utilisons la fonction hist :: (Ix a, Num b) => (a, a) -> [a] -> Array ab , qui, selon la liste des éléments transférés et la plage à laquelle ces éléments doivent appartenir, forme un tableau, qui stocke le nombre de répétitions d'éléments de la liste. Cette fonction, bien qu'elle ne soit pas incluse dans le module Data.Array, est souvent donnée à titre d'exemple d'utilisation d'une autre fonction de bibliothèque déjà existante, accumArray. Nous ne pouvons que copier son implémentation et écrire main - l'avantage de la comparaison pour l'égalité pour Array Char Int est déjà défini. J'attire votre attention sur une fonctionnalité intéressante - en tant qu'index, nous pouvons utiliser non seulement des entiers, mais tout représentant de la classe Ix . Dans notre cas, Char joue un rôle naturel dans ce rôle.
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
Fusionner k listes triées
Étant donné k tableaux de nombres entiers non négatifs triés par ordre non décroissant, dont chacun ne dépasse pas 100. Il est nécessaire de construire le résultat de leur fusion: un tableau trié par ordre non décroissant contenant tous les éléments des tableaux k originaux.
La longueur de chaque tableau ne dépasse pas 10 ⋅ k.
Essayez de faire fonctionner la solution pour le temps k ⋅ log (k) ⋅ n, si nous supposons que les tableaux d'entrée sont de longueur n.
La fusion de deux listes triées est une tâche de liste classique et est couverte dans de nombreux cours sur la programmation Haskell. Par exemple, il peut être résolu comme suit.
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
Eh bien, nous pouvons fusionner deux listes. Et que faire de la liste des listes? Convoluez-le avec cette fonction! Ainsi, nous combinerons toutes les listes en une seule, et nous n'aurons qu'à l'imprimer.
Solution 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
Cependant, cette solution a deux problèmes graves - la complexité de calcul est supérieure à celle requise - O (k ^ 2 ⋅ n) au lieu de O (k ⋅ log (k) ⋅ n) , en plus elle utilise beaucoup de mémoire supplémentaire. En conséquence, cette solution échoue au test numéro 17 en raison du dépassement de la limite de mémoire utilisée - 17,27 Mo au lieu des 10 Mo autorisés.
Bien que nous ne prêtions pas attention au fait que les nombres fournis à l'entrée appartiennent à une plage limitée de valeurs, et nous continuons à rechercher des solutions pour un cas plus général.
L'étape suivante consiste à essayer de mettre en œuvre l'approche qui a été proposée dans l'article d'origine avec l'analyse de ces tâches. Permettez-moi de vous rappeler qu'il est basé sur l'utilisation d'une structure de données qui fournit un moyen efficace d'extraire l'élément minimum. En tant que telle structure, sélectionnez Data.Set . Nous initialisons Set avec la liste des premiers éléments, puis à chaque étape nous allons extraire et imprimer l'élément minimum, puis ajouter l'élément suivant de la liste correspondante. De plus, nous aurons besoin d'une structure Data.Sequence pour stocker les listes elles-mêmes. Il a été choisi pour des raisons qu'à chaque étape, il est nécessaire à la fois d'avoir un accès rapide à la liste par son index (que la liste ne peut pas fournir), et de changer l'élément de cet élément sans avoir besoin de copier la structure entière (qui en général ne peut pas fournir de données immuables . Array ).
Ainsi, nous avons le programme suivant:
Solution 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
Nous envoyons la solution et découvrons que même si le programme a commencé à consommer beaucoup moins de mémoire (10,26 Mo au lieu de 17,27 Mo au 17e test), il n'a toujours pas atteint la limite. La raison à cela réside dans le fait qu'avec cette décision, d'une manière ou d'une autre, nous devons lire la totalité des données d'entrée dans la mémoire. Essayons d'éviter cela à l'aide de la troisième solution à ce problème - le tri par comptage.
Nous avons déjà effectué le comptage du nombre de caractères entrants lors de la résolution du problème d'anagramme précédent. De plus, comme pour le résoudre, nous utiliserons Data.Array . Tout d'abord, nous implémentons la fonction addToArray :: Array Int Int -> [Int] -> Array Int Int , qui forme un tableau basé sur celui existant en augmentant les valeurs aux indices qui correspondent aux valeurs de la liste.
addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]
Ensuite, nous utiliserons l'approche que nous connaissons dans le problème de la suppression des répétitions - en utilisant la convolution monadique, en appliquant séquentiellement la fonction addToArray à k tableaux source. Et ... nous obtenons le même résultat de 10,26 Mo lors du 17e test. Et puis il est temps de se rappeler que foldl (dont l'analogue est foldM ) selon l'ordre de réduction accepté va d'abord étendre toute la chaîne des expressions imbriquées et ensuite seulement procéder à leur calcul actif. Comme vous le savez, pour lutter contre ce fait, le module Data.List implémente la fonction foldl ' , qui utilise la fonction seq :: a -> b -> b , qui transforme d'abord le premier argument en forme normale de tête faible, c'est-à-dire le réduit à la partie externe - la valeur de la fonction ou du constructeur, puis renvoie la seconde ( https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ). Nous n'avons d'autre choix que d'implémenter la fonction foldM 'de manière indépendante .
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
En conséquence, la quantité de mémoire utilisée lors du 17e test a presque diminué de moitié et s'élève à 5,64 Mo! Bien que les 17e et 18e tests aient été réussis, cette implémentation n'a pas réussi le 19e test pour la même raison que la limite de mémoire a été dépassée - 10,25 Mo.
D'accord, continuez - nous n'avons pas encore essayé Data.Array.Unboxed. Ce type de tableaux est remarquable en ce que, contrairement à la norme, il peut stocker les valeurs elles-mêmes, plutôt que des pointeurs vers elles ( https://wiki.haskell.org/Arrays#Unboxed_arrays ). De ce fait, ces baies prennent moins d'espace mémoire et sont plus efficaces. Pour les utiliser, il suffit de modifier les types d'importation et de fonction, car Data.Array et Data.Array.Unboxed implémentent une interface de tableaux IArray immuables.
Nous envoyons une solution - la consommation de mémoire a diminué de 4,5 fois pour atteindre 2,26 Mo, mais elle n'a pas dépassé la limite de temps - le temps d'exécution était de 1,09 seconde. À quoi cela pourrait-il être lié? À en juger par le fait que le temps d'exécution des tests restants reste le même, je pense que la raison n'est pas que le tableau non conditionné s'est avéré plus lent que le contenu, mais en particulier le système de test. Il semble que la tâche soit interrompue dès qu'une des restrictions est violée. Cependant, dans de très rares cas, cette implémentation réussit toujours le 19e test avec un résultat de 0,98 seconde, mais échoue au test numéro 20 également en raison du dépassement de la limite de temps.
Après cela, j'ai essayé d'utiliser l'analogue dangereux de la fonction d'accumulation, qui en théorie devrait être plus rapide, diverses méthodes de mise en mémoire tampon ( hSetBuffering :: Handle -> BufferMode -> fonction IO () ), des tableaux IOArray mutables, mais aucune de ces méthodes n'a donné de résultats .
Je ne suis pas enclin à croire que les limites pour Haskell sont trop strictes, et j'espère qu'il existe toujours une solution qui passera tous les tests. Dans le référentiel du projet, j'ai posté plusieurs versions différentes du code pour résoudre ce problème (avec Array et IOArray), ce sera peut-être le point de départ d'une solution qui passera tous les tests.
Conclusion
Même en dépit du fait que seulement cinq tâches sur six m'ont succombé, j'ai terminé ma tâche principale - pratiquer la programmation fonctionnelle. Le moindre rôle a été joué par de sévères restrictions sur les ressources consommées par le programme, ce qui nous a obligés à chercher de plus en plus de nouvelles approches pour résoudre les problèmes. J'espère que leur description sera utile pour ceux qui commencent tout juste leur voyage dans la programmation fonctionnelle
L'approche fonctionnelle était-elle pratique pour résoudre de tels problèmes? Honnêtement, j'ai une double impression. D'une part, les solutions à la plupart des problèmes se sont avérées très concises et les outils expressifs de Haskell lui-même, ainsi que sa riche bibliothèque standard, ont joué un rôle important à cet égard. D'un autre côté, on ne peut qu'admettre que dans la plupart des cas, la gestion des ressources consommées peut être un certain problème, ce qui ne permettra pas de résoudre le problème dans les restrictions données.