0votos

Spotify, tráfico de influencias en Haskell

por josejuan hace 4 años

Hace dos años comenté que el problema es NP-completo, estaba equivocado, pues en el caso de grafos bipartitos (como ocurre aquí) usando el teorema de König existe un algoritmo polinomial fácil de implementar (siguiendo la demostración de http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29 )

Spotify presenta tres retos para quien quiera trabajar allí como programador. Uno de ellos es obtener una lista de beneficiarios sujeta a ciertas restricciones.

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
import Data.List 
import Data.Graph.Inductive.Graph 
import Data.Graph.Inductive.Tree 
import Data.Graph.Inductive.Query.Matchings 
 
spotify :: [(Int, Int)] -> [Int] 
spotify es = 
  let ln = nub $ sort $ map fst es 
      rn = nub $ sort $ map snd es 
      ns = nub $ sort $ ln ++ rn 
      em = maximumMatching (mkUGraph ns es :: Gr () ())         -- sí en maximum matching 
      e0 = filter (not . flip elem em) es                       -- no en maximum matching 
      t0 = [v | v <- ln, v `elem` (map fst e0 ++ map snd e0)]   -- aquellos de ln que no son del matching 
      toRight t = let t' = [r | (l, r) <- e0, l `elem` t, not (r `elem` t)] 
                  in  if null t' then t else toLeft  (t ++ t') 
      toLeft  t = let t' = [l | (l, r) <- em, r `elem` t, not (l `elem` t)] 
                  in  if null t' then t else toRight (t ++ t') 
      tn = toRight t0 
  in  filter (not . flip elem tn) ln ++ filter (flip elem tn) rn 
 
e :: [(Int, Int)] 
e = [ (1001, 2001) 
    , (1001, 2002) 
    , (1001, 2003) 
    , (1001, 2004) 
    , (1002, 2001) 
    , (1003, 2002) 
    , (1004, 2003) 
    , (1005, 2004) ] 
 
main = print $ spotify e 
-- Resultado: [2001,2002,2003,2004] 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.