El problema de las celebridades
La celebridad de una reunión es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reunión 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ón es la 3.
La relación de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, la reunión anterior se puede representar por [(1,3),(2,1),(2,3)].
Definir la función
|
1 |
celebridad :: Ord a => [(a,a)] -> Maybe a |
tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,
|
1 2 3 4 5 |
celebridad [(1,3),(2,1),(2,3)] == Just 3 celebridad [(1,3),(2,1),(3,2)] == Nothing celebridad [(1,3),(2,1),(2,3),(3,1)] == Nothing celebridad [(x,1) | x <- [2..10^6]] == Just 1 celebridad [(x,10^6) | x <- [1..10^6-1]] == Just 1000000 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
import Data.List (delete, nub) import Data.Maybe (listToMaybe) import qualified Data.Set as S -- 1ª solución -- =========== celebridad1 :: Ord a => [(a,a)] -> Maybe a celebridad1 r = listToMaybe [x | x <- personas r, esCelebridad r x] personas :: Ord a => [(a,a)] -> [a] personas r = nub (map fst r ++ map snd r) esCelebridad :: Ord a => [(a,a)] -> a -> Bool esCelebridad r x = [y | y <- ys, (y,x) `elem` r] == ys && null [y | y <- ys, (x,y) `elem` r] where ys = delete x (personas r) -- 2ª solución -- =========== celebridad2 :: Ord a => [(a,a)] -> Maybe a celebridad2 r = listToMaybe [x | x <- personas2 c, esCelebridad2 c x] where c = S.fromList r -- λ> personas2 (S.fromList [(1,3),(2,1),(2,3)]) -- [1,2,3] personas2 :: Ord a => S.Set (a,a) -> [a] personas2 c = S.toList (S.map fst c `S.union` S.map snd c) esCelebridad2 :: Ord a => S.Set (a,a) -> a -> Bool esCelebridad2 c x = [y | y <- ys, (y,x) `S.member` c] == ys && null [y | y <- ys, (x,y) `S.member` c] where ys = delete x (personas2 c) -- 3ª definición -- ============= celebridad3 :: Ord a => [(a,a)] -> Maybe a celebridad3 r | S.null candidatos = Nothing | esCelebridad = Just candidato | otherwise = Nothing where conjunto = S.fromList r dominio = S.map fst conjunto rango = S.map snd conjunto total = dominio `S.union` rango candidatos = rango `S.difference` dominio candidato = S.findMin candidatos noCandidatos = S.delete candidato total esCelebridad = S.filter (\x -> (x,candidato) `S.member` conjunto) total == noCandidatos -- Comparación de eficiencia -- ========================= -- λ> celebridad1 [(x,1) | x <- [2..300]] -- Just 1 -- (2.70 secs, 38,763,888 bytes) -- λ> celebridad2 [(x,1) | x <- [2..300]] -- Just 1 -- (0.01 secs, 0 bytes) -- -- λ> celebridad2 [(x,1000) | x <- [1..999]] -- Just 1000 -- (2.23 secs, 483,704,224 bytes) -- λ> celebridad3 [(x,1000) | x <- [1..999]] -- Just 1000 -- (0.02 secs, 0 bytes) -- -- λ> celebridad3 [(x,10^6) | x <- [1..10^6-1]] -- Just 1000000 -- (9.56 secs, 1,572,841,088 bytes) -- λ> celebridad3 [(x,1) | x <- [2..10^6]] -- Just 1 -- (6.17 secs, 696,513,320 bytes) |