Permutations
Algorithms
Logic
Given a list of 5 integers and the operators +, -, * and /, what equations will give the minimum and maximum answers?
There is no operator precedence, the equations are simply evaluated from left to right, and each operator can be used only once.
The input is an array of 5 integers, and the output should be a pair of strings showing the order of the operators.
For example, with the input \[1, 2, 3, 4, 5\], the answer should be ["+/-\*","-/_\*"], giving the minimum of (((1 + 2) / 3) - 4) \* 5 = -15, and the maximum of (((1 - 2) / 3) + 4) * 5 = 18.3333.
#include <map>
#include <array>
#include <string>
using namespace std;
double add(double a, double b) { return a + b; }
double sub(double a, double b) { return a - b; }
double mul(double a, double b) { return a * b; }
double div(double a, double b) { return a / b; }
typedef double (*opFunc)(double a, double b);
double calculate(array<int, 5> const numbers, string ops) {
map<char const, opFunc> const opFuncs = {
{'+', add}, {'-', sub}, {'*', mul}, {'/', div},
};
double result = numbers[0];
for (int i = 0; i < 4; i++) {
opFunc op = opFuncs.at(ops[i]);
result = op(result, numbers[i + 1]);
}
return result;
}
pair<string, string> MinMaxEquations(array<int, 5> const& numbers) {
map<string, double> results;
string ops = "+-*/";
sort(ops.begin(), ops.end());
do {
results[ops] = calculate(numbers, ops);
} while (next_permutation(ops.begin(), ops.end()));
auto [min, max] = minmax_element(results.begin(), results.end(),
[](const pair<string, double>& p1, const pair<string, double>& p2) {
return p1.second < p2.second; });
return make_pair(min->first, max->first);
}using namespace std;
Describe(Basic_tests)
{
It(should_return_correct_equations)
{
array<int, 5> numbers1{1,2,3,4,5};
pair<string, string> exp1{"+/-*","-/+*"};
pair<string, string> ans1 = MinMaxEquations(numbers1);
Assert::That(ans1, Fulfills(EqualsStringPair(exp1)));
array<int, 5> numbers2{12,2,19,5,4};
pair<string, string> exp2{"/-*+","/+*-"};
pair<string, string> ans2 = MinMaxEquations(numbers2);
Assert::That(ans2, Fulfills(EqualsStringPair(exp2)));
}
};