Geekly Articles each Day
📜 ⬆️ ⬇️

Bus ticket

Introductory


Those of us who have to spend half an hour on the journey from Moscow to Moscow have to look for something to occupy and warm up the brain that has not yet fully awakened. Someone reads, someone throws birds, someone solves math puzzles. For example, a classic problem: put the brackets and operators among the six digits of the bus ticket so that the number is 100. It happens that you don’t manage to find a solution, and the specific task doesn’t let go of the rest of the day. Inevitably think about the algorithm.
The decision "in the forehead" by substituting brackets and operators and checking on any mathematical engine did not suit, genetic algorithms, which I am crazy about , did not fit because of the tendency to accumulate in local extremes. As a result, the task has been reduced to the enumeration of all possible binary trees with a given number of leaves (for six of them exactly 42 ).

Getting to the point


Obviously, the complexity of the algorithm is exponential: adding one sheet, we conditionally replace each sheet of the previous tree with a node. Some of the trees are the same, but asymptotically the difference is small.

However, for six digits, the program runs in less than a second, thus having the right to life.
We will implement in C ++. Disclaimer: I'm still learning. If you see a frankly bad or just a non-optimal code, please report it.
Skipping a fairly trivial constructor, consider creating the next tree. Operators are located at the nodes of the trees, saving us from the fuss with brackets and priorities. There are only five operators: concatenation, addition, subtraction, multiplication and division. Unary minus is not used. The trees are sorted according to the following principle: for each right subtree we make a walk through all left subtrees. Repeat for each operator, that is, five times. Inside subtrees exactly the same thing happens.
Tree generation
void BinTree::buildNext() { if (type == NUMBER) //  , throw BinTreeLastTree(); //     . try { left->buildNext(); } catch (BinTreeLastTree) { try { right->buildNext(); } catch (BinTreeLastTree) { bool isLast = false; leftSize++; if (leftSize == size) { leftSize = 1; type = (Operation)(type + 1); if (type == NUMBER) //      , { type = CONCAT; //     isLast = true; //   «». } } delete left; delete right; generateSubTrees(); if (isLast) throw BinTreeLastTree(); //       ,    « ». } } }

It also does not stand up for the calculation, so we will not dwell on it in detail.
The main problem was the same solutions: a silicon friend assured me that (1+ (2 + 3)) and ((1 + 2) +3) are different things. To explain to him the opposite, apply the "smart" arrangement of parentheses, and in order not to waste time filtering the result, we will entrust this to std :: set.
Bracketing code
 std::string BinTree::toString(bool parentheses) { switch (type) { case CONCAT: return left->toString() + right->toString(); case ADD: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)), rightStr = right->toString(!(right->getType() == ADD || right->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case SUB: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + right->toString() + (parentheses?")":""); } case MUL: { std::string leftStr = left->toString(!(left->getType() == MUL || left->getType() == DIV)), rightStr = right->toString(!(right->getType() == MUL || right->getType() == DIV)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case DIV: return (parentheses?"(":"") + left->toString() + operationSymbol[type] + right->toString() + (parentheses?")":""); case NUMBER: { char str[2] = {(char)(digit[0]+'0'), '\0'}; return str; } default: ; } throw BinTreeException(); }

Voila!
Calling code
 int main() { std::string input; std::cin >> input; std::cout << busPuzzleSolve(input); return 0; } std::string busPuzzleSolve(std::string input) { return BinTree(input.c_str()).solve(); }

Result
 123654 ((((1*2)+3)*6)-5)*4 ((1*(2+(3*6)))+5)*4 ((1*(2+3)*6)-5)*4 ((1*(2-3))+6)*5*4 ((1*2)+(3*6)+5)*4 ((1*2)-(3-6))*5*4 ((1*2)-3+6)*5*4 ((1/(2-3))+6)*5*4 ((12*3)-(6+5))*4 ((12*3)-6-5)*4 (1+23+6-5)*4 (1-((2*3)-(6*5)))*4 (1-(2*3)+(6*5))*4 (12+(3*6)-5)*4 1*(((2+3)*6)-5)*4 1*(2+(3*6)+5)*4 1*(2-(3-6))*5*4 1*(2-3+6)*5*4 1+((2+3+6)*(5+4))

Code on SkyDrive in rar archive (+ project file Code :: Blocks) (~ 2.56 KiB).
The code on pastebin.

')

Source: https://habr.com/ru/post/174715/

More articles:


All Articles