haskell - Given a list of numbers use the four basic operations between them to find another given number -
first: english isn't good, apologies :(
so, problem have solve:
-- based on simple math game: given list of numbers use 4 basic -- operations (+, -, /, *) between them find (or close possible to) -- given number there examples of problem need more concrete resolve , cant think in "haskell mode", i'm c++ player :(
so, have done:
-- find possible 2-combinations of elements of xs. pairs :: [int] -> [(int, int)] pairs xs = [(x, y) | (x:ys) <- tails xs, y <- ys] operations :: (int, int) -> [(int, int, char, int)] operations (x, y) = [ (x, y, '+', x + y) ] ++ [ (x, y, '*', x * y) ] ++ [ (x, y, '-', x - y) | x > y ] ++ [ (x, y, '/', x `div` y) | x >= y, x `mod` y == 0] i have implement function ('solve') following:
'solve' function returns list resulting nodes choose pair of numbers list of available numbers , apply operations possible selected partner.
i'll have update list of available numbers (eliminating used , adding new one) , list of operations (to reflect latest operation)
example:
solve ( 100 , [1,4,5] , [] ) [ ( 100 , [5,5] , [(1,4,'+',5)] ), -- take first tuple 1,4 add , subs "new tuple"5,5 ( 100 , [3,5] , [(4,1,'-',3)] ), ( 100 , [6,4] , [(1,5,'+',6)] ), ( 100 , [4,4] , [(5,1,'-',4)] ), ( 100 , [9,1] , [(4,5,'+',9)] ), ( 100 , [1,1] , [(5,4,'-',1)] ), ( 100 , [20,1] , [(4,5,'*',20)] ) ] first take couple of numbers(using pairs function),
second show [number,number,'operation',result] of 'operations' can do.
i have this:
solve(n,ns) = [ e | ns' <- pairs ns , e <- operations ns'] but can't make work,any idea??
edit:
i appreciate answer,thank much, if can't function i'm asking can't understand development because i'm really new in haskell :(
as say, need function list of numbers , 2 operations wrote in main post (operations , pairs) make function this:
example)
solve ( 100 , [1,4,5] , [] ) [ ( 100 , [5,5] , [(1,4,'+',5)] ), ( 100 , [3,5] , [(4,1,'-',3)] ), ( 100 , [6,4] , [(1,5,'+',6)] ), ( 100 , [4,4] , [(5,1,'-',4)] ), ( 100 , [9,1] , [(4,5,'+',9)] ), ( 100 , [1,1] , [(5,4,'-',1)] ), ( 100 , [20,1] , [(4,5,'*',20)] ) ] thank answer need more specific in answer.
this neat problem, trickier might seem @ first.
we want to, mathematical operations '+', '-', '*', , '/'
data op = plus | minus | mult | div deriving (eq, ord) ops = [op] ops = [plus, minus, div, mult] instance show op show plus = "+" show minus = "-" show div = "/" show mult = "*" and set of numbers ns, search possible arithmetic expressions use each number once expression closest goal. solve this, we'll express problem abstractly, solve in way that's correct, apply optimizations.
let's think of kind of data type represent our expression. each term, call term, needs either combination of op , 2 other terms acting on, or "pure" value, integer itself.
data term = ap op term term | pure double such have (2 + (3 * 4)) represented app plus (pure 2) (app mult (pure 3) (pure 4)). given such term, traverse recursively print out or compute result.
instance show term show (pure x) = show x show (ap op l r) = "(" ++ show l ++ " " ++ show op ++ " " ++ show r ++ ")" we'll investigate in more detail in due time, need focus on generation.
given number in our list of numbers n <- ns, can construct term involves in 3 different ways, either pure n, term op n other, or term op other n op 1 of our ops , other term constructed numbers in data.list.delete n ns (ns without n). valid recursive definition of terms possible construct ns. let's build it.
first we'll need way of selecting or "focusing" on each element in ns. we'll forming zipper through ns pares :: [a] -> [([a], a, [a])] turns list list of triples, 1 each element in original list. middle element "focused" value, left list elements on left side of our focused value , right list values on right side. might seem overkill, it'll come in handy later.
pare :: [a] -> int -> ([a], a, [a]) pare xs n = pare' n ([], xs) -- accumulate left , right sides -- end storing left list in reverse, style of zippers -- seems little weird, makes code simple , shouldn't -- affect our problem pare' 0 (left, x:right) = (left, x, right) pare' n (left, x:right) = pare' (n-1) (x:left, right) -- 'pare' little dangerous since can have out of bounds errors, -- 'pares' can not. pares :: [a] -> [([a], a, [a])] pares xs = map (pare xs) [0..length xs - 1] and can call pares [1,2,3] get
[ ( [] , 1 , [2,3] ) , ( [1] , 2 , [3] ) , ( [2,1] , 3 , [] ) ] from here it's straightforward definition, allterms :: [double] -> [term], using list comprehensions.
allterms ns = [ result | (left, n, right) <- pares ns , result <- pure n : (concat [ [ ap op (pure n) term, ap op term (pure n) ] | op <- ops , term <- allterms (left ++ right) ]) ] okay, not straightfoward. since want return "at least" (pure n) term, have separate out our list comprehension handles recursive terms. otherwise, [] result since list fails return recursive subterms allterms [].
this notation little difficult, let's change monadic notation, list comprehensions can transformed uses of list monad.
allterms ns = (left, n, right) <- pares ns let branches = op <- ops term <- allterms (left ++ right) [ ap op (pure n) term, ap op term (pure n) ] pure n : branches do notation lets strip off unnecessary brackets , gives better ground optimizations later. now, can test thing.
*main> mapm_ print $ allterms [1,2] 1.0 (1.0 + 2.0) (2.0 + 1.0) (1.0 - 2.0) (2.0 - 1.0) (1.0 / 2.0) (2.0 / 1.0) (1.0 * 2.0) (2.0 * 1.0) 2.0 (2.0 + 1.0) (1.0 + 2.0) (2.0 - 1.0) (1.0 - 2.0) (2.0 / 1.0) (1.0 / 2.0) (2.0 * 1.0) (1.0 * 2.0) it should easy check is... well, comprehensive. demonstrates weakness in our definition---we ignored lots of symmetry of problem. instance, it's not necessary generate subterms number we've visited (those terms generated later terms again. furthermore, when op plus or mult, can take advantage of commutativity. it's quick rewrite fix this.
allterms ns = (left, n, right) <- pares ns let branches = op <- ops term <- allterms right -- no longer visit left terms -- value of using 'pares' makeapps op (pure n) term pure n : branches -- makeapps applies symmetry when operator div or -- minus. makeapps plus t1 t2 = [ap plus t1 t2] makeapps mult t1 t2 = [ap mult t1 t2] makeapps op l r = [ap op l r, ap op r l] if ns = [1,2,3] our first version generate 195 terms. second 1 takes advantage of symmetry generate 57 terms. reasonable, let's keep moving forward.
so we've generated of possible terms, need evaluate them. our show instance relatively simple recursive definition.
calcterm :: term -> double calcterm (pure x) = x calcterm (ap plus l r) = calcterm l + calcterm r calcterm (ap minus l r) = calcterm l - calcterm r calcterm (ap mult l r) = calcterm l * calcterm r calcterm (ap div l r) = calcterm l / calcterm r let's we're looking term has value closest goal :: double. can annotate every term t "error", abs (goal - calcterm t) sort that. we'll need use specialized sortby :: (a -> -> ordering) -> [a] -> [a] data.list.
import data.list (sortby) bestterm :: double -> [term] -> (double, term) bestterm g = minimumby (\(a, _) (b, _) -> `compare` b) . map (\t -> (abs (g - calcterm t), t)) or, using specialized functions control.arrow.&&& , data.ord.comparing can write quickly
bestterm :: double -> [term] -> (double, term) bestterm g = minimumby (comparing fst) . map (first error) error t = abs (g - calcterm t) and can begin answer question
*main> bestterm 31 $ allterms [1..5] (0.0,(1.0 + ((3.0 * (4.0 * 5.0)) / 2.0))) but sometimes, since waiting on length $ allterms [1..10] defeats patience. looks there (7^n-1)/6 terms on n numbers (see sloane) we'd waiting on compute 47,079,208 terms.
hopefully demonstrates how go computing answer problem , gives amble locations search ways optimize result.
and think answer example (79.0, (1.0 + (4.0 * 5.0)))
Comments
Post a Comment