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
fuente
1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4
Estoy obteniendo A <B 17/36, B> C 19/36, C <A 16/36.Respuestas:
Dyalog APL,
107100 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 derechoA:B
guardia ("siA
luego regresaB
")T
es 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...10
sería la tabla de multiplicar que conocemos de la escuela). Aplicamos esto entre cada (¨
) elemento de⍵
y su elemento correspondiente en1⌽⍵
.×
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+/
sumaLuego maneje los casos por turno:
3≠|S←T⍵:'none'
siT⍵
el valor absoluto no es 3, devuelve 'none'N←'nontransitive'
necesitaremos mucho esta palabraS=D←T∘.+⍨¨⍵:'strongly ',N
calcularT
para pares de dados (∘.+⍨¨⍵
← →⍵((∘.+)¨)⍵
) y devolver "fuertemente ..." si las mismas relaciones entre ABC aún se mantienenS=-D:'Grime-',N
⍝ "Grime" si las relaciones están en direcciones opuestasN
si todo lo demás falla, simplemente "no transitivo"fuente
{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
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.
fuente
J -
311257 bytesActualización (13 de enero de 2015):
Explicación: Usando Gerundios, simplifique los
if.
s a@.
s.Versión antigua:
Primero intente tanto la codificación en J como el golf.
Ejecútelo usando una sintaxis similar a la siguiente (espacios adicionales para mayor claridad):
Explicación:
g
se define como un diad que toma dos matrices que indica si el primer dado vence al segundo dadoh
se define como un diad que toma dos matrices que dice que si lanza dos veces y suma, si el primer dado vence al segundof
es una mónada que toma una mesa y devuelve una cadena con el respuesta correctaEditar: corregir un error en Grime-no transitiva condición (reemplazando
,
con*
)fuente
Pyth 129
133Pruébelo aquí , o al menos podría, pero en línea
eval
no 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 deQ
con esa variable. Una inicialización de muestra: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)
Bastante simple, hace una función
y
que 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.Define una función
g
de 2 argumentos que devuelve cuántas veces un dado vence a otro. Equivalente adef g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H)
.Define una función
P
que 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:Las
AGH
asignaciones actúan como una asignación de 2 tuplas de Python. EsencialmenteG,H=(result)
Voy a explicar al revés a través de los mapas.
m,@Qb@QhbUQ
itera 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,yhkyek
itera sobre el resultado del mapa anterior, con cada par de dados almacenados en k sobre cada carrera. Devolucionestuple(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,
msdC
suma 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.Una cosa asquerosa que imprime los resultados. Si G es 0 o no divisible por 3, este robot capturas +/- 3, (
|!G%G3
), impresionesnone
, 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.fuente
J (204)
Demasiado tiempo, probablemente podría jugar mucho golf al tener un sistema más eficiente para elegir la cuerda correcta.
fuente
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!
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:
fuente
input()
y luego le asignas los tres elementosa,b,c
? También, por favor utilice las cadenas exactas en la especificación (none
,nontransitive
y en mayúsculasGrime
) ... debe probablemente incluso ahorrar bytes.disp
comandos en la versión larga, fueron solo para probar el programa, pero el mensaje final se almacenam
. Y corregí elG
.JavaScript: 276 bytes
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:
fuente