31
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I had totally forgotten about non-transitive dice. Thank you :) \$\endgroup\$ – npst Jan 9 '15 at 11:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Tobia Jan 13 '15 at 0:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 13 '15 at 9:23
5
\$\begingroup\$

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"

\$\endgroup\$
  • 1
    \$\begingroup\$ 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} \$\endgroup\$ – Tobia Jan 16 '15 at 0:10
  • \$\begingroup\$ @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! \$\endgroup\$ – Tobia Jan 16 '15 at 0:14
  • \$\begingroup\$ @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. \$\endgroup\$ – ngn Jan 16 '15 at 1:03
  • \$\begingroup\$ @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... \$\endgroup\$ – ngn Jan 16 '15 at 1:07
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 16 '15 at 8:00
13
\$\begingroup\$

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"
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I would love any suggestions for improvement. :) \$\endgroup\$ – Jay Bosamiya Jan 10 '15 at 22:56
  • \$\begingroup\$ @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... \$\endgroup\$ – Jay Bosamiya Jan 13 '15 at 16:41
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
)
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Jan 8 '15 at 19:53
  • \$\begingroup\$ 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. \$\endgroup\$ – flawr Jan 8 '15 at 20:05
0
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Hm, I don't think this is really in the spirit of the challenge. You basically turned it from a probability theory challenge into a statistics challenge. ;) ... Instead of random throws, you could simply enumerate all possible throws exactly once. That would give you the exact results (and would run much faster). \$\endgroup\$ – Martin Ender Jan 8 '15 at 14:43
  • \$\begingroup\$ I'll check if this leads to a more concise script. Thanks for your advice :). \$\endgroup\$ – Blackhole Jan 8 '15 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.