# Etiqueta: splitAt

## División equitativa

Definir la función

` divisionEquitativa :: [Int] -> Maybe ([Int],[Int])`

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

``` divisionEquitativa [1,2,3,4,5,15] == Just ([1,2,3,4,5],[15]) divisionEquitativa [15,1,2,3,4,5] == Just ([15],[1,2,3,4,5]) divisionEquitativa [1,2,3,4,7,15] == Nothing divisionEquitativa [1,2,3,4,15,5] == Nothing```

#### Soluciones

```import Data.Maybe (isNothing, fromJust, listToMaybe) import Data.List (elemIndex, inits, tails)   -- 1ª solución divisionEquitativa1 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa1 xs = aux (particiones xs) where aux [] = Nothing aux ((as,bs):ys) | sum as == sum bs = Just (as,bs) | otherwise = aux ys particiones xs = [splitAt i xs | i <- [1..length xs-1]]   -- 2ª solución divisionEquitativa2 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa2 xs | 2 * b == suma = Just \$ splitAt (length as + 1) xs | otherwise = Nothing where suma = sum xs (as,(b:bs)) = span (<suma `div` 2) \$ scanl1 (+) xs   -- 3ª solución divisionEquitativa3 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa3 xs | odd n = Nothing | isNothing p = Nothing | otherwise = Just (splitAt (1 + fromJust p) xs) where n = sum xs ys = scanl1 (+) xs p = elemIndex (n `div` 2) ys   -- 4ª solución divisionEquitativa4 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa4 xs | odd (sum xs) = Nothing | otherwise = aux [] xs where aux as bs@(b:bs') | sum as == sum bs = Just (reverse as, bs) | sum as > sum bs = Nothing | otherwise = aux (b:as) (bs')   -- 5ª solución divisionEquitativa5 :: [Int] -> Maybe ([Int],[Int]) divisionEquitativa5 xs = listToMaybe [(ys, zs) | (ys,zs) <- zip (inits xs) (tails xs) , sum ys == sum zs ]```

## Sumas parciales de Juzuk

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

• se comienza con la lista de todos los enteros positivos
` [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...`
• se agrupan tomando el primer elemento, los dos siguientes, los tres
siguientes, etc.
` [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15], ...`
• se seleccionan los elementos en posiciones pares
` [[1], [4, 5, 6], [11, 12, 13, 14, 15], ...`
• se suman los elementos de cada grupo
` [1, 15, 65, ...`
• se calculan las sumas acumuladas
` [1, 16, 81, ...`

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

``` listasParcialesJuzuk :: [a] -> [[a]] sumasParcialesJuzuk :: [Integer] -> [Integer]```

tal que

• (listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,
``` λ> take 4 (listasParcialesJuzuk [1..]) [[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]] λ> take 4 (listasParcialesJuzuk [1,3..]) [[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]```
• (sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,
``` take 4 (sumasParcialesJuzuk [1..]) == [1,16,81,256] take 4 (sumasParcialesJuzuk [1,3..]) == [1,28,153,496]```

Comprobar con QuickChek que, para todo entero positivo n,

• el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es `n^4`.
• el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es `n^2*(2*n^2 - 1)`.
• el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es `4*n^4-3*n^2`.
• el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es `n^2*(n^2+1)`.

#### Soluciones

```import Data.List (genericIndex) import Test.QuickCheck   listasParcialesJuzuk :: [a] -> [[a]] listasParcialesJuzuk = elementosEnPares . listasParciales   -- (listasParciales xs) es la agrupación de los elementos de xs obtenida -- tomando el primer elemento, los dos siguientes, los tres siguientes, -- etc. Por ejemplo, -- λ> take 5 (listasParciales [1..]) -- [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]] listasParciales :: [a] -> [[a]] listasParciales = aux 1 where aux n xs = ys : aux (n+1) zs where (ys,zs) = splitAt n xs   -- (elementosEnPares xs) es la lista de los elementos de xs en -- posiciones pares. Por ejemplo, -- λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]] -- [[1],[4,5,6],[11,12,13,14,15]] elementosEnPares :: [a] -> [a] elementosEnPares [] = [] elementosEnPares [x] = [x] elementosEnPares (x:_:xs) = x : elementosEnPares xs   sumasParcialesJuzuk :: [Integer] -> [Integer] sumasParcialesJuzuk xs = scanl1 (+) (map sum (listasParcialesJuzuk xs))   -- La primera propiedad es prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool prop_sumasParcialesJuzuk (Positive n) = sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4   -- Su comprobación es -- λ> quickCheck prop_sumasParcialesJuzuk -- +++ OK, passed 100 tests.   -- La segunda propiedad es prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool prop_sumasParcialesJuzuk2 (Positive n) = sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)   -- Su comprobación es -- λ> quickCheck prop_sumasParcialesJuzuk2 -- +++ OK, passed 100 tests.   -- La tercera propiedad es prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool prop_sumasParcialesJuzuk3 (Positive n) = sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2   -- Su comprobación es -- λ> quickCheck prop_sumasParcialesJuzuk3 -- +++ OK, passed 100 tests.   -- La cuarta propiedad es prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool prop_sumasParcialesJuzuk4 (Positive n) = sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)   -- Su comprobación es -- λ> quickCheck prop_sumasParcialesJuzuk4 -- +++ OK, passed 100 tests.```

## Sumas parciales de Nicómaco

Nicómaco de Gerasa vivió en Palestina entre los siglos I y II de nuestra era. Escribió Arithmetike eisagoge (Introducción a la aritmética) que es el primer trabajo en donde se trata la Aritmética de forma separada a la Geometría. En el tratado se encuentra la siguiente proposición: «si se escriben los números impares

` 1, 3, 5, 7, 9, 11, 13, 15, 17, ...`

entonces el primero es el cubo de 1; la suma de los dos siguientes, el cubo de 2; la suma de los tres siguientes, el cubo de 3; y así sucesivamente.»

Definir las siguientes funciones

``` listasParciales :: [a] -> [[a]] sumasParciales :: [Int] -> [Int]```

tales que

• (listasParciales xs) es la lista obtenido agrupando los elementos de la lista infinita xs de forma que la primera tiene 0 elementos; la segunda, el primer elemento de xs; la tercera, los dos siguientes; y así sucesivamente. Por ejemplo,
``` λ> take 7 (listasParciales [1..]) [[],[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15],[16,17,18,19,20,21]] λ> take 7 (listasParciales [1,3..]) [[],[1],[3,5],[7,9,11],[13,15,17,19],[21,23,25,27,29],[31,33,35,37,39,41]]```
• (sumasParciales xs) es la lista de las sumas parciales de la lista infinita xs. Por ejemplo,
``` λ> take 15 (sumasParciales [1..]) [0,1,5,15,34,65,111,175,260,369,505,671,870,1105,1379] λ> take 15 (sumasParciales [1,3..]) [0,1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744]```

Comprobar con QuickChek la propiedad de Nicómaco; es decir, que para todo número natural n, el término n-ésimo de (sumasParciales [1,3..]) es el cubo de n.

#### Soluciones

```import Test.QuickCheck   listasParciales :: [a] -> [[a]] listasParciales = aux 0 where aux n xs = ys : aux (n+1) zs where (ys,zs) = splitAt n xs   sumasParciales :: [Int] -> [Int] sumasParciales = map sum . listasParciales   prop_Nicomaco :: (Positive Int) -> Bool prop_Nicomaco (Positive n) = sumasParciales [1,3..] !! n == n^3```

## Rotaciones divisibles por 8

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816 de las que 3 son divisibles por 8 (928160, 160928 y 92816).

Definir la función

` nRotacionesDivisiblesPor8 :: Integer -> Int`

tal que (nRotacionesDivisiblesPor8 x) es el número de rotaciones de x divisibles por 8. Por ejemplo,

``` nRotacionesDivisiblesPor8 928160 == 3 nRotacionesDivisiblesPor8 43262488612 == 4 nRotacionesDivisiblesPor8 (read (take (10^4) (cycle "248"))) == 6666```

#### Soluciones

```-- 1ª definición -- =============   nRotacionesDivisiblesPor8 :: Integer -> Int nRotacionesDivisiblesPor8 x = length [y | y <- rotaciones x , y `mod` 8 == 0]   -- rotaciones 1234 == [1234,2341,3412,4123] rotaciones :: Integer -> [Integer] rotaciones x = [read ys | ys <- rotacionesLista xs] where xs = show x   -- rotacionesLista "abcd" == ["abcd","bcda","cdab","dabc"] rotacionesLista :: [a] -> [[a]] rotacionesLista xs = [zs ++ ys | k <- [0 .. length xs - 1] , let (ys,zs) = splitAt k xs]   -- 2ª definición -- =============   nRotacionesDivisiblesPor8b :: Integer -> Int nRotacionesDivisiblesPor8b x = length [y | y <- tresDigitosConsecutivos x , y `mod` 8 == 0]   -- tresDigitosConsecutivos 1234 == [123,234,341,412] tresDigitosConsecutivos :: Integer -> [Integer] tresDigitosConsecutivos x = [read (take 3 ys) | ys <- rotacionesLista (show x)]   -- Comparación de eficiencia -- =========================   -- λ> nRotacionesDivisiblesPor8 (read (take (3*10^3) (cycle "248"))) -- 2000 -- (3.59 secs, 4,449,162,144 bytes) -- λ> nRotacionesDivisiblesPor8b (read (take (3*10^3) (cycle "248"))) -- 2000 -- (0.48 secs, 593,670,656 bytes)```

## Biparticiones de un número

Definir la función

` biparticiones :: Integer -> [(Integer,Integer)]`

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

``` biparticiones 2025 == [(202,5),(20,25),(2,25)] biparticiones 10000 == [(1000,0),(100,0),(10,0),(1,0)]```

#### Soluciones

```import Test.QuickCheck   -- 1ª solución -- ===========   biparticiones1 :: Integer -> [(Integer,Integer)] biparticiones1 x = [(read y, read z) | (y,z) <- biparticionesL1 xs] where xs = show x   -- (biparticionesL1 xs) es la lista de los pares formados por los -- prefijos no vacío de xs y su resto. Por ejemplo, -- biparticionesL1 "2025" == [("2","025"),("20","25"),("202","5")] biparticionesL1 :: [a] -> [([a],[a])] biparticionesL1 xs = [splitAt k xs | k <- [1..length xs - 1]]   -- 2ª solución -- ===========   biparticiones2 :: Integer -> [(Integer,Integer)] biparticiones2 x = [(read y, read z) | (y,z) <- biparticionesL2 xs] where xs = show x   -- (biparticionesL2 xs) es la lista de los pares formados por los -- prefijos no vacío de xs y su resto. Por ejemplo, -- biparticionesL2 "2025" == [("2","025"),("20","25"),("202","5")] biparticionesL2 :: [a] -> [([a],[a])] biparticionesL2 xs = takeWhile (not . null . snd) [splitAt n xs | n <- [1..]]   -- 3ª solución -- ===========   biparticiones3 :: Integer -> [(Integer,Integer)] biparticiones3 a = takeWhile ((>0) . fst) [divMod a (10^n) | n <- [1..]]   -- 4ª solución -- ===========   biparticiones4 :: Integer -> [(Integer,Integer)] biparticiones4 n = [quotRem n (10^x) | x <- [1..length (show n) -1]]   -- 5ª solución -- ===========   biparticiones5 :: Integer -> [(Integer,Integer)] biparticiones5 n = takeWhile (/= (0,n)) [divMod n (10^x) | x <- [1..]]   -- Comparación de eficiencia -- =========================   -- λ> numero n = (read (replicate n '2')) :: Integer -- (0.00 secs, 0 bytes) -- λ> length (biparticiones1 (numero 10000)) -- 9999 -- (0.03 secs, 10,753,192 bytes) -- λ> length (biparticiones2 (numero 10000)) -- 9999 -- (1.89 secs, 6,410,513,136 bytes) -- λ> length (biparticiones3 (numero 10000)) -- 9999 -- (0.54 secs, 152,777,680 bytes) -- λ> length (biparticiones4 (numero 10000)) -- 9999 -- (0.01 secs, 7,382,816 bytes) -- λ> length (biparticiones5 (numero 10000)) -- 9999 -- (2.11 secs, 152,131,136 bytes) -- -- λ> length (biparticiones1 (numero (10^7))) -- 9999999 -- (14.23 secs, 10,401,100,848 bytes) -- λ> length (biparticiones4 (numero (10^7))) -- 9999999 -- (11.43 secs, 7,361,097,856 bytes)```