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.
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.