Oblicz prawdopodobieństwo uzyskania o połowę więcej głów niż rzut monetą.
Wpis gliniarzy (opublikowany przez Conor O'Brien): /codegolf//a/100521/8927
Pierwotne pytanie: obliczyć prawdopodobieństwo uzyskania o połowę mniejszej liczby głów niż rzut monetą.
W opublikowanym rozwiązaniu zastosowano kilka technik zaciemniania, a następnie wiele warstw tej samej techniki zaciemniania. Po przejściu kilku pierwszych sztuczek wyodrębnienie rzeczywistej funkcji stało się prostym (choć żmudnym!) Zadaniem:
nCr(a,b) = a! / ((a-b)! * b!)
result = nCr(x, x/2) / 2^x
Chwilę zajęło mi zrozumienie, na co patrzę (przez pewien czas podejrzewałem, że ma to coś wspólnego z entropią), ale kiedy już się zakręciło, udało mi się łatwo znaleźć pytanie, szukając „prawdopodobieństwa rzutu monetą”.
Ponieważ Conor O'Brien zakwestionował dogłębne wyjaśnienie swojego kodu, oto podsumowanie ciekawszych fragmentów:
Zaczyna się od zaciemnienia niektórych wbudowanych wywołań funkcji. Uzyskuje się to przez kodowanie base-32 nazw funkcji, a następnie przypisanie ich do nowych nazw przestrzeni globalnej pojedynczego znaku. W rzeczywistości używany jest tylko „atob”; pozostałe 2 są tylko czerwonymi śledziami (eval ma ten sam skrót jak atob, ale musi zostać zastąpiony, a btoa po prostu nie jest używane).
_=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)]
}
);
Następnie jest kilka trywialnych pomyłek w celu ukrywania kodu. Można je łatwo odwrócić:
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))')"
Większość zaciemniania polega na użyciu gfunkcji, która po prostu definiuje nowe funkcje. Jest to stosowane rekurencyjnie, przy czym funkcje zwracają nowe funkcje lub wymagają funkcji jako parametrów, ale ostatecznie upraszczają się od samego początku. Najciekawszą funkcją, która z tego wynika, jest:
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)
}
Istnieje również ostatnia sztuczka z tą linią:
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"
Chociaż ponieważ następnym bitem jest „.pow (T, a)”, zawsze było całkiem prawdopodobne, że będzie to „Math”!
Kroki, które podjąłem na drodze rozszerzania funkcji, to:
// 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))
}
Struktura zagnieżdżania funkcji jest oparta na użyteczności; najbardziej zewnętrzna funkcja „D” / „j” oblicza stosunek, a następnie funkcje wewnętrzne „C” / „h” i „E” (inline) obliczają niezbędne zliczanie monet. Funkcja „F”, usunięta w trzecim przejściu, odpowiada za połączenie ich razem w użyteczną całość. Podobnie funkcja „k” odpowiada za wybór liczby głowic, które należy obserwować; zadanie, które deleguje do funkcji stosunku „D” / „j” za pomocą funkcji wiązania parametrów „L”; służy tutaj do ustalenia parametru bna T(tutaj zawsze 2, czyli liczba stanów, jaką moneta może przyjąć).
W końcu otrzymujemy:
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)
}