34
\$\begingroup\$

As we all know, meta is overflowing with complaints about scoring code-golf between languages (yes, each word is a seperate link, and these may be just the tip of the iceberg).

With so much jealousy towards those who actually bothered to look up the Pyth documentation, I thought it would be nice to have a little bit more of a constructive challenge, befitting of a website that specializes in code challenges.


The challenge is rather straightforward. As input, we have the language name and byte count. You can take those as function inputs, stdin or your languages default input method.

As output, we have a corrected byte count, i.e., your score with the handicap applied. Respectively, the output should be the function output, stdout or your languages default output method. Output will be rounded to integers, because we love tiebreakers.

Using the most ugly, hacked together query (link - feel free to clean it up), I have managed to create a dataset (zip with .xslx, .ods and .csv) that contains a snapshot of all answers to questions. You can use this file (and assume it to be available to your program, e.g., it's in the same folder) or convert this file to another conventional format (.xls, .mat, .sav etc - but it may only contain the original data!). The name should remain QueryResults.ext with ext the extension of choice.


Now for the specifics. For each language, there is a Boilerplate B and Verbosity V parameters. Together, they can be used to create a linear model of the language. Let n be the actual number of bytes, and c be the corrected score. Using a simple model n=Vc+B, we get for the corrected score:

    n-B
c = ---
     V

Simple enough, right? Now, for determining V and B. As you might expect, we're going to do some linear regression, or more precise, a least squares weighted linear regression. I'm not going to explain the details on that - if you're not sure how to do that, Wikipedia is your friend, or if you're lucky, your language's documentation.

The data will be as follows. Each data point will be the byte count n and the question's average bytecount c. To account for votes, the points will be weighted, by their number of votes plus one (to account for 0 votes), let's call that v. Answers with negative votes should be discarded. In simple terms, an answer with 1 vote should count the same as two answers with 0 votes.

This data is then fitted into the aforementioned model n=Vc+B using weighted linear regression.


For example, given the data for a given language

n1=20, c1=8.2, v1=1
n2=25, c2=10.3, v2=2
n3=15, c3=5.7, v3=5

Now, we compose the relevant matrices and vectors A, y and W, with our parameters in the vector

  [1 c1]    [n1]    [1 0 0]  x=[B]
A=[1 c2]  y=[n2]  W=[0 2 0],   [V]
  [1 c3]    [n3]    [0 0 5]

we solve the matrix equation (with ' denoting the transpose)

A'WAx=A'Wy

for x (and consequently, we get our B and V parameter).


Your score will be the output of your program, when given your own language name and bytecount. So yes, this time even Java and C++ users can win!

WARNING: The query generates a dataset with a lot of invalid rows due to people using 'cool' header formatting and people tagging their questions as . The download I provided has most of the outliers removed. Do NOT use the CSV provided with the query.

Happy coding!

\$\endgroup\$
  • 3
    \$\begingroup\$ s/look up the Pyth documentation/carefully study the two existing pieces of Jelly documentation \$\endgroup\$ – lirtosiast Feb 4 '16 at 20:09
  • \$\begingroup\$ Your query doesn't seem to distinguish between Perl 5 and Perl 6. Which is similar to not distinguishing C++ from Haskell. \$\endgroup\$ – Brad Gilbert b2gills Feb 4 '16 at 21:47
  • \$\begingroup\$ @BradGilbertb2gills I know - it does a whole lot of quirky things, mostly due to people going crazy with formatting. Feel free to improve on it, but right now, it's a trade-off between a lack of version numbering and languages called C++ <s>6 bytes</s>. Besides, I never did any T-SQL before today and I'm already impressed with myself that I managed to extract the bytecount. \$\endgroup\$ – Sanchises Feb 4 '16 at 21:52
  • \$\begingroup\$ Can we remove outliers, ie any languages with only one entry (usually incorrect language names) or the ones that have >10,000 bytes? \$\endgroup\$ – Robert Fraser Feb 5 '16 at 9:08
  • \$\begingroup\$ @RobertFraser I thought that would be too much for a single challenge. I'll fix the data file, see edit. \$\endgroup\$ – Sanchises Feb 5 '16 at 9:22
21
+100
\$\begingroup\$

Mathematica, 244.719 (245 bytes)

f[l_,n_]:=x/.Solve[d=Rest@Import@"QueryResults.csv";LinearModelFit[#.#2/Tr@#&@@{#~Max~-1&/@#4+1,#3}&@@Thread@#&/@{#,#~Cases~{_,l,__}}&/@d~GroupBy~Last/@#[[;;,1,5]],x,x,Weights->Tr/@#[[;;,;;,4]]]&[d~Cases~{_,l,_,v_/;v>=0,_}~GatherBy~Last]@x==n,x]

Test case

f["mathematica", n]   (* { .820033 (n + 53.4263) } *)
f["mathematica", 245] (* { 244.719 } *)

What about other languages?

f["c++", n]           (* { .821181 (n - 79.5437) } *)
f["java", n]          (* { .717579 (n - 56.0858) } *)
f["cjam", n]          (* { 2.21357 (n + 2.73772) } *)
f["pyth", n]          (* { 4.52194 (n - 8.82806) } *)

Alternative model: log(c)=log((n-B)/V)

One notable feature of code golf (and probably other coding problems) is that the distribution of the lengths of programs tends to be exponential distribution (in contrast to uniform distribution). Hence model log(n)=log(Vc+B) is much more likely to balance the influences between points with large c and small c.

As we can see in the graphs below, the distribution of points are suitable for fitting in logarithmic scale.


Results of the new model

Language       V       B

Python       1.365   -19.4    
Javascript   1.002     1.6
Ruby         0.724     1.7
Perl         1.177   -32.7
C            1.105     1.5
Haskell      1.454   -24.5
Mathematica  1.319   -39.7
PHP          1.799   -62.0
Java         1.642     4.4
C#           1.407     4.5

CJam         0.608   -12.5
Pyth         0.519   -11.4
Golfscript   0.766   -18.0
J            0.863   -21.4
APL          0.744   -17.7
K            0.933   -23.3
Retina       1.322   -37.9
MATL         0.762   -13.3
Jelly        0.965   -23.8

We have found two exceptional language - Ruby with V=0.724 and Retina with V=1.322, and a criterion of being a popular golfing language - having a large negative boilerplate.

\$\endgroup\$
  • \$\begingroup\$ @sanchises So far so good, except that you use semicolons as delimiters in csv. \$\endgroup\$ – njpipeorgan Feb 5 '16 at 11:44
  • \$\begingroup\$ That's Microsoft Excel for you. Apparently saving as csv is too difficult for it. \$\endgroup\$ – Sanchises Feb 5 '16 at 11:49
  • \$\begingroup\$ So apparently CJam has a negative boilerplate length. Interesting. \$\endgroup\$ – PurkkaKoodari Feb 5 '16 at 13:13
  • \$\begingroup\$ @Pietu1998 Linear model is not so accurate, I think. \$\endgroup\$ – njpipeorgan Feb 5 '16 at 13:15
  • \$\begingroup\$ @Pietu1998 Not entirely surprising, since golfing languages generally take implicit input and may return implicit output. Note that "Boilerplate length" is defined w.r.t the average, not w.r.t an ideal boilerplateless language. I'm actually positively surprised by how well this simple model seems to be doing when glancing at these results. \$\endgroup\$ – Sanchises Feb 5 '16 at 14:07
3
+200
\$\begingroup\$

Python3, 765.19 (765) bytes

Probably some room for golfing here. Requires numpy for matrix stuff. Reads from stdin, formatted as follows: [lang] [bytes/n]. Stops when you send q.

import numpy as n,csv
L={};Q={};X={};D=n.dot;f=open('QueryResults.csv',encoding="utf8");R=csv.reader(f);f.readline();Z=list.append;M=n.matrix
for r in R:
 if r[1] not in L:L[r[1]]=[]
 if r[4] not in Q:Q[r[4]]=[]
 Z(L[r[1]],r);Z(Q[r[4]],r)
for l in L:
 b=[];a=[];v=[];t=[]
 for r in L[l]:
  if int(r[3])>-1:
   Z(b,int(r[2]));o=[]
   for q in Q[r[4]]:Z(o,int(q[2]))
   Z(a,sum(o)/len(o));Z(v,int(r[3])+1)
 for k in a:Z(t,[1,k])
 if len(t)<1:continue
 A=M(t);T=A.transpose();W=n.diag(v);y=M(b).reshape((len(b),1));e=D(D(T,W),A)
 if n.linalg.det(e)==0:continue
 i=n.linalg.inv(e);X[l]=D(i,D(D(T,W),y))
p=input()
while(p!="q"):
 S=p.split()
 if S[1]=='n':print("(n-("+str(X[S[0]].item(0))+"))/"+str(X[S[0]].item(1)))
 else:print(str((int(S[1])-X[S[0]].item(0))/X[S[0]].item(1)))
 p=input()

Results

I might have done something wrong at some point; I get different results than the Mathematica answer:

python3 808 -> 765.19
python3 n   -> (n-(32.41))/1.01

c++ n        -> (n-(71.86))/1.17
cjam n       -> (n-(-14.09))/0.51
java n       -> (n-(18.08))/1.64
pyth n       -> (n-(1.42))/0.28
jelly n      -> (n-(-4.88))/0.34
golfscript n -> (n-(-0.31))/0.44
\$\endgroup\$

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.