Thread: Solution to Google Puzzle 3,3,8,8=24

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:

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;
}