{"id":2691,"date":"2016-12-14T06:00:21","date_gmt":"2016-12-14T04:00:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2691"},"modified":"2016-12-21T23:22:12","modified_gmt":"2016-12-21T21:22:12","slug":"distancia-a-erdos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/distancia-a-erdos\/","title":{"rendered":"Distancia a Erd\u0151s"},"content":{"rendered":"<p>Una de las razones por la que el matem\u00e1tico h\u00fangaro <a href=\"http:\/\/bit.ly\/2hBrixP\">Paul Erd\u0151s<\/a> es conocido es por la multitud de colaboraciones que realiz\u00f3 durante toda su carrera, un total de 511. Tal es as\u00ed que se establece la distancia a Erd\u0151s como la distancia que has estado de coautor\u00eda con Erd\u0151s. Por ejemplo, si eres Paul Erd\u0151s tu distancia a Erd\u0151s es 0, si has escrito un art\u00edculo con Erd\u0151s tu distancia es 1, si has escrito un art\u00edculo con alguien que ha escrito un art\u00edculo con Erd\u0151s tu distancia es 2, etc. El objetivo de este problema es definir una funci\u00f3n que a partir de una lista de pares de coautores y un n\u00famero natural n calcular la lista de los matem\u00e1ticos a una distancia n de Erd\u0151s.<\/p>\n<p>Para el problema se considerar\u00e1 la siguiente lista de coautores<\/p>\n<pre lang=\"text\">\n   coautores :: [(String,String)]\n   coautores =\n     [(\"Paul Erdos\",\"Ernst Straus\"),(\"Paul Erdos\",\"Pascual Jordan\"),\n      (\"Paul Erdos\",\"D. Kleitman\"),(\"Albert Einstein\",\"Ernst Straus\"),\n      (\"John von Newmann\",\"David Hilbert\"),(\"S. Glashow\",\"D. Kleitman\"),\n      (\"John von Newmann\",\"Pascual Jordan\"), (\"David Pines\",\"D. Bohm\"),\n      (\"Albert Einstein\",\"Otto Stern\"),(\"S. Glashow\", \"M. Gell-Mann\"),\n      (\"Richar Feynman\",\"M. Gell-Mann\"),(\"M. Gell-Mann\",\"David Pines\"),\n      (\"David Pines\",\"A. Bohr\"),(\"Wolfgang Pauli\",\"Albert Einstein\"),\n      (\"D. Bohm\",\"L. De Broglie\"), (\"Paul Erdos\",\"J. Conway\"),\n      (\"J. Conway\", \"P. Doyle\"),(\"Paul Erdos\",\"A. J. Granville\"),\n      (\"A. J. Granville\",\"B. Mazur\"),(\"B. Mazur\",\"Andrew Wiles\")]\n<\/pre>\n<p>La lista anterior es real y se ha obtenido del art\u00edculo <a href=\"http:\/\/bit.ly\/2hBtiWY\">Famous trails to Paul Erd\u0151s<\/a>.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   numeroDeErdos :: [(String, String)] -> Int -> [String]\n<\/pre>\n<p>tal que (numeroDeErdos xs n) es la lista de lista de los  matem\u00e1ticos de la<br \/>\nlista de coautores xs que se encuentran a una distancia n de Erd\u0151s. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> numeroDeErdos coautores 0\n   [\"Paul Erdos\"]\n   \u03bb> numeroDeErdos coautores 1\n   [\"Ernst Straus\",\"Pascual Jordan\",\"D. Kleitman\",\"J. Conway\",\"A. J. Granville\"]\n   \u03bb> numeroDeErdos coautores 2\n   [\"Albert Einstein\",\"John von Newmann\",\"S. Glashow\",\"P. Doyle\",\"B. Mazur\"]\n<\/pre>\n<p><strong>Nota<\/strong>: Este ejercicio ha sido propuesto por Enrique Naranjo.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\ndata Arbol a = N a [Arbol a]\n             deriving Show \n\ncoautores :: [(String,String)]\ncoautores =\n  [(\"Paul Erdos\",\"Ernst Straus\"),(\"Paul Erdos\",\"Pascual Jordan\"),\n   (\"Paul Erdos\",\"D. Kleitman\"),(\"Albert Einstein\",\"Ernst Straus\"),\n   (\"John von Newmann\",\"David Hilbert\"),(\"S. Glashow\",\"D. Kleitman\"),\n   (\"John von Newmann\",\"Pascual Jordan\"), (\"David Pines\",\"D. Bohm\"),\n   (\"Albert Einstein\",\"Otto Stern\"),(\"S. Glashow\", \"M. Gell-Mann\"),\n   (\"Richar Feynman\",\"M. Gell-Mann\"),(\"M. Gell-Mann\",\"David Pines\"),\n   (\"David Pines\",\"A. Bohr\"),(\"Wolfgang Pauli\",\"Albert Einstein\"),\n   (\"D. Bohm\",\"L. De Broglie\"), (\"Paul Erdos\",\"J. Conway\"),\n   (\"J. Conway\", \"P. Doyle\"),(\"Paul Erdos\",\"A. J. Granville\"),\n   (\"A. J. Granville\",\"B. Mazur\"),(\"B. Mazur\",\"Andrew Wiles\")]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnumeroDeErdos :: [(String, String)] -> Int -> [String]\nnumeroDeErdos xs n = nivel n (arbolDeErdos xs \"Paul Erdos\")\n\n-- (arbolDeErdos xs a) es el \u00e1rbol de coautores de a seg\u00fan la lista de\n-- coautores xs. Por ejemplo,\n--    \u03bb> arbolDeErdos coautores \"Paul Erdos\"\n--    N \"Paul Erdos\"\n--      [N \"Ernst Straus\"\n--         [N \"Albert Einstein\"\n--           [N \"Wolfgang Pauli\" [],\n--            N \"Otto Stern\" []]],\n--          N \"Pascual Jordan\"\n--            [N \"John von Newmann\"\n--               [N \"David Hilbert\" []]],\n--          N \"D. Kleitman\"\n--            [N \"S. Glashow\"\n--               [N \"M. Gell-Mann\"\n--                  [N \"Richar Feynman\" [],\n--                   N \"David Pines\"\n--                     [N \"A. Bohr\" [],\n--                      N \"D. Bohm\"\n--                        [N \"L. De Broglie\" []]]]]],\n--          N \"J. Conway\"\n--            [N \"P. Doyle\" []],\n--             N \"A. J. Granville\"\n--               [N \"B. Mazur\"\n--                  [N \"Andrew Wiles\" []]]]\narbolDeErdos :: [(String, String)] -> String -> Arbol String\narbolDeErdos xs a =\n  N a [arbolDeErdos noColaboradores n | n <- colaboradores]\n  where\n    colaboradores   = [filtra a (x,y) | (x,y) <- xs, x == a || y == a]\n    filtra a (x,y) | a == x    = y\n                   | otherwise = x\n    noColaboradores = [(x,y) | (x,y) <- xs, x \/= a, y \/= a]\n\n-- (nivel n a) es la lista de los elementos del \u00e1rbol a en el nivel\n-- n. Por ejemplo,      \n--    nivel 0 (N 3 [N 5 [N 6 []], N 7 [N 9 []]])   ==  [3]\n--    nivel 1 (N 3 [N 5 [N 6 []], N 7 [N 9 []]])   ==  [5,7]\n--    nivel 2 (N 3 [N 5 [N 6 []], N 7 [N 9 []]])   ==  [6,9]\nnivel :: Int -> Arbol a -> [a]\nnivel 0 (N a xs) = [a]\nnivel n (N a xs) = concatMap (nivel (n-1)) xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnumeroDeErdos2 :: [(String, String)] -> Int -> [String]\nnumeroDeErdos2 = auxC [\"Paul Erdos\"] \n  where\n    auxC v xs 0 = v\n    auxC v xs x = auxC  (n v) (m v xs) (x-1)\n      where n v =     [a | (a,b) <- xs, elem b v] ++\n                      [b | (a,b) <- xs, elem a v]\n            m ys xs = [(a,b) | (a,b) <- xs\n                             , notElem a ys &#038;&#038; notElem b ys]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnumeroDeErdos3 :: [(String, String)] -> Int -> [String]\nnumeroDeErdos3 ps n = (sucCoautores \"Paul Erdos\" ps) !! n\n\n-- (sucCoautores a ps) es la sucesi\u00f3n de coautores de a en ps ordenados\n-- por diatancia. Por ejemplo, \n--    \u03bb> take 3 (sucCoautores \"Paul Erdos\" coautores)\n--    [[\"Paul Erdos\"],\n--     [\"Ernst Straus\",\"Pascual Jordan\",\"D. Kleitman\",\"J. Conway\",\n--      \"A. J. Granville\"],\n--     [\"Albert Einstein\",\"John von Newmann\",\"S. Glashow\",\"P. Doyle\",\n--      \"B. Mazur\"]]\n--    \u03bb> sucCoautores \"Albert Einstein\" coautores\n--    [[\"Albert Einstein\"],\n--     [\"Ernst Straus\",\"Otto Stern\",\"Wolfgang Pauli\"],\n--     [\"Paul Erdos\"],\n--     [\"Pascual Jordan\",\"D. Kleitman\",\"J. Conway\", \"A. J. Granville\"],\n--     [\"John von Newmann\",\"S. Glashow\",\"P. Doyle\",\"B. Mazur\"],\n--     [\"David Hilbert\",\"M. Gell-Mann\",\"Andrew Wiles\"],\n--     [\"David Pines\",\"Richar Feynman\"],\n--     [\"D. Bohm\",\"A. Bohr\"],\n--     [\"L. De Broglie\"]]\nsucCoautores :: String -> [(String, String)] -> [[String]]\nsucCoautores a ps =\n  takeWhile (not . null) (map fst (iterate sig ([a], as \\\\ [a])))\n  where as = elementos ps\n        sig (xs,ys) = (zs,ys \\\\ zs)\n          where zs = [y | y <- ys\n                        , or [elem (x,y) ps || elem (y,x) ps | x <- xs]]\n\n-- (elementos ps) es la lista de los elementos de los pares ps. Por\n-- ejemplo,\n--    elementos [(1,3),(3,2),(1,5)]  ==  [1,3,2,5]\nelementos :: Eq a => [(a, a)] -> [a]\nelementos = nub . (concatMap (\\(x,y) -> [x,y]))\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Una de las razones por la que el matem\u00e1tico h\u00fangaro Paul Erd\u0151s es conocido es por la multitud de colaboraciones que realiz\u00f3 durante toda su carrera, un total de 511. Tal es as\u00ed que se establece la distancia a Erd\u0151s como la distancia que has estado de coautor\u00eda con Erd\u0151s. Por ejemplo, si eres Paul&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[7],"tags":[269,8,58,26,80,50,10,181,27,24,141,169,11,6,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2691"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=2691"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2691\/revisions"}],"predecessor-version":[{"id":2731,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2691\/revisions\/2731"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}