Calculate probability of getting half as many heads as coin tosses.
Cops entry (posted by Conor O'Brien): https://codegolf.stackexchange.com/a/100521/8927
Original question: Calculate probability of getting half as many heads as coin tosses.
The posted solution had a couple of obfuscation techniques applied, followed by multiple layers of the same obfuscation technique. Once past the first few tricks, it became a simple (if tedious!) task to extract the actual function:
nCr(a,b) = a! / ((a-b)! * b!)
result = nCr(x, x/2) / 2^x
Took a while to realise what I was looking at (for a while I suspected something to do with entropy), but once it twigged, I managed to find the question easily by searching for "probability of coin toss".
Since Conor O'Brien challenged an in-depth explanation of his code, here's a rundown of the more interesting bits:
It starts by obfuscating some built-in function calls. This is achieved by base-32 encoding the function names, then assigning them to new global-namespace names of a single character. Only 'atob' is actually used; the other 2 are just red-herrings (eval takes the same shorthand as atob, only to be overridden, and btoa simply isn't used).
_=this;
[
490837, // eval -> U="undefined" -> u(x) = eval(x) (but overwritten below), y = eval
358155, // atob -> U="function (M,..." -> u(x) = atob(x)
390922 // btoa -> U="function (M,..." -> n(x) = btoa(x), U[10] = 'M'
].map(
y=function(M,i){
return _[(U=y+"")[i]] = _[M.toString(2<<2<<2)]
}
);
Next there are a couple of trivial string mix-ups to hide the code. These are easily reversed:
u(["","GQ9ZygiYTwyPzE6YSpk","C0tYSki","SkoYSkvZChhLWIpL2QoYikg"].join("K"))
// becomes
'(d=g("a<2?1:a*d(--a)"))(a)/d(a-b)/d(b) '
u("KScpKWIsYShFLCliLGEoQyhEJyhnLGM9RSxiPUQsYT1D").split("").reverse().join("")
// becomes
"C=a,D=b,E=c,g('D(C(a,b),E(a,b))')"
The bulk of the obfuscation is the use of the g function, which simply defines new functions. This is applied recursively, with functions returning new functions, or requiring functions as parameters, but eventually simplifies right down. The most interesting function to come out of this is:
function e(a,b){ // a! / ((a-b)! * b!) = nCr
d=function(a){return a<2?1:a*d(--a)} // Factorial
return d(a)/d(a-b)/d(b)
}
There's also a final trick with this line:
U[10]+[![]+[]][+[]][++[+[]][+[]]]+[!+[]+[]][+[]][+[]]+17..toString(2<<2<<2)
// U = "function (M,i"..., so U[10] = 'M'. The rest just evaluates to "ath", so this just reads "Math"
Although since the next bit is ".pow(T,a)", it was always pretty likely that it would have to be "Math"!
The steps I took along the route of expanding functions were:
// Minimal substitutions:
function g(s){return Function("a","b","c","return "+s)};
function e(a,b,c){return (d=g("a<2?1:a*d(--a)"))(a)/d(a-b)/d(b)}
function h(a,b,c){return A=a,B=b,g('A(a,B(a))')}
function j(a,b,c){return a/b}
function L(a,b,c){return Z=a,Y=b,g('Z(a,Y)')}
k=L(j,T=2);
function F(a,b,c){return C=a,D=b,E=c,g('D(C(a,b),E(a,b))')}
RESULT=F(
h(e,k),
j,
function(a,b,c){return _['Math'].pow(T,a)}
);
// First pass
function e(a,b){
d=function(a){return a<2?1:a*d(--a)}
return d(a)/d(a-b)/d(b)
}
function h(a,b){
A=a
B=b
return function(a){
return A(a,B(a))
}
}
function j(a,b){ // ratio function
return a/b
}
function L(a,b){ // binding function (binds param b)
Z=a
Y=b
return function(a){
return Z(a,Y)
}
}
T=2; // Number of states the coin can take
k=L(j,T); // function to calculate number of heads required for fairness
function F(a,b,c){
C=a
D=b
E=c
return function(a,b,c){return D(C(a,b),E(a,b))}
}
RESULT=F(
h(e,k),
j,
function(a){return Math.pow(T,a)}
);
// Second pass
function e(a,b){...}
function k(a){
return a/2
}
function F(a,b,c){
C=a
D=b
E=c
return function(a,b,c){return D(C(a,b),E(a,b))}
}
RESULT=F(
function(a){
return e(a,k(a))
},
function(a,b){
return a/b
},
function(a){return Math.pow(2,a)}
);
// Third pass
function e(a,b) {...}
C=function(a){ // nCr(x,x/2) function
return e(a,a/2)
}
D=function(a,b){ // ratio function
return a/b
}
E=function(a){return Math.pow(2,a)} // 2^x function
RESULT=function(a,b,c){
return D(C(a,b),E(a,b))
}
The structure of the function nesting is based around utility; the outer-most "D" / "j" function calculates a ratio, then the inner "C" / "h" and "E" (inline) functions calculate the necessary coin flip counts. The "F" function, removed in the third pass, is responsible for connecting these together into a usable whole. Similarly the "k" function is responsible for choosing the number of heads which need to be observed; a task which it delegates to the ratio function "D"/"j" via the parameter binding function "L"; used here to fix parameter b to T (here always 2, being the number of states the coin can take).
In the end, we get:
function e(a,b){ // a! / ((a-b)! * b!)
d=function(a){return a<2?1:a*d(--a)} // Factorial
return d(a)/d(a-b)/d(b)
}
RESULT=function(a){
return e(a, a/2) / Math.pow(2,a)
}
Related meta post – Loovjo – 2016-11-18T19:21:10.763
#Gabriel Benamy http://codegolf.stackexchange.com/questions/28190/convenient-palindrome-checker
– Laikoni – 2016-11-18T21:18:25.083