so as fun i decided to write a simple program that can solve the 8 Out of 10 Cats Does Countdown number puzzle, link is form Countdown, but same rules. so my program simply goes through a all possible combinations of AxBxCxDxExF, where letters are numbers and "x" are +, -, / and *. here is the code for it:
private void combineRecursive( int step, int[] numbers, int[] operations, int combination[]){
if( step%2==0){//even steps are numbers
for( int i=0; i<numbers.length; i++){
combination[ step] = numbers[ i];
if(step==10){//last step, all 6 numbers and 5 operations are placed
int index = Solution.isSolutionCorrect( combination, targetSolution);
if( index>=0){
solutionQueue.addLast( new Solution( combination, index));
}
return;
}
combineRecursive( step+1, removeIndex( i, numbers), operations, combination);
}
}else{//odd steps are operations
for( int i=0; i<operations.length; i++){
combination[ step] = operations[ i];
combineRecursive( step+1, numbers, operations, combination);
}
}
}
and here is what i use to test if the combination is what i want to not.
public static int isSolutionCorrect( int[] combination, int targetSolution){
double result = combination[0];
//just a test
if( Arrays.equals( combination, new int[]{100,'*',7,'-',8,'*',3,'+',7,'+',50})){
System.out.println( "found");
}
for( int i=1; i<combination.length; i++){
if(i%2!=0){
switch( (char)combination[i]){
case '+': result+= combination[++i];break;
case '-': result-= combination[++i];break;
case '*': result*= combination[++i];break;
case '/': result/= combination[++i];break;
}
}
if( targetSolution==result){
return i;
}
}
return targetSolution==result?0:-1;
}
so in last episode i found a problem with my code. this was the solution to one of the puzzles.
(10*7)-(8*(3+7))
i noticed that i do find this combination "10*7-8*3+7" (twice), but because i check for solutions by doing the operation left to right i actually don't find all answers. i only check for solutions like this ((((10*7)-8)*3)+7). so even though i found the combination i don't have the right order.
so now the question is how do i test all possible math orders, like (10*7)-(8*(3+7)), (10*7)-((8*3)+7) or 10*(7-8)*(3+7)? i though i can use a balance tree with operations as balancing nodes. but still i have not idea how to go through all possible combinations without moving around the formula.
(10*7)-(8*(3+7))
-
/ \
* *
/ \ / \
700 7 8 +
/ \
7 3
(10*7)-((8*3)+7)
-
/ \
* +
/ \ / \
700 7 * 7
/ \
8 3
10*(7-8)*(3+7)
*
/ \
*
/ \ 10
- +
/ \ / \
7 8 3 7
how do i do this in code? not looking for solved code more of how i should change perspective to fix it. i don't know why i am stumped at it.
about me: 4th year computer science, not new or noob at programming (i like to believe at least ;))
This is easier solved with a dedicated class that represents an expression, and not with an array. Then you can simply enumerate all possible trees. A mix of another answer that I wrote for a similar task, and an answer that shows how to generate all binary trees gave this:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NumberPuzzleWithCats
{
public static void main(String[] args)
{
List<Integer> numbers = Arrays.asList(10,7,8,3,7);
solve(numbers);
}
private static void solve(List<Integer> numbers)
{
List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<numbers.size(); i++)
{
Integer number = numbers.get(i);
nodes.add(new Node(number));
}
System.out.println(nodes);
List<Node> all = create(nodes);
System.out.println("Found "+all.size()+" combinations");
for (Node node : all)
{
String s = node.toString();
System.out.print(s);
if (s.equals("((10*7)-(8*(3+7)))"))
{
System.out.println(" <--- There is is :)");
}
else
{
System.out.println();
}
}
}
private static List<Node> create(Node n0, Node n1)
{
List<Node> nodes = new ArrayList<Node>();
nodes.add(new Node(n0, '+', n1));
nodes.add(new Node(n0, '*', n1));
nodes.add(new Node(n0, '-', n1));
nodes.add(new Node(n0, '/', n1));
nodes.add(new Node(n1, '+', n0));
nodes.add(new Node(n1, '*', n0));
nodes.add(new Node(n1, '-', n0));
nodes.add(new Node(n1, '/', n0));
return nodes;
}
private static List<Node> create(List<Node> nodes)
{
if (nodes.size() == 1)
{
return nodes;
}
if (nodes.size() == 2)
{
Node n0 = nodes.get(0);
Node n1 = nodes.get(1);
return create(n0, n1);
}
List<Node> nextNodes = new ArrayList<Node>();
for (int i=1; i<nodes.size()-1; i++)
{
List<Node> s0 = create(nodes.subList(0, i));
List<Node> s1 = create(nodes.subList(i, nodes.size()));
for (Node n0 : s0)
{
for (Node n1 : s1)
{
nextNodes.addAll(create(n0, n1));
}
}
}
return nextNodes;
}
static class Node
{
int value;
Node left;
Character op;
Node right;
Node(Node left, Character op, Node right)
{
this.left = left;
this.op = op;
this.right = right;
}
Node(Integer value)
{
this.value = value;
}
@Override
public String toString()
{
if (op == null)
{
return String.valueOf(value);
}
return "("+left.toString()+op+right.toString()+")";
}
}
}
It will print all combinations that are created, including the one that you have been looking for:
[10, 7, 8, 3, 7]
Found 16384 combinations
(10+(7+(8+(3+7))))
(10*(7+(8+(3+7))))
...
((10*7)+(8*(3+7)))
((10*7)*(8*(3+7)))
((10*7)-(8*(3+7))) <--- There is is :)
((10*7)/(8*(3+7)))
((8*(3+7))+(10*7))
...
((7/3)-((8/7)/10))
((7/3)/((8/7)/10))
Of course, checking whether the right solution is found by comparing the String representations is ... "very pragmatic", to state it that way, but I think the actual approach of the generation is what was important here.
(I hope this really is what you have been looking for - I could not view the site that you linked to...)