haskell - Given a string of ints and an objective number print out all the possible combinations of tuples and their results -


well, understand whole point of haskell (mostly) advantage of using recursivity build more complex functions out of simpler ones, have function named pairs string of ints returns possible tuple combinations, have function called operations given tuple, prints out of possible operations 2 numbers can (*,+,-,/), comes part can't round head:

-- 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/=4 && y/=2) ] ++     [ (x, y, '/', x `div` y) | x >= y, x `mod` y == 0]

i'm trying implement function given string of ints , objective number (ultimate aim obtain number string of ints) print out possible combinations of tuples , results, e.g.)

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)] ) ]

im confused how approach this, know have function prints possible operations on tuple , 1 produces tuples yet can't see how combine them, appreciated, thanks.

i see solution , makes sense late me start scratch,

i have done this:

solve(n,ns) = [ e | ns' <- pairs ns                       , e   <- operations ns']

( 100 , [3,5] , [(4,1,'-',3)] ), want

i see, want try way work seems bit different , confused after 2nd where, i'm still bit terrible @ haskell. functions do: pairs: when given string returns possible tuples: pairs [1,2,3,4,5,6] return [(1,2),(1,3)...etc] operations takes tuple , returns possible operations tuple (has positive integer result else don't want it) , finally

solve(n,ns) = [ e | ns' <- pairs ns                       , e   <- operations ns']

takes n objective number, ns string of 6 +ints , far returns string combinations of tuples printed such as: [(3,'+',4,7),(3,´*´,4,12)...etc] want printing @ each stage:

[n,(result of tuple operation,string number)(tuple operation)] eg ( 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)] ),

there lot of ways solve problem. follows outline of relatively straight-forward haskell-esque solution. note uses algebraic data types, you'll want become familiar if aren't already.

note: involved problem. solution (which relatively clean) 55 lines long.

the first step define appropriate data type problem. choose following:

data expr = lit int    | plus expr expr    | times expr expr    | minus expr expr    | divide expr expr   deriving show

a value of type expr expression tree composed of 4 binary operations , has integers @ leaves. using definition you'll want define following functions:

eval :: expr -> int       -- "evaluate" expression  exprs :: [int] -> [expr]  -- derive expression trees literals come                           -- list of integers

then finding expressions evaluate particular number just:

findexprs :: [int] -> int -> [expr] findexprs xs y = filter (\e -> eval e == y) $ exprs xs

writing eval

the eval function going straight-forward case analysis:

eval (lit x) = x eval (plus b) = (eval a) + (eval b) eval (minus b) = (eval a) - (eval b) ...

hint: division, quot function.

writing exprs

the first couple of cases exprs pretty easy:

exprs :: [int] -> [expr] exprs []  = [] exprs [x] = [ lit x ] exprs xs  = ...

when there 1 number in list, expression can create lit.

the final case of exprs goes this:

  1. divide xs 2 sub-lists: left , right
  2. formulate expression tree using list left
  3. formulate expression tree using list right
  4. combine 2 expression trees binary operator

steps 2 , 3 recursive calls exprs function. step 4 iterates through of possible binary operators. can use list comprehension this.

for step 1 need find ways of splitting list 2 sub-lists. is, need define function:

parts :: [int] -> [ ([int], [int]) ]

for example, parts [1,2] = [ ([1,2],[]), ([1],[2]), ([2],[1]), ([], [1,2]) ].

of course, parts can defined recursively, , trick find pattern:

parts [] = [ ([],[]) ] parts (x:xs) = ...???...

a hint here ask how form parts (x:xs) parts xs.

caveats

i've left out implementation details. first of all, if want implement division correctly you'll have re-consider type signature eval:

eval :: expr -> int

initially things working may want leave out division operator. may want read on maybe data type.

i've left out details in definition of exprs. there's infinite-loop pitfall (which can side-stepped) lurking in steps i've outlined.

good luck!

comments

(since doesn't long-running threads in comments, i'll address op's questions here.)

as mentioned before, there many ways solve problem, e.g. see algorithm permutations of operators , operands

this approach more complicated, useful decompositional pattern see used in haskell. takes care separate following concerns:

  1. generating possible trees (the exprs function)
  2. evaluating expression tree (the eval function)
  3. find trees of interest (filter ...)

your approach combines first 2 concerns. may not problem if solving problem, suppose change criteria legal expression. instance, if numbers in list can reused multiple times (currently numbers may used once.) or, if don't need use of numbers? these variations require changing exprs function.


Comments

Post a Comment