７９問目

http://projecteuler.net/index.php?section=problems&id=79
パスコードに含まれる任意の3つの文字によって認証を行う方法がある。例えば 531278 というパスコードから 2, 3, 5 番目の文字を取り出すと 317 となる。逆に、認証を通った 3 文字の文字列 50 個から、元のパスコードのうち最小のものを求める。
トポロジカルソートというらしいです。で、Haskell にはそれを扱うライブラリもある、と。
そんなことは知らず、総当りで調べました。
それでも解けてしまうくらいには簡単です。

import Data.List

main = do
    keylog <- readFile "keylog.txt"
    print $ euler079 $ lines keylog

euler079 :: [String] -> [String]
euler079 keys = [ pass | pass <- perm (nub $ concat keys), all (contains pass) keys ]

contains :: String -> String -> Bool
contains pass keys = "" /= (foldl rest pass keys)
    where rest pass key = dropWhile (/= key) pass

perm :: Eq a => [a] -> [[a]]
perm [] = [[]]
perm s = [ x : xs | x <- s, xs <- perm $ delete x s ]