This a quick cheat if some friends challenge you the 24 puzzle: Run in Compiler explorer: https://godbolt.org/z/6aajvcrx5
The C++ code is certainly not optimized, but written cursorily:
#include <memory> // std::unique_ptr
#include <optional> // std::optional
#include <utility> // std::move
#include <vector> // std::vector
#include <variant> // std::variant
#include <cassert> // assert
#include <iostream>
enum class Operator {
Add,
Subtract,
Multiply,
Divide
};
struct Expression;
inline void printIndent(std::ostream& os, int indent) {
for(int i=0; i<indent; ++i) {
os << " ";
}
}
std::ostream& operator<<(std::ostream& os, Operator op) {
switch(op){
case Operator::Add: os << "+"; break;
case Operator::Subtract: os << "-"; break;
case Operator::Multiply: os << "*"; break;
case Operator::Divide: os << "/"; break;
default: assert(false); break;
}
return os;
}
struct BinaryExpression {
std::unique_ptr<Expression> left;
Operator op;
std::unique_ptr<Expression> right;
BinaryExpression(BinaryExpression&&) = default;
BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right);
BinaryExpression clone() const;
std::optional<int> evaluate() const;
friend std::ostream& operator<< (std::ostream& os, const BinaryExpression& v);
};
struct Expression {
std::variant<int, BinaryExpression> expr; // terminal or binary expression
Expression(BinaryExpression binaryExpr) : expr(std::move(binaryExpr)) {}
Expression(int terminal) : expr(terminal) {}
std::unique_ptr<Expression> clone() const {
if( std::holds_alternative<int>(expr) ) {
return std::make_unique<Expression>(std::get<int>(expr));
}
else {
return std::make_unique<Expression>(std::get<BinaryExpression>(expr).clone());
}
}
std::optional<int> evaluate() const {
return std::holds_alternative<int>(expr) ?
std::optional{std::get<int>(expr)} : std::get<BinaryExpression>(expr).evaluate();
}
friend std::ostream& operator<< (std::ostream& os, const Expression& v) {
return std::holds_alternative<int>(v.expr)? (os << std::get<int>(v.expr)) : (os << std::get<BinaryExpression>(v.expr) );
}
};
BinaryExpression::BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right)
: left(std::move(left)), op(op), right(std::move(right)) {
}
BinaryExpression BinaryExpression::clone() const {
return BinaryExpression{ left->clone(), op, right->clone() };
}
std::optional<int> BinaryExpression::evaluate() const {
auto a = left->evaluate();
auto b = right->evaluate();
if( !a || !b ) {
return {}; // error
}
switch(op) {
case Operator::Add: return (*a) + (*b);
case Operator::Subtract: return (*a) - (*b);
case Operator::Multiply: return (*a) * (*b);
case Operator::Divide: {
if( (*b) == 0 ) {
return {}; // divided by 0
}
else if( (*a) % (*b) != 0 ) {
return {}; // has remainder
}
else {
return (*a) / (*b); // good
}
}
default:
assert(false); // should not be here.
return {};
}
}
std::ostream& operator<< (std::ostream& os, const BinaryExpression& v) {
return os << "(" << *v.left << v.op << *v.right << ")";
}
std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target);
// add `ab` to end of `others` and try to shoot target
// if failure, return empty, and restore `others` (for next try later)
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(std::unique_ptr<Expression> ab, std::vector<std::unique_ptr<Expression>>& others, int target) {
others.push_back( std::move(ab) );
if(auto result = get_expression_for_target(others, target)) {
return result;
}
// did not work: revert `others`.
others.pop_back();
return {};
}
// try to construct an expression using members in `expressions` exactly once with operators (+,-,*,/) to evaluate to `target`
// if failure, return empty.
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target) {
if( expressions.size()==0u ) {
return {}; // no way
}
// base case
if( expressions.size()==1u ) {
if( auto value = expressions.front()->evaluate(); value && *value == target ) {
return expressions.front()->clone();
}
else {
return {}; // no result
}
}
// reduce to a size-1 problem by combining 2 arbitrary expressions
for(size_t i=0; i<expressions.size()-1u; ++i) {
for(size_t j=i+1; j<expressions.size(); ++j) {
auto& a = expressions[i];
auto& b = expressions[j];
std::vector<std::unique_ptr<Expression>> others;
for(size_t k=0; k<expressions.size(); ++k) {
if( k!=i && k!=j) {
others.push_back(expressions[k]->clone());
}
}
// a + b
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Add, b->clone())),
others, target)) {
return result;
}
// a - b
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Subtract, b->clone())),
others, target)) {
return result;
}
// b - a
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Subtract, a->clone())),
others, target)) {
return result;
}
// a * b
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Multiply, b->clone())),
others, target)) {
return result;
}
// a / b
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Divide, b->clone())),
others, target)) {
return result;
}
// b / a
if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Divide, a->clone())),
others, target)) {
return result;
}
}
}
return {}; // no result
}
std::vector<std::unique_ptr<Expression>> create_expressions(const std::vector<int>& numbers) {
std::vector<std::unique_ptr<Expression>> expressions;
for(auto number : numbers) {
expressions.push_back(std::make_unique<Expression>(number));
}
return expressions;
}
void test(int target, const std::vector<int>& numbers) {
std::cout << "Trying to get " << target << " from: ";
for(auto number : numbers) {
std::cout << number << " ";
}
if( auto expr = get_expression_for_target(create_expressions(numbers), target) ) {
std::cout << " Success: " << (**expr) << "\n";
}
else {
std::cout << " Failure: No result\n";
}
}
int main() {
test(24, std::vector<int>{1,1,1,1,1});
test(24, std::vector<int>{2,2,2,2,2});
test(24, std::vector<int>{3,3,3,3,3});
test(24, std::vector<int>{4,4,4,4,4});
test(24, std::vector<int>{5,5,5,5,5});
test(24, std::vector<int>{6,6,6,6,6});
test(24, std::vector<int>{7,7,7,7,7});
test(24, std::vector<int>{8,8,8,8,8});
test(24, std::vector<int>{9,9,9,9,9});
return 0;
}
Note that it can handle any length of numbers, not necessorily 4 numbers. The target does not have to be 24 either. Don’t use a lot of numbers; it might be slow as it is doing exhsautive searching.
The testing results above:
Trying to get 24 from: 1 1 1 1 1 Failure: No result
Trying to get 24 from: 2 2 2 2 2 Success: ((2+2)*(2+(2+2)))
Trying to get 24 from: 3 3 3 3 3 Success: ((3+3)+(3*(3+3)))
Trying to get 24 from: 4 4 4 4 4 Success: ((4*(4+4))-(4+4))
Trying to get 24 from: 5 5 5 5 5 Success: (((5*(5*5))-5)/5)
Trying to get 24 from: 6 6 6 6 6 Success: ((6+6)*((6+6)/6))
Trying to get 24 from: 7 7 7 7 7 Failure: No result
Trying to get 24 from: 8 8 8 8 8 Success: ((8+8)-(8-(8+8)))
Trying to get 24 from: 9 9 9 9 9 Failure: No result
Binglong's space 