Создайте программу для анализа выбора последовательности монет

15

В одной из головоломок в моей старой книге определена игра, в которой два игрока выбирают последовательности бросков монет, которые, по их мнению, появятся первыми, когда монета неоднократно подбрасывается. (Это были странные и четные броски кубиков, но эта маленькая деталь не имеет значения с точки зрения эквивалентности задач.)

Следует отметить, что если игрок 1 выбирает, TTTа игрок 2 выбирает HTT, то у игрока 2 есть шанс выиграть игру 7/8, поскольку единственный путь TTTможет быть достигнут раньше HTT, если все первые три броска - это хвосты.

Ваша задача - создать программу или функцию, которая будет определять вероятность того, что одна из двух выбранных последовательностей будет первой. Ваша программа будет принимать две строки ввода (или две строки в качестве аргументов), каждая из которых представляет последовательность длиной 10 или менее:

HTT
TTT

И выведите вероятность того, что первый игрок выиграет, в дробной или десятичной форме:

7/8
0.875

Самый короткий код для этого на любом языке выигрывает.

Джо З.
источник
6
Всегда ли последовательности имеют одинаковую длину?
Ури Гранта
1
@UriZarfaty Нет, не обязательно.
Джо З.
Хотя предположительно последовательности должны быть различны (поскольку выходные данные не могут указывать связь).
Ури Гранта
Да, последовательности должны быть разными.
Джо З.
Более конкретно, одна не может быть терминальной подстрокой другой.
Джо З.

Ответы:

4

Python 3 (139 136 134 132 126 115 143)

Использует алгоритм Конвея, как описано здесь . Обрабатывает все пары последовательностей, пока первая не является завершающей подпоследовательностью второй (согласно инструкциям).

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]

Спасибо xnor за то, что сбрил 6 байтов. Спасибо Згарбу за обнаружение ошибки с подпоследовательностями.

Ури Гранта
источник
Текущая версия не работает для меня. Для ввода "HTT"и "TTT", oимеет значение -1и делит его на 0.
Якуб
1
Хороший гольф! Мне нравится трюк с аргументами по умолчанию. Пара (непроверенных) советов: вы можете умножить на 2**iс <<i, а вероятность вывода можно записать как 1/(1/o + 1), в которую вы можете поместить обратную величину oнепосредственно.
xnor
Благодарю. Хорошее место re o / (1 + o). Несколько смущен, что пропустил <<!
Ури Гранта
@Jakube Извините, не заметил ваш комментарий! Текущая версия отлично работает для меня с "HTT" и "TTT".
Ури Гранта
1
Это дает ненулевой ответ для HTHи T, даже если первый игрок не может выиграть. Другой ответ имеет ту же проблему.
Згарб
3

CJam, 44 38 36 байт

Используя тот же алгоритм Конвея, что и здесь .

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

Ввод - это две отдельные последовательности в две строки. Выход - это вероятность первого выигрыша за секунду. Входы не должны быть одинаковой длины

Я использую формулу для выигрыша шансов ( p) для первого игрока A как

введите описание изображения здесь

Тогда вероятность определяется как

введите описание изображения здесь

который после упрощения становится

введите описание изображения здесь

и после некоторого упрощения становится

введите описание изображения здесь


Пример ввода:

HTT
TTT

Выход:

0.875

Попробуйте онлайн здесь

оптимизатор
источник
Джо сказал в комментариях (после того, как это было опубликовано), что строки не обязательно имеют одинаковую длину. Тем не менее, +1, потому что я не понимаю CJam.
mdc32
@ mdc32 исправлено, теперь на 1 байт больше :(
Оптимизатор
Вы уже позволили мне поверить, что codegolfSE теперь поддерживает LaTeX ... = (
flawr
@ Flawr HAHA. Извините за это :(. Это PNG-файлы из онлайн-редактора LaTeX.
Оптимизатор
Это дает ненулевой ответ для HTHи T, даже если первый игрок не может выиграть. Другой ответ имеет ту же проблему.
Згарб
0

Луа 211 190 184

Также используя алгоритм Конвея. Все еще новичок в Lua, так что это может быть в гольф больше наверняка.

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

Первая версия

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()));
Теун Пронк
источник