6
\$\begingroup\$

Given required values for an expression with 2 variables, output a short expression which fulfill these values

Input

You may take the input in any reasonable format, e.g. f(x,y)=z, {(x, y): z}, [[[x,y],z]], but please write what format is your input is taken in

Output

Your output needs the be a valid infix expression for two variables, and it has to output the correct value when rounding the output to three digits after the comma, but the current value isn't rounded during calculation. The following symbols/operators are allowed:

symbols

x - the first input variables
y - the second input variables
pi - 3.1415 (4 digit precision)
e - 2.7182 (4 digit precision)
every possible numeric constant (1, 0.12, 42, 13.241)

operators

+ sum of two values, in the format a+b
- difference of two values, in the format a-b
* multiplication of two values, in the format a*b
/ division of two values, in the format a/b
^ power of two values, in the format a^b
|| absolute value, in the format |a|
() parentheses, in the format (a)
floor the floor of a value, in the format floor(a)
ceil the ceil of a value, in the format ceil(a)

if I forgot anything that you think is important tell me in the comments please.

Example Testcases

other expressions are okay if they result in the correct values

f(0.12, 0.423) = 3.142
f(0.89, 0.90) = 3.142
|
\/
pi (3.1415 gets rounded to 3 digits after the comma - 3.142)

f(0.12, 0.423) = 0.543
f(0.89,0.9)=1.79
|
\/
x+y

Score

Your score is the average length of expression for the following input: https://pastebin.com/tfuBjpc6 , where each batch of inputs (a different function) is separated by a newline. You can transform the format to any format your program accept.

Good luck!

\$\endgroup\$
  • 1
    \$\begingroup\$ Since the score depends on the size of the expressions, I guess the program is supposed to be deterministic. Is that correct? \$\endgroup\$ – Arnauld Mar 24 at 10:09
  • \$\begingroup\$ It doesn't have it be, it's goal is that the average expression length would be minimal. \$\endgroup\$ – Command Master Mar 24 at 10:10
  • \$\begingroup\$ You might want to specify a little bit better on what input values we should score our programs. Even if you set the seed to a specific value in your scorer program, that only works for Python programs. Different submissions will be scored differently from eachother. \$\endgroup\$ – RGS Mar 24 at 10:29
  • \$\begingroup\$ the generate_expression code should call the program (i.e. by executing a shell command), but I think I should randomly generate expressions and then post there values in here and the average length of these would be counted \$\endgroup\$ – Command Master Mar 24 at 10:35
  • \$\begingroup\$ I edited it to include the test-battery tag, and a link to the list of tested values \$\endgroup\$ – Command Master Mar 24 at 11:32
1
\$\begingroup\$

C++ (gcc), score: 39.2533

Interpolate xs or ys and fs with lagrange interpolation.

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <set>
using namespace std;
string ml(const string& a,const string& b) {
	if(a.size()<b.size()) return a;
	return b;
};
string prt(double x,int g,int d=0) {
	char buf[100],buf2[100];
	sprintf(buf,"%%+.%dlf",g);
	sprintf(buf2,buf,x);
	string s=buf2;
	while(s.size()&&s.back()=='0') s.pop_back();
	if(s.size()&&s.back()=='.') s.pop_back();
	if(s=="-0") s="+0";
	if(s=="+3.1415") s="+pi";
	if(s=="-3.1415") s="-pi";
	if(s=="+2.7182") s="+e";
	if(s=="-2.7182") s="-e";
	return s;
};
int main()
{
	double tl=0; int tc=0;
	while(1)
	{
		double x[5],y[5],f[5];
		int bad=0;
		char s[2][20];
		for(int j=0,k;j<5;++j)
		{
			if(scanf("%s %s",s[0],s[1])==EOF) {
				bad=1; break;
			}
			s[0][strlen(s[0])-1]=0;
			sscanf(s[0]+2,"%lf",x+j);
			for(k=0;s[1][k]!=')';++k) ;
			s[1][k]=0;sscanf(s[1],"%lf",y+j);
			sscanf(s[1]+k+2,"%lf",f+j);
		}
		if(bad) break;
		set<double> dx,dy;
		for(int j=0;j<5;++j) dx.insert(x[j]),dy.insert(y[j]);
		string ans; ans.resize(2000);
		auto work=[&](double*d,char s) {
			double md=0;
			stringstream ss;
			double p[5];
			memset(p,0,sizeof p);
			for(int j=0;j<5;++j)
			{
				double w=f[j];
				md=max(md,fabs(d[j]));
				for(int k=0;k<5;++k) if(j!=k)
					w/=d[j]-d[k];
				double q[5];
				memset(q,0,sizeof q);
				q[0]=w;
				for(int k=0;k<5;++k) if(j!=k)
					for(int s=4;s>=0;--s)
						q[s]=(s?q[s-1]:0)-q[s]*d[k];
				for(int k=0;k<5;++k) p[k]+=q[k];
			}
			for(int j=0;j<5;++j)
			{
				double prec=1.0/10000/pow(md,j);
				int u=0;
				while(prec<1) prec*=10,++u;
				string w=prt(p[j],u);
				if(w=="+0") continue;
				ss<<w;
				if(j) ss<<"*"<<s;
				if(j>=2) ss<<"^"<<j;
			}
			string o=ss.str();
			if(o.size()&&o[0]=='+') o.erase(o.begin());
			if(!o.size()) o="0";
			if(o.size()<ans.size()) ans=o;
		};
		if(dx.size()==5) work(x,'x');
		if(dy.size()==5) work(y,'y');
		tl+=ans.size(); ++tc;
		cout<<ans<<"\n";
	}
	cerr<<setprecision(4)<<fixed;
	cerr<<tl/tc<<"\n";
}

The output looks like:

-265.3786-74.29574*x+344.81918*x^2+225.130398*x^3+36.610661*x^4
35.1581-3.27602*y+0.113946*y^2+0.412073*y^3-0.080117*y^4
-14.961
0.3769+0.50931*x-0.172598*x^2-0.0317501*x^3+0.0113617*x^4
-9.3762-1.54567*y+9.224426*y^2+5.413074*y^3+0.8106773*y^4
-3.7267-3.1155*x+0.011054*x^2-0.002775*x^3-0.0010706*x^4
1
4
31.8856+38.31442*x-0.94623*x^2-24.221891*x^3-8.086617*x^4
0.4856+0.08145*y+0.084768*y^2+0.0113*y^3+0.0001758*y^4
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ cool! You might be able to combine the constants in the final equation for better score? \$\endgroup\$ – Command Master Apr 11 at 5:38
  • \$\begingroup\$ How does it take input? \$\endgroup\$ – Command Master Apr 11 at 5:40
  • \$\begingroup\$ I think just feed the sample through stdin. @CommandMaster \$\endgroup\$ – newbie Apr 11 at 6:21
  • \$\begingroup\$ Yeah I may try to improve on that later. It's a bit more difficult than it looks because of the problems with precision. @CommandMaster \$\endgroup\$ – newbie Apr 11 at 6:33
-1
\$\begingroup\$

C (gcc), 798 bytes, score: 3.323226 or 16.521740

There are two versions of the code. The less cheaty version will output an expression in form of x * y * 0 + z, while the more cheaty version will output an expression in form of z.

Obviously creating a "real" solution would bump the score down, but given that it's just a tiny gain and as far as I can tell it's a NP-complete problem, it's simply not worth doing it (some edge cases where you tell a 7-long number that's for instance x+1, then you lose a few points, but it's not significant this much).

cheaty/ Average length: 11618 / 3496: 3.323226
less cheaty/ Average length: 57760 / 3496: 16.521740

The code:

float round(float x) {
    float v = (int)(x * 1000 + .5); 
    return (float)v / 1000; 
} 

char * find_constants(float f) {
	float x = round(f);
	static char buf[16];
	if(x == 3.142) return "pi";
	if(x == 2.718) return "e";
	sprintf(buf, "%.3g", f);
	return buf;
}

int main(void) {
	float x, y, z;
	long total_len = 0, amount = 0;
	while(scanf("%f %f %f", &x, &y, &z) == 3) {
		#ifdef LESS_CHEATY
			total_len += strlen(find_constants(x))+strlen(find_constants(y))+strlen(find_constants(z))+4;
			// printf("%s*%s*0+%s\n", find_constants(x), find_constants(y), find_constants(z));
		#else
			total_len += strlen(find_constants(z));
			// printf("%s\n", find_constants(z));
		#endif
		amount++;
	}
	printf("Average length: %d / %d: %f\n", total_len, amount, (float)total_len / (float)amount);
}

Try me online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I believe you should consider the restrictions separated by one blank line to be for one function instead of considering each of them to be separated ones. \$\endgroup\$ – newbie Apr 10 at 13:44
  • \$\begingroup\$ each batch of input is separated by an excess newline, you need to be able to interpret the function when given multiple values of it in different points \$\endgroup\$ – Command Master Apr 10 at 13:54
  • \$\begingroup\$ Also you can use the name x directly instead of stating that value when you want. \$\endgroup\$ – newbie Apr 10 at 13:56
  • 1
    \$\begingroup\$ I agree the question is unclear, but it's not a loophole I would say. You're supposed to treat every five equations to be restrictions on one function you generated. \$\endgroup\$ – newbie Apr 10 at 13:59
  • 1
    \$\begingroup\$ I think where each batch of inputs (a different function) is separated by a newline. on the score section. Also example testcases is also suggesting it. tbh I also didn't realize what's going on until I found the weird line breaks in the testcase. \$\endgroup\$ – newbie Apr 10 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.