Posiciones del 2019 en el número pi

PorJosé A. Alonso 17-enero-201924-enero-2019

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

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

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

1	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]

λ> 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

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

2 Comentarios

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

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

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

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