24 Puzzle

[zwA4jE8b]

lol, creative solution ascii

[ultifinitus]

I think these two solutions work =]

(cheating)

toint(tostring(6-4)+tostring(3+1))

or

((6+4)*3)*1 = 30 (30 is oct for 24 =] )

[ne555]

^ You can also try with base 7,9,16

6*9 = 42 in base 13

[tition]

It took me forever to solve this one...

So, waiting for the first to post of a program-to-enumerate-all-possibilities... (I will give it a try as soon as I have nothing better (I never had anything better to do) more urgent to do).

[helios]

It's so annoying to automate. I found the answer by only trying out (((a $ b) $ c) $ d), ((a $ b) $ (c $ d)), and (a $ (b $ (c $ d))) (I missed two expression trees), but even just that was an ugly mess. For example:

double eval_left(int operands[4],OP operators[3]){
	return apply(apply(apply(operands[0],operators[0],operands[1]),operators[1],operands[2]),operators[2],operands[3]);
}

std::string print_left(int operands[4],OP operators[3]){
	std::stringstream accum;
	accum <<"(("<<operands[0]<<to_char(operators[0])<<operands[1]<<")"<<to_char(operators[1])<<operands[2]<<")"<<to_char(operators[2])<<operands[3];
	return accum.str();
}

How would you automate producing all expression trees for n operators?

[hamsterman]

Here: http://codepad.org/PLXBj8zN
Running this results in spoilers.
Excuse my Haskell.

[m4ster r0shi]

Here's another one -> http://codepad.org/E4xXp3zf

It's neither as fast nor as short as hamsterman's.
It's just the first thing that came to my mind.

At first, I generate a list of lists that looks like this:

[
  [ (number_1, operation_1, priority_1), 
    (number_2, operation_2, priority_2), 
    ...,
    (number_n,         '#',          0) ],

  [ (number_1', operation_1', priority_1'), 
    (number_2', operation_2', priority_2'), 
    ...,
    (number_n',          '#',           0) ],

  ...
]

(In this particular problem, n == 4)

And then, I evaluate each sublist like this:

[ (5.0, '+', 1), (1.0, '-', 3), (3.0, '*', 2), (4.0, '/', 4), (2.0, '#', 0) ] -->

[ (5.0, '+', 1), (1.0, '-', 3), (3.0, '*', 2), (2.0, '#', 0) ] -->

[ (5.0, '+', 1), (-2.0, '*', 2), (2.0, '#', 0) ] -->

[ (5.0, '+', 1), (-4.0, '#', 0) ] -->

[ (1.0, '#', 0) ]

Now, I'm sure (No, I'm not. Really.) that if I read carefully hamsterman's code, I'll be
able to figure out what's going on, eventually, but I'd appreciate some explanation.

Also, this is a very interesting thread. I'd like to see more threads like this one in the future.

EDIT:

@hamsterman:

Regarding gen 1, I'm not sure, but I think you could do...

import List (delete)

gen 1 ls = [ (x, delete x ls, show x) | x <- ls ]

[hamsterman]

My idea was that since every arithmetic expression is a binary tree, it can be built from an operator and two smaller trees. If I'm generating a tree of N nodes, I need to consider all pairs of trees, such that the number of their leaves adds up to N. Also, each tree is paired up with a list of numbers that are still available.

Regarding gen 1, I'm not sure, but I think you could do...

You're right, I could. To be honest I didn't know about delete. I'm not too familiar with Haskell's standard libraries.

[zwA4jE8b]

one could also represent this as Geometric series An=6(3/4)^n !!

[m4ster r0shi]

The second thing that came to my mind was this thing called symbolic regression. Its
purpose is to find an analytical expression for a given function, using a specific set of
symbols, and it's (usually)  implemented  using  genetic  algorithms.  In this particular
problem, the  function  is  f(x) = 24  and  the  set  of  symbols  is {+, -, *, /, 1, 3, 4, 6}

A solution is represented by a fixed length sequence of symbols
in polish notation.  Example -> * 4 / 6 3 - 1 6 4 1 3 1 1 3 4

Each solution  (of  length  n + n + 1)  consists of two parts, one  (of  length  n)  that can
contain both operations and numbers and one  (of  length  n + 1)  that can only contain
numbers.  This is important,  because it ensures the validity  of  the  solutions  obtained
through  genetic  operations.  For example,  * 4 / 6 3 - 1 6 4 1 3 1 1 3 4  evaluates
to 4 * ( 6 / 3 ) = 8. The part past * 4 / 6 3 does not contribute to the evaluation of the
expression. However, if a mutation were to change that last 3 into a +,  we would have
* 4 / 6 + - 1 6 4 1 3 1 1 3 4,  which  evaluates  to  4 * { 6 / [ ( 1 - 6 ) + 4 ] } = - 24.

Anyway, I wrote something quick and dirty in C++ and after some tweaking (e.g. fitness bonus
if the only operations used are - and /, and if the effective size is 7) I managed to get a couple
of solutions in the form of ->  / 6 - 1 / 3 4 ? ? ? ? ? ?  ... among others ... once or twice ...

[Gaminic]

Can you use powers? I'm guessing not, because that would make it very easy..

[ascii]

and only addition, subtraction, multiplication and/or division

That's a no.

[tfityo]

I wrote the code below. It is quite messy and also I included possibility to "glue" numbers. So my code also generates the following solution (14-6)*3, which was rejected by CodeMonkey. Also, since I included unary minuses I can pay no attention to operation priority, I just rely on all possible permutations of digits (and idea with trees is better).

#include<iostream>
#include<algorithm>

using namespace std;

enum oper {Add, Sub, Mul, Div};

const int Num = 4; //how many digits are in initial set
int digits[Num] = {1, 3, 4, 6};
int nums[Num];
int snums[Num];
oper ops[Num-1];

const double target = 24;
const double eps = 0.01;

double evaluate(int counter){
	double res = (double)snums[0];

	for (int i = 1; i < counter; i++){
		switch (ops[i - 1]){
			case Add: res += snums[i];
				 break;
			case Sub: res -= snums[i];
				 break;
			case Mul: res *= snums[i];
				 break;
			case Div: res /= snums[i];
		}
	}
	return res;
}

void printNumber(int num){
    if (num < 0)
        cout << "(" << num << ")";
	else
		cout << num;
}

void print(int counter, bool inverse = false){
	if (counter == 0) return;
	if (counter > 1) cout << "(";
	print(counter - 1);
	if (counter > 1)
	switch (ops[counter - 2]){
		case Add: cout <<'+';
				 break;
		case Sub: cout <<'-';
				 break;
		case Mul: cout <<'*';
				 break;
		case Div: cout <<'/';
    }
    printNumber(snums[counter - 1]);
    if (counter > 1) cout << ")";
}

void printInverse(int counter){
    printNumber(snums[counter - 1]);
    cout << "/";
    print(counter - 1);
}

int main(int argc, char* argv[])
{
	do{//all permutations of digits
		for (int i = 0; i < (1<<(Num-1)); i++){//glue digits into numbers:8 variants
			int counter = 0;
			nums[0] = digits[0];
			for (int pow = 0; pow < Num-1; pow++)
				if ((i >> pow)&1)
					nums[counter] = nums[counter]*10 + digits[pow+1];
				else
					nums[++counter] = digits[pow+1];

			counter++;

			for (int j = 0; j < (1 << counter); j++){//assign unary signs
			    for (int pow = 0; pow < counter; pow++)
					if ((j >> pow) & 1)
						snums[pow] = -nums[pow];
					else
						snums[pow] = nums[pow];

				for (int k = 0; k < (1 << (2*counter - 2)); k++){//assign operations
					for (int pow = 0; pow < counter - 1; pow++){
						int op = (k >> (2*pow)) & 3;
						switch (op){
							case 0: ops[pow] = Add; break;
							case 1: ops[pow] = Sub; break;
							case 2: ops[pow] = Mul; break;
							case 3: ops[pow] = Div;
						}
					}

					double d = evaluate(counter);
					if (d > target - eps && d < target + eps){
						print(counter);
						cout << " = " << evaluate(counter) << endl;
					}
                                        else if (ops[counter - 2] == Div && 1/d > target - eps && 1/d < target + eps){
                                                printInverse(counter);
                                                cout << " = " << 1/evaluate(counter) <<endl;
                                        }
				}
			}
		}
	} while ( next_permutation (digits, digits+4) );
	return 0;
}