Sumas de tres capicúas

Definir la función

   sumas3Capicuas  :: Integer -> [(Integer, Integer, Integer)]

1	sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,

   sumas3Capicuas 0  ==  [(0,0,0)]
   sumas3Capicuas 1  ==  [(0,0,1)]
   sumas3Capicuas 2  ==  [(0,0,2),(0,1,1)]
   sumas3Capicuas 3  ==  [(0,0,3),(0,1,2),(1,1,1)]
   sumas3Capicuas 4  ==  [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]
   length (sumas3Capicuas 17)      ==  17
   length (sumas3Capicuas 2017)    ==  47
   length (sumas3Capicuas 999999)  ==  15266

sumas3Capicuas 0 == [(0,0,0)]

sumas3Capicuas 1 == [(0,0,1)]

sumas3Capicuas 2 == [(0,0,2),(0,1,1)]

sumas3Capicuas 3 == [(0,0,3),(0,1,2),(1,1,1)]

sumas3Capicuas 4 == [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]

length (sumas3Capicuas 17) == 17

length (sumas3Capicuas 2017) == 47

length (sumas3Capicuas 999999) == 15266

Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.

Soluciones

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas x =
  [(a,b,c) | a <- as
           , b <- dropWhile (< a) as
           , let c = x - a - b
           , b <= c 
           , esCapicua c]
  where as = takeWhile (<= x) capicuas

-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x

-- La propiedad es
prop_sumas3Capicuas :: Integer -> Property
prop_sumas3Capicuas x =
  x >= 0 ==> not (null (sumas3Capicuas x))

-- La comprobación es
--    λ> quickCheck prop_sumas3Capicuas
--    +++ OK, passed 100 tests.

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

sumas3Capicuas x =

[(a,b,c) | a <- as

, b <- dropWhile (< a) as

, let c = x - a - b

, b <= c

, esCapicua c]

where as = takeWhile (<= x) capicuas

-- capicuas es la sucesión de los números capicúas. Por ejemplo,

-- λ> take 45 capicuas

-- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

-- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

-- 303,313,323,333,343,353]

-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".

capicuas :: [Integer]

capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

-- La propiedad es

prop_sumas3Capicuas :: Integer -> Property

prop_sumas3Capicuas x =

x >= 0 ==> not (null (sumas3Capicuas x))

-- La comprobación es

-- λ> quickCheck prop_sumas3Capicuas

-- +++ OK, passed 100 tests.

4 Comentarios

-- Usando la funcion capicuas2 definida en el ejercicio anterior
sumas3CapicuasA1 :: Integer -> [(Integer, Integer, Integer)]
sumas3CapicuasA1 n =
  [(x,y,z) | x <- menores,
             y <- dropWhile (<x) menores,
             let z = n - (x + y),
             z >= y,
             (read . reverse . show) z == z]
  where menores = (takeWhile (<=n) capicuas2)

-- Usando la funcion capicuas2 definida en el ejercicio anterior

sumas3CapicuasA1 :: Integer -> [(Integer, Integer, Integer)]

sumas3CapicuasA1 n =

[(x,y,z) | x <- menores,

y <- dropWhile (<x) menores,

let z = n - (x + y),

z >= y,

(read . reverse . show) z == z]

where menores = (takeWhile (<=n) capicuas2)

Responder

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas n = [ (a,b,c) | a <- xs
                             , b <- intervalo (a, (n-a) `div` 2) xs
                             , let c = n - a - b
                             , esCapicua c ]
  where xs = takeWhile (<= n) capicuas
        intervalo (a,b) = takeWhile (<= b) . dropWhile (<a)
        esCapicua = (==) <$> id <*> reverse <$> show


prop_triocapicuas :: Positive Integer -> Bool
prop_triocapicuas = not.null.sumas3Capicuas . getPositive

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

sumas3Capicuas n = [ (a,b,c) | a <- xs

, b <- intervalo (a, (n-a) `div` 2) xs

, let c = n - a - b

, esCapicua c ]

where xs = takeWhile (<= n) capicuas

intervalo (a,b) = takeWhile (<= b) . dropWhile (<a)

esCapicua = (==) <$> id <*> reverse <$> show

prop_triocapicuas :: Positive Integer -> Bool

prop_triocapicuas = not.null.sumas3Capicuas . getPositive

Responder

sumas3Capicuas  :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas x =
  [(a,b,x-a-b) | a <- takeWhile (div x 3>=) capicuas
               , b <- dropWhile (a>) $ takeWhile (div (x-a) 2>=) capicuas
               , isCap (x-a-b)]
  where isCap x = show x == reverse (show x)

capicuas :: [Integer]
capicuas = 0 : rRr 1
  where rRr n =  [read (show x ++ tail (reverse (show x)))
                 | x <- [10^(n-1)..10^n-1]]
              ++ [read (show x ++ reverse (show x))
                 | x <- [10^(n-1)..10^n-1]]
              ++ rRr (n+1)

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

sumas3Capicuas x =

[(a,b,x-a-b) | a <- takeWhile (div x 3>=) capicuas

, b <- dropWhile (a>) $ takeWhile (div (x-a) 2>=) capicuas

, isCap (x-a-b)]

where isCap x = show x == reverse (show x)

capicuas :: [Integer]

capicuas = 0 : rRr 1

where rRr n = [read (show x ++ tail (reverse (show x)))

| x <- [10^(n-1)..10^n-1]]

++ [read (show x ++ reverse (show x))

| x <- [10^(n-1)..10^n-1]]

++ rRr (n+1)

Responder

import Data.List

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas x = sinRepetir [(a,b,c) | a <- [0..x]
                                       , b <- [a..x-a]
                                       , let c = x - a - b
                                       , esCapicua a
                                       , esCapicua b
                                       , esCapicua c ]

esCapicua :: Integer -> Bool
esCapicua n | even x    = take y n' == reverse (drop y n')
            | otherwise = take y n' == reverse (drop (y+1) n')
          where n' = show n
                x  = length n'
                y = x `div` 2

sinRepetir :: [(Integer, Integer, Integer)] -> [(Integer, Integer, Integer)]
sinRepetir xs = aTerna $ sinIguales $ aLista xs

aLista :: [(Integer, Integer, Integer)] -> [[Integer]]
aLista []           = []
aLista ((a,b,c):xs) = [a,b,c] : aLista xs

aTerna :: [[Integer]] -> [(Integer, Integer, Integer)]
aTerna []           = []
aTerna ([a,b,c]:xs) = (a,b,c) : aTerna xs

iguales :: Eq a => [a] -> [a] -> Bool
iguales xs ys = and (map (`elem` ys) xs) && null (xs\\ys)

sinIguales :: Eq a => [[a]] -> [[a]]
sinIguales []       = []
sinIguales (xs:xss) | or (map (iguales xs) xss) = xs : sinIguales (xss\\[ys| ys <- xss, iguales xs ys])
                    | otherwise                  = xs : sinIguales xss

import Data.List

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

sumas3Capicuas x = sinRepetir [(a,b,c) | a <- [0..x]

, b <- [a..x-a]

, let c = x - a - b

, esCapicua a

, esCapicua b

, esCapicua c ]

esCapicua :: Integer -> Bool

esCapicua n | even x = take y n' == reverse (drop y n')

| otherwise = take y n' == reverse (drop (y+1) n')

where n' = show n

x = length n'

y = x `div` 2

sinRepetir :: [(Integer, Integer, Integer)] -> [(Integer, Integer, Integer)]

sinRepetir xs = aTerna $ sinIguales $ aLista xs

aLista :: [(Integer, Integer, Integer)] -> [[Integer]]

aLista [] = []

aLista ((a,b,c):xs) = [a,b,c] : aLista xs

aTerna :: [[Integer]] -> [(Integer, Integer, Integer)]

aTerna [] = []

aTerna ([a,b,c]:xs) = (a,b,c) : aTerna xs

iguales :: Eq a => [a] -> [a] -> Bool

iguales xs ys = and (map (`elem` ys) xs) && null (xs\\ys)

sinIguales :: Eq a => [[a]] -> [[a]]

sinIguales [] = []

sinIguales (xs:xss) | or (map (iguales xs) xss) = xs : sinIguales (xss\\[ys| ys <- xss, iguales xs ys])

| otherwise = xs : sinIguales xss

Responder

Sumas de tres capicúas

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico