Menu Close

Posiciones del 2019 en el número pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

   posiciones :: String -> Int -> IO [Int]

tal que (posicion cs k) es es la lista de las posiciones iniciales de cs en la sucesión formada por los k primeros dígitos decimales del número pi. Por ejemplo,

   λ> posiciones "141" 1000
   [0,294]
   λ> posiciones "4159" 10000
   [1,5797,6955,9599]

Calcular la primera posición de 2019 en los decimales de pi y el número de veces que aparece 2019 en en el primer millón de decimales de pi.

Soluciones

import Data.List ( isPrefixOf
                 , findIndices
                 , tails  
                 )
 
-- 1ª definición
-- =============
 
posiciones :: String -> Int -> IO [Int]
posiciones cs k = do
  ds <- readFile "Digitos_de_pi.txt"
  return (posicionesEnLista cs (take (k-1) (drop 2 ds)))
 
--    posicionesEnLista "23" "234235523"  ==  [0,3,7]
posicionesEnLista :: Eq a => [a] -> [a] -> [Int]
posicionesEnLista xs ys = reverse (aux ys 0 [])
  where aux []      _ ns = ns
        aux (y:ys') n ns | xs `isPrefixOf` (y:ys') = aux ys' (n+1) (n:ns)
                         | otherwise               = aux ys' (n+1) ns
 
-- 2ª definición
-- =============
 
posiciones2 :: String -> Int -> IO [Int]
posiciones2 cs k = do
  ds <- readFile "Digitos_de_pi.txt"
  return (findIndices (cs `isPrefixOf`) (tails (take (k-1) (drop 2 ds))))
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length <$> posiciones "2019" (10^6)
--    112
--    (1.73 secs, 352,481,272 bytes)
--    λ> length <$> posiciones2 "2019" (10^6)
--    112
--    (0.16 secs, 144,476,384 bytes)
 
-- El cálculo es
--    λ> ps <- posiciones "2019" (10^6)
--    λ> head ps
--    243
--    λ> length ps
--    112
-- Por tanto, la posición de la primera ocurrencia es 243 y hay 112
-- ocurrencias. Otra forma de hacer los cálculos anteriores es
--    λ> head <$> posiciones "2019" (10^6)
--    243
--    λ> length <$> posiciones "2019" (10^6)
--    112

Pensamiento

Aprendió tantas cosas, que no tuvo tiempo para pensar en ninguna de ellas.

Antonio Machado

Posted in Avanzado

2 Comments

  1. frahidzam
    import Data.List (isPrefixOf)
     
    posiciones :: String -> Int -> IO [Int]
    posiciones xs n = do
      ds <- readFile "Digitos_de_pi.txt"
      return (indice (take n (drop 2 ds)) xs)
     
    indice :: String -> String -> [Int]
    indice xs ys = indiceAux xs 0
      where indiceAux [] _ = []
            indiceAux (x:xs) n
              | isPrefixOf ys (x:xs) = [n] ++ indiceAux xs (n+1)
              | otherwise            = indiceAux xs (n+1) 
     
    -- Para calcular la primera posición del 2019
    -- λ> posicionesA1 "2019" 1000000
    -- [243, 701, 994, 3823, 5361, 5644, 13532, 23824, 25219, 25978, 31161,
    -- 32353, 37811, 42991, 53194, 59270, 65773, 85060, 89905, 126998,
    -- 147951, 148122, 152111, 165835, 195270, 206258, 208615, 220146,
    -- 252644, 256554, 267405, 271133, 271673, 295725, 297395, 298873,
    -- 303034, 305641, 315448, 342848, 354144, 361105, 364832, 386296,
    -- 388597, 404340, 404398, 424723, 426769, 437333, 442975, 447937,
    -- 450445, 453009, 459151, 462490, 472910, 480654, 484735, 490977,
    -- 491423, 494428, 516226, 518961, 520662, 544042, 551067, 561060,
    -- 562516, 563176, 563408, 564114, 569491, 570057, 575120, 582373,
    -- 609675, 611462, 620488, 636794, 641096, 647300, 667854, 668820,
    -- 672849, 682203, 697430, 725181, 745271, 751066, 758411, 779708,
    -- 815874, 824103, 846338, 847347, 848129, 855276, 859224, 864808,
    -- 867873, 876900, 881387, 900028, 902414, 938872, 940861, 952467,
    -- 957606, 959555, 976395, 980356]  
    --
    -- Vemos que sale el 243
    -- 
    -- Calculamos la longitud de la lista anterior para ver el número de
    -- apariciones. Nos sale que es 112
  2. luipromor
    import Data.List (isPrefixOf)
     
    posiciones :: String -> Int -> IO [Int]
    posiciones xs k  = do
      cs <- readFile "Digitos_de_pi.txt"
      return (aux xs (take k  (drop 2 cs)) 0)
      where aux xs [] n = []
            aux xs (x:xss) n
              | isPrefixOf xs (x:xss) = n : aux xs xss (n+1)
              | otherwise             = aux xs xss (n+1)
     
    -- λ> xs = posiciones "2019" 1000000
    -- λ> xs
    -- [243, 701, 994, 3823, 5361, 5644, 13532, 23824, 25219, 25978,
    -- 31161, 32353, 37811, 42991, 53194, 59270, 65773, 85060, 89905,
    -- 126998, 147951, 148122, 152111, 165835, 195270, 206258, 208615,
    -- 220146, 252644, 256554, 267405, 271133, 271673, 295725, 297395,
    -- 298873, 303034, 305641, 315448, 342848, 354144, 361105, 364832,
    -- 386296, 388597, 404340, 404398, 424723, 426769, 437333, 442975,
    -- 447937, 450445, 453009, 459151, 462490, 472910, 480654, 484735,
    -- 490977, 491423, 494428, 516226, 518961, 520662, 544042, 551067,
    -- 561060, 562516, 563176, 563408, 564114, 569491, 570057, 575120,
    -- 582373, 609675, 611462, 620488, 636794, 641096, 647300, 667854,
    -- 668820, 672849, 682203, 697430, 725181, 745271, 751066, 758411,
    -- 779708, 815874, 824103, 846338, 847347, 848129, 855276, 859224,
    -- 864808, 867873, 876900, 881387, 900028, 902414, 938872, 940861,
    -- 952467, 957606, 959555, 976395, 980356] 
    -- λ> length it
    -- 112
    -- λ> xs = posicionesA2 "2019" 1000000
    -- λ> xs
    -- [243, 701, 994, 3823, 5361, 5644, 13532, 23824, 25219, 25978,
    -- 31161, 32353, 37811, 42991, 53194, 59270, 65773, 85060, 89905,
    -- 126998, 147951, 148122, 152111, 165835, 195270, 206258, 208615,
    -- 220146, 252644, 256554, 267405, 271133, 271673, 295725, 297395,
    -- 298873, 303034, 305641, 315448, 342848, 354144, 361105, 364832,
    -- 386296, 388597, 404340, 404398, 424723, 426769, 437333, 442975,
    -- 447937, 450445, 453009, 459151, 462490, 472910, 480654, 484735,
    -- 490977, 491423, 494428, 516226, 518961, 520662, 544042, 551067,
    -- 561060, 562516, 563176, 563408, 564114, 569491, 570057, 575120,
    -- 582373, 609675, 611462, 620488, 636794, 641096, 647300, 667854,
    -- 668820, 672849, 682203, 697430, 725181, 745271, 751066, 758411,
    -- 779708, 815874, 824103, 846338, 847347, 848129, 855276, 859224,
    -- 864808, 867873, 876900, 881387, 900028, 902414, 938872, 940861,
    -- 952467, 957606, 959555, 976395, 980356] 
    -- λ> head it
    -- 243

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.