Are these dice nontransitive?

Question

Nontransitive dice are nice little toys that defy our intuition in probability theory. We'll need a few definitions for this challenge:

Consider two dice A and B which are thrown at the same time. We say that A beats B if the probability of A showing a larger number than B is strictly greater than the probability of B showing a larger number than A.

Now consider a set of three dice, with labels A, B, C. Such a set of dice is called nontransitive if

• either A beats B, B beats C and C beats A
• or C beats B, B beats A and A beats C.

As one of my favourite examples, consider the Grime dice, which have the following sides:

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

^{Interestingly, the mean of each die is 3.5, just like a regular die.}

One can show that:

• A beats B with a probability of 7/12.
• B beats C with a probability of 7/12.
• C beats A with a probability of 25/36.

Now these particular dice are even weirder. If we roll each die twice and add up the results, the order of which beats which gets reversed:

• B beats A with a probability of 85/144.
• C beats B with a probability of 85/144.
• A beats C with a probability of 671/1296.

Let's call a set of dice with this property Grime-nontransitive.

On the other hand, if the dice retain their original cycle when using two throws, we call them strongly nontransitive. (If there is no cycle at all for two throws, we simply call them nontransitive.)

The Challenge

Given three six-sided dice, determine which of the above properties this set has, and output one of the following strings: none, nontransitive, Grime-nontransitive, strongly nontransitive.

You may write a program or function, take input via STDIN, command-line argument, prompt or function argument, and write the result to STDOUT or return it as a string.

You may assume that all sides are non-negative integers. You cannot assume that the sides or the dice are in any particular order. You can take input in any convenient list or string format.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

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

If you want to test your code even more thoroughly, Peter Taylor was kind enough to write a reference implementation, which classified all ~5000 sets of dice with sides 1 to 6 and a mean of 3.5. Pastebin link

Answer 1

Dyalog APL, 107 100 bytes

{({+/×+/¨,¨×⍵∘.-¨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}

(Thanks @Tobia for this simpler, shorter, better solution)

Basics:

• ← assignment

• ⋄ statement separator

• {} lambda form

• ⍺⍵ left and right argument

• A:B guard ("if A then return B")

T is a function that returns 3 if A beats B, B beats C, and C beats A; -3 if the exact opposite is the case; and something inbetween otherwise. In detail:

• 1⌽⍵ is the one-rotation of ⍵. If ⍵ is ABC, the rotation is BCA.

• ∘.- computes a subtraction table between two vectors (1 2...10 ∘.× 1 2...10 would be the multiplication table we know from school). We apply this between each (¨) item of ⍵ and its corresponding item in 1⌽⍵.

• × signum of all numbers in the subtraction tables

• ∊¨ flatten each table

• +/¨ and sum it. We now have three numbers that represent balances: number of winning minus losing cases for each of A vs B, B vs C, C vs A.

• × signum of those

• +/ sum

Then handle the cases in turn:

• 3≠|S←T⍵:'none' if T⍵'s absolute value isn't 3, return 'none'

• N←'nontransitive' we'll need this word a lot

• S=D←T∘.+⍨¨⍵:'strongly ',N compute T for pairs of dice (∘.+⍨¨⍵ ←→ ⍵((∘.+)¨)⍵) and return "strongly..." if the same relationships among ABC still hold

• S=-D:'Grime-',N ⍝ "Grime" if the relationships are in the opposite directions

• N if all else fails, just "nontransitive"

Answer 2

Python 2, 269

Here's a nice little expression that evaluates to a function. It accepts three lists of integers. Passes all test cases.

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"

Answer 3

J - 311 257 bytes

Update (13 Jan 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'
)

Explanation: Using Gerunds, simplify the if.s to @.s.

Older version:

First try at both coding in J as well as golfing.

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.
)

Run it using a syntax similar to following (extra spaces for clarity):

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

Explanation:

g is defined as a diad taking two arrays that tells if first dice beats second dice
h is defined as a diad taking two arrays that tells if throwing twice and summing, does first dice beat second
f is a monad that takes a table and returns a string with the right answer

Edit: Fix a mistake in Grime-nontransitive condition (replacing , with *)

Answer 4

Matlab (427)

It is not that short and I am sure it can be golfed a lot more, I just tried to solve this challenge because I thought it was a very fun task, so thanks @MartinBüttner for creating this challenge!

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

Here the full length code with some comments if you want to try to understand what's going on. I included some test cases hare and excluced the input commands:

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

Answer 5

Pyth 129 133

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

Try it here, or at least you could, but the online eval doesn't seem to like lists of lists :( If you want to try it there, manually store a list of 3 dice into a variable not used by the program and then replace all instances of Q with that variable. A sample initialization:

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

This passes all of Martin's test cases, I haven't the heart go through all of Peter's cases :P

Explanation (this is gonna be a doozy)

Lmsd^b2

Pretty simple, makes a function y that returns the sum of each Cartesian pair of values in an iterable. Equivalent to: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). This is used to create many-sided dies that simulate throwing the regular dies twice.

Msmsm>bkGH

Defines a function g of 2 arguments that returns how many times a die beats another. Equivalent to def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).

DPNK-ghNeNgeNhNR?^tZ<KZKZ

Defines a funtion P that takes a list of two dice as its argument. This returns -1 if the first die 'loses', 0 for a tie and 1 if the first die 'wins'. Equivalent to:

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

The AGH assigns acts like a python 2-tuple assignment. Essentially G,H=(result)

msdCm,PkP,yhkyekm,@Qb@QhbUQ

Going to explain backwards through the maps. m,@Qb@QhbUQ iterates over b=0..2 and generates 2-tuples of dice with index b and index b+1. This gives us dice (A,B),(B,C),(C,A) (pyth automatically mods indexes by the length of the list).

Next, m,PkP,yhkyek iterates over the result of the previous map, with each dice pair being stored in k over each run. Returns tuple(P(k),P(tuple(y(k[0]),y(k[-1])))) for each value. That boils down to `((A beats B?, 2*A beats 2*B), (B beats C?, 2*B beats..)).

Finally, msdC sums the values of the previous map after it has been zipped. The zip causes all of the single dice 'beats' values in the first tuple, and the double dice values in the second.

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

A gross thing that prints out the results. If G is 0 or not divisible by 3, this catches bot +/- 3, (|!G%G3), prints none, otherwise prints the sum of the follwing list: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. I think the booleans are fairly self-explanatory with regard to the definitions in the question. Do note that G cannot be zero here, as that is caught by the previous check.

Answer 6

J (204)

Way too long, could probably be golfed a lot by having a more efficient system for picking the right string.

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.
)

Answer 7

JavaScript - 276 bytes

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')}

I'm not really good in probability, so to be sure of my results, I prefer to just throw the dice hundreds of thousands times.

The expression evaluates to a function, that should be called with only one argument: an array of three arrays of integers. Check the Fiddle to be able to run the code by yourself.

Here is the ungolfed version:

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