That's far too many solutions.
(I won't take the time to examine them all, but number 16, for example, produces a
negative 315, which is not an answer to the problem.)
In any case,
helios's solutions brings up an important issue when calculating results: how do we handle intermediary values?
I posit three options:
- Permit only exact division: quotient
must be an integer
This behavior is what OP desires (as per his second post above)
(157 solutions to OP's example)
- Allow floating point intermediaries when dividing
An example is 7 = 1 + 4 / (2 / 3).
(232 solutions to OP's example)
- Use "integer division" (discard any remainder)
(558 solutions to OP's example)
This is actually for a game at my son's math club. |
This is a pretty brutal problem for your average child, as it is NP-complete and requires both permutations and combinations, not to mention generating valid RPN sequences and nested loops.
And it is pretty slow.
There are some things you can do to shave time (like shaving recalculating subsolutions), but you cannot shave testing every solution.
I've only got a brute-force algorithm in Tcl ATM. The strict division problem works in about 3 minutes. I'm sure I can cut a lot of that out by getting rid of shimmering and using some prefix trees and caching output. (And by writing it in C++.)
If you only need a single solution, you can usually get that pretty quick though, and just quit after it is found. If you want to check a user's solution that requires only evaluating the expression itself, which is faster than anything else.
Caveats: my solution may have missed something!
(I don't think it did, but I still have to carefully validate my RPN sequence generator.)