Sign in to follow this  
Darwin08

Tricky problem

Recommended Posts

Darwin08    122
my friend just asked me a question about programming that he got for a hw problem. I dont know how to approach it. Basically you get a string of digits like "1928923717", and somehow you have to insert addition and multiplication signs in between the digits to somehow equal a target value like "12,891" so say the use inputs 333, and the target value is "12", the function should output: 3+3*3 (i'm assuming multiplication goes first) does anyone know how to approach this problem? it's a tough one.

Share this post


Link to post
Share on other sites
HappyCoder    5052
Well at first glance it would seem that having a * will make bigger numbers than +. So maybe you could do something like a trial and error and make it so if the result is bigger than you want, switch a * to a +. If it is smaller change a + to a *. There is also probably an intelligent way to systematically work through that was well.

Share this post


Link to post
Share on other sites
HappyCoder    5052
Actually, thinking about it more. You could probably just brute force it. Write a program to loop through every possible combination until you find the answer.

only 3^9 combinations. That is 19683. A computer should be able to calculate that pretty quickly.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
The problem has a quite simple recursive solution...

let get (Some x) = x;;

let rec solve n = function
| [e] -> if e = n then Some " " else None
| a::b::t ->
if n < a then None
else let r = solve (n-a) (b::t) in if r <> None then Some (" +" ^ get r)
else let r = solve n ((a*b)::t) in if r <> None then Some (" *" ^ get r)
else None
;;


By the way, 12891 cannot be expressed using addition and multiplication from 1928923717, because it's too big (something which the above program determines faster than a second). The performance impact of the exhaustive search only begins to appear past 30 digits, and that happens when using the ocaml toplevel (native code generation and optimization should get past that, as would memoization).

However, 128 = 1*9 + 2*8 + 9*2*3 + 7*1*7.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this