data Arbol a = N a [Arbol a]
deriving Show
coautores :: [(String,String)]
coautores =
[("Paul Erdos","Ernst Straus"),("Paul Erdos","Pascual Jordan"),
("Paul Erdos","D. Kleitman"),("Albert Einstein","Ernst Straus"),
("John von Newmann","David Hilbert"),("S. Glashow","D. Kleitman"),
("John von Newmann","Pascual Jordan"), ("David Pines","D. Bohm"),
("Albert Einstein","Otto Stern"),("S. Glashow", "M. Gell-Mann"),
("Richar Feynman","M. Gell-Mann"),("M. Gell-Mann","David Pines"),
("David Pines","A. Bohr"),("Wolfgang Pauli","Albert Einstein"),
("D. Bohm","L. De Broglie"), ("Paul Erdos","J. Conway"),
("J. Conway", "P. Doyle"),("Paul Erdos","A. J. Granville"),
("A. J. Granville","B. Mazur"),("B. Mazur","Andrew Wiles")]
-- 1ª solución
-- ===========
numeroDeErdos :: [(String, String)] -> Int -> [String]
numeroDeErdos xs n = nivel n (arbolDeErdos xs "Paul Erdos")
-- (arbolDeErdos xs a) es el árbol de coautores de a según la lista de
-- coautores xs. Por ejemplo,
-- λ> arbolDeErdos coautores "Paul Erdos"
-- N "Paul Erdos"
-- [N "Ernst Straus"
-- [N "Albert Einstein"
-- [N "Wolfgang Pauli" [],
-- N "Otto Stern" []]],
-- N "Pascual Jordan"
-- [N "John von Newmann"
-- [N "David Hilbert" []]],
-- N "D. Kleitman"
-- [N "S. Glashow"
-- [N "M. Gell-Mann"
-- [N "Richar Feynman" [],
-- N "David Pines"
-- [N "A. Bohr" [],
-- N "D. Bohm"
-- [N "L. De Broglie" []]]]]],
-- N "J. Conway"
-- [N "P. Doyle" []],
-- N "A. J. Granville"
-- [N "B. Mazur"
-- [N "Andrew Wiles" []]]]
arbolDeErdos :: [(String, String)] -> String -> Arbol String
arbolDeErdos xs a =
N a [arbolDeErdos noColaboradores n | n <- colaboradores]
where
colaboradores = [filtra a (x,y) | (x,y) <- xs, x == a || y == a]
filtra a (x,y) | a == x = y
| otherwise = x
noColaboradores = [(x,y) | (x,y) <- xs, x /= a, y /= a]
-- (nivel n a) es la lista de los elementos del árbol a en el nivel
-- n. Por ejemplo,
-- nivel 0 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [3]
-- nivel 1 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [5,7]
-- nivel 2 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [6,9]
nivel :: Int -> Arbol a -> [a]
nivel 0 (N a xs) = [a]
nivel n (N a xs) = concatMap (nivel (n-1)) xs
-- 2ª solución
-- ===========
numeroDeErdos2 :: [(String, String)] -> Int -> [String]
numeroDeErdos2 = auxC ["Paul Erdos"]
where
auxC v xs 0 = v
auxC v xs x = auxC (n v) (m v xs) (x-1)
where n v = [a | (a,b) <- xs, elem b v] ++
[b | (a,b) <- xs, elem a v]
m ys xs = [(a,b) | (a,b) <- xs
, notElem a ys && notElem b ys]
-- 3ª solución
-- ===========
numeroDeErdos3 :: [(String, String)] -> Int -> [String]
numeroDeErdos3 ps n = (sucCoautores "Paul Erdos" ps) !! n
-- (sucCoautores a ps) es la sucesión de coautores de a en ps ordenados
-- por diatancia. Por ejemplo,
-- λ> take 3 (sucCoautores "Paul Erdos" coautores)
-- [["Paul Erdos"],
-- ["Ernst Straus","Pascual Jordan","D. Kleitman","J. Conway",
-- "A. J. Granville"],
-- ["Albert Einstein","John von Newmann","S. Glashow","P. Doyle",
-- "B. Mazur"]]
-- λ> sucCoautores "Albert Einstein" coautores
-- [["Albert Einstein"],
-- ["Ernst Straus","Otto Stern","Wolfgang Pauli"],
-- ["Paul Erdos"],
-- ["Pascual Jordan","D. Kleitman","J. Conway", "A. J. Granville"],
-- ["John von Newmann","S. Glashow","P. Doyle","B. Mazur"],
-- ["David Hilbert","M. Gell-Mann","Andrew Wiles"],
-- ["David Pines","Richar Feynman"],
-- ["D. Bohm","A. Bohr"],
-- ["L. De Broglie"]]
sucCoautores :: String -> [(String, String)] -> [[String]]
sucCoautores a ps =
takeWhile (not . null) (map fst (iterate sig ([a], as \\ [a])))
where as = elementos ps
sig (xs,ys) = (zs,ys \\ zs)
where zs = [y | y <- ys
, or [elem (x,y) ps || elem (y,x) ps | x <- xs]]
-- (elementos ps) es la lista de los elementos de los pares ps. Por
-- ejemplo,
-- elementos [(1,3),(3,2),(1,5)] == [1,3,2,5]
elementos :: Eq a => [(a, a)] -> [a]
elementos = nub . (concatMap (\(x,y) -> [x,y]))