Cree un programa para analizar las opciones de secuencia de lanzamiento de monedas

15

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.

Joe Z.
fuente
66
¿Las secuencias son siempre de la misma longitud entre sí?
Uri Granta
1
@UriZarfaty No, no necesariamente.
Joe Z.
Aunque presumiblemente las secuencias tienen que ser distintas (ya que la salida no puede especificar un empate).
Uri Granta
Sí, las secuencias deben ser distintas.
Joe Z.
Más específicamente, uno no puede ser una subcadena terminal del otro.
Joe Z.

Respuestas:

4

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.

Uri Granta
fuente
La versión actual no me funciona. Para la entrada "HTT"y "TTT", otiene el valor -1y lo divide por 0.
Jakube
1
Buen golf! Me gusta el truco de argumento predeterminado. Un par de consejos (no probado): se puede multiplicar por 2**icon <<i, y la probabilidad de salida se puede escribir como 1/(1/o + 1), en la que se puede poner el recíproco de oforma directa.
xnor
Gracias. Buen lugar re o / (1 + o). Algo avergonzado de haber perdido <<!
Uri Granta
@Jakube Lo siento, ¡no vi tu comentario! La versión actual funciona bien para mí con "HTT" y "TTT".
Uri Granta
1
Esto da una respuesta distinta de cero HTHy T, a pesar de que el primer jugador no puede ganar. La otra respuesta tiene el mismo problema.
Zgarb
3

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

ingrese la descripción de la imagen aquí

Entonces la probabilidad se define como

ingrese la descripción de la imagen aquí

que, después de simplificar se convierte

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí


Entrada de ejemplo:

HTT
TTT

Salida:

0.875

Pruébalo en línea aquí

Optimizador
fuente
Joe dijo en comentarios (después de que esto fue publicado) que las cadenas no son necesariamente de la misma longitud. Aún así, +1 porque no entiendo CJam.
mdc32
@ mdc32 solucionado, 1 byte más ahora :(
Optimizer
Ya me dejaste creer que codegolfSE ahora es compatible con LaTeX ... = (
flawr
@flawr HAHA. Lo sentimos :(. Estos son PNG del editor en línea de LaTeX.
Optimizer
Esto da una respuesta distinta de cero HTHy T, a pesar de que el primer jugador no puede ganar. La otra respuesta tiene el mismo problema.
Zgarb
0

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()));
Teun Pronk
fuente