Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Solution for match problem
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment