Crie um programa para analisar as opções de sequência de troca de moedas

15

Em um quebra-cabeça em um livro antigo meu, é definido um jogo no qual dois jogadores escolhem sequências de lançamentos de moedas que eles acreditam que aparecerão primeiro quando uma moeda for lançada repetidamente. (Na verdade, eram dados ímpares e pares, mas esse pequeno detalhe não importa em termos de equivalência de problemas.)

Note-se que se o jogador 1 escolhe TTTe o jogador 2 escolhe HTT, esse jogador 2 tem 7/8 de chance de ganhar o jogo, pois a única maneira que TTTpode surgir antes HTTé se os três primeiros flips forem coroa.

Seu trabalho é criar um programa ou função que deduza a probabilidade de que uma das duas seqüências escolhidas chegue primeiro. Seu programa terá duas linhas de entrada (ou duas seqüências de caracteres como argumentos), cada uma representando uma sequência de 10 ou menos de comprimento:

HTT
TTT

E produza a probabilidade de o primeiro jogador vencer, na forma de fração ou decimal:

7/8
0.875

O código mais curto para fazer isso em qualquer idioma vence.

Joe Z.
fonte
6
As seqüências têm sempre o mesmo comprimento uma da outra?
Uri Granta
1
@UriZarfaty Não, não necessariamente.
Joe Z.
Embora presumivelmente as sequências tenham que ser distintas (já que a saída não pode especificar um empate).
Uri Granta
Sim, as sequências devem ser distintas.
Joe Z.
Mais especificamente, um não pode ser uma substring terminal do outro.
Joe Z.

Respostas:

4

Python 3 (139 136 134 132 126 115 (143)

Usa o algoritmo de Conway, conforme descrito aqui . Manipula todos os pares de seqüências, desde que o primeiro não seja uma subsequência final do segundo (conforme as instruções).

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]

Obrigado xnor por remover 6 bytes. Obrigado Zgarb por detectar um bug com subsequências.

Uri Granta
fonte
A versão atual não funciona para mim. Para a entrada "HTT"e "TTT", otem o valor -1e o divide por 0.
Jakube 5/01
1
Bom golfe! Eu gosto do truque de argumento padrão. Um casal de dicas (não testado): você pode multiplicar por 2**icom <<i, e a probabilidade de saída pode ser escrito como 1/(1/o + 1), na qual você pode colocar o recíproco odiretamente.
Xnor
Obrigado. Boa localização re / (1 + o). Um pouco envergonhado por ter perdido <<!
Uri Granta
@Jakube Desculpe, não localizou seu comentário! A versão atual funciona bem para mim com "HTT" e "TTT".
Uri Granta
1
Isso fornece uma resposta diferente de zero para HTHe T, mesmo que o primeiro jogador não possa vencer. A outra resposta tem o mesmo problema.
Zgarb
3

CJam, 44 38 36 bytes

Usando o mesmo algoritmo de Conway como aqui .

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

Entrada são as duas seqüências distintas em duas linhas. O resultado é a probabilidade de ganhar primeiro sobre o segundo. As entradas não precisam ter o mesmo comprimento

Estou usando a fórmula para ganhar odds ( p) para o primeiro jogador A como

insira a descrição da imagem aqui

Então a probabilidade é definida como

insira a descrição da imagem aqui

que, depois de simplificado, se torna

insira a descrição da imagem aqui

e após alguma simplificação, torna-se

insira a descrição da imagem aqui


Exemplo de entrada:

HTT
TTT

Resultado:

0.875

Experimente online aqui

Optimizer
fonte
Joe disse nos comentários (depois que isso foi publicado) que as strings não são necessariamente do mesmo tamanho. Ainda assim, +1 porque eu não entendo CJam.
Mdc32
@ mdc32 corrigido, 1 byte mais agora :(
Otimizador
Você já me deixou acreditar que o codegolfSE agora suporta LaTeX ... = (
flawr 6/15
@flawr HAHA. Desculpe por isso :(. Estes são PNGs do editor on-line do LaTeX.
Optimizer
Isso fornece uma resposta diferente de zero para HTHe T, mesmo que o primeiro jogador não possa vencer. A outra resposta tem o mesmo problema.
Zgarb
0

Lua 211 190 184

Também usando o algoritmo de Conway. Ainda novo para Lua, então isso pode ser jogado mais com certeza.

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

Ungolfed

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

Primeira versão

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
fonte