Calculating a Given Value From an Array of integer

[Jim Yingst]

The following thread was originally started by Sameer Jamal. I'm reposting it this way because it was accidentally deleted during the move to Programming Diversions:
***************************************************
Posted by: Sameer Jamal, 05-12-2003 09:50 AM
Can you build an algorithm for computing a given number from a given array of integers.
Example: Target number to calculate = 937
Array(5) of integers: {100,10,9,8,7,3}
Each array number can only be used once.
The human answer would be:
100 * 9
+ 10 * 3
+ 7
-----
= 937
======
Of course the example is oversimplified, but it communicates the general idea. The algorithm must be sufficiently general to calculate any number from any combination of numbers.
It may be possible that the array combination may not yield a solution equal to the TargetNumber, in which case the solution should be the closest possible number to the TargetNumber.
Here is an example:
TargetNumber = 789
myArray {75,50,25,7,4,1} ' or is it possible to compute the TargetNumber?
***************************************************
Posted by: Simon Lee, 05-12-2003 11:29 AM
there is a tv show in the UK called 'countdown'. I am 100% sure (I'm not even going to hit google) that if you search for 'countdown solver channel4' you will find dozens of javascript implementations...
***************************************************
Posted by: Jason Menard, 05-19-2003 12:24 PM
I was playing around with this one. I solved it using a brute force method.
Given an int array "seed" of size n ,and an int "target", with seed being the array of integers used to compute target, and a set of operations OPS {"*","+","-"}:
1. Find all permutations of seed (n P 1..n) along with each combination of operations from OPS that may be performed on each permutation.
2. Solve each permutation p. If the solution for a permutation equals the target, we have our solution. Otherwise, if the abs(target - p) is the closest solution so far, store it as the solution and continue.
I stored each permutation as a stack. If seed = {1,2,3}, a few of the permutation stacks for this set would be:
[1]
[3,2,*]
[1,3,-,2,+]
The stack [1,3,-,2,+] evaluates as follows:
1 - 3 = -2
-2 + 2 = 0
Some performance enhancements that could be made to the included code:
1. Don't keep a collection of all permutations and then iterate through the collection to find the solution, simply solve each permutation as it is discovered. I wanted to see all the various permutations so this is why I did it the way I did.
2. Don't bother storing and/or solving permutations which are essentially the same. For example [1,3,+] is the same as [3,1,+].
I'm sure there are more, but these are the obvious ones. Of course as I stated previously, there must be a better way to find the solution aside from this brute force method.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
 
public class CountdownSolver {
    private static final int MULTIPLY = 1;
    private static final int ADD = 2;
    private static final int SUBTRACT = 3;
    private static final String[] OPS = {"*","+","-"};
 
    private String[] seed;
    private int target;
    private Stack solution;
    private Stack evalStack;
    private int distance;
    private List permutations;
 
    public CountdownSolver(int[] seed, int target) {
        this();
        this.seed = convertArray(seed);
        this.target = target;
    }
 
    public CountdownSolver() {
        permutations = new ArrayList();
    }
 
    public void setSeed(int[] seed) {
        this.seed = convertArray(seed);
    }
 
    public void setTarget(int target) {
        this.target = target;
    }
 
    public void solve() {
        findPermutations();
        for (Iterator i = permutations.iterator(); i.hasNext(); ){
            Stack stack = (Stack)i.next();
            evalStack = new Stack();
            evalStack.addAll(stack);
            int result = Math.abs(target - evaluate());
            if (solution == null || result < distance) {
                solution = stack;
                distance = result;
                if (result == 0) {
                    return;
                }
            }
        }
    }
 
    public void displayPermutations() {
        for (Iterator i = permutations.iterator(); i.hasNext(); ) {
            Stack stack = (Stack)i.next();
            System.out.println(displayStack(stack));
        }
    }
 
    private String displayStack(Stack stack) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < stack.size(); i++) {
            sb.append((String)stack.elementAt(i) + " ");
        }
        return sb.toString();
    }
 
    private String displayStackSolution(Stack stack) {
        String newline = System.getProperty("line.separator");
        StringBuffer sb = new StringBuffer();
        Stack tempStack = new Stack();
        tempStack.addAll(stack);
        if (tempStack.size() == 1) {
            return (String)tempStack.pop();
        }
        else if (tempStack.size() > 1) {
            while (!tempStack.isEmpty() && tempStack.size() > 1) {
                int result = evaluate(tempStack);
                sb.insert(0, newline);
                sb.insert(0, result);
                sb.insert(0, " = ");
                String token = (String) tempStack.pop();
                if (isOp(token)) {
                    sb.insert(0, (String) tempStack.pop());
                    sb.insert(0, " " + token + " ");
                    sb.insert(0, evaluate(tempStack));
                }
                else {
                    sb.insert(0, token);
                }
            }
        }
        return sb.toString();
    }
 
    private boolean isOp(String s) {
        for (int i = 0; i < OPS.length; i++) {
            if (OPS[i].equals(s)) {
                return true;
            }
        }
        return false;
    }
 
    public void showSolution() {
        StringBuffer seedNums = new StringBuffer("[");
        int seedLen = seed.length;
        for (int i = 0; i < seedLen; i++) {
            seedNums.append(seed[i]);
            if (i < seedLen - 1) {
                seedNums.append(",");
            }
        }
        seedNums.append("]");
        System.out.println("Seed Numbers: " + seedNums);
        System.out.println("Target: " + target);
        System.out.print("Solution: " +displayStackSolution(solution));
        System.out.println("Distance from target: " + (target - evaluate(solution)));
    }
 
    private void findPermutations() {
        List list = makeListOfStacks(seed);
        for (int i = 0; i < seed.length; i++) {
            list = findPermutations(list);
        }
    }
 
    private List findPermutations(List l) {
        List perms = new ArrayList();
        for (Iterator i = l.iterator(); i.hasNext(); ) {
            Stack stack = (Stack)i.next();
            permutations.add(stack);
            for (int j = 0; j < seed.length; j++) {
                Stack newStack = new Stack();
                newStack.addAll(stack);
                if (!newStack.contains(seed[j])) {
                    newStack.push(seed[j]);
                    for (int k = 0; k < OPS.length; k++) {
                        Stack newerStack = new Stack();
                        newerStack.addAll(newStack);
                        newerStack.push(OPS[k]);
                        perms.add(newerStack);
                    }
                }
            }
        }
        return perms;
    }
 
    private int evaluate(Stack stack) {
        evalStack = new Stack();
        evalStack.addAll(stack);
        return evaluate();
    }
 
    private int evaluate() {
        int result = 0;
        if (evalStack.isEmpty()) {
            return 0;
        }
        String token = (String)evalStack.pop();
        if ("*".equals(token)) {
            result = evaluate(MULTIPLY);
        }
        else if ("+".equals(token)) {
            result = evaluate(ADD);
        }
        else if ("-".equals(token)) {
            result = evaluate(SUBTRACT);
        }
        else {
            result = Integer.parseInt(token);
        }
        return result;
    }
 
    private int evaluate(int op) {
        int value = Integer.parseInt((String)evalStack.pop());
        switch(op) {
            case MULTIPLY:
                return evaluate() * value;
            case ADD:
                return evaluate() + value;;
            case SUBTRACT:
                return evaluate() - value;;
        }
        return 0;
    }
 
    private String[] convertArray(int[] a) {
        String[] s = new String[a.length];
        for (int i = 0; i < a.length; i++) {
            s[i] = String.valueOf(a[i]);
        }
        return s;
    }
 
    private List makeListOfStacks(String[] s) {
        List list = new ArrayList();
        for (int i = 0; i < s.length; i++) {
            Stack stack = new Stack();
            stack.add(s[i]);
            list.add(stack);
        }
        return list;
    }
 
    public static void main(String[] args) {
        int[] seed = {100,10,9,8,7,3};
        int target = 937;
        CountdownSolver cs = new CountdownSolver(seed, target);
        cs.solve();
        cs.showSolution();
    }
}

[ May 20, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Paul Stevens, 05-19-2003 04:44 PM
This doesn't look MDish to me.
***************************************************
Posted by: Simon Lee, 05-20-2003 02:23 AM
Maybe you should watch countdown (the tv show). Imagine watching two people taking 30 seconds to come up with a solution, then they explain it to carol for 10 points.
MD is the best describtion for it.
***************************************************
Posted by: Don Kiddick, 05-20-2003 03:35 AM
I actually got this question in an interview ! Solution given (which I didn't get) was recursive and it involved finding each pair of numbers and the possible values that could result from them (using +-*/), then calling the function recursively with the result and the other numbers. Something like that anyway - it was long time ago !
***************************************************
Posted by: Joel McNary, 05-22-2003 08:48 AM

Originally posted by Don Kiddick:
I actually got this question in an interview ! Solution given (which I didn't get) was recursive and it involved finding each pair of numbers and the possible values that could result from them (using +-*/), then calling the function recursively with the result and the other numbers. Something like that anyway - it was long time ago !

OK, OK...I was a little bored and worked out the recursive method...

/*
 * CountdownSolver.java
 *
 * Created on May 21, 2003, 11:37 PM
 */
class CountdownComponent{
    /**The value of the expression*/
    private double value;
    /**The String representation of the expression*/
    private String expression;
    /**
     * Creates a new CountdownComponent object.
     *
     * @param anExpression The String representation of the integer to use to calculate
     *
     * @throws NumberFormatException If the String cannot be formatted to a double
     */
    public CountdownComponent(String anExpression) throws NumberFormatException{
        value = Double.parseDouble(anExpression);
        expression = anExpression;
    }
    /**
     * Creates a new CountdownComponent object.
     *
     * @param aValue The value of the complex expression
     * @param anExpression The complex expression (e.g., "((5 * 10) + 4)"
     */
    public CountdownComponent(double aValue, String anExpression){
        value = aValue;
        expression = anExpression;
    }
    /**
     * calculate produces a new CountdownComponent
     *
     * @param that The CountdownComponent with which to perform the function
     * @param function The mathematical function to perform on this and that.
     *
     * @return CountdownComponent the result of the calculation
     */
    public CountdownComponent calculate(CountdownComponent that, char function){
        double newValue;
        String newExpression;
        switch (function){
        case '+':
            newValue = this.value + that.value;
            newExpression = "(" + this.expression + " + " + that.expression + ")";
            break;
        case '-':
            newValue = this.value - that.value;
            newExpression = "(" + this.expression + " - " + that.expression + ")";
            break;
        case '*':
            newValue = this.value * that.value;
            newExpression = "(" + this.expression + " * " + that.expression + ")";
            break;
        case '/':
            newValue = this.value / that.value;
            newExpression = "(" + this.expression + " / " + that.expression + ")";
            break;
        default:
            throw new java.lang.IllegalArgumentException("Function must be one of +, -, *, or /");
        }
        return new CountdownComponent(newValue, newExpression);
    }
    /**
     * getValue returns the value of the value member variable
     *
     * @return double the value of the value member variable.
     */
    public double getValue(){
        return value;
    }
    /**
     * getExpression returns the value of the expression member variable
     *
     * @return String the value of the expression member variable
     */
    public String getExpression(){
        return expression;
    }
    /**
     * toString returns the value of this object in a printable format.
     *
     * @return the value of this object in a printable format.
     */
    public String toString(){
        return expression + "[" + value + "]";
    }
}
/**
 * CountdownSolver is a class that, given a list of integers and a target number
 * attempts to find the mathematical expression using the array and the operators
 * +, -, *, and / that is equal to (or is closest to) the target number.
 *
 * @author Joel McNary
 */
public class CountdownSolver{
    /**The target number that is the goal*/
    private int target;
 
    /**The array of integers
     * Inactuality, this is a List of CountdownComponent elements, which provide
     * information not only about the number but also the expression used to
     * acheive that number.  It is a list because of the large amount of adding and
     * removing that occurs on it in processing.
     */
    private java.util.List source;
    /**The difference between the value of the currentBestComponent and the target*/
    private java.lang.Double currentDeviation;
    /**This is the CountdownComponent whose value is closest to the target*/
    private CountdownComponent currentBestComponent;
    /**This is the list of mathematical operations that can be performed*/
    private final static char[] functions = new char[] { '+', '-', '*', '/' };
    /**
     * Creates a new instance of CountdownSolver
     *
     * @param aTarget The target number
     * @param aList The list of numbers to use.
     */
    public CountdownSolver(int aTarget, java.util.List aList){
        target = aTarget;
        source = aList;
    }
    /**
     * The main method of the program
     * Useage: java CountdownSolver <target> <int1> <int2> ... <intX>
     *
     * @param argv the command line arguments
     */
    public static void main(String[] argv){
        int aTarget;
        java.util.List aList;
        try{
            aTarget = Integer.parseInt(argv[0]);
            aList = new java.util.LinkedList();
            for (int index = 1; index < argv.length; index++){
                aList.add(new CountdownComponent(argv[index]));
            }
        }
        catch (Exception e){
            System.out.println("Useage: java CountdownSolver <target> <int1> <int2> ... <intX>");
            return;
        }
        CountdownSolver aSolver = new CountdownSolver(aTarget, aList);
        aSolver.solve();
    }
    /**
     * solve starts the recursion and prints the solution
     */
    public void solve(){
        this.evaluate(source);
        System.out.println("Target: " + this.target);
        System.out.println("Best Solution" + this.currentBestComponent.getExpression());
        System.out.println("Value: " + this.currentBestComponent.getValue());
        System.out.println("Deviation: " + this.currentDeviation);
    }
    /**
     * evaluate takes each combination of two elements from the
     * specified list and creates new CountdownComponents from those
     * two elements using each of the mathematical functions.
     * The resulting CountdownCompnent is placed in the list and the method
     * is called again.  When only one element is in the list, it's value
     * is compared to that of the target.  If it is closer than the
     * current "best" component, this component becomes the current "best."
     * If the value and the target are equal, it halts the recursion and
     * finishes the process.
     *
     * @param currentList the array of integers to use.
     * This is the same list as source, but is passed as a parameter
     * to emphasise the recursiveness of the function.
     *
     * @return double the current best deviation
     */
    public double evaluate(java.util.List currentList){
        if (currentList.size() == 1){
            CountdownComponent aComponent = (CountdownComponent) currentList.get(0);
            double value = aComponent.getValue();
            double deviation = java.lang.Math.abs(target - value);
            if ((currentDeviation == null) || (deviation < currentDeviation.doubleValue())){
                currentDeviation = new java.lang.Double(deviation);
                currentBestComponent = aComponent;
            }
            if (deviation == 0){
                return 0;
            }
        }
        else{
            for (int index = 0; index < currentList.size(); index++){
                CountdownComponent component1 = (CountdownComponent) currentList.remove(index);
                for (int index2 = 0; index2 < currentList.size(); index2++){
                    CountdownComponent component2 = (CountdownComponent) currentList.remove(index2);
                    for (int index3 = 0;
                             index3 < CountdownSolver.functions.length;
                             index3++){
                        CountdownComponent aComponent = component1.calculate(component2, CountdownSolver.functions[index3]);
                        currentList.add(aComponent);
                        if (this.evaluate(currentList) == 0){
                            return 0;
                        }
                        currentList.remove(aComponent);
                    }
                    currentList.add(index2, component2);
                }
                currentList.add(index, component1);
            }
        }
        return this.currentDeviation.doubleValue();
    }
}

and the solution to:
TargetNumber = 789
myArray {75,50,25,7,4,1}

C:\>java CountdownSolver 789 75 50 25 7 4 1
Target: 789
Best Solution(((75 - 1) * (7 + 4)) - (50 - 25))
Value: 789.0
Deviation: 0.0

***************************************************
Posted by: Jason Menard, 05-22-2003 10:17 AM
I was a little bored and worked out the recursive method...
Actually, both solutions are recursive.
***************************************************
Posted by: Joel McNary, 05-22-2003 11:19 AM
Oops...I guess they are. Silly me.
It was a good exercise anyway.
I note that your solution does not include division; is division permitted? (I included it in mine...)
I think that most interesting result I got was calculation 788 using the same numbers as for 789:
C:\>java CountdownSolver 788 75 50 25 7 4 1
Target: 788
Best Solution(7 - ((1 - (25 * (75 + 50))) / 4))
Value: 788.0
Deviation: 0.0
***************************************************
Posted by: Jason Menard, 05-22-2003 11:37 AM
[quote riginally posted by Joel McNary:
I note that your solution does not include division; is division permitted? (I included it in mine...)
Trying to find out some info about the game Countdown, it seemed that the only operations allowed were multiplication, addition, and subtraction, so that's the direction I headed. Besides, as you found out, division leads to all sorts of nastiness.

I think that most interesting result I got was calculation 788 using the same numbers as for 789:

I just reviewed a book called Java Number Cruncher: The Java Programmer's Guide to Numerical Computing. It goes into detail about precisely the type of problems you ran into. It's worth a read if you get the chance.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Randall Twede, 05-22-2003 11:55 AM
how about one using mod, trig functions, integrals, derivatives, and factorials?
***************************************************
Posted by: Jason Menard, 05-22-2003 11:57 AM

Originally posted by Joel McNary:
I think that most interesting result I got was calculation 788 using the same numbers as for 789:
C:\>java CountdownSolver 788 75 50 25 7 4 1
Target: 788
Best Solution(7 - ((1 - (25 * (75 + 50))) / 4))
Value: 788.0
Deviation: 0.0

Without division, it looks like that one can't be solved exactly. I ended up with the following solution:
Seed Numbers: [75,50,25,7,4,1]
Target: 788
Solution: 75 + 25 = 100
100 + 4 = 104
104 + 1 = 105
105 * 7 = 735
735 + 50 = 785
Distance from target: -3
***************************************************
Posted by: Randall Twede, 05-22-2003 12:01 PM
oh and lets not forget exponents and logarithms
***************************************************
Posted by: Jason Menard, 05-22-2003 12:07 PM

Originally posted by Randall Twede:
how about one using mod, trig functions, integrals, derivatives, and factorials?

Luckily, the game seems to only allow the three operations. If you are trying to solve using brute force, the number of possible permutations gets ridiculous with all those other operations, not to mention the problems of accuracy that would arise. However if you'd like to tackle a version with all these extras, I know I'd be interested in seeing it.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Joel McNary, 05-22-2003 12:52 PM

Originally posted by Jason Menard:
Without division, it looks like that one can't be solved exactly. I ended up with the following solution:
Seed Numbers: [75,50,25,7,4,1]
Target: 788
Solution: 75 + 25 = 100
100 + 4 = 104
104 + 1 = 105
105 * 7 = 735
735 + 50 = 785
Distance from target: -3

Interesting. I thought you should come up with 789 (((75 - 1) * (7 + 4)) - (50 - 25)), which is 1 away...or can't you use parens to group?
***************************************************
Posted by: Jason Menard, 05-22-2003 01:23 PM
hatever page I looked at to try to figure out the rules didn't use either division or parens, but now that I am looking on other sites I can see many that do use these. I would of course have to alter not only my evaluation but the way I found permutations.
Maybe you have to be British to really understand it. In any case, it was a fun exercise. I think I should at least get style points for my stacks and evaluate methods! Although somewhere out there is a genetic algorithm solution (whatever that is exactly) for these types of problems, which is probably far more elegant than anything my lowly brain can produce in its current state.
To be honest I'd like to see more of these kind of postings. Particularly if several people take a stab at solving them.
[ May 22, 2003: Message edited by: Jason Menard ]
***************************************************
Posted by: Joel McNary, 05-23-2003 06:08 AM

Originally posted by Jason Menard:
Although somewhere out there is a genetic algorithm solution

I'll get to work on it...but it'll take a back seat to some of my other projects

To be honest I'd like to see more of these kind of postings. Particularly if several people take a stab at solving them.

Me too....I'll se what I can come up with...
[ May 31, 2003: Message edited by: Jim Yingst ]