Hace unos meses, apareció un artículo en el blog de Yandex que discutía el paso de la sección algorítmica de la entrevista. Entre otras cosas, en este artículo, se proporcionó un enlace a un concurso especial que contenía tareas similares a las ofrecidas por Yandex a sus candidatos.
Al registrarme en el sistema, me llamó la atención de inmediato la capacidad de resolver problemas en Haskell. El hecho es que, aunque soy aficionado a la programación en este lenguaje, no he avanzado más allá de la implementación de tareas de varios cursos de plataformas educativas en línea. Habiendo decidido que su solución puede ser un desafío interesante y aumentará mi nivel como desarrollador, procedí a resolverlos.
A quién le importa lo que finalmente surgió, bienvenido a cat.
A. Piedras y joyas.
Se dan dos líneas de caracteres latinos en minúscula: cadena J y cadena S. Los caracteres incluidos en la cadena J son "joyas" y se incluyen en la cadena S son "piedras". Es necesario determinar cuántos caracteres de S son simultáneamente "joyas". En pocas palabras, debe verificar cuántos caracteres de S hay en J.
La primera tarea es un calentamiento, lo resolveremos "en la frente". Definimos la función jewelleryCount :: String -> String -> Int , que, utilizando la convolución de la lista pasada por el segundo argumento, resume todos los casos del elemento que se procesa en la primera lista. Para estos fines, definimos la función elemInt en función de la función elem , que, a diferencia de la última, no devolverá True o False, sino el número 0 o 1. En la función principal, solo necesita leer dos líneas, pasarlas a la función correspondiente e imprimir el resultado. El veredicto del sistema de prueba está bien, pasamos a la segunda tarea.
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
El código fuente para resolver esta y otras tareas también está disponible en el repositorio de github.
B. Unidades consecutivas
Se requiere encontrar la secuencia más larga de unidades en el vector binario e imprimir su longitud.
Para resolver este problema, implementamos una función recursiva que recorrerá la lista transferida y calculará la longitud de la secuencia requerida. Con los argumentos de la función, además de la lista en sí, pasaremos la longitud máxima actual y el número de unidades consecutivas en la llamada actual. Primero, definimos la base de recursión en la lista vacía, y luego el paso de recursión en sí.
Para leer los datos de entrada, definimos la función getUserInputs :: IO [Char] , en la que primero leemos el número n - el tamaño de la lista, y luego usando el combinador replicateM obtenemos una función que llamará a la función <<get> getLine n veces y fusionará los resultados en una 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
Enviamos la decisión, el veredicto está bien. Seguimos adelante.
C. Eliminación duplicada
Se proporciona una matriz de enteros de 32 bits ordenados en orden no decreciente. Es necesario eliminar todas las repeticiones.
Comencemos con una implementación simple. Definimos una función inicial que lee un número, lo imprime y lo devuelve envuelto en la mónada IO. También definimos la función deleteDoubles :: Int -> Int -> IO () , que lee un número y lo imprime solo si no es igual al segundo argumento (pasaremos el número leído en el paso anterior allí). Después de eso, la función se llama recursivamente y, por lo tanto, pasa al siguiente número en la secuencia de entrada. La base de recursión es el número de números a leer, le pasaremos el primer 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 la solución, pasa todas las pruebas y parece que podemos pasar a la siguiente tarea, pero en mi opinión, la llamada recursiva de la función que funciona en la mónada IO es más confusa que concisa. Intentemos mejorarlo.
Tenga en cuenta que, en términos generales, primero puede leer la lista completa de números (usaremos el combinador replicateM que ya está familiarizado con la segunda tarea), luego pasarlo a una función pura que filtre todas las repeticiones y finalmente imprima el 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
Estoy enviando una solución, y la primera decepción es que el programa no pasa la prueba 193 debido a que excede el límite de memoria utilizada. El error principal es leer la lista completa en la memoria como un todo. Intentaremos evitar esto e implementaremos un cierto híbrido de la primera y segunda versión.
Tenga en cuenta que la tarea de eliminar duplicados recuerda un poco a una convolución asociativa izquierda: en cada paso calculamos una función que, dependiendo del elemento actual leído y parte de su resultado, en el paso anterior decide imprimir, y luego pasa al siguiente par de valores.
Una función que imprime o no imprime el resultado dependiendo de sus argumentos, después de lo cual devuelve su segundo argumento, envuelto en la mónada IO, es bastante simple, llamémoslo paso:
step :: Int -> Int -> IO Int step fst snd = unless (fst == snd) (print snd) >> return snd
Descubrimos si imprimir o no, dependiendo de los valores pasados, pero ¿cómo organizar la lectura? Para hacer esto, utilizamos la función de convolución monádica foldM :: (Plegable t, Mónada m) => (b -> a -> mb) -> b -> ta -> mb , que es aplicable a la lista de funciones de lectura.
Por tipo de función foldM, observamos que en cada paso el “desempaquetado” del resultado de la aplicación previa de la función ocurre bajo el capó de foldM. Por lo tanto, en cada paso solo necesitamos comenzar un cálculo monádico del elemento de la lista actual (de hecho, leer el siguiente número) usando el operador de enlace ( >> = ) y pasarlo junto con el número anterior al paso. Como resultado, obtenemos el siguiente 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. Generación de secuencias de paréntesis.
Dado un número entero n. Es necesario derivar todas las secuencias de paréntesis correctas de longitud 2 n, ordenadas lexicográficamente (ver https://ru.wikipedia.org/wiki/Lexographic_order ).
Solo se usan paréntesis en la tarea.
Es recomendable obtener una solución que funcione en un tiempo proporcional al número total de secuencias de paréntesis correctas en la respuesta, y al mismo tiempo utiliza una capacidad de memoria proporcional a n.
Esta tarea, como muchas otras, en la que es necesario derivar secuencias que satisfagan ciertas condiciones (por ejemplo, la tarea de intercambiar monedas, organizar ocho reinas y otras, se puede leer con más detalle aquí ), se resuelve sucintamente utilizando la mónada de la lista. En resumen, este enfoque se basa en el enlace monádico para listas, cuyo significado es unir el conjunto de operaciones realizadas en cada elemento de la lista.
Defina la función recursiva generate ':: Int -> Int -> [[Char]] , que toma el número de corchetes que se colocarán como segundo argumento, y el número de corchetes de apertura no cerrados ya establecidos. Para el paso de recursión, necesitamos dos funciones auxiliares: posible : devuelve una lista de corchetes que se pueden colocar en el siguiente paso y paso : realiza una llamada recursiva a la función de generación con los parámetros necesarios.
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 la solución y entendemos que no tomamos en cuenta la restricción que se impuso a la cantidad de memoria utilizada por el programa; la solución no pasa la 14a prueba debido a que se excede el límite de memoria utilizada.
Modificamos la función de generación para que, en lugar de construir la lista completa de secuencias de paréntesis correctas, las muestre inmediatamente en la pantalla. Para hacer esto, tendremos que agregar el tercer argumento a la función: un fragmento de la secuencia construida para el paso actual. Observo que en esta implementación construiremos la secuencia en el orden inverso, esto nos permitirá usar el constructor de lista ( :) en lugar del operador de concatenación más costoso ( ++ ).
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
Se dan dos líneas, que consisten en letras latinas minúsculas. Es necesario determinar si estas líneas son anagramas, es decir, difieren solo en la secuencia de caracteres.
Para resolver este problema, contaremos cuántas veces aparece una letra en cada fila y compararemos los resultados. Inmediatamente entendemos que las listas estándar no son adecuadas para nosotros, y es necesario usar una estructura de datos que nos permita acceder efectivamente al elemento por su índice. Existen varios tipos de datos que satisfarían nuestras condiciones, pero usaremos la matriz de datos inmutable estándar Data.Array (todavía hay al menos varias matrices mutables, así como Data.Vector ).
Para construir las matrices necesarias, utilizamos la función hist :: (Ix a, Num b) => (a, a) -> [a] -> Array ab , que, de acuerdo con la lista de elementos transferidos y el rango al que deben pertenecer estos elementos, forma una matriz, que almacena el número de repeticiones de elementos de la lista. Esta función, aunque no se incluye en el módulo Data.Array, a menudo se da como un ejemplo del uso de otra función, ya de biblioteca, acumulaciónArray. Solo podemos copiar su implementación y escribir main: el beneficio de la comparación de igualdad para Array Char Int ya está definido. Le llamo la atención sobre una característica agradable: como índice podemos usar no solo enteros, sino también cualquier representante de la clase Ix . En nuestro caso, Char juega un papel natural en este 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. Fusionar k listas ordenadas
Se proporcionan matrices de enteros no negativos ordenados en orden no decreciente, cada uno de los cuales no supera los 100. Se requiere construir el resultado de su fusión: una matriz ordenada en orden no decreciente que contiene todos los elementos de las matrices k originales.
La longitud de cada matriz no excede 10 ⋅ k.
Intente hacer que la solución funcione durante el tiempo k ⋅ log (k) ⋅ n, si suponemos que las matrices de entrada son de longitud n.
La fusión de dos listas ordenadas es una tarea de lista clásica y está cubierta en muchos cursos sobre programación de Haskell. Por ejemplo, se puede resolver de la siguiente manera.
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
Bueno, podemos fusionar dos listas. ¿Y qué debemos hacer con la lista de listas? ¡Convolúcelo con esta función! Por lo tanto, combinaremos todas las listas en una, y solo tendremos que imprimirla.
Solución 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
Sin embargo, esta solución tiene dos problemas serios: la complejidad computacional es mayor que la requerida: O (k ^ 2 ⋅ n) en lugar de O (k ⋅ log (k) ⋅ n) , además de que usa mucha memoria adicional. Como resultado, esta solución falla la prueba número 17 debido a que excede el límite de memoria utilizada: 17.27Mb en lugar de los 10Mb permitidos.
Si bien no prestaremos atención al hecho de que los números suministrados a la entrada pertenecen a un rango limitado de valores, y continuamos buscando soluciones para un caso más general.
El siguiente paso es tratar de implementar el enfoque que se propuso en el artículo original con el análisis de estas tareas. Permítame recordarle que se basa en el uso de una estructura de datos que proporciona una forma eficiente de extraer el elemento mínimo. Como tal estructura, seleccione Data.Set . Inicializamos Set con la lista de primeros elementos, luego en cada paso extraeremos e imprimiremos el elemento mínimo, y luego agregaremos el siguiente elemento de la lista correspondiente. Además, necesitaremos una estructura Data.Sequence para almacenar las listas. Se eligió por razones que en cada paso es necesario tener acceso rápido a la lista por su índice (que la lista no puede proporcionar) y cambiar el elemento de este elemento sin la necesidad de copiar toda la estructura (que en general no puede proporcionar datos inmutables ). Array ).
Por lo tanto, tenemos el siguiente programa:
Solución 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 la solución y descubrimos que a pesar de que el programa comenzó a consumir mucha menos memoria (10.26Mb en lugar de 17.27Mb en la 17a prueba), aún no alcanzó el límite. La razón de esto radica en el hecho de que con esta decisión, de una forma u otra, tenemos que leer todos los datos de entrada en la memoria. Intentemos evitar esto con la ayuda de la tercera solución a este problema: ordenar por conteo.
Ya hemos realizado el recuento de la cantidad de caracteres entrantes al resolver el problema del anagrama anterior. Además, como para resolverlo, usaremos Data.Array . Primero, implementamos la función addToArray :: Array Int Int -> [Int] -> Array Int Int , que forma una matriz basada en la existente al aumentar los valores en los índices que corresponden a los valores de la lista.
addToArray :: Array Int Int -> [Int] -> Array Int Int addToArray acc elems = accum (+) acc [(i, 1) | i<-elems]
Luego, usaremos el enfoque que conocemos en el problema de eliminar repeticiones: usar la convolución monádica, aplicando secuencialmente la función addToArray a k matrices de origen. Y ... obtenemos el mismo resultado de 10.26Mb en la 17a prueba. Y luego es hora de recordar que foldl (cuyo análogo es foldM ) de acuerdo con el orden de reducción aceptado expandirá primero toda la cadena de expresiones anidadas y solo luego procederá a su cálculo activo. Como saben, para combatir este hecho, el módulo Data.List implementa la función foldl ' , que usa la función seq :: a -> b -> b , que primero lanza el primer argumento a la forma normal de la cabeza débil, es decir, la reduce a la parte externa. el valor de la función o constructor, y luego devuelve el segundo ( https://www.ibm.com/developerworks/ru/library/l-haskell4/index.html ). No tenemos más remedio que implementar la función foldM 'de forma independiente .
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, ¡la cantidad de memoria usada en la 17ª prueba casi se redujo a la mitad y ascendió a 5.64Mb! Aunque las pruebas 17 y 18 se aprobaron con éxito, esta implementación no pasó la prueba 19 por la misma razón por la que se excedió el límite de memoria: 10.25Mb.
Bien, sigan adelante: todavía no hemos probado Data.Array.Unboxed. Este tipo de matrices es notable porque, a diferencia del estándar, puede almacenar los valores en sí mismos, en lugar de indicadores para ellos ( https://wiki.haskell.org/Arrays#Unboxed_arrays ). Debido a esto, tales matrices ocupan menos espacio en la memoria y son más eficientes. Para usarlos, solo necesitamos cambiar los tipos de importación y función, ya que Data.Array y Data.Array.Unboxed implementan una interfaz de matrices IArray inmutables.
Estamos enviando una solución: el consumo de memoria ha disminuido 4.5 veces a 2.26 MB, pero no ha pasado el límite de tiempo, el tiempo de ejecución fue de 1.09 segundos. ¿Con qué podría estar conectado esto? A juzgar por el hecho de que el tiempo de ejecución de las pruebas restantes sigue siendo el mismo, creo que la razón no es que la matriz sin caja resultó ser más lenta que la caja, sino en particular el sistema de prueba. Parece que la tarea se interrumpe tan pronto como se viola una de las restricciones. Sin embargo, en casos muy raros, esta implementación todavía pasa la prueba 19 con un resultado de 0,98 segundos, pero falla la prueba número 20 también debido a que excede el límite de tiempo.
Después de eso, intenté usar el análogo inseguro de la función acumular, que en teoría debería ser más rápido, varios métodos de almacenamiento en búfer ( hSetBuffering :: Handle -> BufferMode -> IO () function), matrices IOArray mutables, pero ninguno de estos métodos arrojó ningún resultado .
No me inclino a creer que los límites para Haskell estén demasiado ajustados, y espero que todavía haya una solución que pase todas las pruebas. En el repositorio del proyecto, publiqué varias versiones diferentes del código para resolver este problema (con Array e IOArray), quizás este sea el punto de partida para una solución que pasará todas las pruebas.
Conclusión
Incluso a pesar de que solo cinco de las seis tareas me sucumbieron, completé mi tarea principal: practicar la programación funcional. Las restricciones severas sobre los recursos consumidos por el programa jugaron un papel importante, lo que nos obligó a buscar cada vez más enfoques nuevos para resolver problemas. Espero que su descripción sea útil para aquellos que recién comienzan su viaje en la programación funcional.
¿Fue conveniente el enfoque funcional para resolver tales problemas? Sinceramente, tengo una doble impresión. Por un lado, las soluciones a la mayoría de los problemas resultaron ser muy concisas, y las herramientas expresivas del propio Haskell, así como su rica biblioteca estándar, jugaron un papel importante en esto. Por otro lado, uno no puede dejar de admitir que, en la mayoría de los casos, la gestión de los recursos consumidos puede ser un cierto problema, que no permitirá resolver el problema en las restricciones dadas.