Solution for match problem

mathproblem.cpp

#include <sstream>
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <vector>
#include <queue>
#include <set>
#include <strings.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <limits>
#include <initializer_list>
#include <functional>

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<typename T> void remove(vector<T>& 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<operations> ops;
	vector<int> 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<float> 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<int> (*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<solution_t, solution_t, bool> {
	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<int> input;
public:
	finder(const initializer_list<int> && list): input(list) {
	}
	solution_t find(int target) {
			CostComparer c;
			c.target = target;
			//priority_queue<solution_t,vector<solution_t>,CostComparer > q(c);
			queue<solution_t> q;
			solution_t initial;
			forr(i,input.size()-1) initial.ops.push_back(op_plus);
			initial.input = input;
			q.push(initial);
			set<long> 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:"<<s<<"="<<r<<" (tested "<<tests<<")"<<endl;
					return s;
				}
				visited.insert(s.get_hash());
				auto tryop = [&](operations op,int n) {
					operations old = s.ops[n];
					s.ops[n] = op;
					long h = s.get_hash();
					if (visited.count(h)==0) q.push(s);
					s.ops[n] = old;
				};
				forr(i,s.input.size())
				forr(j,s.input.size()) {
					if (i==j) continue;
					swap(s.input[i], s.input[j]);
					forr(n,s.ops.size()) {
						tryop(op_minus,n);
						tryop(op_mul,n);
						tryop(op_div,n);
					}
					swap(s.input[i], s.input[j]);
				}
			}
			cout<<"Tested "<<tests<<" solutions without result."<<endl;
			return solution_t();
		}

	};

int main(int argc, const char** argv) {
	//finder f(24,{1,3,4,6});
	//finder f( { 1, 2, 3, 4, 5 });
	finder f = { 1, 2, 3, 4, 5 };
	//f.find(0);
	forr(i,40) f.find(i);
	return 0;
}