¿Son estos dados no transitivos?

31

Los dados no transitivos son pequeños y bonitos juguetes que desafían nuestra intuición en la teoría de la probabilidad. Necesitaremos algunas definiciones para este desafío:

Considere dos dados A y B que se lanzan al mismo tiempo. Decimos que A es mejor que B si la probabilidad de un mostrando un número mayor que B es estrictamente mayor que la probabilidad de B que muestra un número mayor que A .

Consideremos ahora un conjunto de tres dados, con las etiquetas A , B , C . Tal conjunto de dados se llama no transitivo si

  • o bien A es mejor que B , B es mejor que C y C late A
  • o C late B , B es mejor que A y A late C .

Como uno de mis ejemplos favoritos, considere los dados Grime , que tienen los siguientes lados:

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

Curiosamente, la media de cada dado es 3.5, al igual que un dado normal.

Uno puede demostrar que:

  • A vence a B con una probabilidad de 7/12.
  • B vence a C con una probabilidad de 7/12.
  • C vence a A con una probabilidad de 25/36.

Ahora estos dados en particular son aún más extraños. Si tiramos cada dado dos veces y sumamos los resultados, cuyo orden es el que se invierte:

  • B vence a A con una probabilidad de 85/144.
  • C vence a B con una probabilidad de 85/144.
  • A vence a C con una probabilidad de 671/1296.

Llamemos a un juego de dados con esta propiedad Grime-nontransitive .

Por otro lado, si los dados conservan su ciclo original cuando usan dos lanzamientos, los llamamos fuertemente no transitivos . (Si no hay ningún ciclo para dos lanzamientos, simplemente los llamamos no transitivos ).

El reto

Dada tres dados de seis caras, determinar cuál de las propiedades anteriores de este conjunto tiene, y una salida de las siguientes cadenas: none, nontransitive, Grime-nontransitive, strongly nontransitive.

Puede escribir un programa o función, tomar datos a través de STDIN, argumento de línea de comandos, argumento de solicitud o función, y escribir el resultado en STDOUT o devolverlo como una cadena.

Puede suponer que todos los lados son enteros no negativos. No puedes asumir que los lados o los dados están en un orden particular. Puede tomar la entrada en cualquier lista conveniente o formato de cadena.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

Casos de prueba

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 desea probar su código aún más a fondo, Peter Taylor tuvo la amabilidad de escribir una implementación de referencia, que clasificó todos los ~ 5000 juegos de dados con los lados 1 a 6 y una media de 3.5. Enlace de Pastebin

Martin Ender
fuente
Me había olvidado por completo de los dados no transitivos. Gracias :)
npst
¿Es correcto el primer ejemplo no transitivo? 1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4Estoy obteniendo A <B 17/36, B> C 19/36, C <A 16/36.
Tobia
@Tobia Estás olvidando que los sorteos son posibles. También debe determinar la frecuencia con la que cada dado pierde contra los demás, y verificar si es menor que la probabilidad de ganar: Sí A gana contra B con 17/36, pero A pierde contra B con solo 16/36, por lo que A vence a B Del mismo modo, C gana contra A con 16/36 como dijiste, pero C pierde contra A con solo 14/36, por lo que C vence a A.
Martin Ender

Respuestas:

5

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}

(Gracias @Tobia por esta solución más simple, más corta y mejor)

Lo esencial:

  • asignación

  • separador de declaraciones

  • {} forma lambda

  • ⍺⍵ argumento izquierdo y derecho

  • A:Bguardia ("si Aluego regresa B")

Tes una función que devuelve 3 si A vence a B, B vence a C y C vence a A; -3 si el caso es exactamente lo contrario; y algo intermedio de lo contrario. En detalle:

  • 1⌽⍵es la rotación de uno . Si es ABC, la rotación es BCA.

  • ∘.-calcula una tabla de resta entre dos vectores ( 1 2...10 ∘.× 1 2...10sería la tabla de multiplicar que conocemos de la escuela). Aplicamos esto entre cada ( ¨) elemento de y su elemento correspondiente en 1⌽⍵.

  • × signo de todos los números en las tablas de resta

  • ∊¨ aplanar cada mesa

  • +/¨y resumirlo. Ahora tenemos tres números que representan saldos: número de casos ganadores menos perdedores para cada uno de A vs B, B vs C, C vs A.

  • × signo de aquellos

  • +/ suma

Luego maneje los casos por turno:

  • 3≠|S←T⍵:'none'si T⍵el valor absoluto no es 3, devuelve 'none'

  • N←'nontransitive' necesitaremos mucho esta palabra

  • S=D←T∘.+⍨¨⍵:'strongly ',Ncalcular Tpara pares de dados ( ∘.+⍨¨⍵← → ⍵((∘.+)¨)⍵) y devolver "fuertemente ..." si las mismas relaciones entre ABC aún se mantienen

  • S=-D:'Grime-',N ⍝ "Grime" si las relaciones están en direcciones opuestas

  • N si todo lo demás falla, simplemente "no transitivo"

ngn
fuente
1
¡Me ganaste! Estaba trabajando en este problema hace 3 días, pero luego me detuve antes de escribir mi respuesta. De todos modos, es muy similar al tuyo, así que lo publicaré aquí. Es un poco más corto con 100 caracteres:{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
Tobia
@ MartinBüttner: El término correcto en el título es "caracteres", porque la cantidad de bytes variará dependiendo del juego de caracteres utilizado para codificar los símbolos APL. Tradicionalmente, solo se codificaban en la mitad superior de los bytes de 8 bits, después de ASCII. Hoy en día utilizamos UTF-8, pero los viejos juegos de caracteres siguen siendo útiles ... ¡principalmente para reducir el recuento de bytes al recuento de caracteres cuando se juega al golf!
Tobia
@Tobia En el código de golf triunfos más cortos antes, ¡así que ganas! No estoy muy familiarizado con la etiqueta del golf, pero creo que debería publicarlo como una respuesta separada, ya que es sustancialmente diferente y llegó a él de forma independiente.
ngn
@Tobia prefiero contar en personajes, también, pero si se da a entender la codificación clásica, entonces bytes = caracteres, así que tal vez en realidad no importa mucho lo que los llamamos ...
NGN
@Tobia Bueno, definitivamente es inútil proporcionar el recuento de caracteres en un desafío que puntúa por bytes. Sin embargo, nadie dijo que estamos anotando en bytes UTF-8. De hecho, el wiki de etiquetas dice explícitamente que se puede usar una codificación existente diferente para caracteres fuera del rango ASCII. Y APL tiene su propia página de códigos, por lo que todo el conjunto de caracteres cabe dentro de un byte. La política sobre PPCG es utilizar esta página de códigos para contar APL: no es justo castigar a APL por ser más antiguo que ASCII.
Martin Ender
13

Pitón 2, 269

Aquí hay una pequeña expresión agradable que se evalúa como una función. Acepta tres listas de enteros. Pasa todos los casos de prueba.

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
fuente
2

J - 311 257 bytes

Actualización (13 de enero de 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'
)

Explicación: Usando Gerundios, simplifique los if.s a @.s.

Versión antigua:

Primero intente tanto la codificación en J como el 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.
)

Ejecútelo usando una sintaxis similar a la siguiente (espacios adicionales para mayor claridad):

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

Explicación:

gse define como un diad que toma dos matrices que indica si el primer dado vence al segundo dado
hse define como un diad que toma dos matrices que dice que si lanza dos veces y suma, si el primer dado vence al segundo
fes una mónada que toma una mesa y devuelve una cadena con el respuesta correcta

Editar: corregir un error en Grime-no transitiva condición (reemplazando ,con *)

Jay Bosamiya
fuente
Me encantaría cualquier sugerencia para mejorar. :)
Jay Bosamiya
@ MartinBüttner, inicialmente lo había intentado, pero no sabía cómo concatenar sobre varias líneas (u oraciones, como se conoce en J) sin aumentar mucho la longitud del código ... aprender sobre "gerundios" me llevó a hacer el muchas oraciones en una que termina acortando el código también ...
Jay Bosamiya
1

Pyth 129 133

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

Pruébelo aquí , o al menos podría, pero en línea evalno parece que le gusten las listas de listas :( Si desea probarlo allí, almacene manualmente una lista de 3 dados en una variable no utilizada por el programa y luego reemplace todas las instancias de Qcon esa variable. Una inicialización de muestra:

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

Esto pasa todos los casos de prueba de Martin, no tengo el corazón para revisar todos los casos de Peter: P

Explicación (esto va a ser un desastre)

Lmsd^b2

Bastante simple, hace una función yque devuelve la suma de cada par de valores cartesianos en un iterable. Al equivalente: def y(b):return map(lambda d:sum(d),product(b,repeats=2)). Esto se usa para crear troqueles de muchos lados que simulan lanzar dos veces los dados regulares.

Msmsm>bkGH

Define una función gde 2 argumentos que devuelve cuántas veces un dado vence a otro. Equivalente a def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H).

DPNK-ghNeNgeNhNR?^tZ<KZKZ

Define una función Pque toma una lista de dos dados como argumento. Esto devuelve -1 si el primer dado 'pierde', 0 para un empate y 1 si el primer dado 'gana'. Equivalente a:

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

Las AGHasignaciones actúan como una asignación de 2 tuplas de Python. EsencialmenteG,H=(result)

msdCm,PkP,yhkyekm,@Qb@QhbUQ

Voy a explicar al revés a través de los mapas. m,@Qb@QhbUQitera sobre b = 0..2 y genera 2-tuplas de dados con índice b e índice b + 1. Esto nos da dados (A, B), (B, C), (C, A) (pyth modifica automáticamente los índices según la longitud de la lista).

Luego, m,PkP,yhkyekitera sobre el resultado del mapa anterior, con cada par de dados almacenados en k sobre cada carrera. Devoluciones tuple(P(k),P(tuple(y(k[0]),y(k[-1]))))para cada valor. Eso se reduce a '((A vence a B ?, 2 * A vence a 2 * B), (B vence a C ?, 2 * B vence a ...)).

Finalmente, msdCsuma los valores del mapa anterior después de haber sido comprimido. El zip causa todos los valores de 'latidos' de dados individuales en la primera tupla, y los valores de dados dobles en la segunda.

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

Una cosa asquerosa que imprime los resultados. Si G es 0 o no divisible por 3, este robot capturas +/- 3, ( |!G%G3), impresiones none, de lo contrario imprime la suma de la lista siguientes aparatos: [not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]. Creo que los booleanos se explican por sí mismos con respecto a las definiciones en la pregunta. Tenga en cuenta que G no puede ser cero aquí, ya que eso se detecta en la verificación anterior.

FryAmTheEggman
fuente
1

J (204)

Demasiado tiempo, probablemente podría jugar mucho golf al tener un sistema más eficiente para elegir la cuerda correcta.

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
fuente
1

Matlab (427)

No es tan corto y estoy seguro de que se puede jugar mucho más al golf, solo intenté resolver este desafío porque pensé que era una tarea muy divertida, ¡así que gracias @ MartinBüttner por crear este desafío!

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

Aquí el código completo con algunos comentarios si quieres tratar de entender lo que está sucediendo. Incluí algunos casos de prueba de liebre y excluí los comandos de entrada:

%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);
falla
fuente
¿No es más corto si lees una matriz input()y luego le asignas los tres elementos a,b,c? También, por favor utilice las cadenas exactas en la especificación ( none, nontransitivey en mayúsculas Grime) ... debe probablemente incluso ahorrar bytes.
Martin Ender
Sí, esto probablemente sea más corto, lo echaré un vistazo. Las cadenas serán exactamente las que acabo de eliminar los dispcomandos en la versión larga, fueron solo para probar el programa, pero el mensaje final se almacena m. Y corregí el G.
falla
0

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

No soy muy bueno en probabilidad, así que para estar seguro de mis resultados, prefiero tirar los dados cientos de miles de veces.

La expresión se evalúa como una función, que debería llamarse con un solo argumento: una matriz de tres matrices de enteros. Verifique el Fiddle para poder ejecutar el código usted mismo.

Aquí está la versión sin golf:

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);
}
Agujero negro
fuente
Hm, no creo que esto sea realmente en el espíritu del desafío. Básicamente lo convertiste de un desafío de teoría de probabilidad en un desafío de estadística. ;) ... En lugar de lanzamientos aleatorios, simplemente puede enumerar todos los lanzamientos posibles exactamente una vez. Eso le daría los resultados exactos (y correría mucho más rápido).
Martin Ender
Comprobaré si esto lleva a un guión más conciso. Gracias por su consejo :).
Blackhole