ITコンサルの日常

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

5つのビリヤード玉問題の重複解をなくす

前回のプログラム

ふつうのHaskellプログラミングのp99に、List.group関数の説明が載ってます。

group関数は、リストxsに連続して同じ要素が現れたらそれをリストにまとめて返します。

ですが、「同じ要素」の判定を自分で決められるgroupByを使います。

import List

result = [1..21]

main = print $ head $ concat $ groupBy gb $ 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]

gb xs ys = if ((sort xs) == (sort ys)) then True else False

結果はこう。

[1,3,10,2,5]

というわけで、無事重複解が排除されて出力されました。


ミソなのは、新しく定義したgb関数で、二つのリストをそれぞれソートして同じであればgroupされるようになっています。

(4/15 追記)
headを使っているので、答えが一つになるのは当たり前なのでした。
上の例は、別解が無いので問題ありませんが、別解がある場合は、最初の答えしか表示されないということになってしまいます。
group byを使うところまでは合ってたと思うので、こんな風にしました。

main = print $ map head $ groupBy gb $ 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]

gb xs ys = if ((sort xs) == (sort ys)) then True else False

結果はこう。

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