# Are these dice nontransitive?

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

– npst
Jan 9, 2015 at 11:00
• Is the first nontransitive example correct? 1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4 I'm getting A<B 17/36, B>C 19/36, C<A 16/36. Jan 13, 2015 at 0:14
• @Tobia You're forgetting that draws are possible. You also need to work out how often each dice loses against the others, and check if that's less than the winning probability: Yes A wins against B with 17/36, but A loses against B with only 16/36, so A beats B. Likewise, C wins against A with 16/36 as you said, but C loses against A with only 14/36, so C beats A. Jan 13, 2015 at 9:23

# 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"


# 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"

• You beat me to it! I was working on this problem 3 days ago, but then I stopped just short of writing my answer. It's too similar to yours anyways, so I'll just post it here. It's a bit shorter at 100 chars: {T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N} Jan 16, 2015 at 0:10
• @MartinBüttner: The correct term in the title is "characters", because the amount of bytes will vary depending on the charset used to encode the APL symbols. Traditionally they were just encoded in the upper half of 8-bit bytes, after ASCII. Nowadays we use UTF-8, but the old charsets are still useful… mainly to reduce the byte count to the character count when golfing! Jan 16, 2015 at 0:14
• @Tobia In code golf shorter trumps earlier, so you win! I'm not really familiar with golfing etiquette but I think you should post it as a separate answer as it's substantially different and you arrived at it independently.
– ngn
Jan 16, 2015 at 1:03
• @Tobia I prefer to count in characters, too, but if classic encoding is implied, then bytes=characters, so maybe it doesn't really matter much what we call them...
– ngn
Jan 16, 2015 at 1:07
• @Tobia Well it's definitely useless to supply the character count in a challenge that scores by bytes. However, no one ever said we're scoring in UTF-8 bytes. In fact the tag wiki explicitly says that a different existing encoding can be used for characters outside the ASCII range. And APL does have its own codepage so the entire character set does fit within a byte. The policy on PPCG is to use this codepage to count APL - it's hardly fair to punish APL for being older than ASCII. Jan 16, 2015 at 8:00

# 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 *)

• I would love any suggestions for improvement. :) Jan 10, 2015 at 22:56
• @MartinBüttner, I had initially tried that, but didn't know how to concatenate over several lines (or sentences, as it is known in J) without increasing code length much more... learning about "gerunds" led me to make the many sentences into one which ends up shortening the code as well... Jan 13, 2015 at 16:41

## 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,N[-1]) - g(N[-1],N)
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),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.

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


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

• Isn't it shorter if you read an array one input() and then assign the three elements to a,b,c? Also, please use the exact strings in the spec (none, nontransitive, and capitalised Grime)... should probably even save you bytes. Jan 8, 2015 at 19:53
• Yeah this would be probably shorter, I'll take a look at that. The strings will be exactly those I just removed the disp commands in the long version, they were just for testing the program, but the final message is stored in m. And I corrected the G. Jan 8, 2015 at 20:05

## 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';
}