6

This question is quite a long shot. It could take quite long, so if you haven't the time I understand.

Let me start by explaining what I want to achieve: Me and some friends play this math game where we get 6 random numbers out of a pool of possible numbers: 1 to 10, 25, 50, 75 and 100. 6 numbers are chosen out of these and no duplicates are allowed. Then a goal number will be chosen in the range of [100, 999]. With the 6 aforementioned numbers, we can use only basic operations (addition, subtraction, multiplication and division) to reach the goal. Only integers are allowed and not all 6 integers are required to reach the solution.

An example: We start with the numbers 4,8,6,9,25,100 and need to find 328. A possible solution would be: ((4 x 100) - (9 x 8)) = 400 - 72 = 328. With this, I have only used 4 out of the 6 initial numbers and none of the numbers have been used twice. This is a valid solution.

We don't always find a solution on our own, that's why I figured a program would be useful. I have written a program (in Java) which has been tested a few times throughout and it had worked. It did not always give all the possible solutions, but it worked within its own limitations. Now I've tried to expand it so all the solutions would show.

On to the main problem: The program that I am trying to execute is running incredibly long. As in, I would let it run for 15 minutes and it doesn't look like it's anywhere near completion. So I thought about it and the options are indeed quite endless. I start with 6 numbers, I compare the first with the other 5, then the second with the other 5 and so on until I've done this 6 times (and each comparison I compare with every operator, so 4 times again). Out of the original one single state of 6 numbers, I now have 5 times 6 times 4 = 120 states (with 5 numbers each). All of these have to undergo the same ritual, so it's no wonder it's taking so long.

The program is actually too big to list here, so I will upload it for those interested: http://www.speedyshare.com/ksT43/MathGame3.jar (Click on the MathGame3.jar title right next to download)

Here's the general rundown on what happens:

-6 integers + goal number are initialized
-I use the class StateNumbers that are acting as game states
  -> in this class the remaining numbers (initially the 6 starting numbers)
     are kept as well as the evaluated expressions, for printing purposes

This method is where the main operations happen:

StateNumbers stateInProcess = getStates().remove(0);
ArrayList<Integer> remainingNumbers = stateInProcess.getRemainingNumbers();
for(int j = 0; j < remainingNumbers.size(); j++){
  for(int i = 0; i < remainingNumbers.size(); i++){
    for(Operator op : Operator.values()){       // Looping over different operators
       if(i == j) continue;
           ...

    }
  }
}

I evaluate for the first element all the possible operations with all the remaining numbers for that state. I then check with a self written equals to see if it's already in the arraylist of states (which acts as a queue, but the order is not of importance). If it's not there, then the state will be added to the list and then I do the same for the other elements. After that I discard the state and pick another out of the growing list.

The list grows in size to 80k states in 10 minutes and grows slower and slower. That's because there is an increasing amount of states to compare to when I want to add a new state. It's making me wonder if comparing with other states to prevent duplicates is such a good idea.

The completion of this program is not really that important, but I'd like to see it as a learning experience. I'm not asking anyone to write the code for me, but a friendly suggestion on what I could have handled better would be very much appreciated. This means if you have something you'd like to mention about another aspect of the program, please do. I'm unsure if this is too much to ask for on this forum as most topics handle a specific part of a program. While my question is specific as well, the causes could be many.

EDIT: I'm not trying to find the fastest single solution, but every solution. So if I find a solution, my program will not stop. It will however try to ignore doubles like: ((4+5)7) and (7(5+4)). Only one of the two is accepted because the equals method in addition and multiplication do not care about the positioning of the operands.

8

3 Answers 3

4

It would probably be easier to write this using recursion, i.e. a depth-first search, as this would simplify the bookkeeping for intermediary states.

If you want to keep a breath-first approach, make sure that the list of states supports efficient removal of the first element, i.e. use a java.util.Queue such as java.util.ArrayDeque. I mention this because the most frequently used List implementation (i.e. java.util.ArrayList) needs to copy its entire contents to remove the first element, which makes removing the first element very expensive if the list is large.

120 states (with 5 numbers each). All of these have to undergo the same ritual, so it's no wonder it's taking so long.

Actually, it is quite surprising that it would. After all, a 2GHz CPU performs 2 billion clock cycles per second. Even if checking a state were to take as many as 100 clock cycles, that would still mean 20 million states per second!

On the other hand, if I understand the rules of the game correctly, the set of candidate solutions is given by all orderings of the 6 numbers (of which there are 6! = 720), with one of 4 operators in the 5 spaces in between, and a defined evaluation order of the operators. That is, we have a total of 6! * 4^5 * 5! = 88 473 600 candidate solutions, so processing should complete in a couple of seconds.

PS: A full solution would probably not be very time-consuming to write, so if you wish, I can also postcode - I just didn't want to spoil your learning experience.

Update: I have written the code. It was harder than I thought, as the requirement to find all solutions implies that we need to print a solution without unwinding the stack. I, therefore, kept the history for each state on the heap. After testing, I wasn't quite happy with the performance (about 10 seconds), so I added memoization, i.e. each set of numbers is only processed once. With that, the runtime dropped to about 3 seconds.

As Stackoverflow doesn't have a spoiler tag, I increased the indentation so you have to scroll right to see anything :-)

                                                                                                        package katas.countdown;
                                                                                                        
                                                                                                        import java.util.Arrays;
                                                                                                        import java.util.HashSet;
                                                                                                        import java.util.Set;
                                                                                                                                                                                                                        
                                                                                                        enum Operator {
                                                                                                            plus("+", true), 
                                                                                                            minus("-", false), 
                                                                                                            multiply("*", true), 
                                                                                                            divide("/", false);
                                                                                                            
                                                                                                            final String sign;
                                                                                                            final boolean commutes;
                                                                                                            
                                                                                                            Operator(String sign, boolean commutes) {
                                                                                                                this.sign = sign;
                                                                                                                this.commutes = commutes;
                                                                                                            }
                                                                                                            
                                                                                                            int apply(int left, int right) {
                                                                                                                switch (this) {
                                                                                                                case plus:
                                                                                                                    return left + right;
                                                                                                                case minus:
                                                                                                                    return left - right;
                                                                                                                case multiply:
                                                                                                                    return left * right;
                                                                                                                case divide:
                                                                                                                    int mod = left % right;
                                                                                                                    if (mod == 0) {
                                                                                                                        return left / right;
                                                                                                                    } else {
                                                                                                                        throw new ArithmeticException();
                                                                                                                    }
                                                                                                                }
                                                                                                                throw new AssertionError(this);
                                                                                                            }
                                                                                                            
                                                                                                            @Override
                                                                                                            public String toString() {
                                                                                                                return sign;
                                                                                                            }
                                                                                                        }
                                                                                                        
                                                                                                        class Expression implements Comparable<Expression> {
                                                                                                            final int value;
                                                                                                        
                                                                                                            Expression(int value) {
                                                                                                                this.value = value;
                                                                                                            }
                                                                                                            
                                                                                                            @Override
                                                                                                            public int compareTo(Expression o) {
                                                                                                                return value - o.value;
                                                                                                            }
                                                                                                        
                                                                                                            @Override
                                                                                                            public int hashCode() {
                                                                                                                return value;
                                                                                                            }
                                                                                                            
                                                                                                            @Override
                                                                                                            public boolean equals(Object obj) {
                                                                                                                return value == ((Expression) obj).value;
                                                                                                            }
                                                                                                            
                                                                                                            @Override
                                                                                                            public String toString() {
                                                                                                                return Integer.toString(value);
                                                                                                            }
                                                                                                        }
                                                                                                        
                                                                                                        class OperationExpression extends Expression {
                                                                                                            final Expression left;
                                                                                                            final Operator operator;
                                                                                                            final Expression right;
                                                                                                            
                                                                                                            OperationExpression(Expression left, Operator operator, Expression right) {
                                                                                                                super(operator.apply(left.value, right.value));
                                                                                                                this.left = left;
                                                                                                                this.operator = operator;
                                                                                                                this.right = right;
                                                                                                            }
                                                                                                            
                                                                                                            @Override
                                                                                                            public String toString() {
                                                                                                                return "(" + left + " " + operator + " " + right + ")";
                                                                                                            }
                                                                                                        }
                                                                                                        
                                                                                                        class State {
                                                                                                            final Expression[] expressions;
                                                                                                            
                                                                                                            State(int... numbers) {
                                                                                                                expressions = new Expression[numbers.length];
                                                                                                                for (int i = 0; i < numbers.length; i++) {
                                                                                                                    expressions[i] = new Expression(numbers[i]);
                                                                                                                }
                                                                                                            }
                                                                                                            
                                                                                                            private State(Expression[] expressions) {
                                                                                                                this.expressions = expressions;
                                                                                                            }
                                                                                                            
                                                                                                            /**
                                                                                                             * @return a new state constructed by removing indices i and j, and adding expr instead
                                                                                                             */
                                                                                                            State replace(int i, int j, Expression expr) {
                                                                                                                Expression[] exprs = Arrays.copyOf(expressions, expressions.length - 1);
                                                                                                                if (i < exprs.length) {
                                                                                                                    exprs[i] = expr;
                                                                                                                    if (j < exprs.length) {
                                                                                                                        exprs[j] = expressions[exprs.length];
                                                                                                                    }
                                                                                                                } else {
                                                                                                                    exprs[j] = expr;
                                                                                                                }
                                                                                                                Arrays.sort(exprs);
                                                                                                                return new State(exprs);
                                                                                                            }
                                                                                                        
                                                                                                            @Override
                                                                                                            public boolean equals(Object obj) {
                                                                                                                return Arrays.equals(expressions, ((State) obj).expressions);
                                                                                                            }
                                                                                                            
                                                                                                            public int hashCode() {
                                                                                                                return Arrays.hashCode(expressions);
                                                                                                            }
                                                                                                        }
                                                                                                        
                                                                                                        public class Solver {
                                                                                                        
                                                                                                            final int goal;
                                                                                                            
                                                                                                            Set<State> visited = new HashSet<>();
                                                                                                            
                                                                                                            public Solver(int goal) {
                                                                                                                this.goal = goal;
                                                                                                            }
                                                                                                            
                                                                                                            public void solve(State s) {
                                                                                                                if (s.expressions.length > 1 && !visited.contains(s)) {
                                                                                                                    visited.add(s);
                                                                                                                    for (int i = 0; i < s.expressions.length; i++) {
                                                                                                                        for (int j = 0; j < s.expressions.length; j++) {
                                                                                                                            if (i != j) {
                                                                                                                                Expression left = s.expressions[i];
                                                                                                                                Expression right = s.expressions[j];
                                                                                                                                for (Operator op : Operator.values()) {
                                                                                                                                    if (op.commutes && i > j) {
                                                                                                                                        // no need to evaluate the same branch twice
                                                                                                                                        continue;
                                                                                                                                    }
                                                                                                                                    try {
                                                                                                                                        Expression expr = new OperationExpression(left, op, right);
                                                                                                                                        if (expr.value == goal) {
                                                                                                                                            System.out.println(expr);
                                                                                                                                        } else {
                                                                                                                                            solve(s.replace(i, j, expr));
                                                                                                                                        }
                                                                                                                                    } catch (ArithmeticException e) {
                                                                                                                                        continue;
                                                                                                                                    }
                                                                                                                                }
                                                                                                                            }
                                                                                                                        }
                                                                                                                    }
                                                                                                                }
                                                                                                            }
                                                                                                            
                                                                                                            public static void main(String[] args) {
                                                                                                                new Solver(812).solve(new State(75, 50, 2, 3, 8, 7));
                                                                                                            }
                                                                                                        }
                    }

As requested, each solution is reported only once (where two solutions are considered equal if their set of intermediary results is). Per Wikipedia description, not all numbers need to be used. However, there is a small bug left in that such solutions may be reported more than once.

3
  • If you put it that way, I suppose checking every time if my arraylist contains an element is the most time consuming operation. My pc has a 2.5GHz cpu and was nowhere near finished after 10 minutes. I will try using a set and apply depth first to prevent the list from growing too much. You are always welcome to post the solution! It really shows my lack of skills since I've been working on this almost a week. If you post it here, could you cover it in a spoiler tag? I'd like to keep that as a last resort or to compare with what I have.
    – Babyburger
    Dec 22, 2013 at 22:58
  • 1
    Reading the wikipedia page, I noticed that the evaluation order of the operators may be chosen. I have updated the performance estimate to account for this. I have also posted some code :-)
    – meriton
    Dec 23, 2013 at 2:20
  • Thanks a lot! I haven't checked your solution yet as I'm still working on mine. It's also appreciated that you have given me the proper terminology for your techniques for self studying. And indeed, while all the numbers can only be used once, not all of them are required for the solution. My apologies for the lack of detail in my OP. (editing it right now)
    – Babyburger
    Dec 23, 2013 at 10:44
3

What you're doing is basically a breadth-first search for a solution. This was also my initial idea when I saw the problem, but I would add a few things.

First, the main thing you're doing with your ArrayList is to remove elements from it and test if elements are already present. Since your range is small, I would use a separate HashSet, or BitSet for the second operation.

Second, and more to the point of your question, you could also add the final state to your initial points, and search backward as well. Since all your operations have inverses (addition and subtraction, multiplication and division), you can do this. With the Set idea above, you would effectively halve the number of states you need to visit (this trick is known as meet-in-the-middle).

Other small things would be:

  • Don't divide unless your resulting number is an integer
  • Don't add a number outside the range (so >999) into your set/queue

The total number of states is 999 (the number of integers between 1 and 999 inclusive), so you shouldn't really run into performance issues here. I'm thinking your biggest drain is that you're testing inclusion in an ArrayList which is O(n).

Hope this helps!

EDIT: Just noticed this. You say you check whether a number is already in the list, but then remove it. If you remove it, there's a good chance you're going to add it back again. Use a separate data structure (a Set works perfectly here) to store your visited states, and you should be fine.

EDIT 2: As per other answers and comments (thanks @kutschkem and @meriton), a proper Queue is better for popping elements (constant versus linear for ArrayList). In this case, you have too few states for it to be noticeable, but use either a LinkedList or ArrayDeque when you do a BFS.


Updated answer to solve Countdown

Sorry for my misunderstandings before. To solve countdown, you can do something like this:

Suppose your 6 initial numbers are a1, a2, ..., a6, and your target number is T. You want to check whether there is a way to assign operators o1, o2, ..., o5 such that

a1 o1 a2 ... o5 a6 = T

There are 5 operators, each can take one of 4 values, so there are 4 ^ 5 = 2 ^ 10 possibilities. You can use less than the entire 6, but if you build your solution recursively, you will have checked all of them at the end (more on this later). The 6 initial numbers can also be permuted in 6! = 720 ways, which leads to a total number of solutions of 2 ^ 10 * 6! which is roughly 720,000.

Since this is small, what I would do is loop through every permutation of the initial 6 numbers, and try to assign the operators recursively. For that, define a function

void solve(int result, int index, List<Integer> permutation)

where result is the value of the computation so far, and index is the index in the permutation list. You then loop over every operator and call

solve(result op permutation.get(index), index + 1, permutation)

If at any point you find a solution, check to see if you haven't found it before, and add it if not.

Apologies for being so dense before. I hope this is more to the point.

7
  • Also, ArrayList is not a good choice when you remove a lot, LinkedList might actually be better in such a case.
    – kutschkem
    Dec 22, 2013 at 22:18
  • 1
    @Sebii Thanks a lot! Good ideas here. I feel so stupid that I didn't think of a set to keep track of visited states.. I should indeed use sets instead of arraylist since I do not allow duplicates. I'm having trouble understanding why you think there are only 999 states. Though if I understood you correctly, it might be a good idea to get the states with low amount of remaining numbers out of the way first, to reduce the amount of states. A last thing: I wasn't clear about this in the OP, but I don't want to find the fastest solution, but all solutions. I'll edit this in the OP.
    – Babyburger
    Dec 22, 2013 at 22:36
  • @Babyburger All the solutions changes the solution a bit. One thing is that there are infinitely many solutions. For if a1 'op' a2 ... 'op' an is a solution, then so is a1 'op' a2 ... 'op' an + a1 - a1 (or * a1 / a1). This might explain why it was taking so long. As for why you only have 999 states, I assumed you only want to find one solution, in which case visiting a number twice doesn't help you.
    – sebii
    Dec 22, 2013 at 22:44
  • @Sebii But I only have 6 integers that I initially start with, not 999. I only mentioned that these integers can only take the values 1..10,25,50,75,100 and once chosen, they do not change for the remainder of the game. These are the 6 numbers you work with to find the goal (a number between 100-900, that doesn't change once determined either). So there's definitely a finite amount of answers.
    – Babyburger
    Dec 22, 2013 at 23:05
  • @Babyburger Are you sure? Maybe I'm misunderstanding yet again (sorry), but let's say you chose 1, 2, 3, 4, 5, 6 initially and want to find 200. You can definitely find a solution (5 + 5 + ... + 5), but then why isn't (5 * 40) + 1 - 1 also a solution? And if that is one, (5 * 40) + 1 - 1 + 1 - 1 is also one, and you can go on forever.
    – sebii
    Dec 22, 2013 at 23:15
1

Your problem is analogous to a Coin Change Problem. First do all of the combinations of subtractions so that you can have your 'unit denomination coins' which should be all of the subtractions and additions, as well as the normal numbers you are given. Then use a change making algorithm to get to the number you want. Since we did subtractions beforehand, the result may not be exactly what you want but it should be close and a lot faster than what you are doing.

Say we are given the 6 numbers as the set S = {1, 5, 10, 25, 50, 75, 100}. We then do all the combinations of subtractions and additions and add them to S i.e. {-99, -95, -90,..., 1, 5, 10,..., 101, 105,...}. Now we use a coin change algorithm with the elements of S as the denominations. If we do not get a solution then it is not solvable.

There are many ways to solve the coin change problem, a few are discussed here: AlgorithmBasics-examples.pdf

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.