{"id":3282,"date":"2017-05-09T06:00:58","date_gmt":"2017-05-09T04:00:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3282"},"modified":"2021-04-25T17:04:39","modified_gmt":"2021-04-25T15:04:39","slug":"el-problema-de-las-celebridades-17","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-problema-de-las-celebridades-17\/","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, ka reunio\u0144 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<p>[schedule expon='2017-05-16' expat=\"06:00\"]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 16 de mayo.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\"haskell\"&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on='2017-05-16' at=\"06:00\"]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.List (delete, nub)\r\nimport Data.Maybe (listToMaybe)\r\nimport qualified Data.Set as S\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ncelebridad1 :: Ord a => [(a,a)] -> Maybe a\r\ncelebridad1 r =\r\n  listToMaybe [x | x <- personas r, esCelebridad r x]\r\n\r\npersonas :: Ord a => [(a,a)] -> [a]\r\npersonas r =\r\n  nub (map fst r ++ map snd r)\r\n\r\nesCelebridad :: Ord a => [(a,a)] -> a -> Bool\r\nesCelebridad r x =\r\n     [y | y <- ys, (y,x) `elem` r] == ys\r\n  &#038;&#038; null [y | y <- ys, (x,y) `elem` r]\r\n  where ys = delete x (personas r)\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ncelebridad2 :: Ord a => [(a,a)] -> Maybe a\r\ncelebridad2 r =\r\n  listToMaybe [x | x <- personas2 c, esCelebridad2 c x]\r\n  where c = S.fromList r\r\n\r\n--    \u03bb> personas2 (S.fromList [(1,3),(2,1),(2,3)])\r\n--    [1,2,3]\r\npersonas2 :: Ord a => S.Set (a,a) -> [a]\r\npersonas2 c =\r\n  S.toList (S.map fst c `S.union` S.map snd c)\r\n\r\nesCelebridad2 :: Ord a => S.Set (a,a) -> a -> Bool\r\nesCelebridad2 c x = \r\n      [y | y <- ys, (y,x) `S.member` c] == ys\r\n   &#038;&#038; null [y | y <- ys, (x,y) `S.member` c]\r\n   where ys = delete x (personas2 c)\r\n\r\n-- 3\u00aa definici\u00f3n\r\n-- =============\r\n\r\ncelebridad3 :: Ord a => [(a,a)] -> Maybe a\r\ncelebridad3 r\r\n  | S.null candidatos = Nothing\r\n  | esCelebridad      = Just candidato\r\n  | otherwise         = Nothing\r\n  where\r\n    conjunto          = S.fromList r\r\n    dominio           = S.map fst conjunto\r\n    rango             = S.map snd conjunto\r\n    total             = dominio `S.union` rango\r\n    candidatos        = rango `S.difference` dominio\r\n    candidato         = S.findMin candidatos\r\n    noCandidatos      = S.delete candidato total\r\n    esCelebridad      =\r\n      S.filter (\\x -> (x,candidato) `S.member` conjunto) total == noCandidatos\r\n     \r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n--    \u03bb> celebridad1 [(x,1) | x <- [2..300]]\r\n--    Just 1\r\n--    (2.70 secs, 38,763,888 bytes)\r\n--    \u03bb> celebridad2 [(x,1) | x <- [2..300]]\r\n--    Just 1\r\n--    (0.01 secs, 0 bytes)\r\n-- \r\n--    \u03bb> celebridad2 [(x,1000) | x <- [1..999]]\r\n--    Just 1000\r\n--    (2.23 secs, 483,704,224 bytes)\r\n--    \u03bb> celebridad3 [(x,1000) | x <- [1..999]]\r\n--    Just 1000\r\n--    (0.02 secs, 0 bytes)\r\n-- \r\n--    \u03bb> celebridad3 [(x,10^6) | x <- [1..10^6-1]]\r\n--    Just 1000000\r\n--    (9.56 secs, 1,572,841,088 bytes)\r\n--    \u03bb> celebridad3 [(x,1) | x <- [2..10^6]]\r\n--    Just 1\r\n--    (6.17 secs, 696,513,320 bytes)\r\n<\/pre>\n<p>[\/schedule]<\/p>\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\/3282"}],"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=3282"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3282\/revisions"}],"predecessor-version":[{"id":3283,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3282\/revisions\/3283"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}