Posiciones de un carácter en una cadena
Definir la función
|
1 |
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,
|
1 |
posiciones 'a' "Salamamca" == [1,3,5,8] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
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 |