Public Group

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

## 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 on other sites
Well first off this problem has nothing at all to do with programming.. as far as i can tell. I will try to figure it out though

##### 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 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 on other sites
yeah but they could also input a string of digits like 19128271727181, then it would be a lot more intensive

##### 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 on other sites
hi tooh, could you put that in c-like pseudo code? make it easier to read for my newb eyes.

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631768
• Total Posts
3002242
×