Эти кости нетранзитивны?

31

Нетранзитивные кости - это милые маленькие игрушки, которые бросают вызов нашей интуиции в теории вероятностей. Нам понадобится несколько определений для этой задачи:

Рассмотрим две кости A и B, которые выбрасываются одновременно. Мы говорим, что A побеждает B, если вероятность того, что A показывает большее число, чем B , строго больше, чем вероятность B показывает большее число , чем A .

Теперь рассмотрим набор из трех костей, с этикетками , B , C . Такой набор кубиков называется нетранзитивным, если

  • либо A бьет B , B бьет C, а C бьет A
  • или C бьет B , B бьет и бьется C .

В качестве одного из моих любимых примеров рассмотрим кости Грайма , у которых есть следующие стороны:

A: 3 3 3 3 3 6
B: 2 2 2 5 5 5
C: 1 4 4 4 4 4

Интересно, что среднее значение каждого кубика равно 3,5, как и у обычного кубика.

Можно показать, что:

  • А бьет Б с вероятностью 7/12.
  • B бьет C с вероятностью 7/12.
  • С бьет А с вероятностью 25/36.

Теперь эти конкретные кости еще более странные. Если мы бросим каждый кубик дважды и суммируем результаты, порядок которых превосходит, который меняется на противоположный:

  • B бьет A с вероятностью 85/144.
  • С бьет В с вероятностью 85/144.
  • А бьет С с вероятностью 671/1296.

Давайте назовем набор кубиков с этим свойством Grime-нетранзитивных .

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

Соревнование

Принимая во внимание три шестигранного кубика, определяют , какие из указанных выше свойств этого набора имеет, и выход одного из следующих строк: none, nontransitive, Grime-nontransitive, strongly nontransitive.

Вы можете написать программу или функцию, получить ввод через STDIN, аргумент командной строки, приглашение или аргумент функции и записать результат в STDOUT или вернуть его в виде строки.

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

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

Тестовые случаи

none
1 2 3 4 5 6, 6 5 4 3 2 1, 1 3 5 2 4 6
1 1 1 6 6 6, 4 4 4 5 5 5, 5 5 5 5 5 5
1 1 2 5 6 6, 2 2 3 4 4 6, 2 3 3 4 4 5
0 1 2 3 4 5, 1 1 2 3 3 5, 1 2 2 2 3 5
3 13 5 7 13 7, 5 7 11 5 7 13, 5 9 13 5 7 9

nontransitive
1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4
1 4 4 4 4 4, 2 2 2 4 5 6, 2 3 3 3 5 5
1 2 1 6 5 6, 3 1 3 6 2 6, 2 4 2 4 4 5
3 4 6 6 7 7, 4 4 4 7 7 7, 5 5 5 5 6 7
2 5 11 11 14 14, 5 5 5 14 14 14, 8 8 8 8 8 17

Grime-nontransitive
3 3 3 3 3 6, 2 2 2 5 5 5, 1 4 4 4 4 4
1 1 4 5 5 5, 2 2 2 3 6 6, 3 3 3 4 4 4
2 1 4 6 4 4, 2 4 5 2 3 5, 3 3 6 3 3 3
11 11 13 15 15 16, 12 12 12 13 16 16, 13 13 13 14 14 14
4 4 7 16 19 19, 4 7 13 13 13 19, 4 10 10 10 16 19

strongly nontransitive
2 2 2 5 5 5, 2 3 3 3 5 5, 1 1 4 5 5 5
2 2 2 3 6 6, 2 2 2 5 5 5, 2 2 4 4 4 5
1 5 1 3 6 5, 6 6 4 2 2 1, 5 3 4 3 4 2
0 0 2 4 4 5, 0 1 1 3 5 5, 1 1 2 3 4 4
1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

Если вы хотите протестировать свой код еще более тщательно, Питер Тейлор был достаточно любезен и написал эталонную реализацию, которая классифицировала все ~ 5000 наборов кубиков со сторонами от 1 до 6 и средним значением 3,5. Вставить ссылку

Мартин Эндер
источник
Я полностью забыл о нетранзитивных игральных костях. Спасибо :)
npst
Верен ли первый нетранзитивный пример? 1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4Я получаю A <B 17/36, B> C 19/36, C <A 16/36.
Тобия
@Tobia Ты забыл, что розыгрыши возможны. Вам также необходимо выяснить, как часто каждая игральная кость проигрывает другим, и проверить, не меньше ли это вероятности выигрыша: Да, А выигрывает у Б с 17/36, но А проигрывает с Б только с 16/36, поэтому А побеждает Б Аналогично, C выигрывает у A с 16/36, как вы сказали, но C проигрывает с A только с 14/36, поэтому C выигрывает у A.
Мартин Эндер

Ответы:

5

Dyalog APL, 107 100 байт

{({+/×+/¨,¨×⍵∘.-¨1⌽⍵}{3≠|a←⍺⍺⍵:1⋄a=b←⍺⍺∘.+⍨¨⍵:2⋄3+a=-b}⍵)⊃(⊂'none'),'strongly '⍬'Grime-',¨⊂'nontransitive'}

{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}

(Спасибо @Tobia за это более простое, короткое и лучшее решение)

Основы:

  • назначение

  • разделитель операторов

  • {} лямбда-форма

  • ⍺⍵ левый и правый аргумент

  • A:Bохранник («если Aпотом вернуться B»)

Tявляется функцией, которая возвращает 3, если A бьет B, B бьет C, а C бьет A; -3, если с точностью до наоборот; и что-то среднее между прочим. В деталях:

  • 1⌽⍵это одно вращение . Если ABC, вращение BCA.

  • ∘.-вычисляет таблицу вычитания между двумя векторами ( 1 2...10 ∘.× 1 2...10это будет таблица умножения, которую мы знаем из школы). Мы применяем это между каждым ( ¨) элементом и соответствующим элементом в 1⌽⍵.

  • × знак всех чисел в таблицах вычитания

  • ∊¨ сплющить каждый стол

  • +/¨и подвести итог. Теперь у нас есть три числа, которые представляют сальдо: количество выигрышных минус проигрышных дел для каждого из A против B, B против C, C против A.

  • × подпись тех

  • +/ сумма

Затем разберитесь со случаями по очереди:

  • 3≠|S←T⍵:'none'если T⍵абсолютное значение не равно 3, вернуть «нет»

  • N←'nontransitive' нам нужно это слово много

  • S=D←T∘.+⍨¨⍵:'strongly ',Nвычислить Tдля пар костей ( ∘.+⍨¨⍵← → ⍵((∘.+)¨)⍵) и вернуть «сильно ...», если все еще сохраняются те же отношения между ABC

  • S=-D:'Grime-',N Gri «Грязь», если отношения в противоположных направлениях

  • N если все остальное терпит неудачу, только "нетранзитивный"

СПП
источник
1
Ты подтолкнул меня на это! Я работал над этой проблемой 3 дня назад, но потом я перестал писать свой ответ. В любом случае, он слишком похож на ваш, поэтому я просто опубликую его здесь. Это немного короче на 100 символов:{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
Tobia
@ MartinBüttner: правильный термин в заголовке - «символы», потому что количество байтов будет варьироваться в зависимости от кодировки, используемой для кодирования символов APL. Традиционно они были просто закодированы в верхней половине 8-битных байтов после ASCII. В настоящее время мы используем UTF-8, но старые кодировки по-прежнему полезны ... главным образом для уменьшения количества байтов до количества символов при игре в гольф!
Tobia
@Tobia В коде гольф короче козыри, так что вы выиграли! Я не очень знаком с гольф-этикетом, но я думаю, что вы должны опубликовать его как отдельный ответ, поскольку он существенно отличается, и вы пришли к нему независимо.
NNN
@Tobia Я тоже предпочитаю считать в символах, но если подразумевается классическая кодировка, тогда байты = символы, так что, возможно, это не имеет большого значения, как мы их называем ...
ngn
@ Tobia Ну, определенно бесполезно указывать количество символов в вызове, который набирается в байтах. Однако никто никогда не говорил, что мы выигрываем в байтах UTF-8. На самом деле тег wiki явно говорит о том, что для символов за пределами диапазона ASCII можно использовать другую существующую кодировку. И у APL есть своя собственная кодовая страница, поэтому весь набор символов помещается в байте. Политика PPCG заключается в использовании этой кодовой страницы для подсчета APL - вряд ли справедливо наказывать APL за то, что он старше ASCII.
Мартин Эндер
13

Python 2, 269

Вот миленькое выражение, которое оценивает функцию. Он принимает три списка целых чисел. Проходит все тестовые случаи.

lambda A,B,C,w=lambda A,B:cmp(sum(cmp(a,b)for a in A for b in B),0),x=lambda A,B:cmp(sum(cmp(a+c,b+d)for a in A for b in B for c in A for d in B),0): (w(A,B)==w(B,C)==w(C,A)!=0)*((x(A,B)==x(B,C)==x(C,A))*["","strongly ","Grime-"][x(A,B)*w(A,B)]+"nontransitive")or"none"
feersum
источник
2

J - 311 257 байт

Обновление (13 января 2015 г.):

g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
'none'([`]@.((a g b)*(b g c)*c g a))((''([`]@.((b h a)*(c h b)*a h c))'Grime-')([`]@.((a h b)*(b h c)*c h a))'strongly '),'nontransitive'
)

Пояснение: Используя Gerunds, упростите if.s до @.s.

Старая версия:

Сначала попробуйте как кодирование в J, так и гольф.

g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
if. (a g b)*(b g c)*c g a do.
if. (a h b)*(b h c)*c h a do.
'strongly nontransitive'
elseif. (b h a)*(c h b)*a h c do.
'Grime-nontransitive'
elseif. do.
'nontransitive'
end.
else.
'none'
end.
)

Запустите его, используя синтаксис, подобный следующему (дополнительные пробелы для ясности):

f 3 6 $          1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

Объяснение:

gопределяется как диада с двумя массивами, которая сообщает, что если первая кость бьет вторые кости
h, определяется как диада с двумя массивами, которая сообщает, если два броска и сумма суммируются, будет ли первая кость бить вторую
f - это монада, которая берет таблицу и возвращает строку с правильный ответ

Редактировать: Исправить ошибку в нетранзитивном состоянии (замена ,на *)

Джей Босамия
источник
Буду рад любым предложениям по улучшению. :)
Джей Босамия
@ MartinBüttner, я изначально пробовал это, но не знал, как объединить несколько строк (или предложений, как это известно в J), не увеличивая длину кода гораздо больше ... изучение «gerunds» заставило меня сделать много предложений в одно, что также приводит к сокращению кода ...
Джей Босамия
1

Pyth 129 133

Lmsd^b2Msmsm>bkGHDPNK-ghNeNgeNhNR?^tZ<KZKZAGHmsdCm,PkP,yhkyekm,@Qb@QhbUQ?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

Попробуйте это здесь , или, по крайней мере, вы могли бы, но онлайн evalне похоже списки списков :( Если вы хотите попробовать это там, вручную сохраните список из 3 кубиков в переменную, не используемую программой, а затем замените все экземпляры Qс этой переменной. Пример инициализации:

J[[3 3 3 3 3 6)[2 2 2 5 5 5)[1 4 4 4 4 4))

Это проходит все тестовые задания Мартина, у меня нет сердца пройти через все дела Питера: P

Пояснение (это будет глупо)

Lmsd^b2

Довольно просто, делает функцию, yкоторая возвращает сумму каждой декартовой пары значений в итерируемом. Эквивалент: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). Это используется для создания многогранных кубиков, которые имитируют бросание обычных кубиков дважды.

Msmsm>bkGH

Определяет функцию gиз 2 аргументов, которая возвращает, сколько раз кубик бьет другого. Эквивалент def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).

DPNK-ghNeNgeNhNR?^tZ<KZKZ

Определяет функцию, Pкоторая принимает список из двух кубиков в качестве аргумента. Возвращает -1, если первый кубик «проигрывает», 0 за ничью и 1, если первый кубик «выигрывает». Эквивалентно:

def P(N):
 K=g(N[0],N[-1]) - g(N[-1],N[0])
 return -1**(K<0) if K else 0

Назначения AGHдействуют как присваивание Python с двумя кортежами. по существуG,H=(result)

msdCm,PkP,yhkyekm,@Qb@QhbUQ

Собираюсь объяснить задом наперед по картам. m,@Qb@QhbUQперебирает b = 0..2 и генерирует 2 набора игральных костей с индексом b и индексом b + 1. Это дает нам кости (A, B), (B, C), (C, A) (pyth автоматически изменяет индексы по длине списка).

Затем m,PkP,yhkyekвыполняется итерация по результату предыдущей карты с каждой парой костей, сохраняемой в k за каждый прогон. Возвращает tuple(P(k),P(tuple(y(k[0]),y(k[-1]))))для каждого значения. Это сводится к `((A бьет B ?, 2 * A бьет 2 * B), (B бьет C?, 2 * B бьет ..)).

Наконец, msdCсуммирует значения предыдущей карты после ее архивирования. Zip вызывает все значения «биений» одиночных костей в первом кортеже и значения двойных костей во втором.

?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

Грубая вещь, которая распечатывает результаты. Если G = 0 или не делится на 3, это ловит бот +/- 3, ( |!G%G3), печатает none, в противном случае выводит сумму списка follwing: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. Я думаю, что логические значения довольно очевидны в отношении определений в вопросе. Обратите внимание, что здесь G не может быть нулем, так как это поймано предыдущей проверкой.

FryAmTheEggman
источник
1

J (204)

Слишком долго, вероятно, можно много играть в гольф, имея более эффективную систему для выбора правильной струны.

f=:3 :'(<,>)/"1+/"2>"1,"2(<,>)/L:0{(,.(1&|.))y'
n=:'nontransitive'
d=:3 :0
if.+/*/a=.f y do.+/*/b=.f<"1>,"2+/L:0{,.~y if.a-:b do.'strongly ',n elseif.a-:-.b do.'Grime-',n elseif.do.n end.else.'none'end.
)
ɐɔıʇǝɥʇuʎs
источник
1

Матлаб (427)

Это не так уж и мало, и я уверен, что это может быть гораздо больше, я просто попытался решить эту задачу, потому что я думал, что это было очень забавное задание, поэтому спасибо @ MartinBüttner за создание этого задания !

a=input();b=input();c=input();
m = 'non';l=@(a)ones(numel(a),1)*a;n=@(a,b)sum(sum(l(a)>l(b)'));g=@(a,b)n(a,b)>n(b,a);s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
x=s(a,b,c);y=s(a,c,b);if x~=3 && y~=3;m=[m,'e'];else m=[m,'transitive'];o=ones(6,1);a=o*a;a=a+a';a=a(:)';b=o*b;b=b+b';b=b(:)';c=o*c;c=c+c';c=c(:)';u=s(a,b,c);
v=s(a,c,b);if u==3|| v==3;if x==3&&u==3 || y==3&&v==3 m=['strongly ',m];else m=['Grime-',m];end;end;end;disp(m);

Вот полный код с некоторыми комментариями, если вы хотите попытаться понять, что происходит. Я включил несколько тестовых примеров зайца и исключил входные команды:

%nontransitive
% a = [1 2 2 4 6 6];
% b = [1 2 3 5 5 5];
% c = [2 3 4 4 4 4];

%none
% a = [1 2 3 4 5 6];
% b = [6 5 4 3 2 1];
% c = [1 3 5 2 4 6];

%grime nontransitive
% a = [3 3 3 3 3 6];
% b = [2 2 2 5 5 5];
% c = [1 4 4 4 4 4];

%strongly nontransitive
% a = [2 2 2 5 5 5];
% b = [2 3 3 3 5 5];
% c = [1 1 4 5 5 5];

m = 'non';

l=@(a)ones(numel(a),1)*a;
n=@(a,b)sum(sum(l(a)>l(b)'));
%input as row vector, tests whether the left one beats the right one:
g=@(a,b)n(a,b)>n(b,a);
s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
%if one of those x,y has the value 3, we'll have intransitivity
x=s(a,b,c); 
y=s(a,c,b);
if x~=3 && y~=3 %nontransitive
    m=[m,'e'];
else %transitive
    m=[m,'transitive'];
    o=ones(6,1);
    a=o*a;a=a+a';a=a(:)'; %all possible sums of two elements of a
    b=o*b;b=b+b';b=b(:)';
    c=o*c;c=c+c';c=c(:)';
    u=s(a,b,c);
    v=s(a,c,b);

    %again: is u or v equal to 3 then we have transitivity
    if u==3 || v==3 %grime OR strongly
        % if e.g. x==3 and u==3 then the 'intransitivity' is in the same
        % 'order', that means stronlgy transitive
        if x==3 && u==3 || y==3 && v==3%strongly
            m=['strongly ',m];
        else %grime
            m=['Grime-',m];
        end   
    end
end

disp(m);
flawr
источник
Разве это не короче, если вы читаете один массив, input()а затем назначаете три элемента a,b,c? Кроме того , пожалуйста , используйте точные строки в спецификации ( none, nontransitiveи капитализированной Grime) ... должен , вероятно , даже сохранить вам байты.
Мартин Эндер
Да, это будет, вероятно, короче, я посмотрю на это. Строки будут именно теми, которые я только что удалил, dispкоманды в длинной версии, они были только для тестирования программы, но окончательное сообщение сохраняется в m. И я исправил G.
flawr
0

JavaScript - 276 байт

function(l){r=function(i){return l[i][Math.random()*6|0]};p=q=0;for(i=0;j=(i+1)%3,i<3;++i)for(k=0;k<1e5;++k){p+=(r(i)>r(j))-(r(i)<r(j));q+=(r(i)+r(i)>r(j)+r(j))-(r(i)+r(i)<r(j)+r(j))}alert((a=Math.abs)(p)>5e3?((a(q)>5e3?p*q>0?'strongly ':'Grime-':'')+'nontransitive'):'none')}

Я не очень хорош в вероятности, поэтому, чтобы быть уверенным в моих результатах, я предпочитаю просто бросать кости сотни тысяч раз.

Выражение вычисляется как функция, которая должна вызываться только с одним аргументом: массивом из трех массивов целых чисел. Проверьте Fiddle, чтобы иметь возможность запустить код самостоятельно.

Вот негольфированная версия:

function (diceList) {
    var getRandomValue = function (idDie) {
        return diceList[idDie][Math.floor(Math.random() * 6)];
    };

    var probabilitySimpleThrow = 0;
    var probabilityDoubleThrow = 0;

    for (var idDieA = 0; idDieA < 3; ++idDieA)
    {
        var idDieB = (idDieA + 1) % 3;
        for (var idThrow = 0; idThrow < 1e5; ++idThrow)
        {
            probabilitySimpleThrow += getRandomValue(idDieA) > getRandomValue(idDieB);
            probabilitySimpleThrow -= getRandomValue(idDieA) < getRandomValue(idDieB);

            probabilityDoubleThrow += getRandomValue(idDieA) + getRandomValue(idDieA) > getRandomValue(idDieB) + getRandomValue(idDieB);
            probabilityDoubleThrow -= getRandomValue(idDieA) + getRandomValue(idDieA) < getRandomValue(idDieB) + getRandomValue(idDieB);
        }
    }

    if (Math.abs(probabilitySimpleThrow) > 5e3) {
        if (Math.abs(probabilityDoubleThrow) > 5e3) {
            if (probabilitySimpleThrow * probabilityDoubleThrow > 0) {
                var result = 'strongly ';
            }
            else {
                var result = 'Grime-';
            }
        }
        else {
            var result = '';
        }

        result += 'nontransitive';
    }
    else {
        var result = 'none';
    }

    alert(result);
}
Черная дыра
источник
Хм, я не думаю, что это действительно в духе проблемы. Вы в основном превратили его из задачи теории вероятностей в задачу статистики. ;) ... Вместо случайных бросков вы можете просто перечислить все возможные броски ровно один раз. Это даст вам точные результаты (и будет работать намного быстрее).
Мартин Эндер
Я проверю, приведет ли это к более лаконичному сценарию. Спасибо за совет :).
Blackhole