Menu Close

Posiciones del 2019 en el número pi

José A. Alonso,

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
Tagged , , , , , , ,

2 Comments

  1. frahidzam
    Responder 
    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
    Responder 
    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.