Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // buspuzzle.h
- #ifndef BUSPUZZLE_H
- #define BUSPUZZLE_H
- #include <string>
- #include <set>
- typedef uint8_t byte;
- std::string busPuzzleSolve(std::string input);
- class BinTree
- {
- private:
- struct BinTreeException {};
- struct BinTreeIncorrectSeed: BinTreeException {};
- struct BinTreeLastTree: BinTreeException {};
- struct BinTreeDivisionError: BinTreeException {};
- enum Operation
- {
- CONCAT, ADD, SUB, MUL, DIV, NUMBER
- } type;
- static const char operationSymbol[];
- byte* digit;
- byte leftSize;
- byte size;
- BinTree *left, *right;
- void buildNext();
- void generateSubTrees();
- std::string filterSolutions(std::set<std::string> solutions);
- public:
- BinTree(const char* seed);
- ~BinTree();
- int compute();
- Operation getType();
- std::string toString(bool parentheses = true);
- std::string solve();
- };
- #endif // BUSPUZZLE_H
- //-------------------------------------------------------------------------------------//
- // buspuzzle.cpp
- #include <cmath>
- #include <cstdlib>
- #include <iostream>
- #include <cstring>
- #include "buspuzzle.h"
- std::string busPuzzleSolve(std::string input)
- {
- return BinTree(input.c_str()).solve();
- }
- const char BinTree::operationSymbol[] = {' ', '+', '-', '*', '/'};
- BinTree::BinTree(const char* seed)
- {
- size = strlen(seed);
- leftSize = 1;
- if (size == 1)
- type = NUMBER;
- else
- type = CONCAT;
- digit = new byte[size];
- for (int i = 0; i < size; i++)
- {
- if (!isdigit(seed[i]))
- throw BinTreeIncorrectSeed();
- digit[i] = seed[i] - '0';
- }
- left = right = NULL;
- if (type != NUMBER)
- {
- generateSubTrees();
- }
- }
- BinTree::~BinTree()
- {
- delete left;
- delete right;
- delete[] digit;
- }
- 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();
- }
- }
- }
- void BinTree::generateSubTrees()
- {
- char *leftSeed = new char[leftSize + 1];
- char *rightSeed = new char[size - leftSize + 1];
- for (int i = 0; i < leftSize; i++)
- {
- leftSeed[i] = digit[i] + '0';
- }
- leftSeed[leftSize] = '\0';
- for (int i = 0; i < size - leftSize; i++)
- {
- rightSeed[i] = digit[i+leftSize] + '0';
- }
- rightSeed[size-leftSize] = '\0';
- left = new BinTree(leftSeed);
- right = new BinTree(rightSeed);
- delete[] leftSeed;
- delete[] rightSeed;
- }
- int BinTree::compute()
- {
- switch (type)
- {
- case CONCAT:
- if ((left->getType() == NUMBER || left->getType() == CONCAT) &&
- left->compute() != 0 && right->getType() == NUMBER)
- return left->compute()*10 + right->compute();
- else
- break;
- case ADD:
- return left->compute() + right->compute();
- case SUB:
- return left->compute() - right->compute();
- case MUL:
- return left->compute() * right->compute();
- case DIV:
- {
- int l = left->compute(), r = right->compute();
- if ((r == 0) || (l%r != 0))
- throw BinTreeDivisionError();
- return l/r;
- }
- case NUMBER:
- return digit[0];
- default:
- ;
- }
- throw BinTreeException();
- }
- BinTree::Operation BinTree::getType()
- {
- return type;
- }
- 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();
- }
- std::string BinTree::solve()
- {
- std::set<std::string> solutions;
- try
- {
- while (true)
- {
- buildNext();
- int result = 0;
- try
- {
- result = compute();
- }
- catch (...)
- {
- //
- }
- if (result == 100)
- solutions.insert(toString(false));
- }
- }
- catch (BinTreeLastTree)
- {
- //
- }
- return filterSolutions(solutions);
- }
- std::string BinTree::filterSolutions(std::set<std::string> solutions)
- {
- std::string filtered = "";
- for (std::set<std::string>::iterator i = solutions.begin(); i != solutions.end(); ++i)
- {
- filtered += *i + "\n";
- }
- return filtered;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement