デジタル時計が冗長な件

問題は某ジャグリングサークルの会誌から意訳。
デジタル時計が冗長なことがわかる。

問題

[00-23]時:[00-59]分表示のデジタル時計から、各時刻(1440通り)が区別できる限りできるだけ棒を取り除くとき、何本取り除けるか？

方針

0から9までを表示する必要のある桁を考える。
数字の表示に使う棒の集合を とする。
ある棒の集合を考えたときに、との共通集合の族の元が互いに区別できれば、その棒集合で各数字は区別できることになる。

これを7本の棒集合の部分集合全てについてテストすればよい。

という観点でHaskellで書いてみた。関数7つ。

module Main where
import List

--no duplication
nodup :: Eq a => [a] -> Bool
nodup [] = True
nodup (x:xs) = not (x `elem` xs) && nodup xs

--power set
ps :: [a] -> [[a]]
ps [] = [[]]
ps (x:xs) = xss ++ (map (x:) xss) where xss = ps xs

--shortest list
shortest :: [[a]] -> [a]
shortest = minimumBy (\xs ys -> compare (length xs) (length ys))

--bars used to denote digits
digits :: [[Int]]
digits = [
	[0,1,2,3,4,5],	--0
	[4,5],	--1
	[0,2,3,5,6],	--2
	[0,3,4,5,6],	--3
	[1,4,5,6],	--4
	[0,1,3,4,6],	--5
	[0,1,2,3,4,6],	--6
	[0,1,4,5],	--7
	[0,1,2,3,4,5,6],	--8
	[0,1,3,4,5,6]	--9
		]

--test one set of bars if they can distinguish [0-n]
j6test :: Int -> [Int] -> Bool	
j6test n ns = nodup $ map (intersect ns) $ take (n+1) digits

--minimum bars necessary to distinguish [0-n]
j6aux :: Int -> [Int]
j6aux n = shortest $ filter (j6test n) $ ps [0..6]

--maximum number of bars those can be removed
j6ans :: Int
j6ans = (7 * 4 -) $ sum $ map (length . j6aux) [2,9,5,9]

main = print j6ans

簡単に思いつく改良点としては、本の棒では状態しか区別することができないので、テストする棒集合のサイズを限定することが考えられる。