W łamigłówce ze starej mojej książki zdefiniowana jest gra, w której dwóch graczy wybiera sekwencje rzutów monetą, które według nich pojawią się jako pierwsze, gdy moneta zostanie wielokrotnie odwrócona. (To było rzeczywiście dziwne, a nawet rzuty kostką, ale ten mały szczegół nie ma znaczenia pod względem równoważności problemu.)

Należy zauważyć, że jeśli gracz 1 wybierze, TTTa gracz 2 wybierze HTT, ten gracz 2 ma szansę wygranej 7/8, ponieważ jedyną możliwą drogą TTTmoże być HTTto, że wszystkie trzy pierwsze rzuty są remisem.

Twoim zadaniem jest stworzenie programu lub funkcji, która wydedukuje prawdopodobieństwo, że jedna z dwóch wybranych sekwencji pojawi się pierwsza. Twój program pobierze dwa wiersze danych wejściowych (lub dwa ciągi jako argumenty), z których każdy reprezentuje sekwencję o długości 10 lub mniejszej:

HTT
TTT

Podaj prawdopodobieństwo, że pierwszy gracz wygra, w postaci ułamkowej lub dziesiętnej:

7/8
0.875

Wygrywa najkrótszy kod do wykonania tego w dowolnym języku.

Python 3 (139 136 134 132 126 115 143)

Używa algorytmu Conwaya, jak opisano tutaj . Obsługuje wszystkie pary sekwencji, o ile pierwsza nie jest końcowym podsekwencją drugiej (zgodnie z instrukcjami).

def f(a,b):c=lambda x,y=a:sum((x[~i:]==y[:i+1])<<i for i in range(len(x)));return 0 if b in a else(1/(1+(c(a)-c(a,b))/(c(b,b)-c(b))),1)[a in b]

Dzięki xnor za zgolenie 6 bajtów. Dzięki Zgarb za wykrycie błędu z podsekwencjami.

CJam, 44 38 36 bajtów

Korzystanie z tego samego algorytmu Conwaya, jak tutaj .

ll]_m*{~1$,,@f>\f{\#!}2b}/\-:X--Xd\/

Dane wejściowe to dwie odrębne sekwencje w dwóch wierszach. Dane wyjściowe to prawdopodobieństwo pierwszego wygrania w drugim. Wejścia nie muszą być tej samej długości

Używam wzoru na wygraną po kursie ( p) dla pierwszego gracza A as

Następnie prawdopodobieństwo definiuje się jako

który po uproszczeniu staje się

i po pewnym uproszczeniu staje się

Przykładowe dane wejściowe:

HTT
TTT

Wynik:

0.875

Wypróbuj online tutaj

Lua 211 190 184

Również używając algorytmu Conwaya. To wciąż nowość w Lua, więc na pewno można w nią grać w golfa.

z=io.read;e=function(s,t)r='';for d in s:gmatch"."do r=r..(d==t:sub(1,1)and 1 or 0);end;return tonumber(r,2);end;a=z();b=z();print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

Nie golfił

z=io.read;
e=function(s,t)
r='';
    for d in s:gmatch"."do 
        r=r..(d==t:sub(1,1)and 1 or 0);
    end;
    return tonumber(r,2);
end;
a=z();
b=z();
print((e(a,a)-e(a,b))/(e(b,b)-e(b,a))/(1/((1/2)^b:len())));

Pierwsza wersja

z=io.read;
e=function(s,t) 
    r=0;
    for d in s:gmatch"."do 
        r=r*10;
        if d==t:sub(1,1)then r=r+1 end;
    end
    return tonumber(r,2);
end;
f=function(n,o)
    return ((e(n,n)-e(n,o))/(e(o,o)-e(o,n)))/(1/((1/2)^3));
end;
print(f(z(),z()));