Instantly share code, notes, and snippets.

olostan/mathproblem.cpp Created Mar 25, 2011

What would you like to do?
Solution for match problem
 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define forr(i,n) for(size_t i = 0; i < n; i++) #define forrange(i,s,n) for(int i = s; i < n; i++) #define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it) enum operations { op_plus, op_minus, op_mul, op_div }; char op(operations o) { switch (o) { case op_plus: return '+'; case op_minus: return '-'; case op_mul: return '*'; case op_div: return '/'; default: throw new runtime_error("Unknown operation"); } } template void remove(vector& v, size_t pos) { size_t i = 0; For(itr, v) { if (i++ == pos) { v.erase(itr); return; } } throw new runtime_error("index!"); } struct solution_t { vector ops; vector input; solution_t(const solution_t& s) : ops(s.ops), input(s.input) { calc_cashed = false; } solution_t() { calc_cashed = false; } friend ostream& operator<<(ostream &out, const solution_t &obj); mutable float calc_cash; mutable bool calc_cashed; float calc() const { if (calc_cashed) return calc_cash; // multiply/divide vector inp; For(itr, input) inp.push_back((float) (*itr)); decltype(ops) s = ops; for (;;) { int op_i = -1; forr(i,s.size()) { operations o = s[i]; if (o == op_mul || o == op_div) { op_i = i; break; } } if (op_i == -1) break; float tmp = inp[op_i]; if (s[op_i] == op_mul) tmp *= inp[op_i + 1]; else tmp /= inp[op_i + 1]; inp[op_i] = tmp; remove(inp, op_i + 1); remove(s, op_i); } float r = inp[0]; forr(i, s.size()) { if (s[i] == op_plus) r += inp[i + 1]; else r -= inp[i + 1]; } calc_cash = r; calc_cashed = true; return r; } long get_hash() const { long r = 0; For(i,ops) { r += static_cast (*i); r = r << 2; } For(i,input) { r += (*i); r = r << 5; } return r; } }; ostream& operator<<(ostream &out, const solution_t &s) { forr(i,s.input.size()) { out << s.input[i]; if (i < s.input.size() - 1) out << op(s.ops[i]); } return out; } struct CostComparer: public binary_function { int target; bool operator()(const solution_t& l, const solution_t& r) const { return (abs(l.calc() - target) >= abs(r.calc() - target)); } }; class finder { private: vector input; public: finder(const initializer_list && list): input(list) { } solution_t find(int target) { CostComparer c; c.target = target; //priority_queue,CostComparer > q(c); queue q; solution_t initial; forr(i,input.size()-1) initial.ops.push_back(op_plus); initial.input = input; q.push(initial); set visited; long tests =0; while (!q.empty()) { tests++; //auto s = q.top(); auto s = q.front(); q.pop(); if (visited.count(s.get_hash())>0) continue; auto r = s.calc(); if (r == target) { cout<<"result:"<