I was watching a TV contest where contestants needed to solve a simple math quiz. Six positive integers are given to get as close as possible to a given target number (usually larger) using arithmetic operations, where each number can only be used once at most. Sometimes there is a perfect match, other times the best shot is a few units away from the target. Any good solution is acceptable, but a solution with fewer numbers might be viewed as better.
Since I had my laptop with me, I thought I could write a program to solve the questions faster than I could. But I needed to think about what that program looked like. And then, if my program works, another question would be if it will work fast enough.
Finding a solution
If we start with a simple problem, where we have just two numbers (a, b) and a target (t), the program could try if any of these (a+b), (a-b), (b-a), (a*b), (b/a), or (b/a) equals t.
If we add a third number c, we could then try to combine it with any of the previous values obtained from (a, b) using the available operations. And this idea gives us a base for a possible recursion strategy. If the target is reached at any point, we can stop (unless we wish to output all possible solutions).
If we only want to return the best solution (the one that uses fewer numbers), we might need to obtain all the solutions and choose the best, or obtain solutions in a way that ensures the best one appears the soonest.
Some numerical considerations
While I do not know whether a formal problem statement was provided during the show history, I do not know whether there are limits on the numbers used (I only see one- or two-digit numbers, mostly one-digit), and targets are usually two- or three-digit numbers. So we can assume 32-bit integers are more than sufficient for our job, but current processors can process 64-bit integers just as fast. Certain languages, such as Python, may use arbitrary-precision numbers by default.
While multiplication and addition are commutative, division and subtraction are not. We need to take that into account. When working with integers, only integer division is considered here. We could use fractions, but the contest rules only allow positive integers as intermediate results.
Another detail is that, if we consider only (a-b) rather than (b-a) when exploring the solution space, given a>b, we can avoid a negative intermediate result. That is not a limitation, as this number can appear as -b in an upcoming subtraction, thereby creating fewer combinations in the search tree. Yes, we can also avoid returning the 0 result when a=b without that causing a problem.
Regarding division, we cannot accept any a/b where b equals 0. And since we are only using integer division, we cannot divide if b > a, as that would return 0, which is not a useful result in our search either.
Providing the result
We need to know not only whether the target can be reached or approximated, but also the exact sequence of operations that will achieve it. So that means that as we search each potential solution, we need to store the partial sequence of operations. Once the solution is found, we just print the stored sequence associated with it.
Let us start with the base case: if the target is already one of the numbers in the input list, then the solution is just it, no math needed at all!
If not, we should try to find a valid solution with two numbers, so we need to loop through every possible pair (and no combination) from the input list. Next, we will try three-number sets, and so on until we use the full set of six numbers, stopping at any point if an exact solution is found and keeping the best approximation along the way in case a perfect match is never found. This will make any exact solution faster than approximations, since the latter require searching the entire problem space before producing a result.
You can find the Python source code
here.
Comments