Erstellen Sie ein Programm, um die Auswahlen der Münzwurfsequenzen zu analysieren

15

In einem Puzzle in einem alten Buch von mir wird ein Spiel definiert, in dem zwei Spieler Sequenzen von Münzwürfen auswählen, von denen sie glauben, dass sie zuerst erscheinen, wenn eine Münze wiederholt geworfen wird. (Eigentlich war es ein ungerader und ein gerader Würfelwurf, aber dieses kleine Detail spielt in Bezug auf die Problemäquivalenz keine Rolle.)

Es wird darauf hingewiesen, dass Spieler 1 TTTund Spieler 2 HTTeine 7/8-Chance haben, das Spiel zu gewinnen, da der einzige Weg TTTdavor bestehen kann, HTTwenn die ersten drei Flips allesamt "Tails" sind.

Ihre Aufgabe ist es, ein Programm oder eine Funktion zu erstellen, die die Wahrscheinlichkeit herleiten, dass eine von zwei ausgewählten Sequenzen an erster Stelle steht. Ihr Programm verwendet zwei Eingabezeilen (oder zwei Zeichenfolgen als Argumente), die jeweils eine Sequenz mit einer Länge von 10 oder weniger darstellen:

HTT
TTT

Und die Wahrscheinlichkeit ausgeben, dass die erste Spieler gewinnt, entweder als Bruch oder als Dezimalzahl:

7/8
0.875

Der kürzeste Code, um dies in einer Sprache zu tun, gewinnt.

Joe Z.
quelle
6
Sind die Sequenzen immer gleich lang?
Uri Granta
1
@UriZarfaty Nein, nicht unbedingt.
Joe Z.
Vermutlich müssen die Sequenzen jedoch unterschiedlich sein (da die Ausgabe kein Unentschieden spezifizieren kann).
Uri Granta
Ja, die Sequenzen müssen unterschiedlich sein.
Joe Z.
Genauer gesagt kann eine nicht eine terminale Teilzeichenfolge der anderen sein.
Joe Z.

Antworten:

4

Python 3 (139 136 134 132 126 115 143)

Verwendet den hier beschriebenen Conway-Algorithmus . Behandelt alle Sequenzpaare, solange die erste keine abschließende Teilsequenz der zweiten ist (gemäß Anweisung).

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]

Danke, xnor, dass du 6 Bytes weniger hast. Vielen Dank an Zgarb, dass er einen Fehler mit Untersequenzen entdeckt hat.

Uri Granta
quelle
Die aktuelle Version funktioniert bei mir nicht. Für die Eingabe "HTT"und "TTT", owird der Wert angegeben -1und durch dividiert 0.
Jakube
1
Schönes Golf! Ich mag den Standardargument-Trick. Ein paar (nicht getestet) Tipps: Sie können multiplizieren 2**imit <<i, und die Ausgabewahrscheinlichkeit kann geschrieben werden 1/(1/o + 1), in dem Sie den Kehrwert setzen können odirekt.
Xnor
Vielen Dank. Guter Ort für (1 + o). Etwas peinlich verpasst zu haben <<!
Uri Granta
@ Jakube Sorry, habe deinen Kommentar nicht gefunden! Die aktuelle Version funktioniert für mich mit "HTT" und "TTT".
Uri Granta
1
Dies gibt eine Antwort ungleich Null für HTHund T, obwohl der erste Spieler nicht gewinnen kann. Die andere Antwort hat das gleiche Problem.
Zgarb
3

CJam, 44 38 36 Bytes

Verwenden des gleichen Conway-Algorithmus wie hier .

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

Eingabe sind die zwei unterschiedlichen Sequenzen in zwei Zeilen. Der Output ist die Wahrscheinlichkeit, dass der erste über den zweiten gewinnt. Die Eingänge müssen nicht gleich lang sein

Ich verwende die Formel zum Gewinnen von Gewinnchancen ( p) für den ersten Spieler A als

Bildbeschreibung hier eingeben

Dann ist die Wahrscheinlichkeit definiert als

Bildbeschreibung hier eingeben

was nach der Vereinfachung wird

Bildbeschreibung hier eingeben

und nach einiger Vereinfachung wird

Bildbeschreibung hier eingeben


Beispiel Eingabe:

HTT
TTT

Ausgabe:

0.875

Probieren Sie es hier online aus

Optimierer
quelle
Joe sagte in Kommentaren (nachdem dies gepostet wurde), dass die Zeichenfolgen nicht unbedingt die gleiche Länge haben. Trotzdem +1, weil ich CJam nicht verstehe.
mdc32
@ mdc32 behoben, jetzt 1 Byte länger :(
Optimizer
Sie haben mich schon glauben lassen, dass codegolfSE jetzt LaTeX unterstützt ... = (
flawr
@flawr HAHA. Entschuldigung :(. Dies sind PNGs aus dem Online-LaTeX-Editor.
Optimizer
Dies gibt eine Antwort ungleich Null für HTHund T, obwohl der erste Spieler nicht gewinnen kann. Die andere Antwort hat das gleiche Problem.
Zgarb
0

Lua 211 190 184

Auch unter Verwendung des Conway-Algorithmus. Lua ist noch neu, so dass man sicher mehr Golf spielen kann.

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

Erste Version

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
quelle