En un rompecabezas de un viejo libro mío, se define un juego en el que dos jugadores eligen secuencias de lanzamientos de monedas que creen que aparecerán primero cuando una moneda se lanza repetidamente. (En realidad, era una tirada de dados par e impar, pero este pequeño detalle no importa en términos de equivalencia problemática).

Se observa que si el jugador 1 elige TTTy el jugador 2 elige HTT, ese jugador 2 tiene una probabilidad de 7/8 de ganar el juego, ya que la única forma de TTThacerlo HTTes si los primeros tres lanzamientos son todos colas.

Su trabajo es crear un programa o función que deduzca la probabilidad de que una de las dos secuencias elegidas sea lo primero. Su programa tomará dos líneas de entrada (o dos cadenas como argumentos), cada una representando una secuencia de longitud 10 o menos:

HTT
TTT

Y genere la probabilidad de que gane el primer jugador, ya sea en forma fraccionaria o decimal:

7/8
0.875

El código más corto para hacer esto en cualquier idioma gana.

Python 3 (139 136 134 132 126 115 143)

Utiliza el algoritmo de Conway como se describe aquí . Maneja todos los pares de secuencias siempre que el primero no sea una subsecuencia de terminación del segundo (según las instrucciones).

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]

Gracias xnor por reducir 6 bytes. Gracias Zgarb por detectar un error con subsecuencias.

CJam, 44 38 36 bytes

Usando el mismo algoritmo de Conway que aquí .

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

La entrada son las dos secuencias distintas en dos líneas. La salida es la probabilidad de ganar primero sobre el segundo. Las entradas no necesitan ser de la misma longitud

Estoy usando la fórmula para ganar probabilidades ( p) para el primer jugador A como

Entonces la probabilidad se define como

que, después de simplificar se convierte

y después de alguna simplificación, se convierte

Entrada de ejemplo:

HTT
TTT

Salida:

0.875

Pruébalo en línea aquí

Lua 211 190 184

También usando el algoritmo de Conway. Todavía nuevo en Lua, por lo que esto se puede jugar más seguro.

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())));

Sin golf

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())));

Primera versión

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()));