Countdown Problem

Programming in Haskell의 Chapter. 11 Countdown Problem의 요약

- Countdown Problem
여러 개의 수들과 목표로 하는 결과값이 주어지면, 주어진 여러 개의 수들로부터 원하는 숫자를 골라 덧셈, 뺄셈, 곱셈, 나눗셈 및 괄호를 써서 식을 만들어, 그 만들어진 식의 계산 결과가 목표로 하는 결과값과 같도록 하는 문제(주어진 숫자들은 많아야 한 번씩만 식에 나타나야 하며, 계산 중간값을 포함한 계산에 쓰이는 모든 수들은 반드시 양의 정수여야 한다.).
예를 들어, 1,3,7,10,25,50로부터 765를 결과값으로 계산하기를 생각해보자. (1 + 50) * (5 - 10) 가 가능한 식의 하나가 될 것이다.

- 문제 풀이

네가지 수치 연산을 나타내는 타입을 다음과 같이 정의한다.
data Op = Add | Sub | Mul | Div

연산을 수행하는 함수 apply를 다음과 같이 정의한다.
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를 적용하기 전에 그 결과가 양의 정수인지 알아보는 함수 valid를 다음과 같이 정의한다.
valid                 :: Op -> Int -> Int -> Bool
valid (Add x y) = x <= y
valid (Sub x y) = x > y
valid (Mul x y) = x /= 1 && y /=1 && x <= y
valid (Div x y) = y /= 1 && x `mod` y == 0

덧셈의 경우 (Add 3 2)와 (Add 2 3)은 결과가 같기 때문에 하나만 계산하면 되고, 곱셈의 경우 x나 y가 1인 경우나 나눗셈의 경우 y가 1인 경우는 1인 값이 없는 경우와 같다. 따라서 이러한 경우는 더이상 계산하지 않고 유효하지 않은 값으로 처리한다.

이제 수식을 나타내는 타입을 아래와 같이 정의한다.
data Expr = Val Int | App Op Expr Expr

이 타입을 써서 식이 주어졌을 때 식의 결과 값을 돌려주는 eval 함수를 정의한다.
eval                   :: Expr -> [Int]
eval (Val n)      = [n | n > 0]
eval (App o l r) = [apply o l r | x <- eval l, y <- eval r, valid o x y]

성공하면 한원소 리스트를 값으로 돌려주고, 실패의 경우는 빈 리스트를 값으로 돌려준다.

이제 가능한 모든 식을 통해 결과를 찾는 함수를 정의해보자.
solutions        :: [Int] -> Int -> [Expr]
solutions ns n = [e | ns <- choices ns, (e, m) <- results ns, m == n]

이 식의 구현은 다음과 같이 생각할 수 있다. 양의 정수가 주어지면 이것으로 0개 이상의 수를 취하여 만들 수 있는 모든 부분 집합을 생성한다(choices). 이 부분 집합에 가능한 모든 계산 식을 적용한다(results ns). 이 계산 식의 값이 결과 값과 같으면 이 계산 식은 답이 된다.

그럼 먼저 choices를 정의해 보자.
이 함수는 주어진 리스트의 부분 집합을 만들고 이를 순서를 바꾸어 가능한 모든 수를 만들어 내면 된다. 부분 집합을 만드는 함수를 subs라 하고 부분 집합의 순서를 바꾸는 함수를 perms라 하면 choices는 아래와 같이 정의 된다.
choices     :: [a] -> [[a]]
choices xs = concat (map perms (subs xs))

subs []       = [[]]
subs (x:xs) = yss ++ map (x:) yss
                     where yss = subs xs

perms          :: [a] -> [[a]]
perms []       = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))

interleave              :: a -> [a] -> [[a]]
interleave x []       = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)

식을 생성하는 과정 중에 결과 값이 양의 정수가 아닐 수가 있다. 이 경우에는 바로 유효하지 않은 식으로 처리하면 된다. 이것을 위해 제대로 된 값을 가지는 식과 그 값을 순서쌍으로 묶은 아래의 타입을 정의하자.
type Result = (Expr, Int)

results       :: [Int] -> [Result]
results []   = []
results [n] = [(Val n, n) | n > 0]
results ns  = [res | (ls, rs) <- split ns, lx <- results ls, ry <- results rs, res <- combine lx ry]

-- 하나의 리스트를 두 개의 비어 있지 않은 리스트로 나눈다.
split           :: [a] -> [([a], [a])]
split []       = []
split [_]     = []
split (x:xs) = ([x], xs) : [(x:ls, rs) | (ls, rs) <- split xs]

- 주어진 두 식의 가능한 모든 연산을 적용하여 유효한 식을 돌려준다.
combine                 :: Result -> Result -> [Result]
combine (l,x) (r,y) = [(App o l r, apply o x y) | o <- ops, valid o x y]

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