puzzle2 http://www.douban.com/group/topic/74245173/

puzzle2.hs

import Data.List
import Data.Function
import Control.Monad

groupOn f = groupBy ((==) `on` f) . sortBy (compare `on` f)
uniq = map (!! 0) . groupOn id

-- 场景：假设a得到了数字x，b得到了数字y
-- 可看做二分图，其中possibleX，possibleY是顶点，possible是边，(aGuessY x)和(bGuessX y)分别表达x点和y点的邻接点集
possible = [(5, 15), (5, 16), (5, 19), (6, 17), (6, 18), (7, 14), (7, 16), (8, 14), (8, 15), (8, 17)]

possibleX = uniq $ [i | (i, j) <- possible]
possibleY = uniq $ [j | (i, j) <- possible]

aGuess x = [(i, j) | (i, j) <- possible, i == x]
bGuess y = [(i, j) | (i, j) <- possible, j == y]

aGuessY x = map (\(i, j) -> j) $ aGuess x
bGuessX x = map (\(i, j) -> i) $ bGuess x

-- A说“我不知道，并且我确定你也不知道”
xs = [x | x <- possibleX, (length $ aGuessY x) > 1, (all ((>1) . length) [bGuessX y | y <- aGuessY x])]

-- B说“我现在知道了！”
ys = [y | y <- (uniq $ join $ map aGuessY $ xs), (length $ intersect (bGuessX y) xs) == 1]

-- A说“我现在也知道了！”
xs2 = [x | x <- intersect xs (uniq $ join $ map bGuessX $ ys), (length $ intersect (aGuessY x) ys) == 1]

-- 结论
rst = [(x, y) | x <- xs2, y <- intersect (aGuessY x) ys]