Choose best combinations of operators to find target number

Question

I have an array of operations and a target number.

The operations could be

+ 3
- 3
* 4
/ 2

I want to find out how close I can get to the target number by using those operations.

I start from 0 and I need to iterate through the operations in that order, and I can choose to either use the operation or not use it.

So if the target number is 13, I can use + 3 and * 4 to get 12 which is the closest I can get to the target number 13.

I guess I need to compute all possible combinations (I guess the number of calculations is thus 2^n where n is the number of operations).

I have tried to do this in java with

import java.util.*;

public class Instruction {
    public static void main(String[] args) {
        // create scanner
        Scanner sc = new Scanner(System.in);

        // number of instructions
        int N = sc.nextInt();

        // target number
        int K = sc.nextInt();

        //
        String[] instructions = new String[N];

        // N instructions follow
        for (int i=0; i<N; i++) {
            //
            instructions[i] = sc.nextLine();
        }

        //
        System.out.println(search(instructions, 0, N, 0, K, 0, K));
    }

    public static int search(String[] instructions, int index, int length, int progressSoFar, int targetNumber, int bestTarget, int bestDistance) {
        //
        for (int i=index; i<length; i++) {
            // get operator
            char operator = instructions[i].charAt(0);

            // get number
            int number = Integer.parseInt(instructions[i].split("\\s+")[1]);

            //
            if (operator == '+') {
                progressSoFar += number;
            } else if (operator == '*') {
                progressSoFar *= number;
            } else if (operator == '-') {
                progressSoFar -= number;
            } else if (operator == '/') {
                progressSoFar /= number;
            }

            //
            int distance = Math.abs(targetNumber - progressSoFar);

            // if the absolute distance between progress so far
            // and the target number is less than what we have
            // previously accomplished, we update best distance
            if (distance < bestDistance) {
                bestTarget = progressSoFar;
                bestDistance = distance;
            }

            //
            if (true) {
                return bestTarget;
            } else {
                return search(instructions, index + 1, length, progressSoFar, targetNumber, bestTarget, bestDistance);
            }
        }
    }
}

It doesn't work yet, but I guess I'm a little closer to solving my problem. I just don't know how to end my recursion.

But maybe I don't use recursion, but should instead just list all combinations. I just don't know how to do this.

If I, for instance, have 3 operations and I want to compute all combinations, I get the 2^3 combinations

where 1 indicates that the operation is used and 0 indicates that it is not used.

It should be rather simple to do this and then choose which combination gave the best result (the number closest to the target number), but I don't know how to do this in java.

Fun! This reminds me of https://en.wikipedia.org/wiki/24_Game. — JakeRobb, Apr 01 '16 at 14:05
you do not need to pass 'length' around. Java arrays can always tell you their length. Example: `int[] a = new int[5]; System.out.println(""+a.length); outputs 5;` — tucuxi, Apr 01 '16 at 14:09
Oh. How did you solve this? But in this case, each operation can only be used once. But thanks! — Jamgreen, Apr 01 '16 at 14:41
@Paul I suspect that OP is not allowed to reuse the same operation over and over — tucuxi, Apr 01 '16 at 14:41
I recommend that you choose a different combination of operations. The set you give produces only seven distinct results, three of which are the inverses of three others. Change the second operation to -1, and you'll have a better example. — Prune, Apr 01 '16 at 17:04
Related at least, similar probably: http://stackoverflow.com/questions/21461084/how-to-find-the-exact-set-of-operations-for-a-specific-number/21463659#21463659 — Marco13, Apr 01 '16 at 18:17

tucuxi · Answer 1 · 2016-04-01T14:49:47.207

In pseudocode, you could try brute-force back-tracking, as in:

// ops: list of ops that have not yet been tried out
// target: goal result
// currentOps: list of ops used so far
// best: reference to the best result achieved so far (can be altered; use
//     an int[1], for example)
// opsForBest: list of ops used to achieve best result so far
test(ops, target, currentOps, best, opsForBest)
      if ops is now empty,
         current = evaluate(currentOps)
         if current is closer to target than best,
            best = current
            opsForBest = a copy of currentOps
      otherwise, 
         // try including next op
         with the next operator in ops,
            test(opsAfterNext, target, 
                currentOps concatenated with next, best, opsForBest)
         // try *not* including next op
         test(opsAfterNext, target, currentOps, best, opsForBest)

This is guaranteed to find the best answer. However, it will repeat many operations once and again. You can save some time by avoiding repeat calculations, which can be achieved using a cache of "how does this subexpression evaluate". When you include the cache, you enter the realm of "dynamic programming" (= reusing earlier results in later computation).

Edit: adding a more OO-ish variant

Variant returning the best result, and avoiding the use of that best[] array-of-one. Requires the use of an auxiliary class Answer with fields ops and result.

// ops: list of ops that have not yet been tried out
// target: goal result
// currentOps: list of ops used so far
Answer test(ops, target, currentOps, opsForBest)
      if ops is now empty,
         return new Answer(currentOps, evaluate(currentOps))
      otherwise, 
         // try including next op
         with the next operator in ops,
            Answer withOp = test(opsAfterNext, target, 
                currentOps concatenated with next, best, opsForBest)
         // try *not* including next op
         Answer withoutOp = test(opsAfterNext, target, 
                currentOps, best, opsForBest)
         if withOp.result closer to target than withoutOp.target,
            return withOp
         else
            return withoutOp

You do not return it. Once it exits, the value in `best` is correct, and the `opsForBest` contains the sequence of operators that generated it. Of course, you can make it return best (and then you would not need to pass it along). Editing in the variant. — tucuxi, Apr 01 '16 at 14:33
@tucuxi I think the word you're looking for is amortize, not cache per say. — SGM1, Apr 01 '16 at 14:42
@SGM1 I really do not see how the word `amortize` can replace `cache` in the above context. Can you explain? — tucuxi, Apr 01 '16 at 14:52
Ops, I was mistaken, memoization is the correct word, got it from j_random. — SGM1, Apr 01 '16 at 17:57

score 0 · Answer 2 · answered Apr 01 '16 at 17:47

Dynamic programming

If the target value is t, and there are n operations in the list, and the largest absolute value you can create by combining some subsequence of them is k, and the absolute value of the product of all values that appear as an operand of a division operation is d, then there's a simple O(dkn)-time and -space dynamic programming algorithm that determines whether it's possible to compute the value i using some subset of the first j operations and stores this answer (a single bit) in dp[i][j]:

dp[i][j] = dp[i][j-1] || dp[invOp(i, j)][j-1]

where invOp(i, j) computes the inverse of the jth operation on the value i. Note that if the jth operation is a multiplication by, say, x, and i is not divisible by x, then the operation is considered to have no inverse, and the term dp[invOp(i, j)][j-1] is deemed to evaluate to false. All other operations have unique inverses.

To avoid loss-of-precision problems with floating point code, first multiply the original target value t, as well as all operands to addition and subtraction operations, by d. This ensures that any division operation / x we encounter will only ever be applied to a value that is known to be divisible by x. We will essentially be working throughout with integer multiples of 1/d.

Because some operations (namely subtractions and divisions) require solving subproblems for higher target values, we cannot in general calculate dp[i][j] in a bottom-up way. Instead we can use memoisation of the top-down recursion, starting at the (scaled) target value t*d and working outwards in steps of 1 in each direction.

C++ implementation

I've implemented this in C++ at https://ideone.com/hU1Rpq. The "interesting" part is canReach(i, j); the functions preceding this are just plumbing to handle the memoisation table. Specify the inputs on stdin with the target value first, then a space-separated list of operations in which operators immediately preceed their operand values, e.g.

10 +8 +11 /2

or

10 +4000 +5500 /1000

The second example, which should give the same answer (9.5) as the first, seems to be around the ideone (and my) memory limits, although this could be extended somewhat by using long long int instead of int and a 2-bit table for _m[][][] instead of wasting a full byte on each entry.

Exponential worst-case time and space complexity

Note that in general, dk or even just k by itself could be exponential in the size of the input: e.g. if there is an addition, followed by n-1 multiplication operations, each of which involves a number larger than 1. It's not too difficult to compute k exactly via a different DP that simply looks for the largest and smallest numbers reachable using the first i operations for all 1 <= i <= n, but all we really need is an upper bound, and it's easy enough to get a (somewhat loose) one: simply discard the signs of all multiplication operands, convert all - operations to + operations, and then perform all multiplication and addition operations (i.e., ignoring divisions).

There are other optimisations that could be applied, for example dividing through by any common factor.

How does this deal with finding the _nearest_ result to the goal, as opposed to an exact match? — tucuxi, Apr 01 '16 at 19:21
@tucuxi: The `for` loop on line 116 starts looking at the exact target, and continues trying values at an increasing distance from the target (both above and below) until it finds one. (It must terminate, because it will eventually try the value 0.) — j_random_hacker, Apr 02 '16 at 14:26
@tucuxi: Also see in my answer "Instead we can use memoisation of the top-down recursion, starting at the (scaled) target value t*d and working outwards in steps of 1 in each direction.". Finally, I deliberately chose the example of target=10, nearest solution=9.5 to show that non-exact nearest solutions are found :) — j_random_hacker, Apr 02 '16 at 14:28

SGM1 · Answer 3 · 2016-04-05T19:46:06.763

Here's a Java 8 example, using memoization. I wonder if annealing can be applied...

public class Tester {

    public static interface Operation {
        public int doOperation(int cur);
    }

    static Operation ops[] = { // lambdas for the opertions
            (x -> x + 3),
            (x -> x - 3),
            (x -> x * 4),
            (x -> x / 2), 
    };

    private static int getTarget(){
        return 2;
    }

    public static void main (String args[]){
        int map[];
        int val = 0;
        int MAX_BITMASK = (1 << ops.length) - 1;//means ops.length < 31 [int overflow]
        map = new int[MAX_BITMASK];
        map[0] = val;

        final int target = getTarget();// To get rid of dead code warning

        int closest = val, delta = target < 0? -target: target;
        int bestSeq = 0;

        if (0 == target) {
            System.out.println("Winning sequence: Do nothing");
        }

        int lastBitMask = 0, opIndex = 0;
        int i = 0;
        for (i = 1; i < MAX_BITMASK; i++){// brute force algo
            val = map[i & lastBitMask]; // get prev memoized value
            val = ops[opIndex].doOperation(val); // compute
            map[i] = val; //add new memo

            //the rest just logic to find the closest
            // except the last part
            int d = val - target;
            d = d < 0? -d: d;
            if (d < delta) {
                bestSeq = i;
                closest = val;
                delta = d;
            }
            if (val == target){ // no point to continue
                break;
            }

            //advance memo mask 0b001 to 0b011 to 0b111, etc.
            // as well as the computing operation.
            if ((i & (i + 1)) == 0){ // check for 2^n -1
                lastBitMask = (lastBitMask << 1) + 1;
                opIndex++;
            }
        }
        System.out.println("Winning sequence: " + bestSeq);
        System.out.println("Closest to \'" + target + "\' is: " + closest);
    }

}

Worth noting, the "winning sequence" is the bit representation (displayed as decimal) of what was used and what wasn't, as the OP has done in the question.

For Those of you coming from Java 7, this is what I was referencing for lambdas: Lambda Expressionsin GUI Applications. So if you're constrained to 7, you can still make this work quite easily.

Choose best combinations of operators to find target number

3 Answers3

Dynamic programming

C++ implementation

Exponential worst-case time and space complexity