ITコンサルの日常

ITコンサル会社に勤務する普通のITエンジニアの日常です。

5つのビリヤード玉問題も解けた

先日紹介した、
http://www.sampou.org/cgi-bin/haskell.cgi?Programming%3A%B6%CC%BC%EA%C8%A2%3A%C1%C8%B9%E7%A4%BB
のサイトより、nPmの関数をパクってきて、作りました。

import List

result = [1..21]

main = print $ filter test $ perm [1..11] 5

divid :: [a] -> [([a],[a])]
divid xxs@(x:xs) = ([],xxs) : [(x:ys,zs) | (ys,zs) <- divid xs]
divid []         = [([],[])]

perm :: [a] -> Int -> [[a]]
perm [] _ = []
perm xs 0 = [[]]
perm xs 1 = map (:[]) xs
perm xs n = concatMap (pm n) $ divid xs
 where pm _ (_,[])      = []
       pm n (hs,(t:ts)) = map (t:) $ perm (hs ++ ts) (n-1)

test xs = if testList xs == result then True else False
testList xs = sort $ test1 xs ++ test2 xs ++ test3 xs ++ test4 xs ++ test5 xs
test1 [a,b,c,d,e] = [a,b,c,d,e]
test2 [a,b,c,d,e] = [a+b, b+c, c+d, d+e, e+a]
test3 [a,b,c,d,e] = [a+b+c, b+c+d, c+d+e, d+e+a, e+a+b]
test4 [a,b,c,d,e] = [a+b+c+d, b+c+d+e, c+d+e+a, d+e+a+b, e+a+b+c]
test5 [a,b,c,d,e] = [a+b+c+d+e]

結果はこう。

[[1,3,10,2,5],[1,5,2,10,3],[2,5,1,3,10],[2,10,3,1,5],[3,1,5,2,10],[3,10,2,5,1],[
5,1,3,10,2],[5,2,10,3,1],[10,2,5,1,3],[10,3,1,5,2]]

ゴリって音がしそうなほど、強引って感じですが、まあ一応出来たってことで。
いっぱい答えが出てるのは、始点の違いと、逆周りも含めた答えなので、別解があるわけじゃないです。
今後の目標は、このプログラムの改良、および、divid関数、perm関数の理解ってところでしょうね。


問題と答えの確認はこちら。
http://r27.jp/quiz/mathematical-goodbye/