Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Números de Lychrel
- 2. Suma de los dígitos de una cadena
- 3. Poner en mayúscula la primera letra y las restantes en minúsculas
- 4. Mayúsculas iniciales
- 5. Posiciones de un carácter en una cadena
A continuación se muestran las soluciones.
1. Números de Lychrel
Un número de Lychrel es un número para el que nunca se obtiene un capicúa mediante el proceso de invertir las cifras y sumar los dos números. Por ejemplo, los siguientes números no son números de Lychrel:
- 56, ya que en un paso se obtiene un capicúa: 56+65=121.
- 57, ya que en dos pasos se obtiene un capicúa: 57+75=132, 132+231=363
- 59, ya que en dos pasos se obtiene un capicúa: 59+95=154, 154+451=605, 605+506=1111
- 89, ya que en 24 pasos se obtiene un capicúa.
En esta serie de ejercicios vamos a buscar el primer número de Lychrel.
Ejercicio 1. Definir la función
esCapicua :: Integer -> Bool |
tal que esCapicua x se verifica si x es capicúa. Por ejemplo,
esCapicua 252 == True esCapicua 253 == False |
Ejercicio 2. Definir la función
inverso :: Integer -> Integer |
tal que inverso x es el número obtenido escribiendo las cifras de x en orden inverso. Por ejemplo,
inverso 253 == 352 |
Ejercicio 3. Definir la función
siguiente :: Integer -> Integer |
tal que siguiente x es el número obtenido sumándole a x su inverso. Por ejemplo,
siguiente 253 == 605 |
Ejercicio 4. Definir la función
busquedaDeCapicua :: Integer -> [Integer] |
tal que busquedaDeCapicua x es la lista de los números tal que el primero es x, el segundo es el siguiente de x y así sucesivamente hasta que se alcanza un capicúa. Por ejemplo,
busquedaDeCapicua 253 == [253,605,1111] |
Ejercicio 5. Definir la función
capicuaFinal :: Integer -> Integer |
tal que capicuaFinal x es la capicúa con la que termina la búsqueda de capicúa a partir de x. Por ejemplo,
capicuaFinal 253 == 1111 |
Ejercicio 6. Definir la función
orden :: Integer -> Integer |
tal que orden x es el número de veces que se repite el proceso de calcular el inverso a partir de x hasta alcanzar un número capicúa. Por ejemplo,
orden 253 == 2 |
Ejercicio 7. Definir la función
ordenMayor :: Integer -> Integer -> Bool |
tal que ordenMayor x n se verifica si el orden de x es mayor o igual que n. Dar la definición sin necesidad de evaluar el orden de x. Por ejemplo,
λ> ordenMayor 1186060307891929990 2 True λ> orden 1186060307891929990 261 |
Ejercicio 8. Definir la función
ordenEntre :: Integer -> Integer -> [Integer] |
tal que ordenEntre m n es la lista de los elementos cuyo orden esmayor o igual que m y menor que n. Por ejemplo,
take 5 (ordenEntre 10 11) == [829,928,9059,9149,9239] |
Ejercicio 9. Definir la función
menorDeOrdenMayor :: Integer -> Integer |
tal que menorDeOrdenMayor n es el menor elemento cuyo orden es mayor que n. Por ejemplo,
menorDeOrdenMayor 2 == 19 menorDeOrdenMayor 20 == 89 |
Ejercicio 10. Definir la función
menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)] |
tal que menoresdDeOrdenMayor m es la lista de los pares (n,x) tales que n es un número entre 1 y m y x es el menor elemento de orden mayor que n. Por ejemplo,
menoresdDeOrdenMayor 5 == [(1,10),(2,19),(3,59),(4,69),(5,79)] |
Ejercicio 11. A la vista de los resultados de menoresdDeOrdenMayor 5 conjeturar sobre la última cifra de menorDeOrdenMayor.
Ejercicio 12. Decidir con QuickCheck la conjetura.
Ejercicio 13. Calcular menoresdDeOrdenMayor 50
Ejercicio 14. A la vista de menoresdDeOrdenMayor 50, conjeturar el orden de 196.
Ejercicio 15. Comprobar con QuickCheck la conjetura sobre el orden de 196.
1.1. Soluciones en Haskell
import Test.QuickCheck -- Solución de ejercicio 1 esCapicua :: Integer -> Bool esCapicua x = x' == reverse x' where x' = show x -- Solución de ejercicio 2 inverso :: Integer -> Integer inverso = read . reverse . show -- Solución de ejercicio 3 siguiente :: Integer -> Integer siguiente x = x + inverso x -- Solución de ejercicio 4 busquedaDeCapicua :: Integer -> [Integer] busquedaDeCapicua x | esCapicua x = [x] | otherwise = x : busquedaDeCapicua (siguiente x) -- Solución de ejercicio 5 capicuaFinal :: Integer -> Integer capicuaFinal x = last (busquedaDeCapicua x) -- Solución de ejercicio 6 orden :: Integer -> Integer orden x | esCapicua x = 0 | otherwise = 1 + orden (siguiente x) -- Solución de ejercicio 7 ordenMayor :: Integer -> Integer -> Bool ordenMayor x n | esCapicua x = n == 0 | n <= 0 = True | otherwise = ordenMayor (siguiente x) (n-1) -- Solución de ejercicio 8 ordenEntre :: Integer -> Integer -> [Integer] ordenEntre m n = [x | x <- [1..], ordenMayor x m, not (ordenMayor x n)] -- Solución de ejercicio 9 menorDeOrdenMayor :: Integer -> Integer menorDeOrdenMayor n = head [x | x <- [1..], ordenMayor x n] -- Solución de ejercicio 10 menoresdDeOrdenMayor :: Integer -> [(Integer,Integer)] menoresdDeOrdenMayor m = [(n,menorDeOrdenMayor n) | n <- [1..m]] -- Solución de ejercicio 11 -- La conjetura es que para n mayor que 1, la última cifra de -- (menorDeOrdenMayor n) es 9. -- Solución de ejercicio 12 -- ======================== -- La conjetura es prop_menorDeOrdenMayor :: Integer -> Property prop_menorDeOrdenMayor n = n > 1 ==> menorDeOrdenMayor n `mod` 10 == 9 -- La comprobación es -- λ> quickCheck prop_menorDeOrdenMayor -- *** Failed! Falsifiable (after 22 tests and 2 shrinks): -- 25 -- Se puede comprobar que 25 es un contraejemplo, -- λ> menorDeOrdenMayor 25 -- 196 -- Solución de ejercicio 13 -- El cálculo es -- λ> menoresdDeOrdenMayor 50 -- [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89), -- (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89), -- (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196), -- (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196), -- (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196), -- (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196), -- (47,196),(48,196),(49,196),(50,196)] -- Solución de ejercicio 14 -- La conjetura es que el orden de 196 es infinito y, por tanto, -- 196 es un número del Lychrel. -- Solución de ejercicio 15 -- ======================== -- La propiedad es prop_ordenDe196 :: Integer -> Bool prop_ordenDe196 n = ordenMayor 196 n -- La comprobación es -- λ> quickCheck prop_ordenDe196 -- +++ OK, passed 100 tests. |
1.2. Soluciones en Python
from itertools import islice from sys import setrecursionlimit from typing import Generator, Iterator from hypothesis import given, settings from hypothesis import strategies as st setrecursionlimit(10**6) # Solución del ejercicio 1 def esCapicua(x: int) -> bool: return x == int(str(x)[::-1]) # Solución del ejercicio 2 def inverso(x: int) -> int: return int(str(x)[::-1]) # Solución del ejercicio 3 def siguiente(x: int) -> int: return x + inverso(x) # Solución del ejercicio 4 def busquedaDeCapicua(x: int) -> list[int]: if esCapicua(x): return [x] return [x] + busquedaDeCapicua(siguiente(x)) # Solución del ejercicio 5 def capicuaFinal(x: int) -> int: return busquedaDeCapicua(x)[-1] # Solución del ejercicio 6 def orden(x: int) -> int: if esCapicua(x): return 0 return 1 + orden(siguiente(x)) # Solución del ejercicio 7 def ordenMayor(x: int, n: int) -> bool: if esCapicua(x): return n == 0 if n <= 0: return True return ordenMayor(siguiente(x), n - 1) # Solución del ejercicio 8 # ======================== # naturales es el generador de los números naturales positivos, Por # ejemplo, # >>> list(islice(naturales(), 5)) # [1, 2, 3, 4, 5] def naturales() -> Iterator[int]: i = 1 while True: yield i i += 1 def ordenEntre(m: int, n: int) -> Generator[int, None, None]: return (x for x in naturales() if ordenMayor(x, m) and not ordenMayor(x, n)) # Solución del ejercicio 9 def menorDeOrdenMayor(n: int) -> int: return list(islice((x for x in naturales() if ordenMayor(x, n)), 1))[0] # Solución del ejercicio 10 def menoresdDeOrdenMayor(m: int) -> list[tuple[int, int]]: return [(n, menorDeOrdenMayor(n)) for n in range(1, m + 1)] # Solución del ejercicio 11 # La conjetura es que para n mayor que 1, la última cifra de # menorDeOrdenMayor(n) es 9. # Solución del ejercicio 12 # ========================= # La conjetura es # @given(st.integers(min_value=2, max_value=200)) # def test_menorDeOrdenMayor(n: int) -> None: # assert menorDeOrdenMayor(n) % 10 == 9 # La comprobación es # src> poetry run pytest -q numeros_de_Lychrel.py # E assert (196 % 10) == 9 # E + where 196 = menorDeOrdenMayor(25) # E Falsifying example: test_menorDeOrdenMayor( # E n=25, # E ) # Se puede comprobar que 25 es un contraejemplo, # >>> menorDeOrdenMayor(25) # 196 # Solución del ejercicio 13 # El cálculo es # λ> menoresdDeOrdenMayor 50 # [(1,10),(2,19),(3,59),(4,69),(5,79),(6,79),(7,89),(8,89),(9,89), # (10,89),(11,89),(12,89),(13,89),(14,89),(15,89),(16,89),(17,89), # (18,89),(19,89),(20,89),(21,89),(22,89),(23,89),(24,89),(25,196), # (26,196),(27,196),(28,196),(29,196),(30,196),(31,196),(32,196), # (33,196),(34,196),(35,196),(36,196),(37,196),(38,196),(39,196), # (40,196),(41,196),(42,196),(43,196),(44,196),(45,196),(46,196), # (47,196),(48,196),(49,196),(50,196)] # Solución del ejercicio 14 # El orden de 196 es infinito y, por tanto, 196 es un número # de Lychrel. # Solución del ejercicio 15 # ========================= # La propiedad es @settings(deadline=None) @given(st.integers(min_value=2, max_value=5000)) def test_ordenDe196(n: int) -> None: assert ordenMayor(196, n) # La comprobación es # src> poetry run pytest -q numeros_de_Lychrel.py # 1 passed in 7.74s |
2. Suma de los dígitos de una cadena
Definir la función
sumaDigitos :: String -> Int |
tal que sumaDigitos xs es la suma de los dígitos de la cadena xs. Por ejemplo,
sumaDigitos "SE 2431 X" == 10 |
2.1. Soluciones en Haskell
import Data.Char (digitToInt, isDigit) import Test.QuickCheck -- 1ª solución -- =========== sumaDigitos1 :: String -> Int sumaDigitos1 xs = sum [digitToInt x | x <- xs, isDigit x] -- 2ª solución -- =========== sumaDigitos2 :: String -> Int sumaDigitos2 [] = 0 sumaDigitos2 (x:xs) | isDigit x = digitToInt x + sumaDigitos2 xs | otherwise = sumaDigitos2 xs -- 3ª solución -- =========== sumaDigitos3 :: String -> Int sumaDigitos3 xs = sum (map digitToInt (filter isDigit xs)) -- 4ª solución -- =========== sumaDigitos4 :: String -> Int sumaDigitos4 = sum . map digitToInt . filter isDigit -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sumaDigitos :: String -> Bool prop_sumaDigitos xs = all (== sumaDigitos1 xs) [sumaDigitos2 xs, sumaDigitos3 xs, sumaDigitos4 xs] -- La comprobación es -- λ> quickCheck prop_sumaDigitos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaDigitos1 (take (4*10^6) (cycle "ab12")) -- 3000000 -- (1.92 secs, 819,045,328 bytes) -- λ> sumaDigitos2 (take (4*10^6) (cycle "ab12")) -- 3000000 -- (1.79 secs, 856,419,112 bytes) -- λ> sumaDigitos3 (take (4*10^6) (cycle "ab12")) -- 3000000 -- (0.62 secs, 723,045,296 bytes) -- λ> sumaDigitos4 (take (4*10^6) (cycle "ab12")) -- 3000000 -- (0.63 secs, 723,045,552 bytes) |
2.2. Soluciones en Python
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def sumaDigitos1(xs: str) -> int: return sum((int(x) for x in xs if x.isdigit())) # 2ª solución # =========== def sumaDigitos2(xs: str) -> int: if xs: if xs[0].isdigit(): return int(xs[0]) + sumaDigitos2(xs[1:]) return sumaDigitos2(xs[1:]) return 0 # 3ª solución # =========== def sumaDigitos3(xs: str) -> int: r = 0 for x in xs: if x.isdigit(): r = r + int(x) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.text()) def test_sumaDigitos(xs: str) -> None: r = sumaDigitos1(xs) assert sumaDigitos2(xs) == r assert sumaDigitos3(xs) == r # La comprobación es # src> poetry run pytest -q suma_de_digitos_de_cadena.py # 1 passed in 0.41s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('mayorExponente1(2, 2**(2*10**4))') # Comparación de eficiencia # ========================= # # La comparación es # >>> tiempo('sumaDigitos1("ab12"*5000)') # 0.00 segundos # >>> tiempo('sumaDigitos2("ab12"*5000)') # 0.02 segundos # >>> tiempo('sumaDigitos3("ab12"*5000)') # 0.00 segundos # # >>> tiempo('sumaDigitos1("ab12"*(5*10**6))') # 1.60 segundos # >>> tiempo('sumaDigitos3("ab12"*(5*10**6))') # 1.83 segundos |
3. Poner en mayúscula la primera letra y las restantes en minúsculas
Definir la función
mayusculaInicial :: String -> String |
tal que mayusculaInicial xs es la palabra xs con la letra inicial en mayúscula y las restantes en minúsculas. Por ejemplo,
mayusculaInicial "sEviLLa" == "Sevilla" mayusculaInicial "" == "" |
3.1. Soluciones en Haskell
import Data.Char (toUpper, toLower) import Test.QuickCheck -- 1ª solución -- =========== mayusculaInicial1 :: String -> String mayusculaInicial1 [] = [] mayusculaInicial1 (x:xs) = toUpper x : [toLower y | y <- xs] -- 2ª solución -- =========== mayusculaInicial2 :: String -> String mayusculaInicial2 [] = [] mayusculaInicial2 (x:xs) = toUpper x : aux xs where aux (y:ys) = toLower y : aux ys aux [] = [] -- 3ª solución -- =========== mayusculaInicial3 :: String -> String mayusculaInicial3 [] = [] mayusculaInicial3 (x:xs) = toUpper x : map toLower xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_mayusculaInicial :: String -> Bool prop_mayusculaInicial xs = all (== mayusculaInicial1 xs) [mayusculaInicial2 xs, mayusculaInicial3 xs] -- La comprobación es -- λ> quickCheck prop_mayusculaInicial -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (mayusculaInicial1 (take (10^7) (cycle "aA"))) -- 10000000 -- (2.22 secs, 1,680,592,240 bytes) -- λ> length (mayusculaInicial2 (take (10^7) (cycle "aA"))) -- 10000000 -- (2.57 secs, 2,240,592,192 bytes) -- λ> length (mayusculaInicial3 (take (10^7) (cycle "aA"))) -- 10000000 -- (0.16 secs, 1,440,592,192 bytes) |
3.2. Soluciones en Python
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def mayusculaInicial1(xs: str) -> str: if xs: return "".join([xs[0].upper()] + [y.lower() for y in xs[1:]]) return "" # 2ª solución # =========== def mayusculaInicial2(xs: str) -> str: def aux(ys: str) -> str: if ys: return ys[0].lower() + aux(ys[1:]) return "" if xs: return "".join(xs[0].upper() + aux(xs[1:])) return "" # 3ª solución # =========== def mayusculaInicial3(xs: str) -> str: if xs: return "".join([xs[0].upper()] + list(map(str.lower, xs[1:]))) return "" # 4ª solución # =========== def mayusculaInicial4(xs: str) -> str: return xs.capitalize() # Comprobación de equivalencia # ============================ # La propiedad es @given(st.text()) def test_mayusculaInicial(xs: str) -> None: r = mayusculaInicial1(xs) assert mayusculaInicial2(xs) == r assert mayusculaInicial3(xs) == r # La comprobación es # src> poetry run pytest -q mayuscula_inicial.py # 1 passed in 0.26s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('len(mayusculaInicial1("aB"*(10**7)))') # 1.92 segundos # >>> tiempo('len(mayusculaInicial2("aB"*(10**7)))') # Process Python terminado (killed) # >>> tiempo('len(mayusculaInicial3("aB"*(10**7)))') # 1.59 segundos # >>> tiempo('len(mayusculaInicial4("aB"*(10**7)))') # 0.13 segundos |
4. Mayúsculas iniciales
Se consideran las siguientes reglas de mayúsculas iniciales para los títulos:
- la primera palabra comienza en mayúscula y
- todas las palabras que tienen 4 letras como mínimo empiezan con mayúsculas
Definir la función
titulo :: [String] -> [String] |
tal que titulo ps es la lista de las palabras de ps con las reglas de mayúsculas iniciales de los títulos. Por ejemplo,
λ> titulo ["eL","arTE","DE","La","proGraMacion</b> ["El","Arte","de","la","Programacion</b> |
4.1. Soluciones en Haskell
import Data.Char (toUpper, toLower) import Test.QuickCheck -- 1ª solución -- =========== titulo1 :: [String] -> [String] titulo1 [] = [] titulo1 (p:ps) = mayusculaInicial p : [transforma q | q <- ps] -- (mayusculaInicial xs) es la palabra xs con la letra inicial -- en mayúscula y las restantes en minúsculas. Por ejemplo, -- mayusculaInicial "sEviLLa" == "Sevilla" mayusculaInicial :: String -> String mayusculaInicial [] = [] mayusculaInicial (x:xs) = toUpper x : [toLower y | y <- xs] -- (transforma p) es la palabra p con mayúscula inicial si su longitud -- es mayor o igual que 4 y es p en minúscula en caso contrario transforma :: String -> String transforma p | length p >= 4 = mayusculaInicial p | otherwise = minuscula p -- (minuscula xs) es la palabra xs en minúscula. minuscula :: String -> String minuscula xs = [toLower x | x <- xs] -- 2ª solución -- =========== titulo2 :: [String] -> [String] titulo2 [] = [] titulo2 (p:ps) = mayusculaInicial p : aux ps where aux [] = [] aux (q:qs) = transforma q : aux qs -- 3ª solución -- =========== titulo3 :: [String] -> [String] titulo3 [] = [] titulo3 (p:ps) = mayusculaInicial p : map transforma ps -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_titulo :: [String] -> Bool prop_titulo xs = all (== titulo1 xs) [titulo2 xs, titulo3 xs] -- La comprobación es -- λ> quickCheck prop_titulo -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (titulo1 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre</b>))) -- 10000000 -- (2.17 secs, 1,680,592,512 bytes) -- λ> length (titulo2 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre</b>))) -- 10000000 -- (2.45 secs, 2,240,592,464 bytes) -- λ> length (titulo3 (take (10^7) (cycle ["hOy","Es","juEves","dE","Noviembre</b>))) -- 10000000 -- (0.16 secs, 1,440,592,464 bytes) |
4.2. Soluciones en Python
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== # (mayusculaInicial xs) es la palabra xs con la letra inicial # en mayúscula y las restantes en minúsculas. Por ejemplo, # mayusculaInicial("sEviLLa") == "Sevilla" def mayusculaInicial(xs: str) -> str: return xs.capitalize() # (minuscula xs) es la palabra xs en minúscula. def minuscula(xs: str) -> str: return xs.lower() # (transforma p) es la palabra p con mayúscula inicial si su longitud # es mayor o igual que 4 y es p en minúscula en caso contrario def transforma(p: str) -> str: if len(p) >= 4: return mayusculaInicial(p) return minuscula(p) def titulo1(ps: list[str]) -> list[str]: if ps: return [mayusculaInicial(ps[0])] + [transforma(q) for q in ps[1:]] return [] # 2ª solución # =========== def titulo2(ps: list[str]) -> list[str]: def aux(qs: list[str]) -> list[str]: if qs: return [transforma(qs[0])] + aux(qs[1:]) return [] if ps: return [mayusculaInicial(ps[0])] + aux(ps[1:]) return [] # 3ª solución # =========== def titulo3(ps: list[str]) -> list[str]: if ps: return [mayusculaInicial(ps[0])] + list(map(transforma, ps[1:])) return [] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.text())) def test_titulo(ps: list[str]) -> None: r = titulo1(ps) assert titulo2(ps) == r assert titulo3(ps) == r # La comprobación es # src> poetry run pytest -q mayusculas_iniciales.py # 1 passed in 0.55s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('len(mayusculaInicial1("aB"*(10**7)))') # >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion </b>*1900)') # 0.00 segundos # >>> tiempo('titulo2(["eL","arTE","DE","La","proGraMacion </b>*1900)') # 0.30 segundos # >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion </b>*1900)') # 0.00 segundos # # >>> tiempo('titulo1(["eL","arTE","DE","La","proGraMacion </b>*(2*10**6))') # 2.93 segundos # >>> tiempo('titulo3(["eL","arTE","DE","La","proGraMacion </b>*(2*10**6))') # 2.35 segundos |
5. Posiciones de un carácter en una cadena
Definir la función
posiciones :: Char -> String -> [Int] |
tal que posiciones x ys es la lista de la posiciones del carácter x en la cadena ys. Por ejemplo,
posiciones 'a' "Salamamca" == [1,3,5,8] |
5.1. Soluciones en Haskell
import Data.List (elemIndices) import Test.QuickCheck -- 1ª solución -- =========== posiciones1 :: Char -> String -> [Int] posiciones1 x ys = [n | (y,n) <- zip ys [0..], y == x] -- 2ª solución -- =========== posiciones2 :: Char -> String -> [Int] posiciones2 x ys = aux x ys 0 where aux _ [] _ = [] aux b (a:as) n | a == b = n : aux b as (n+1) | otherwise = aux b as (n+1) -- 3ª solución -- =========== posiciones3 :: Char -> String -> [Int] posiciones3 = elemIndices -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_posiciones :: Char -> String -> Bool prop_posiciones x ys = all (== posiciones1 x ys) [posiciones2 x ys, posiciones3 x ys] -- La comprobación es -- λ> quickCheck prop_posiciones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (posiciones1 'a' (take (6*10^6) (cycle "abc"))) -- 2000000 -- (2.48 secs, 1,680,591,672 bytes) -- λ> length (posiciones2 'a' (take (6*10^6) (cycle "abc"))) -- 2000000 -- (2.98 secs, 1,584,591,720 bytes) -- λ> length (posiciones3 'a' (take (6*10^6) (cycle "abc"))) -- 2000000 -- (0.11 secs, 496,591,600 bytes) |
5.2. Soluciones en Python
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # -- 1ª solución # -- =========== def posiciones1(x: str, ys: str) -> list[int]: return [n for (n, y) in enumerate(ys) if y == x] # -- 2ª solución # -- =========== def posiciones2(x: str, ys: str) -> list[int]: def aux(a: str, bs: str, n: int) -> list[int]: if bs: if a == bs[0]: return [n] + aux(a, bs[1:], n + 1) return aux(a, bs[1:], n + 1) return [] return aux(x, ys, 0) # -- 3ª solución # -- =========== def posiciones3(x: str, ys: str) -> list[int]: r = [] for n, y in enumerate(ys): if x == y: r.append(n) return r # La propiedad es @given(st.text(), st.text()) def test_posiciones(x: str, ys: str) -> None: r = posiciones1(x, ys) assert posiciones2(x, ys) == r assert posiciones3(x, ys) == r # La comprobación es # src> poetry run pytest -q posiciones_de_un_caracter_en_una_cadena.py # 1 passed in 0.29s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('posiciones1("a", "abc"*6000)') # 0.00 segundos # >>> tiempo('posiciones2("a", "abc"*6000)') # 0.06 segundos # >>> tiempo('posiciones3("a", "abc"*6000)') # 0.00 segundos # # >>> tiempo('posiciones1("a", "abc"*(2*10**7))') # 3.02 segundos # >>> tiempo('posiciones3("a", "abc"*(2*10**7))') # 3.47 segundos |