Jump to content
  • Advertisement
Sign in to follow this  
Darwin08

Tricky problem

This topic is 3794 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
Advertisement
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
yeah but they could also input a string of digits like 19128271727181, then it would be a lot more intensive

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!