/*
 * Copyright (c) 2011 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * http://qbonnard.github.com/2011/10/25/The_answer_is_2011_the_question_can_be_brute_force.html
 * http://www.reddit.com/r/programming/comments/lr1eo/the_answer_is_2011_is_the_question_really_a_brute/
 *
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <queue>
#include <stack>
#include <map>

using namespace std;

struct Expr {
	Expr(const string &s) : s(s), l(s.length()), n(0) {
		for (int i = 0; i < l; ++i)
			if (s[i] >= '1' && s[i] <= '9')
				n++;
	}
	bool operator<(const Expr &other) const {
		if (n != other.n)
//			return n > other.n;
			return n < other.n;
		if (l != other.l)
//			return l > other.l;
			return l < other.l;
		return s > other.s;
	}
	string s;
	unsigned char l, n;
};

static priority_queue<Expr> q;
static map<int, string> m;

static bool
isInt(double d)
{
	return (d - floor(d)) < 0.0000001;
}

static void
eval(const string &t)
{
	stack<double> s;
	int n = 1;
	double a, b;
	for (unsigned i = 0; i < t.length(); ++i) {
		switch (t[i]) {
		case '+':
		case '-':
		case '*':
		case '/':
		case '^':
			if (s.size() < 2)
				return;
			b = s.top();
			s.pop();
			a = s.top();
			s.pop();
			switch (t[i]) {
			case '+':
				s.push(a + b);
				break;
			case '-':
				s.push(a - b);
				break;
			case '*':
				s.push(a * b);
				break;
			case '/':
				if (isInt(a / b)) // XXX
					s.push(a / b);
				break;
			case '^':
				if (isInt(pow(a, b))) // XXX
					s.push(pow(a, b));
				break;
			}
			break;
		case '!':
		case 'r':
			if (s.size() < 1)
				return;
			a = s.top();
			s.pop();
			if (t[i] == '!')
				s.push(tgamma(a + 1.0));
			else
				s.push(sqrt(a));
			break;
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			s.push(n++);
			break;
		}
	}
	if (s.size() > 0)
		a = s.top();
	if (s.size() == 1) {
		if ((a - floor(a)) < 0.0000001) {
			int i = (int)a;
			if (i > 0 && i <= 10000) {
				if (m.find(i) == m.end()) {
					printf("found %d = %s\n", i, t.c_str());
					m.insert(make_pair(i, t));
				} else
					m[i] = t;
			}
/*
			if (i == 2011) {
				printf("found %d = %s\n", i, t.c_str());
				exit(0);
			}
*/
		}
	}
	if (q.size() > 30000000)
		return;
	if (s.size() >= 2) {
		q.push(t + "+");
		q.push(t + "-");
		q.push(t + "*");
		if (fabs(a) > 0.0000001)
			q.push(t + "/");
		q.push(t + "^");
	}
	if (s.size() >= 1) {
		if (a >= 0.0 && isInt(a) && isInt(tgamma(a + 1.0)) &&
		    fabs(a - tgamma(a + 1.0)) > 0.0000001)
			q.push(t + "!");
		if (a >= 0.0 && isInt(a) && isInt(sqrt(a)) &&
		    fabs(a - sqrt(a)) > 0.0000001)
			q.push(t + "r");
	}
	if (n <= 8) {
		char c[2] = { '0' + n, 0 };
		q.push(t + c);
	}
}

int main()
{
	unsigned long u = 0;
	q.push(string(""));
	while (!q.empty()) {
		string s = q.top().s;
		u++;
		if (u % 100000 == 0)
			printf("pass %lu: q.size %d, s %s (%d), m %d\n",
			    u, q.size(), s.c_str(), (int)s.length(),
			    (int)m.size());
		q.pop();
		eval(s);
	}
	printf("m.size %d\n", (int)m.size());
	for (map<int, string>::iterator i = m.begin(); i != m.end(); ++i)
		printf("%d = %s\n", i->first, i->second.c_str());
	return 0;
}