Ces dés sont-ils non transitifs?

31

Les dés non transitifs sont de jolis petits jouets qui défient notre intuition en théorie des probabilités. Nous aurons besoin de quelques définitions pour ce défi:

Considérez deux dés A et B qui sont lancés en même temps. Nous disons que A bat B si la probabilité d' un montrant un plus grand nombre que B est strictement supérieure à la probabilité de B montrant un plus grand nombre que A .

Considérons maintenant un ensemble de trois dés, avec des étiquettes A , B , C . Un tel ensemble de dés est appelé non transitif si

  • soit A bat B , B bat C et C bat A
  • ou C vaut B , B bat A et A bat C .

Comme l'un de mes exemples préférés, considérez les dés Grime , qui ont les côtés suivants:

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

Fait intéressant, la moyenne de chaque dé est de 3,5, tout comme un dé ordinaire.

On peut montrer que:

  • A bat B avec une probabilité de 7/12.
  • B bat C avec une probabilité de 7/12.
  • C bat A avec une probabilité de 25/36.

Maintenant, ces dés particuliers sont encore plus étranges. Si nous lançons chaque dé deux fois et additionnons les résultats, l'ordre des battements qui s'inverse:

  • B bat A avec une probabilité de 85/144.
  • C bat B avec une probabilité de 85/144.
  • A bat C avec une probabilité de 671/1296.

Appelons un ensemble de dés avec cette propriété Grime-nonransitive .

En revanche, si les dés conservent leur cycle d'origine lors de l'utilisation de deux lancers, nous les appelons fortement non transitoires . (S'il n'y a pas de cycle du tout pour deux lancers, nous les appelons simplement non transitoires .)

Le défi

Compte tenu de trois dés à six faces, déterminer lequel des propriétés ci - dessus cet ensemble a, et une sortie des chaînes suivantes: none, nontransitive, Grime-nontransitive, strongly nontransitive.

Vous pouvez écrire un programme ou une fonction, prendre une entrée via STDIN, un argument de ligne de commande, une invite ou un argument de fonction, et écrire le résultat dans STDOUT ou le renvoyer sous forme de chaîne.

Vous pouvez supposer que tous les côtés sont des entiers non négatifs. Vous ne pouvez pas supposer que les côtés ou les dés sont dans un ordre particulier. Vous pouvez prendre des entrées dans n'importe quelle liste ou format de chaîne pratique.

Il s'agit du code golf, donc la réponse la plus courte (en octets) l'emporte.

Cas de test

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

Si vous voulez tester votre code encore plus en profondeur, Peter Taylor a eu la gentillesse d'écrire une implémentation de référence, qui a classé tous les ~ 5000 ensembles de dés avec les côtés 1 à 6 et une moyenne de 3,5. Lien Pastebin

Martin Ender
la source
J'avais totalement oublié les dés non transitifs. Merci :)
npst
Le premier exemple non transitif est-il correct? 1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4Je reçois A <B 17/36, B> C 19/36, C <A 16/36.
Tobia
@Tobia Vous oubliez que les tirages sont possibles. Vous devez également déterminer la fréquence à laquelle chaque dé perd contre les autres et vérifier si c'est moins que la probabilité de gagner: Oui A gagne contre B avec 17/36, mais A perd contre B avec seulement 16/36, donc A bat B De même, C gagne contre A avec 16/36 comme vous l'avez dit, mais C perd contre A avec seulement 14/36, donc C bat A.
Martin Ender

Réponses:

5

Dyalog APL, 107100 octets

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

(Merci @Tobia pour cette solution plus simple, plus courte et meilleure)

Bases:

  • affectation

  • séparateur d'instructions

  • {} forme lambda

  • ⍺⍵ argument gauche et droit

  • A:Bgardien ("si Aalors reviens B")

Test une fonction qui renvoie 3 si A bat B, B bat C et C bat A; -3 si l'exact opposé est le cas; et quelque chose entre les deux autrement. En détail:

  • 1⌽⍵est la rotation d'une . Si est ABC, la rotation est BCA.

  • ∘.-calcule une table de soustraction entre deux vecteurs ( 1 2...10 ∘.× 1 2...10serait la table de multiplication que nous connaissons de l'école). Nous appliquons cela entre chaque ¨élément ( ) de et son élément correspondant dans 1⌽⍵.

  • × signum de tous les nombres dans les tables de soustraction

  • ∊¨ aplatir chaque table

  • +/¨et résumer. Nous avons maintenant trois chiffres qui représentent les soldes: nombre de cas gagnants moins cas perdants pour chacun des A contre B, B contre C, C contre A.

  • × signum de ceux

  • +/ somme

Ensuite, manipulez les cas à tour de rôle:

  • 3≠|S←T⍵:'none'si T⍵la valeur absolue n'est pas 3, retourne 'aucun'

  • N←'nontransitive' nous aurons besoin de ce mot beaucoup

  • S=D←T∘.+⍨¨⍵:'strongly ',Ncalculer Tpour des paires de dés ( ∘.+⍨¨⍵← → ⍵((∘.+)¨)⍵) et retourner "fortement ..." si les mêmes relations entre ABC tiennent toujours

  • S=-D:'Grime-',N ⍝ "Grime" si les relations sont dans des directions opposées

  • N si tout le reste échoue, juste "non transitoire"

ngn
la source
1
Tu m'as battu! Je travaillais sur ce problème il y a 3 jours, mais j'ai arrêté juste d'écrire ma réponse. Il est trop similaire au vôtre de toute façon, je vais donc le poster ici. C'est un peu plus court à 100 caractères:{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
Tobia
@ MartinBüttner: Le terme correct dans le titre est "caractères", car la quantité d'octets varie en fonction du jeu de caractères utilisé pour coder les symboles APL. Traditionnellement, ils étaient simplement codés dans la moitié supérieure des octets 8 bits, après ASCII. De nos jours, nous utilisons UTF-8, mais les anciens jeux de caractères sont toujours utiles… principalement pour réduire le nombre d'octets au nombre de caractères lors du golf!
Tobia
@Tobia In code golf atouts plus courts plus tôt, donc vous gagnez! Je ne connais pas vraiment l'étiquette du golf, mais je pense que vous devriez l'afficher comme une réponse distincte car elle est substantiellement différente et vous y êtes parvenue indépendamment.
ngn
@Tobia Je préfère également compter en caractères, mais si l'encodage classique est implicite, alors octets = caractères, donc peut-être que peu importe ce que nous les appelons ...
ngn
@Tobia Eh bien, il est certainement inutile de fournir le nombre de caractères dans un défi qui marque par octets. Cependant, personne n'a jamais dit que nous marquions en octets UTF-8. En fait, le wiki wiki indique explicitement qu'un encodage existant différent peut être utilisé pour les caractères en dehors de la plage ASCII. Et APL a sa propre page de code, donc l'ensemble du jeu de caractères tient dans un octet. La politique sur PPCG est d'utiliser cette page de code pour compter APL - il n'est pas juste de punir APL pour être plus ancien que ASCII.
Martin Ender
13

Python 2, 269

Voici une jolie petite expression qui évalue une fonction. Il accepte trois listes d'entiers. Réussit tous les cas de test.

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
la source
2

J - 311 257 octets

Mise à jour (13 janvier 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'
)

Explication: À l'aide de Gerunds, simplifiez le if.s en @.s.

Ancienne version:

Essayez d'abord le codage en J ainsi que le golf.

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

Exécutez-le en utilisant une syntaxe similaire à la suivante (espaces supplémentaires pour plus de clarté):

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

Explication:

gest définie comme une diade prenant deux tableaux qui indique si le premier dé bat le deuxième dé
hest définie comme une diade prenant deux tableaux qui indique si lancer deux fois et additionner, le premier dé bat-il en second
fest une monade qui prend une table et renvoie une chaîne avec le bonne réponse

Edit: Correction d'une erreur dans un état non transitoire de la crasse (remplacement ,par *)

Jay Bosamiya
la source
J'adorerais toute suggestion d'amélioration. :)
Jay Bosamiya
@ MartinBüttner, j'avais d'abord essayé cela, mais je ne savais pas comment concaténer sur plusieurs lignes (ou phrases, comme on le sait en J) sans augmenter la longueur de code beaucoup plus ... l'apprentissage des "gérondifs" m'a amené à faire le de nombreuses phrases en une qui finit également par raccourcir le code ...
Jay Bosamiya
1

Pyth 129 133

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

Essayez-le ici , ou du moins vous le pourriez, mais la ligne evalne semble pas aimer les listes de listes :( Si vous voulez l'essayer, stockez manuellement une liste de 3 dés dans une variable non utilisée par le programme, puis remplacez toutes les instances de Qavec cette variable. Un exemple d'initialisation:

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

Cela passe tous les cas de test de Martin, je n'ai pas le cœur de passer en revue tous les cas de Peter: P

Explication (ça va être un doozy)

Lmsd^b2

Assez simple, crée une fonction yqui retourne la somme de chaque paire de valeurs cartésiennes dans un itérable. Équivalent à: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). Ceci est utilisé pour créer des matrices à plusieurs côtés qui simulent le lancement des matrices régulières deux fois.

Msmsm>bkGH

Définit une fonction gde 2 arguments qui renvoie le nombre de fois qu'un dé en bat un autre. Équivalent à def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).

DPNK-ghNeNgeNhNR?^tZ<KZKZ

Définit une fonction Pqui prend comme argument une liste de deux dés. Cela renvoie -1 si le premier dé «perd», 0 pour une égalité et 1 si le premier dé «gagne». Équivalent à:

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

L' AGHaffectation agit comme une affectation de 2 tuples python. EssentiellementG,H=(result)

msdCm,PkP,yhkyekm,@Qb@QhbUQ

Va expliquer en arrière à travers les cartes. m,@Qb@QhbUQitère sur b = 0..2 et génère 2 tuples de dés d'index b et d'index b + 1. Cela nous donne les dés (A, B), (B, C), (C, A) (pyth modifie automatiquement les index selon la longueur de la liste).

Ensuite, m,PkP,yhkyekitère le résultat de la carte précédente, chaque paire de dés étant stockée dans k au cours de chaque manche. Renvoie tuple(P(k),P(tuple(y(k[0]),y(k[-1]))))pour chaque valeur. Cela se résume à `((A bat B?, 2 * A bat 2 * B), (B bat C?, 2 * B bat ..)).

Enfin, msdCadditionne les valeurs de la carte précédente après sa fermeture. Le zip provoque toutes les valeurs de battements de dés simples dans le premier tuple, et les valeurs de dés doubles dans le second.

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

Une chose grossière qui imprime les résultats. Si G est 0 ou non divisible par 3, ce bot prises +/- 3, ( |!G%G3), impressions none, sinon imprime la somme de la liste des follwing: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. Je pense que les booléens sont assez explicites en ce qui concerne les définitions de la question. Notez que G ne peut pas être nul ici, car cela a été détecté lors de la vérification précédente.

FryAmTheEggman
la source
1

J (204)

Beaucoup trop long, pourrait probablement être joué beaucoup en ayant un système plus efficace pour choisir la bonne corde.

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
la source
1

Matlab (427)

Ce n'est pas si court et je suis sûr qu'il peut être joué beaucoup plus, j'ai juste essayé de résoudre ce défi parce que je pensais que c'était une tâche très amusante, alors merci @ MartinBüttner d' avoir créé ce défi!

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

Voici le code complet avec quelques commentaires si vous voulez essayer de comprendre ce qui se passe. J'ai inclus des cas de test de lièvre et exclu les commandes d'entrée:

%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
la source
N'est-il pas plus court si vous en lisez un tableau input()puis attribuez les trois éléments à a,b,c? En outre, s'il vous plaît utiliser les chaînes exactes dans les spécifications ( none, nontransitiveet capitalisé Grime) ... devrait probablement même vous sauver octets.
Martin Ender
Oui, ce serait probablement plus court, je vais y jeter un œil. Les chaînes seront exactement celles dans lesquelles je viens de supprimer les dispcommandes de la version longue, elles étaient juste pour tester le programme, mais le message final est stocké dans m. Et j'ai corrigé le G.
flawr
0

JavaScript - 276 octets

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

Je ne suis pas vraiment bon en probabilité, donc pour être sûr de mes résultats, je préfère lancer les dés des centaines de milliers de fois.

L'expression est évaluée en fonction, qui doit être appelée avec un seul argument: un tableau de trois tableaux d'entiers. Vérifiez le Fiddle pour pouvoir exécuter le code par vous-même.

Voici la version non golfée:

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);
}
Trou noir
la source
Hm, je ne pense pas que ce soit vraiment dans l'esprit du défi. Vous l'avez essentiellement transformé d'un défi de théorie des probabilités en un défi de statistiques. ;) ... Au lieu de lancers aléatoires, vous pouvez simplement énumérer tous les lancers possibles exactement une fois. Cela vous donnerait les résultats exacts (et fonctionnerait beaucoup plus rapidement).
Martin Ender
Je vais vérifier si cela conduit à un script plus concis. Merci pour vos conseils :).
Blackhole