make10

「8 8 9 9」のmake10を四則演算でやれと言う話なので。分かんないので。
アルゴリズムとしては「切符の番号で10を作る」のと同じです。カッコよく言うと分割統治法。コードはあんま美しくないけど。

import Data.List


data Expr = C Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr

instance Show Expr where
    show (C x)     = show x
    show (Add x y) = "(" ++ (show x) ++ "+" ++ (show y) ++ ")"
    show (Sub x y) = "(" ++ (show x) ++ "-" ++ (show y) ++ ")"
    show (Mul x y) = "(" ++ (show x) ++ "*" ++ (show y) ++ ")"
    show (Div x y) = "(" ++ (show x) ++ "/" ++ (show y) ++ ")"

instance Eq Expr where
    (C x)     == (C y)     = x == y
    (Add x y) == (Add u v) = (x == u && y == v) || (x == v && y == u)
    (Sub x y) == (Sub u v) = (x == u && y == v)
    (Mul x y) == (Mul u v) = (x == u && y == v) || (x == v && y == u)
    (Div x y) == (Div u v) = (x == u && y == v)
    _         == _         = False


search n a = nub $ concat $ map (\(e,b) -> _search n b (C e)) (picks a)

_search :: Int -> [Int] -> Expr -> [Expr]
_search n a p = if null a
                    then (if eval p == Just (fromIntegral n) then [p] else [])
                    else concat $ map (\(e,b) -> concat $ map (\q -> _search n b q) (opr (C e) p)) (picks a)
 where
     opr x y = [Add x y, Sub x y, Sub y x, Mul x y, Div x y, Div y x]

picks a = [pickAt i a | i <- [0..(length a)-1]]
pickAt n l = (\(a,b) -> (head b, a ++ tail b)) (splitAt n l)

eval :: Expr -> Maybe Rational
eval (C x) = Just (fromIntegral x)
eval (Add x y) = eval x >>= (\m -> eval y >>= Just.(+ m))
eval (Sub x y) = eval x >>= (\m -> eval y >>= Just.(\n -> subtract n m))
eval (Mul x y) = eval x >>= (\m -> eval y >>= Just.(* m))
eval (Div x y) = eval x >>= (\m -> eval y >>= (\n -> if n == 0 then Nothing else Just (m / n)))

出力結果は

*Main> search 10 [2,3,7,7]
[(7+((7+2)/3)),((3+(7*2))-7),(3-(7-(7*2))),(3+((7*2)-7)),(3+((7+7)/2))]
*Main> search 10 [8,8,9,9]
[]

みたいな。要するに最初のは解無しっぽいという話でした。