ComparerInator.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back
#define	SZ(a)	int((a).size())

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define	forn(i, n)	for(int i = 0; i < n; i++)
#define	forab(i, a, b)	for(int i = a; i <= b; i++)
#define	rep(i, a, b)	for(int i = a; i>=b; i--)

int Equal(int a, int b) {
	return a;
}
int Max(int a, int b) {
	return a > b ? a : b;
}
int Min(int a, int b) {
	return a < b ? a : b;
}


class ComparerInator
{
public:
	bool Process(vi a, vi b, vi c, int (*f) (int, int)) {
		forn(i, a.size()) 
			if( f(a[i],b[i]) != c[i] )
				return false;
		return true;
	}

	int makeProgram(vector <int> a, vector <int> b, vector <int> c)
	{
		if(Process(a, b, c, Equal) || Process(b, a, c, Equal))
			return 1;
		if(Process(a, b, c, Max) || Process(a, b, c, Min))
			return 7;

		return -1;
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, vector <int> p2, bool hasAnswer, int p3) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p2.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p2[i];
	}
	cout << "}";
	cout << "]" << endl;
	ComparerInator *obj;
	int answer;
	obj = new ComparerInator();
	clock_t startTime = clock();
	answer = obj->makeProgram(p0, p1, p2);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p3 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p3;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	vector <int> p1;
	vector <int> p2;
	int p3;
	
	{
	// ----- test 0 -----
	int t0[] = {1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 1;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {1,3};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,1};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2,3};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 7;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {1,3,5};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,1,7};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {2,3,5};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = -1;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {1,3,5};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,1,7};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1,3,5};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 1;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {1,2,3,4,5,6,7,8,9,10,11};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {5,4,7,8,3,1,1,2,3,4,6};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1,2,3,4,3,1,1,2,3,4,6};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 7;
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	int t0[] = {1,5,6,7,8};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,5,6,7,8};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1,5,6,7,8};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	p3 = 1;
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, true, p3) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Comparer-inator is a very simple language that is specialized in comparisons. It takes an expression and returns the result. There are only two kinds of expressions: a variable name or a tertiary operator inspired by C syntax (which is also used in many languages like Java, C++, and C#). We are interested to use this language to process two vector <int>s, A and B to generate the vector <int> wanted as a result. We have previously found that there are four candidate programs that could be an optimal way to solve the issue we have. Each of the programs takes two arguments a and b.
// 
// "a" : This program will return the given argument a.
// "b" : This program will return the given argument b.
// "a<b?a:b" : If a is less than b, the program will return a, else it will return b.
// "a<b?b:a" : If a is less than b, the program will return b, else it will return a.
// 
// 
// Given vector <int> A, B and wanted find the shortest of the four candidate programs that, for every index i, will return wanted[i] after being provided a=A[i] and b=B[i] as arguments. Return the length of the shortest program. If no candidate program can do the required job, return -1 instead.
// 
// DEFINITION
// Class:ComparerInator
// Method:makeProgram
// Parameters:vector <int>, vector <int>, vector <int>
// Returns:int
// Method signature:int makeProgram(vector <int> A, vector <int> B, vector <int> wanted)
// 
// 
// CONSTRAINTS
// -A will contain between 1 and 50 elements, inclusive.
// -B and wanted will each contain the same number of elements as A.
// -Each element of A, B and wanted will be between 1 and 1000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// {1}
// {2}
// {2}
// 
// Returns: 1
// 
// "b" and "a<b?b:a" (quotes for clarity) are the two programs that will return 2 after being given a=1, b=2 as arguments. "b" is the shortest of them.
// 
// 
// 1)
// {1,3}
// {2,1}
// {2,3}
// 
// Returns: 7
// 
// "a<b?b:a" is the only program that will return 2 after being provided a=1, b=2 and will also
// return 3 after being provided a=3, b=1.
// 
// 2)
// {1,3,5}
// {2,1,7}
// {2,3,5}
// 
// Returns: -1
// 
// None of the four programs can do the job correctly.
// 
// 3)
// {1,3,5}
// {2,1,7}
// {1,3,5}
// 
// Returns: 1
// 
// 
// 
// 4)
// {1,2,3,4,5,6,7,8,9,10,11}
// {5,4,7,8,3,1,1,2,3,4,6}
// {1,2,3,4,3,1,1,2,3,4,6}
// 
// Returns: 7
// 
// 
// 
// 5)
// {1,5,6,7,8}
// {1,5,6,7,8}
// {1,5,6,7,8}
// 
// Returns: 1
// 
// "a", "b", "a<b?a:b" and "a<b?b:a" are all valid programs that will give the wanted result. "a" and "b" are the shortest.
// 
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!