Definir la función
menorX :: Integer -> Integer |
menorX :: Integer -> Integer
tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que
92 contiene [2,9]
92 y 92×2 contienen [1,2,4,8,9]
92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9]
92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9]
92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9]
92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9] |
92 contiene [2,9]
92 y 92×2 contienen [1,2,4,8,9]
92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9]
92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9]
92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9]
92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]
Otros ejemplos
menorX 92 == 6
menorX 2967 == 3
menorX 266 == 4
menorX 18 == 5
menorX 2 == 45
menorX 125 == 72
menorX 1234567890 == 1
maximum [menorX n | n <- [1..3000]] == 72
minimum [menorX n | n <- [1..3000]] == 3 |
menorX 92 == 6
menorX 2967 == 3
menorX 266 == 4
menorX 18 == 5
menorX 2 == 45
menorX 125 == 72
menorX 1234567890 == 1
maximum [menorX n | n <- [1..3000]] == 72
minimum [menorX n | n <- [1..3000]] == 3
Soluciones
import Data.List ((\\))
-- 1ª definición
-- =============
menorX :: Integer -> Integer
menorX n =
head [x | x <- [1..]
, [0..9] `contenido` digitosMultiplos n x]
contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys =
all (`elem` ys) xs
digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
concatMap digitos [n,2*n..x*n]
digitos :: Integer -> [Integer]
digitos n =
[read [c] | c <- show n]
-- 2ª definición
-- =============
menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
where aux xs x
| [0..9] `contenido` xs = x
| otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1)
-- 3ª definición
-- =============
menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
where aux xs x
| null xs = x
| otherwise = aux (xs \\ show (n*(x+1))) (x+1)
-- 4ª definición
-- =============
menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
where aux xs x nx | null ys = x
| otherwise = aux ys (1+x) (nx+n)
where ys = xs \\ show nx
-- Comparación de eficiencia
-- =========================
-- λ> maximum [menorX n | n <- [1..6000]]
-- 72
-- (2.04 secs, 3,737,579,888 bytes)
-- λ> maximum [menorX2 n | n <- [1..6000]]
-- 72
-- (0.52 secs, 818,602,736 bytes)
-- λ> maximum [menorX3 n | n <- [1..6000]]
-- 72
-- (0.10 secs, 67,090,800 bytes)
-- λ> maximum [menorX3 n | n <- [1..6000]]
-- 72
-- (0.08 secs, 67,090,800 bytes)
--
-- λ> maximum [menorX3 n | n <- [1..10^5]]
-- 72
-- (0.81 secs, 1,044,781,216 bytes)
-- λ> maximum [menorX4 n | n <- [1..10^5]]
-- 72
-- (0.71 secs, 1,009,113,304 bytes) |
import Data.List ((\\))
-- 1ª definición
-- =============
menorX :: Integer -> Integer
menorX n =
head [x | x <- [1..]
, [0..9] `contenido` digitosMultiplos n x]
contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys =
all (`elem` ys) xs
digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
concatMap digitos [n,2*n..x*n]
digitos :: Integer -> [Integer]
digitos n =
[read [c] | c <- show n]
-- 2ª definición
-- =============
menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
where aux xs x
| [0..9] `contenido` xs = x
| otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1)
-- 3ª definición
-- =============
menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
where aux xs x
| null xs = x
| otherwise = aux (xs \\ show (n*(x+1))) (x+1)
-- 4ª definición
-- =============
menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
where aux xs x nx | null ys = x
| otherwise = aux ys (1+x) (nx+n)
where ys = xs \\ show nx
-- Comparación de eficiencia
-- =========================
-- λ> maximum [menorX n | n <- [1..6000]]
-- 72
-- (2.04 secs, 3,737,579,888 bytes)
-- λ> maximum [menorX2 n | n <- [1..6000]]
-- 72
-- (0.52 secs, 818,602,736 bytes)
-- λ> maximum [menorX3 n | n <- [1..6000]]
-- 72
-- (0.10 secs, 67,090,800 bytes)
-- λ> maximum [menorX3 n | n <- [1..6000]]
-- 72
-- (0.08 secs, 67,090,800 bytes)
--
-- λ> maximum [menorX3 n | n <- [1..10^5]]
-- 72
-- (0.81 secs, 1,044,781,216 bytes)
-- λ> maximum [menorX4 n | n <- [1..10^5]]
-- 72
-- (0.71 secs, 1,009,113,304 bytes)
Se puede imprimir o compartir con
Me has servido de inspiración para poder hacerlo.
Solo un comentario, probablemente lookup sea O(n) ya que es una lista y no un diccionario. length también es O(n) y ya que tiene que contener los 10 elementos distintos (por nub), podemos aprovecharnos de eso y ahorrarnos el sort.
Buena definición, mejor si le quitas el sort que no lo necesitas y lo metes como función auxiliar de menorX para no cargar con la variable n en el argumento.
Creo que es algo más eficiente que el resto.
Buenas, puedes hacer tu función aún más eficiente si tomas ys como (y:ys) y así te ahorras el usar head y tail. También puedes usar la función
(\\)
de Data.List para hacer más eficiente el cálculo de m. Quedaría tal que así:Donde menorX2 es tu función.
Muy buena!
Estaba pensando que quizá se podría mejorar la eficiencia de esta manera:
Dejando así la lista infinita [1..] fuera de la definición y en lugar de hacer el producto (
n*y
) cada vez que simplemente sumara n al anterior.Sin embargo esta mejora no resulta eficiente ya que solo se usa el producto hasta
72*n
como mucho, y calcular tan pocos productos y tan pequeños no le resulta costoso al ordenador.Falla para (menorX 1) que da 9 en lugar de 10.
Falla para (menorX 1) que da 9 en lugar de 10.
Se puede eliminar el primer argumento de la función aux.