{"id":7749,"date":"2022-06-11T10:59:35","date_gmt":"2022-06-11T08:59:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7749"},"modified":"2022-06-11T10:59:35","modified_gmt":"2022-06-11T08:59:35","slug":"pfh-la-semana-en-exercitium-11-de-junio-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-11-de-junio-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (11 de junio de 2022)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Diccionario de frecuencias<\/a><\/li>\n<li><a href=\"#ej2\">2. Primos circulares<\/a><\/li>\n<li><a href=\"#ej3\">3. Codificaci\u00f3n de G\u00f6del<\/a><\/li>\n<li><a href=\"#ej4\">4. Representaci\u00f3n matricial de relaciones binarias<\/a><\/li>\n<li><a href=\"#ej5\">5. Distancia esperada entre dos puntos de un cuadrado unitario<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Diccionario de frecuencias<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   frecuencias :: Ord a => [a] -> Map a Int\n<\/pre>\n<p>tal que <code>(frecuencias xs)<\/code> es el diccionario formado por los elementos de <code>xs<\/code> junto con el n\u00famero de veces que aparecen en <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> frecuencias \"sosos\"\n   fromList [('o',2),('s',3)]\n   \u03bb> frecuencias (show (10^100))\n   fromList [('0',100),('1',1)]\n   \u03bb> frecuencias (take (10^6) (cycle \"abc\"))\n   fromList [('a',333334),('b',333333),('c',333333)]\n   \u03bb> size (frecuencias (take (10^6) (cycle [1..10^6])))\n   1000000\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (foldl')\nimport Data.Map (Map, empty, insertWith, fromList, fromListWith, size)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfrecuencias1 :: Ord a => [a] -> Map a Int\nfrecuencias1 []     = empty\nfrecuencias1 (x:xs) = insertWith (+) x 1 (frecuencias1 xs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfrecuencias2 :: Ord a => [a] -> Map a Int\nfrecuencias2 = foldl' (\\d x-> insertWith (+) x 1 d) empty\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nfrecuencias3 :: Ord a => [a] -> Map a Int\nfrecuencias3 xs = fromListWith (+) (zip xs (repeat 1))\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_frecuencias :: [Int] -> Bool\nprop_frecuencias xs =\n  all (== frecuencias1 xs)\n      [ frecuencias2 xs\n      , frecuencias3 xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_frecuencias\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> frecuencias1 (take (10^6) (cycle \"abc\"))\n--    fromList [('a',333334),('b',333333),('c',333333)]\n--    (0.89 secs, 453,842,448 bytes)\n--    \u03bb> frecuencias2 (take (10^6) (cycle \"abc\"))\n--    fromList [('a',333334),('b',333333),('c',333333)]\n--    (0.54 secs, 274,181,128 bytes)\n--    \u03bb> frecuencias3 (take (10^6) (cycle \"abc\"))\n--    fromList [('a',333334),('b',333333),('c',333333)]\n--    (0.29 secs, 313,787,976 bytes)\n     \n--    \u03bb> size (frecuencias1 (take (10^6) (cycle [1..10^6])))\n--    1000000\n--    (3.76 secs, 2,651,926,024 bytes)\n--    \u03bb> size (frecuencias2 (take (10^6) (cycle [1..10^6])))\n--    1000000\n--    (1.03 secs, 1,640,678,448 bytes)\n--    \u03bb> size (frecuencias3 (take (10^6) (cycle [1..10^6])))\n--    1000000\n--    (0.88 secs, 1,672,678,536 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Diccionario_de_frecuencias.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Primos circulares<\/h3>\n<p>Un <strong>primo circular<\/strong> es un n\u00famero tal que todas las rotaciones de  d\u00edgitos producen n\u00fameros primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus d\u00edgitos son 197, 971 y 719 y los tres n\u00fameros son primos.<\/p>\n<p>Definir la lista<\/p>\n<pre lang=\"text\">\n   circulares :: [Integer]\n<\/pre>\n<p>cuyo valor es la lista de los n\u00fameros primos circulares. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   take 16 circulares == [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,197]\n   circulares !! 50   == 933199\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (isPrime, primes)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n  \ncirculares1 :: [Integer]\ncirculares1 = filter esCircular1 primes\n\n-- (esCircular1 n) se verifica si n es un n\u00famero circular. Por ejemplo, \n--    esCircular1 197  ==  True\n--    esCircular1 157  ==  False\nesCircular1 :: Integer -> Bool\nesCircular1 = all (isPrime . read) . rotaciones1 . show \n\n-- (rotaciones1 xs) es la lista de las rotaciones obtenidas desplazando\n-- el primer elemento xs al final. Por ejemplo,\n--    rotaciones1 [2,3,5]  ==  [[2,3,5],[3,5,2],[5,2,3]]\nrotaciones1 :: [a] -> [[a]]\nrotaciones1 xs = reverse (aux (length xs) [xs])\n    where aux 1 yss      = yss\n          aux n (ys:yss) = aux (n-1) (rota ys : ys :yss)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n  \ncirculares2 :: [Integer]\ncirculares2 = filter esCircular2 primes\n\nesCircular2 :: Integer -> Bool\nesCircular2 = all (isPrime . read) . rotaciones2 . show \n\nrotaciones2 :: [a] -> [[a]]\nrotaciones2 xs = take (length xs) (iterate rota xs)\n\n-- (rota xs) es la lista a\u00f1adiendo el primer elemento de xs al\n-- final. Por ejemplo, \n--    rota [3,2,5,7]  ==  [2,5,7,3]\nrota :: [a] -> [a]\nrota (x:xs) = xs ++ [x]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncirculares3 :: [Integer]\ncirculares3 = filter (all isPrime . rotaciones3) primes \n\nrotaciones3 :: Integer -> [Integer]\nrotaciones3 n = [read (take m (drop i (cycle s))) | i <- [1..m]]\n    where s = show n\n          m = length s\n\n-- 4\u00aa definici\u00f3n\n-- =============\n\n-- Nota. La 4\u00aa definici\u00f3n es una mejora observando que para que n sea un\n-- n\u00famero primo circular es necesario que todos los d\u00edgitos de n sean\n-- impares, salvo para n = 2. \n\ncirculares4 :: [Integer]\ncirculares4 = 2 : filter esCircular4 primes\n\n-- (esCircular4 n) se verifica si n es un n\u00famero circular. Por ejemplo, \n--    esCircular4 197  ==  True\n--    esCircular4 157  ==  False\nesCircular4 :: Integer -> Bool\nesCircular4 n = digitosImpares n && \n                all (isPrime . read) (rotaciones2 (show n))\n\n-- (digitosImpares n) se verifica si todos los d\u00edgitos de n son\n-- impares. Por ejemplo,\n--    digitosImpares 7351  ==  True\n--    digitosImpares 7341  ==  False\ndigitosImpares :: Integer -> Bool\ndigitosImpares = all (`elem` \"135679\") . show\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_circulares :: Positive Int -> Bool\nprop_circulares (Positive n) =\n  all (== circulares1 !! n)\n      [circulares2 !! n,\n       circulares3 !! n,\n       circulares4 !! n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=50}) prop_circulares\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> circulares1 !! 46\n--    331999\n--    (2.08 secs, 7,229,208,200 bytes)\n--    \u03bb> circulares2 !! 46\n--    331999\n--    (1.93 secs, 7,165,043,992 bytes)\n--    \u03bb> circulares3 !! 46\n--    331999\n--    (0.74 secs, 2,469,098,648 bytes)\n--    \u03bb> circulares4 !! 46\n--    331999\n--    (0.28 secs, 917,501,600 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Primos_circulares.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Codificaci\u00f3n de G\u00f6del<\/h3>\n<p>Dada una lista de n\u00fameros naturales xs,  <a href=\"http:\/\/bit.ly\/2FOzmW1\">codificaci\u00f3n de G\u00f6del<\/a> de xs se obtiene multiplicando las potencias de los primos sucesivos,  siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificaci\u00f3n de xs es<\/p>\n<pre lang=\"text\">\n   2^7 * 3^1 * 5^5 = 1200000\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   codificaG   :: [Integer] -> Integer\n   decodificaG :: Integer -> [Integer]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>(codificaG xs)<\/code> es la codificaci\u00f3n de G\u00f6del de <code>xs<\/code>. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     codificaG [6,0,4]            ==  1200000\n     codificaG [3,1,1]            ==  3600\n     codificaG [3,1,0,0,0,0,0,1]  ==  4423058640\n     codificaG [1..6]             ==  126111168580452537982500\n<\/pre>\n<ul>\n<li><code>(decodificaG n)<\/code> es la lista xs cuya codificaci\u00f3n es <code>n<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     decodificaG 1200000                   ==  [6,0,4]\n     decodificaG 3600                      ==  [3,1,1]\n     decodificaG 4423058640                ==  [3,1,0,0,0,0,0,1]\n     decodificaG 126111168580452537982500  ==  [1,2,3,4,5,6]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversas; es decir,<\/p>\n<pre lang=\"text\">\n   decodificaG (codificaG xs) = xs\n   codificaG (decodificaG n) = n\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, group)\nimport Data.Numbers.Primes (primes, primeFactors)\nimport Test.QuickCheck (NonNegative (getNonNegative),\n                        NonEmptyList (NonEmpty),\n                        Positive (Positive, getPositive), quickCheck)\n\n-- 1\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG1 :: [Integer] -> Integer\ncodificaG1 = codificaG1' . codificaAux\n\ncodificaAux :: [Integer] -> [Integer]\ncodificaAux = map succ\n\ncodificaG1' :: [Integer] -> Integer\ncodificaG1' = aux primes\n  where aux _ []          = 1\n        aux (p:ps) (x:xs) = p^x * aux ps xs\n\n-- 2\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG2 :: [Integer] -> Integer\ncodificaG2 = codificaG2' . codificaAux\n\ncodificaG2' :: [Integer] -> Integer\ncodificaG2' xs = product [p^x | (p, x) <- zip primes xs]\n\n-- 3\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG3 :: [Integer] -> Integer\ncodificaG3 = codificaG3' . codificaAux\n\ncodificaG3' :: [Integer] -> Integer\ncodificaG3' xs = product (zipWith (^) primes xs)\n\n-- 4\u00aa definici\u00f3n de codificaG\n-- ==========================\n\ncodificaG4 :: [Integer] -> Integer\ncodificaG4 = codificaG4' . codificaAux\n\ncodificaG4' :: [Integer] -> Integer\ncodificaG4' = product . zipWith (^) primes\n\n-- Comprobaci\u00f3n de equivalencia de codificaG\n-- =========================================\n\n-- La propiedad es\nprop_codificaG :: [NonNegative Integer] -> Bool\nprop_codificaG xs =\n  all (== codificaG1 ys)\n      [codificaG2 ys,\n       codificaG3 ys,\n       codificaG4 ys]\n  where ys = map getNonNegative xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_codificaG\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia de codificaG\n-- ======================================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (codificaG1 (replicate (4*10^4) 1)))\n--    208100\n--    (1.73 secs, 2,312,100,136 bytes)\n--    \u03bb> length (show (codificaG2 (replicate (4*10^4) 1)))\n--    208100\n--    (1.63 secs, 2,327,676,832 bytes)\n--    \u03bb> length (show (codificaG3 (replicate (4*10^4) 1)))\n--    208100\n--    (1.62 secs, 2,323,836,832 bytes)\n--    \u03bb> length (show (codificaG4 (replicate (4*10^4) 1)))\n--    208100\n--    (1.54 secs, 2,147,635,680 bytes)\n\n-- Definici\u00f3n de codificaG\n-- =======================\n\n-- Usaremos la 4\u00aa\ncodificaG :: [Integer] -> Integer\ncodificaG = codificaG4\n\n-- Definici\u00f3n de decodificaG\n-- =========================\n\ndecodificaG :: Integer -> [Integer]\ndecodificaG = decodificaAux . decodificaG'\n\ndecodificaAux :: [Integer] -> [Integer]\ndecodificaAux = map pred\n\ndecodificaG' :: Integer -> [Integer]\ndecodificaG' 1 = [0]\ndecodificaG' n = aux primes (group (primeFactors n))\n  where aux _ [] = []\n        aux (x:xs) ((y:ys):yss) | x == y    = 1 + genericLength ys : aux xs yss\n                                | otherwise = 0 : aux xs ((y:ys):yss)\n\n-- Comprobaci\u00f3n de propiedades\n-- ===========================\n\n-- La primera propiedad es\nprop_decodificaG_codificaG :: NonEmptyList (NonNegative Integer) -> Bool\nprop_decodificaG_codificaG (NonEmpty xs) = \n  decodificaG (codificaG ys) == ys\n  where ys = map getNonNegative xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_decodificaG_codificaG\n--    +++ OK, passed 100 tests.\n\n-- La 2\u00aa propiedad es\nprop_codificaG_decodificaG :: Positive Integer -> Bool\nprop_codificaG_decodificaG (Positive n) = \n  codificaG (decodificaG n) == n\n\n-- la comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_codificaG_decodificaG\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Codificacion_de_Godel.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Representaci\u00f3n matricial de relaciones binarias<\/h3>\n<p>Dada una relaci\u00f3n <code>r<\/code> sobre un conjunto de n\u00fameros enteros, la matriz asociada a <code>r<\/code> es una matriz booleana <code>p<\/code> (cuyos elementos son <code>True<\/code> o <code>False<\/code>), tal que <code>p(i,j) = True<\/code> si y s\u00f3lo si <code>i<\/code> est\u00e1 relacionado con <code>j<\/code> mediante la relaci\u00f3n <code>r<\/code>.<\/p>\n<p>Las relaciones binarias homog\u00e9neas y las matrices booleanas se pueden representar por<\/p>\n<pre lang=\"text\">\n   type Relacion = ([Int],[(Int,Int)])\n   type Matriz = Array (Int,Int) Bool\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   matrizRB:: Relacion -> Matriz\n<\/pre>\n<p>tal que <code>(matrizRB r)<\/code> es la matriz booleana asociada a <code>r<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])\n   array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),\n                        ((2,1),False),((2,2),False),((2,3),False),\n                        ((3,1),True) ,((3,2),False),((3,3),True)]\n   \u03bb> matrizRB ([1..3],[(1,3), (3,1)])\n   array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),\n                        ((2,1),False),((2,2),False),((2,3),False),\n                        ((3,1),True) ,((3,2),False),((3,3),False)]\n   \u03bb> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)\n   False\n<\/pre>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array      (Array, accumArray, array, listArray)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, suchThat,\n                        quickCheck)\n\ntype Relacion = ([Int],[(Int,Int)])\ntype Matriz   = Array (Int,Int) Bool\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB1 :: Relacion -> Matriz \nmatrizRB1 r = \n    array ((1,1),(n,n)) \n          [((a,b), (a,b) `elem` grafo r) | a <- [1..n], b <- [1..n]]\n    where n = maximum (universo r)\n          universo (us,_) = us\n          grafo (_,ps)    = ps\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB2 :: Relacion -> Matriz\nmatrizRB2 r = \n    listArray ((1,1),(n,n)) \n              [(a,b) `elem` snd r | a <- [1..n], b <- [1..n]]\n    where n = maximum (fst r)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB3 :: Relacion -> Matriz\nmatrizRB3 r = \n    accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True))\n    where n = maximum (fst r)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Tipo de relaciones binarias\nnewtype RB = RB Relacion\n  deriving Show\n\n-- relacionArbitraria genera una relaci\u00f3n arbitraria. Por ejemplo, \n--    \u03bb> generate relacionArbitraria\n--    RB ([1,2,3,4,5],[(1,4),(1,5),(2,3),(2,4),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4)])\nrelacionArbitraria :: Gen RB\nrelacionArbitraria = do\n  n <- arbitrary `suchThat` (> 1)\n  xs <- sublistOf [(x,y) | x <- [1..n], y <- [1..n]]\n  return (RB ([1..n], xs))\n\n-- RB es una subclase de Arbitrary\ninstance Arbitrary RB where\n  arbitrary = relacionArbitraria\n\n-- La propiedad es\nprop_matrizRB :: RB -> Bool\nprop_matrizRB (RB r) =\n  all (== matrizRB1 r)\n      [matrizRB2 r,\n       matrizRB3 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_matrixzB\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (2.02 secs, 1,505,248,912 bytes)\n--    \u03bb> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (1.92 secs, 833,232,360 bytes)\n--    \u03bb> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (0.05 secs, 32,848,696 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Representacion_matricial_de_relaciones_binarias.hs\">GitHub<\/a>.<\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Distancia esperada entre dos puntos de un cuadrado unitario<\/h3>\n<p>Definir, por simulaci\u00f3n, la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   distanciaEsperada :: Int -> IO Double\n<\/pre>\n<p>tal que <code>(distanciaEsperada n)<\/code> es la distancia esperada entre <code>n<\/code> puntos del cuadrado unitario de v\u00e9rtices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   distanciaEsperada 10     ==  0.43903617921423593\n   distanciaEsperada 10     ==  0.6342350621260004\n   distanciaEsperada 100    ==  0.5180418995364429\n   distanciaEsperada 100    ==  0.5288261085653962\n   distanciaEsperada 1000   ==  0.5143804432569616\n   distanciaEsperada 10000  ==  0.5208360147922616\n<\/pre>\n<p>El valor exacto de la distancia esperada es<\/p>\n<pre lang=\"text\">\n   ve = (sqrt(2) + 2 + 5*log(1+sqrt(2)))\/15 = 0.5214054331647207\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   graficaDistanciaEsperada :: [Int] -> IO ()\n<\/pre>\n<p>tal que <code>(graficaDistanciaEsperada ns)<\/code> dibuja las gr\u00e1ficas de los pares <code>(n, distanciaEsperada n)<\/code> para <code>n<\/code> en la lista creciente <code>ns<\/code> junto con la recta <code>y = ve<\/code>, donde <code>v<\/code>e es el valor exacto. Por ejemplo, <code>(graficaDistanciaEsperada [10,30..4000])<\/code> dibuja<br \/>\n<a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/03\/Distancia_esperada_entre_dos_puntos.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2020\/03\/Distancia_esperada_entre_dos_puntos.png?resize=640%2C480\" alt=\"\" width=\"640\" height=\"480\" class=\"aligncenter size-full wp-image-5680\" data-recalc-dims=\"1\" \/><\/a><\/p>\n<p><!--more--><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List     (genericLength)\nimport System.Random (newStdGen, randomRIO, randomRs)\nimport Control.Monad (replicateM)\nimport Graphics.Gnuplot.Simple\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- Un punto es un par de n\u00fameros reales.\ntype Punto = (Double, Double)\n\n-- (puntosDelCuadrado n) es una lista de n puntos del cuadrado\n-- unitario de v\u00e9rtices opuestos (0,0) y (1,1). Por ejemplo, \n--    \u03bb> puntosDelCuadrado 3\n--    [(0.6067427807212623,0.24785843546479303),\n--     (0.9579158098726746,8.047408846191773e-2),\n--     (0.856758357789639,0.9814972717003113)]\n--    \u03bb> puntosDelCuadrado 3\n--    [(1.9785720974027532e-2,0.6343219201012211),\n--     (0.21903717179861604,0.20947986189590784),\n--     (0.4739903340716357,1.2262474491489095e-2)]\npuntosDelCuadrado :: Int -> IO [Punto]\npuntosDelCuadrado n = do\n  gen <- newStdGen\n  let xs = randomRs (0,1) gen\n      (as, ys) = splitAt n xs\n      (bs, _)  = splitAt n ys\n  return (zip as bs)\n  \n-- (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por\n-- ejemplo,\n--    distancia (0,0) (3,4)  ==  5.0\ndistancia :: Punto -> Punto -> Double\ndistancia (x1,y1) (x2,y2) = sqrt ((x1-x2)^2+(y1-y2)^2)\n\n-- (distancias ps) es la lista de las distancias entre los elementos 1\u00ba\n-- y 2\u00ba, 3\u00ba y 4\u00ba, ... de ps. Por ejemplo,\n--    distancias [(0,0),(3,4),(1,1),(7,9)]  ==  [5.0,10.0]\ndistancias :: [Punto] -> [Double]\ndistancias []         = []\ndistancias (p1:p2:ps) = distancia p1 p2 : distancias ps\n\n-- (media xs) es la media aritm\u00e9tica de los elementos de xs. Por ejemplo,\n--    media [1,7,1]  ==  3.0\nmedia :: [Double] -> Double\nmedia xs =\n  sum xs \/ genericLength xs\n\n-- (distanciaEsperada n) es la distancia esperada entre n puntos\n-- aleatorios en el cuadrado unitario. Por ejemplo,\n--    \u03bb> distanciaEsperada 100\n--    0.4712858421448363\n--    \u03bb> distanciaEsperada 100\n--    0.4947745206856711\ndistanciaEsperada :: Int -> IO Double\ndistanciaEsperada n = do\n  ps <- puntosDelCuadrado (2*n)\n  return (media (distancias ps))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndistanciaEsperada2 :: Int -> IO Double\ndistanciaEsperada2 n = do\n  ps <- puntosDelCuadrado2 (2*n)\n  return (media (distancias ps))\n\n-- (puntosDelCuadrado2 n) es una lista de n puntos del cuadrado\n-- unitario de v\u00e9rtices opuestos (0,0) y (1,1). Por ejemplo, \n--    \u03bb> puntosDelCuadrado2 3\n--    [(0.9836699352638695,0.5143414844876929),\n--     (0.8715237339877027,0.9905157772823782),\n--     (0.29502946161912935,0.16889248111565192)]\n--    \u03bb> puntosDelCuadrado2 3\n--    [(0.20405570457106392,0.47574116941605116),\n--     (0.7128182811364226,3.201419787777959e-2),\n--     (0.5576891231675457,0.9994474730919443)]\npuntosDelCuadrado2 :: Int -> IO [Punto]\npuntosDelCuadrado2 n =\n  replicateM n puntoDelCuadrado2\n\n-- (puntoDelCuadrado2 n) es un punto del cuadrado unitario de v\u00e9rtices\n-- opuestos (0,0) y (1,1). Por ejemplo,  \n--    \u03bb> puntoDelCuadrado2\n--    (0.7512991739803923,0.966436016138578)\n--    \u03bb> puntoDelCuadrado2\n--    (0.7306826194847795,0.8984574498515252)\npuntoDelCuadrado2 :: IO Punto\npuntoDelCuadrado2 = do\n  x <- randomRIO (0, 1.0)\n  y <- randomRIO (0, 1.0)\n  return (x, y)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ndistanciaEsperada3 :: Int -> IO Double\ndistanciaEsperada3 n = do\n  ds <- distanciasAleatorias n\n  return (media ds)\n\n-- (distanciasAleatorias n) es la lista de las distancias aleatorias\n-- entre n pares de puntos del cuadrado unitario. Por ejemplo, \n--    \u03bb> distanciasAleatorias 3\n--    [0.8325589110989705,0.6803336613847881,0.1690051224111662]\n--    \u03bb> distanciasAleatorias 3\n--    [0.3470124940889039,0.459002678562019,0.7665623634969365]\ndistanciasAleatorias :: Int -> IO [Double]\ndistanciasAleatorias n = \n  replicateM n distanciaAleatoria\n\n-- distanciaAleatoria es la distancia de un par de punto del cuadrado\n-- unitario elegidos aleatoriamente. Por ejemplo,\n--    \u03bb> distanciaAleatoria\n--    0.8982361685460913\n--    \u03bb> distanciaAleatoria\n--    0.9777207485571939\n--    \u03bb> distanciaAleatoria\n--    0.6042223512347842\ndistanciaAleatoria :: IO Double\ndistanciaAleatoria = do \n  p1 <- puntoDelCuadrado2\n  distancia p1 <$> puntoDelCuadrado2\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ndistanciaEsperada4 :: Int -> IO Double\ndistanciaEsperada4 n =\n  media <$> distanciasAleatorias n\n\n-- Gr\u00e1fica\n-- =======\n\ngraficaDistanciaEsperada :: [Int] -> IO ()\ngraficaDistanciaEsperada ns = do\n  ys <- mapM distanciaEsperada ns\n  let e = (sqrt 2 + 2 + 5 * log (1 + sqrt 2)) \/ 15\n  plotLists [ Key Nothing\n            -- , PNG \"Distancia_esperada_entre_dos_puntos.png\"\n            ]\n            [ zip ns ys\n            , zip ns (repeat e)]\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Distancia_esperada_entre_dos_puntos_de_un_cuadrado_unitario.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Diccionario de frecuencias 2. Primos circulares 3. Codificaci\u00f3n de G\u00f6del 4. Representaci\u00f3n matricial de relaciones binarias 5. Distancia esperada entre dos puntos de un cuadrado unitario A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7749"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7749"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7749\/revisions"}],"predecessor-version":[{"id":7750,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7749\/revisions\/7750"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7749"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7749"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7749"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}