Sign in to follow this  

Tricky problem

This topic is 3578 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

This topic is 3578 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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