第11章 切符番号遊び #3

11.7 練習問題

  1. 関数 choices、exprs、およびevalを用いて、1、3、7、10、25、50に対し可能な式は33,665,406個あり、そのうち4,672,540個のみが有効であることを確かめよ。

こんな感じでいいのかな。 もっと見た目よく関数合成したいんだけど。F#の |> みたいな演算子はないのかな。

availables :: [Int] -> Int
availables = length . concat . map exprs . choices

valids :: [Int] -> Int
valids = length . concat . map eval . concat . map exprs . choices

main :: IO ()
main = do
  print $ availables [1,3,7,10,25,50]
  print $ valids [1,3,7,10,25,50]
  1. 同様に数値の定義域を整数に拡大すると、有効な式の数が10,839,369個に増えることを確かめよ。
    ヒント：関数 valid の定義を変更せよ。

evalの方は変えなくてよかったのかな……

valid         :: Op -> Int -> Int -> Bool
valid Add _ _ =  True
valid Sub x y =  True
valid Mul _ _ =  True
valid Div x y =  y /= 0 && x `mod` y == 0
  1. 関数 solutions'' を以下のように改良せよ。
    1. 式に累乗演算子が使えるようにする
    2. 解がない場合に、目標の数に最も近い解を算出する
    3. 適切な方法で解を並び替える

6-a

累乗ということでPowを増やした。そしたら整数値がオーバーフローするようになって困った。 しかたなく、validの定義の方でオーバーフローしたものを排除するようにした。

data Op = Add | Sub | Mul | Div | Pow
  deriving Show

valid         :: Op -> Int -> Int -> Bool
valid Add x y =  x <= y && x + y /= 0
valid Sub x y =  x > y
valid Mul x y =  x /= 1 && y /= 1 && x <= y && x * y /= 0
valid Div x y =  y /= 1 && x `mod` y == 0
valid Pow x y =  x > 1 && y > 1 && x ^ y /= 0

apply         :: Op -> Int -> Int -> Int
apply Add x y =  x + y
apply Sub x y =  x - y
apply Mul x y =  x * y
apply Div x y =  x `div` y
apply Pow x y =  x ^ y

ops :: [Op]
ops =  [Add, Sub, Mul, Div, Pow]

6-b

目標とする数値との差の絶対値が最小になる式のリストを作って返すようにした。 わりと面倒なコードになってしまったけど、どうなんだろ。

minsby :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
minsby _ xs     []     = xs
minsby f []     (y:ys) = minsby f [y] ys
minsby f (x:xs) (y:ys)
  | f x y == LT        = minsby f (x:xs) ys
  | f x y == EQ        = minsby f ((x:xs) ++ [y]) ys
  | otherwise          = minsby f [y] ys

solutions'' :: [Int] -> Int -> [Expr]
solutions'' ns n = [e | (e, _) <- minsby f [] candidates]
  where
    f (_, x) (_, y) = compare (abs (x - n)) (abs (y - n))
    candidates = [r | ns' <- choices ns,
                      r <- results ns']

6-c

「適切な方法」って何だよ！意味がわからない。 なので

  • 使用した数値の数が小さい順
  • 使用した数値の並び順
  • 使用した演算子の並び順

という感じにしてみた。

data Op = Add | Sub | Mul | Div | Pow
  deriving (Show, Ord, Eq)

opcodes             :: Expr -> [Op]
opcodes (Val _)     =  []
opcodes (App o l r) =  o : (opcodes l) ++ (opcodes r)

type Comparer a = a -> a -> Ordering

andthen         :: Comparer a -> Comparer a -> Comparer a
andthen f g x y =  if f x y /= EQ then f x y else g x y

compareby       :: Ord b => (a -> b) -> Comparer a
compareby f x y =  compare (f x) (f y)

exprcomparer :: Comparer Expr
exprcomparer =  compareby (length . values) `andthen`
                compareby values `andthen`
                compareby opcodes

solutions'' :: [Int] -> Int -> [Expr]
solutions'' ns n = sortBy exprcomparer [e | (e, _) <- minsby f [] candidates]
  where
    f (_, x) (_, y) = compare (abs (x - n)) (abs (y - n))
    candidates = [r | ns' <- choices ns,
                      r <- results ns']