PDA

View Full Version : Solution to Google Puzzle 3,3,8,8=24



LuckY
05-31-2006, 11:51 AM
At first I was mildly entertained with my initial attempts to solve Google's current puzzle, but after dozens of attempts I became feverishly determined to solve it. I finally decided to screw my manual attempts at a solution and coded a stupid brute force solver for it. The code is below and I just thought I'd provide it in the off chance that anyone else is interested, but don't run it if you want to solve the puzzle yourself or don't give a crap.

If you don't know what I'm talking about, my personalized google.com/ig page "Wei-Hwa's Puzzle Challenges" (which showed up automatically after the Da Vinci Code puzzles ended) currently has this:

Using the numbers 3, 3, 8, 8 (in any order), make a mathematical expression that equals 24. You can use only addition, subtraction, multiplication, and division (and parentheses), but in any order you wish. Note that you have to use all four numbers; otherwise 3 times 8 would be valid -- and that wouldn't be much of a puzzle, would it?

When you think you have an answer, try entering it here (use * for multiplication and / for division)

Here's the code:


#include <iostream>
using namespace std;

enum Action { LEAF, ADD, SUB, DIV, MUL };

struct ExprNode {
ExprNode *left;
ExprNode *right;
Action action;
int value;

ExprNode(int value)
: left(0), right(0), action(LEAF)
{
this->value = value;
}

ExprNode(ExprNode *left, ExprNode *right, Action action)
: value(0)
{
this->left = left;
this->right = right;
this->action = action;
}

double eval() {
switch (action) {
case LEAF: return value;
case ADD: return left->eval() + right->eval();
case SUB: return left->eval() - right->eval();
case DIV: return left->eval() / right->eval();
case MUL: return left->eval() * right->eval();
}
return 0;
}

friend ostream& operator<<(ostream &out, const ExprNode &rhs) {
switch (rhs.action) {
case LEAF: return out << rhs.value;
case ADD: return out << "(" << *rhs.left << " + " << *rhs.right << ")";
case SUB: return out << "(" << *rhs.left << " - " << *rhs.right << ")";
case DIV: return out << "(" << *rhs.left << " / " << *rhs.right << ")";
case MUL: return out << "(" << *rhs.left << " * " << *rhs.right << ")";
}
return out;
}
};

int main() {
Action actions[4] = { ADD, SUB, DIV, MUL };
int values[4] = { 3, 3, 8, 8 };

for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
for (int k = 0; k < 4; ++k)
for (int l = 0; l < 4; ++l) {
// bypass duplicates
if (i == j || i == k || i == l ||
j == k || j == l || k == l)
continue;

ExprNode one (values[i]);
ExprNode two (values[j]);
ExprNode three(values[k]);
ExprNode four (values[l]);

for (int x = 0; x < 4; ++x) {
for (int y = 0; y < 4; ++y) {
for (int z = 0; z < 4; ++z) {
for (int type = 0; type < 5; ++type) {
switch (type) {
// ((a ? b) ? c) ? d
case 0: {
ExprNode AB(&one, &two, actions[x]);
ExprNode ABC(&AB, &three, actions[y]);
ExprNode ABCD(&ABC, &four, actions[z]);
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}

// (a ? b) ? (c ? d)
case 1: {
ExprNode AB(&one, &two, actions[x]);
ExprNode CD(&three, &four, actions[z]);
ExprNode ABCD(&AB, &CD, actions[y]);
if (actions[y] == DIV && CD.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}

// (a ? (b ? c)) ? d
case 2: {
ExprNode BC(&two, &three, actions[y]);
ExprNode ABC(&one, &BC, actions[x]);
ExprNode ABCD(&ABC, &four, actions[z]);
if (actions[x] == DIV && BC.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}

// a ? ((b ? c) ? d)
case 3: {
ExprNode BC(&two, &three, actions[y]);
ExprNode BCD(&BC, &four, actions[z]);
ExprNode ABCD(&one, &BCD, actions[x]);
if (actions[x] == DIV && BCD.eval() == 0)
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}

// a ? (b ? (c ? d))
case 4: {
ExprNode CD(&three, &four, actions[z]);
ExprNode BCD(&two, &CD, actions[y]);
ExprNode ABCD(&one, &BCD, actions[x]);
if ((actions[y] == DIV && CD.eval() == 0) ||
(actions[x] == DIV && BCD.eval() == 0))
break;
if (int(ABCD.eval()) == 24)
cout << ABCD << " = " << ABCD.eval() << endl;
break;
}
}
}
}
}
}
}

return 0;
}

Perspective
05-31-2006, 12:15 PM
ohhh, i had to do one of these for my descrete math course. We had to use the digits from 1 to 10 in order and the answer had to be 100 IIRC.

Fun stuff

Happy_Reaper
05-31-2006, 01:16 PM
If you round down, (3+((8*8)/3)) would work, but I don't know if that's allowed. Is that ok ?

LuckY
05-31-2006, 02:49 PM
Sorry Hairy, but your answer isn't valid. I actually browsed Google's validation code (JavaScript) and it basically does this to check your submission: if ((24 - your_answer) < 0.0001) you_win(); It's not that rounding is explicitly disallowed, but you can see that it must be extremely near 24.0

But don't be discouraged. Keep right on trying.

Magos
05-31-2006, 03:10 PM
Is unary minus allowed?

Aran
05-31-2006, 03:59 PM
That's a really annoying problem. The closest I can get is 23.

Happy_Reaper
05-31-2006, 07:44 PM
Ok. Can't think of anything now, but I'll keep it in my head.
Do you have the answer ?

Perspective
05-31-2006, 09:09 PM
got it!

8 / (3 - (8/3))

Perspective
05-31-2006, 09:12 PM
here's the trick, start with what you want, namely 8 * 3 and try to substitute in the numbers you need.

24 =
8 * 3 =
8 / (1/3) =
8 / (3 - (8/3))

SlyMaelstrom
05-31-2006, 09:39 PM
here's the trick, start with what you want, namely 8 * 3 and try to substitute in the numbers you need.

24 =
8 * 3 =
8 / (1/3) =
8 / (3 - (8/3))

Nice job, Perspective. I had known it and didn't want to say anything, but only because I've seen this exact question before. If I recall it was freshman year of highschool. I think extra credit on some test.

joeprogrammer
06-01-2006, 09:12 AM
here's the trick, start with what you want, namely 8 * 3 and try to substitute in the numbers you need.

College student :rolleyes: