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

This is a discussion on Solution to Google Puzzle 3,3,8,8=24 within the A Brief History of Cprogramming.com forums, part of the Community Boards category; At first I was mildly entertained with my initial attempts to solve Google's current puzzle, but after dozens of attempts ...

  1. #1
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856

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

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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

  3. #3
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    If you round down, (3+((8*8)/3)) would work, but I don't know if that's allowed. Is that ok ?
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  4. #4
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    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.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Is unary minus allowed?
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User Aran's Avatar
    Join Date
    Aug 2001
    Posts
    1,301
    That's a really annoying problem. The closest I can get is 23.

  7. #7
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Ok. Can't think of anything now, but I'll keep it in my head.
    Do you have the answer ?
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    got it!

    8 / (3 - (8/3))

  9. #9
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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))

  10. #10
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    Quote Originally Posted by Perspective
    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.
    Sent from my iPadŽ

  11. #11
    User
    Join Date
    Jan 2006
    Location
    Canada
    Posts
    498
    here's the trick, start with what you want, namely 8 * 3 and try to substitute in the numbers you need.
    College student

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. The puzzle again...Swapping elements of 2D array
    By crazygopedder in forum C Programming
    Replies: 44
    Last Post: 11-05-2008, 12:53 PM
  2. Solution - Israel and Palestine?
    By Vber in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 03-19-2003, 07:27 AM
  3. Speed Challenge, my solution:
    By RoD in forum C++ Programming
    Replies: 11
    Last Post: 03-17-2003, 08:12 PM
  4. Homemade hair bleaching solution
    By deltabird in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 02-10-2003, 09:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21