Problem 93 - Arithmetic Expressions
By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.
For example,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)Note that concatenations of the digits, like 12 + 34, are not allowed.
Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.
Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.
Expression format
On first reading, this problem may seem almost hopelessly complex - there are so many different possible expressions. Although the problem's wording asks us to find target numbers (the results of expressions), it would be a mistake to approach the problem by trying to find an expression for a given target number. The key is to recognize that the number of expressions is low enough to obtain the answer by brute force.
To count how many possible expressions there are, consider the possible variables. An expression has the following form:
a O1 b O2 c O3 d = target
{a, b, c, d} are 4 distinct numbers in the range [1, 9].
{O1, O2, O3} are 3 arithmetic operators (+, −, ×, ÷)
In addition, parentheses may be used anywhere. It turns out the number of different combinations of valid parentheses is given by the Catalan numbers. The nth Catalan number gives the number of different ways n+1 terms can be parenthesized. The sequence of Catalan numbers begins 1, 1, 2, 5, 14, 42, ... With 4 terms, there are C4 = 5 different ways to place parentheses on the above expression. Those ways are:
((a + b) + c) + d
(a + (b + c)) + d
a + ((b + c) + d)
a + (b + (c + d))
(a + b) + (c + d)
With these we can calculate how many total expressions there are to evaluate:
- Sets of 4 numbers (9 choose 4 = 126 sets) ×
- Permutations of a set (4! = 24 permutations) ×
- Arrangements of 3 operators (43 = 64 arrangements) ×
- Arrangements of parentheses (C4 = 5 arrangements)
- = 967,680 total expressions
Implementation
First I'll define the problem specifications:
constexpr int maxNumber = 9; // starting from 1
constexpr int setSize = 4; // {a, b, c, d}
constexpr int numOpCodes = 4;
// 0 = addition
// 1 = subtraction
// 2 = multiplication
// 3 = division
constexpr int numParenthesesCodes = 5;
// 0 = ((ab)c)d
// 1 = (a(bc))d
// 2 = a(b(cd))
// 3 = a(b(cd))
// 4 = (ab)(cd)
constexpr int maxSolution = (maxNumber)*(maxNumber-1)*(maxNumber-2)*(maxNumber-3);
I assign integer codes to represent each arithmetic operator and arrangement of parentheses. maxSolution is the highest possible target number reachable with the problem's specifications (declared constexpr to be used with std::array).
I also define a couple of type aliases to simplify the code:
#include <array>
#include <tuple>
using setArray_t = std::array<float, setSize>
using opArray_t = std::array<int, setSize-1>
A setArray_t variable will hold the values of {a, b, c, d} and an opArray_t variable will hold the values of {O1, O2, O3}. Why is there a float in there? While the problem specifies integer set numbers and integer targets, we'll see later that non-integer numbers can (and must!) be used in the intermediate values calculated in the process of evaluating an expression.
Next, helper functions to evaluate a given expression. First, a function to perform a single operation on two numbers:
inline float calculate(float x, float y, int opCode, bool &valid) {
switch (opCode) {
case 0: return x + y;
case 1: return x - y;
case 2: return x * y;
case 3:
if ((y > 0 ? (y < 0.001f) : (y > -0.001f))) {
// division by 0
valid = false;
return 0.0f;
} else return x / y;
}
valid = false;
return 0.0f;
}
The valid flag will indicate if the result of the calculation can be considered valid. The only complication arises when a division by 0 is inputted. Since this function operates on floating-point numbers, an arbitrarily close approximation to 0 needs to be used instead of direct comparison.
Then, evaluateExpression will calculate the result of a full expression:
Then, evaluateExpression will calculate the result of a full expression:
int evaluateExpression(const setArray_t &numbers, const opArray_t &operations, int pCode, bool &valid) {
valid = true;
float result = 0;
switch (pCode) {
case 0: // ((a + b) + c) + d
result = calculate(numbers[0], numbers[1], operations[0], valid);
result = calculate(result, numbers[2], operations[1], valid);
result = calculate(result, numbers[3], operations[2], valid);
break;
case 1: // (a + (b + c)) + d
result = calculate(numbers[1], numbers[2], operations[1], valid);
result = calculate(numbers[0], result, operations[0], valid);
result = calculate(result, numbers[3], operations[2], valid);
break;
case 2: // a + ((b + c) + d)
result = calculate(numbers[1], numbers[2], operations[1], valid);
result = calculate(result, numbers[3], operations[2], valid);
result = calculate(numbers[0], result, operations[0], valid);
break;
case 3: // a + (b + (c + d))
result = calculate(numbers[2], numbers[3], operations[2], valid);
result = calculate(numbers[1], result, operations[1], valid);
result = calculate(numbers[0], result, operations[0], valid);
break;
case 4: { // (a + b) + (c + d)
result = calculate(numbers[0], numbers[1], operations[0], valid);
float temp = calculate(numbers[2], numbers[3], operations[2], valid);
result = calculate(result, temp, operations[1], valid);
break;
}
default:
valid = false;
break;
}
int iResult = static_cast<int>(result);
if (iResult != result) valid = false;
return iResult;
}
An invalid result from this function is one that does not produce an integer or contains a division by 0.
Generating all expressions
The four variables to iterate through are:
- Sets of 4 numbers
- Permutations of a set
- Arrangements of 3 operators
- Arrangements of parentheses
The sets of numbers are specifically the combinations of 9 numbers taken 4 at a time (9C4 = 126 combinations). To iterate through these 126 sets, I use a binary mask to represent numbers in a set. Indices in the mask correspond to numbers. For example,
\(001101001\) (mask) ➔ \(\{3, 4, 6, 9\}\)
Taking all the permutations of this mask generates all combinations of 4 numbers. The next few permutations are:
...
\(001100110\) ➔ \(\{3, 4, 7, 8\}\)
\(001100101\) ➔ \(\{3, 4, 7, 9\}\)
\(001100011\) ➔ \(\{3, 4, 8, 9\}\)
\(001011100\) ➔ \(\{3, 5, 6, 7\}\)
...
Using std::fill to initialize the mask to 0111100000 (unused 0 index) and std::prev_permutation we can get all sets like so:
#include <array>
#include <algorithm>
std::array<bool, maxNumber+1> mask = {};
std::fill(mask.begin()+1, mask.begin()+1+setSize, true);
do {
setArray_t set;
// read the mask
for (int i = 1, n = 0; i <= maxNumber; i++)
if (mask[i]) set[n++] = static_cast<float>(i);
// all sets
} while (std::prev_permutation(mask.begin()+1, mask.end()));The permutations of each set can also be generated using the similar std::next_permutation:
setArray_t set;
...
do {
// all permutations of a set
} while (std::next_permutation(set.begin(), set.end()));However, arrangements of arithmetic operators can also include repeated operators. Assigning numbers to represent each operator as above, opCode represents the 3 operators in one expression:
opArray_t opCode = {}; // initialize to {0, 0, 0}For example, {0, 3, 1} corresponds to a+b÷c−d and {2, 2, 3} corresponds to a×b×c ÷d. I use a closure to handle all permutations with repetition:
auto nextOpCode = [&]() -> bool {
for (int i = 0; i < setSize-1; i++) {
if (++opCode[i] >= numOpCodes) {
opCode[i] = 0;
if (i == setSize-2) return false;
} else break;
}
return true;
};Finally, since there are only 5 different arrangements of parentheses, a simple for loop handles iteration:
for (int pCode = 0; pCode < numParenthesesCodes; pCode++) {
// all parentheses arrangements
}Putting it all together
Combining the above iteration methods, the final function finds the set of 4 numbers that produce the longest consecutive string of target numbers. The target numbers reachable by a given set are stored in solutions, a boolean array. The indices represent target numbers and a value of true at index i means i is a reachable target number.
#include <string>
#include <array>
#include <algorithm>
std::string longestSolutionSet() {
std::array<bool, maxNumber+1> mask = {};
std::fill(mask.begin()+1, mask.begin()+1+setSize, true);
opArray_t opCode = {};
auto nextOpCode = [&]() -> bool {
for (int i = 0; i < setSize-1; i++) {
if (++opCode[i] >= numOpCodes) {
opCode[i] = 0;
if (i == setSize-2) return false;
} else break;
}
return true;
};
int longestSequence = 0;
setArray_t solutionSet;
do { // All sets of 4 numbers
setArray_t set;
for (int i = 1, n = 0; i <= maxNumber; i++) // read mask
if (mask[i]) set[n++] = static_cast<float>(i);
std::array<bool, maxSolution+1> solutions = {};
// Generate all expressions possible with this set
do { // All permutations of this set
do { // All operator arrangements
for (int pCode = 0; pCode < numParenthesesCodes; pCode++) {
// All parentheses arrangements
bool valid = true;
int result = evaluateExpression(set, opCode, pCode, valid);
if (valid && result > 0 && !solutions[result])
solutions[result] = true;
}
} while (nextOpCode());
} while (std::next_permutation(set.begin(), set.end()));
// Check the number of consecutive target numbers
int sequenceLength = std::find(++solutions.begin(), solutions.end(), false) - solutions.begin() - 1;
if (sequenceLength > longestSequence) {
longestSequence = sequenceLength;
solutionSet = set;
}
} while (std::prev_permutation(mask.begin()+1, mask.end()));
// Convert the solution set into a std::string
std::string result = "";
for (auto i : solutionSet) result += ('0' + static_cast<int>(i));
return result;
}Final Thoughts
On my Github page I added a couple extra functions not shown here that enable my program to print the expressions and target numbers of the problem's solution and also of sets input on the command line. The problem's entire solution found by my program is below.
1258 produces 51 consecutive solutions:
((1 + 2) + 5) / 8 = 1
(1 - (2 + 5)) + 8 = 2
((1 - 2) * 5) + 8 = 3
((1 + 5) * 2) - 8 = 4
((1 * 2) - 5) + 8 = 5
((1 + 2) - 5) + 8 = 6
((1 + 2) * 5) - 8 = 7
((1 - 5) + 8) * 2 = 8
((1 / 2) * 8) + 5 = 9
1 + (5 + (8 / 2)) = 10
((1 * 2) * 8) - 5 = 11
((1 - 2) + 5) + 8 = 12
((1 + 8) * 2) - 5 = 13
((2 - 1) + 5) + 8 = 14
((1 * 2) + 5) + 8 = 15
((1 + 2) + 5) + 8 = 16
((2 * 5) - 1) + 8 = 17
((1 * 2) * 5) + 8 = 18
(1 + (2 * 5)) + 8 = 19
((1 / 2) * 5) * 8 = 20
((1 * 2) * 8) + 5 = 21
(1 + (2 * 8)) + 5 = 22
((1 + 2) * 5) + 8 = 23
(1 - 5) * (2 - 8) = 24
1 - ((2 - 5) * 8) = 25
1 * (2 * (5 + 8)) = 26
1 + (2 * (5 + 8)) = 27
(1 + (5 / 2)) * 8 = 28
((1 + 2) * 8) + 5 = 29
1 * (5 * (8 - 2)) = 30
1 - ((2 - 8) * 5) = 31
((1 - 2) + 5) * 8 = 32
(5 * (8 - 1)) - 2 = 33
2 - ((1 - 5) * 8) = 34
((1 - 2) + 8) * 5 = 35
(1 + 5) * (8 - 2) = 36
2 - ((1 - 8) * 5) = 37
((1 * 5) * 8) - 2 = 38
(1 + 2) * (5 + 8) = 39
((2 - 1) * 5) * 8 = 40
(2 - 1) + (5 * 8) = 41
1 * (2 + (5 * 8)) = 42
1 + (2 + (5 * 8)) = 43
((1 / 2) + 5) * 8 = 44
((2 - 1) + 8) * 5 = 45
((1 + 5) * 8) - 2 = 46
((1 + 8) * 5) + 2 = 47
((2 - 1) + 5) * 8 = 48
(2 + 5) * (8 - 1) = 49
((1 * 2) + 8) * 5 = 50
1 + ((2 + 8) * 5) = 51
In solving this problem, I tried my best to generalize my solution as much as possible. The biggest challenge was finding a general way to handle the arrangements of parentheses. While the other variables to iterate were relatively simple, I found it out of the scope of this problem to implement a general algorithm for different parentheses. Therefore I hardcoded the different arrangements in evaluateExpression with a switch statement.
A truly general solution would most likely require an entirely different way of representing expressions, perhaps using Polish notation (and may be easier with a language other than C++!). For the interested reader I think it would make a fun challenge.