{"id":4076,"date":"2018-05-15T06:00:21","date_gmt":"2018-05-15T04:00:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4076"},"modified":"2018-05-22T07:35:23","modified_gmt":"2018-05-22T05:35:23","slug":"el-problema-de-las-celebridades","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-problema-de-las-celebridades\/","title":{"rendered":"El problema de las celebridades"},"content":{"rendered":"<p>La <em>celebridad<\/em> de una reuni\u00f3n es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reuni\u00f3n hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reuni\u00f3n es la 3.<\/p>\n<p>La relaci\u00f3n de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, la reuni\u00f3n anterior se puede representar por [(1,3),(2,1),(2,3)].<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   celebridad :: Ord a => [(a,a)] -> Maybe a\n<\/pre>\n<p>tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   celebridad [(1,3),(2,1),(2,3)]            ==  Just 3\n   celebridad [(1,3),(2,1),(3,2)]            ==  Nothing\n   celebridad [(1,3),(2,1),(2,3),(3,1)]      ==  Nothing\n   celebridad [(x,1) | x <- [2..10^6]]       ==  Just 1\n   celebridad [(x,10^6) | x <- [1..10^6-1]]  ==  Just 1000000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (delete, nub)\nimport Data.Maybe (listToMaybe)\nimport qualified Data.Set as S\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncelebridad1 :: Ord a => [(a,a)] -> Maybe a\ncelebridad1 r =\n  listToMaybe [x | x <- personas r, esCelebridad r x]\n\npersonas :: Ord a => [(a,a)] -> [a]\npersonas r =\n  nub (map fst r ++ map snd r)\n\nesCelebridad :: Ord a => [(a,a)] -> a -> Bool\nesCelebridad r x =\n     [y | y <- ys, (y,x) `elem` r] == ys\n  &#038;&#038; null [y | y <- ys, (x,y) `elem` r]\n  where ys = delete x (personas r)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncelebridad2 :: Ord a => [(a,a)] -> Maybe a\ncelebridad2 r =\n  listToMaybe [x | x <- personas2 c, esCelebridad2 c x]\n  where c = S.fromList r\n\n--    \u03bb> personas2 (S.fromList [(1,3),(2,1),(2,3)])\n--    [1,2,3]\npersonas2 :: Ord a => S.Set (a,a) -> [a]\npersonas2 c =\n  S.toList (S.map fst c `S.union` S.map snd c)\n\nesCelebridad2 :: Ord a => S.Set (a,a) -> a -> Bool\nesCelebridad2 c x = \n      [y | y <- ys, (y,x) `S.member` c] == ys\n   &#038;&#038; null [y | y <- ys, (x,y) `S.member` c]\n   where ys = delete x (personas2 c)\n\n-- 3\u00aa definici\u00f3n\n-- =============\n\ncelebridad3 :: Ord a => [(a,a)] -> Maybe a\ncelebridad3 r\n  | S.null candidatos = Nothing\n  | esCelebridad      = Just candidato\n  | otherwise         = Nothing\n  where\n    conjunto          = S.fromList r\n    dominio           = S.map fst conjunto\n    rango             = S.map snd conjunto\n    total             = dominio `S.union` rango\n    candidatos        = rango `S.difference` dominio\n    candidato         = S.findMin candidatos\n    noCandidatos      = S.delete candidato total\n    esCelebridad      =\n      S.filter (\\x -> (x,candidato) `S.member` conjunto) total == noCandidatos\n     \n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> celebridad1 [(x,1) | x <- [2..300]]\n--    Just 1\n--    (2.70 secs, 38,763,888 bytes)\n--    \u03bb> celebridad2 [(x,1) | x <- [2..300]]\n--    Just 1\n--    (0.01 secs, 0 bytes)\n-- \n--    \u03bb> celebridad2 [(x,1000) | x <- [1..999]]\n--    Just 1000\n--    (2.23 secs, 483,704,224 bytes)\n--    \u03bb> celebridad3 [(x,1000) | x <- [1..999]]\n--    Just 1000\n--    (0.02 secs, 0 bytes)\n-- \n--    \u03bb> celebridad3 [(x,10^6) | x <- [1..10^6-1]]\n--    Just 1000000\n--    (9.56 secs, 1,572,841,088 bytes)\n--    \u03bb> celebridad3 [(x,1) | x <- [2..10^6]]\n--    Just 1\n--    (6.17 secs, 696,513,320 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La celebridad de una reuni\u00f3n es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reuni\u00f3n hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reuni\u00f3n es la 3&#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":[4],"tags":[8,408,25,406,26,409,407,392,80,246,390,10,395,24,141,404,11,16,405],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4076"}],"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=4076"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4076\/revisions"}],"predecessor-version":[{"id":4106,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4076\/revisions\/4106"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}