Dados não-transitivos são pequenos brinquedos que desafiam nossa intuição na teoria das probabilidades. Precisamos de algumas definições para este desafio:
Considere dois dados A e B que são lançados ao mesmo tempo. Dizemos que um bate B se a probabilidade de A mostrando um número maior do que B é estritamente maior do que a probabilidade de B mostrando um número maior do que um .
Agora, considere um conjunto de três dados, com rótulos A , B , C . Esse conjunto de dados é chamado de não-transitivo se
- ou A vence B , B vence C e C vence A
- ou C bate B , B bate Um e um bate C .
Como um dos meus exemplos favoritos, considere os dados do Grime , que têm os seguintes lados:
A: 3 3 3 3 3 6
B: 2 2 2 5 5 5
C: 1 4 4 4 4 4
Curiosamente, a média de cada dado é 3,5, assim como um dado regular.
Pode-se mostrar que:
- A vence B com uma probabilidade de 7/12.
- B vence C com uma probabilidade de 7/12.
- C bate A com uma probabilidade de 25/36.
Agora, esses dados em particular são ainda mais estranhos. Se rolarmos cada dado duas vezes e somarmos os resultados, cuja ordem é melhor que a invertida:
- B vence A com uma probabilidade de 85/144.
- C bate B com uma probabilidade de 85/144.
- A bate C com uma probabilidade de 671/1296.
Vamos chamar um conjunto de dados com essa propriedade Grime-não-transitiva .
Por outro lado, se os dados mantêm seu ciclo original ao usar dois arremessos, os chamamos de fortemente não-transitivos . (Se não houver ciclo para dois lançamentos, simplesmente os chamamos de não - transitivos .)
O desafio
Dado três dados de seis lados, que determinam as propriedades acima Este conjunto tem, e uma das seguintes cadeias de saída: none
, nontransitive
, Grime-nontransitive
, strongly nontransitive
.
Você pode escrever um programa ou função, receber entrada via STDIN, argumento de linha de comando, prompt ou argumento de função e gravar o resultado em STDOUT ou retorná-lo como uma string.
Você pode assumir que todos os lados são números inteiros não negativos. Você não pode assumir que os lados ou os dados estão em uma ordem específica. Você pode receber entradas em qualquer lista conveniente ou formato de sequência.
Isso é código de golfe, então a resposta mais curta (em bytes) vence.
Casos de teste
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
Se você quiser testar seu código ainda mais detalhadamente, Peter Taylor teve a gentileza de escrever uma implementação de referência, que classificou todos os ~ 5000 conjuntos de dados com os lados 1 a 6 e uma média de 3,5. Link Pastebin
fonte
1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4
Estou recebendo A <B 17/36, B> C 19/36, C <A 16/36.Respostas:
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}
(Obrigado à Tobia por esta solução mais simples, mais curta e melhor)
Noções básicas:
←
tarefa⋄
separador de instruções{}
forma lambda⍺⍵
argumento esquerdo e direitoA:B
guarda ("seA
então retornarB
")T
é uma função que retorna 3 se A vencer B, B vencer C e C vencer A; -3 se for exatamente o oposto; e algo entre o contrário. Em detalhe:1⌽⍵
é a rotação única de⍵
. Se⍵
for ABC, a rotação é BCA.∘.-
calcula uma tabela de subtração entre dois vetores (1 2...10 ∘.× 1 2...10
seria a tabela de multiplicação que conhecemos da escola). Aplicamos isso entre cada¨
item ( )⍵
e o item correspondente em1⌽⍵
.×
sinal de todos os números nas tabelas de subtração∊¨
achatar cada mesa+/¨
e somar. Agora, temos três números que representam saldos: número de vitórias menos casos perdidos para cada um de A vs B, B vs C, C vs A.×
signum daqueles+/
somaDepois, lide com os casos:
3≠|S←T⍵:'none'
seT⍵
o valor absoluto de não for 3, retorne 'none'N←'nontransitive'
vamos precisar muito dessa palavraS=D←T∘.+⍨¨⍵:'strongly ',N
calcularT
pares de dados (∘.+⍨¨⍵
← →⍵((∘.+)¨)⍵
) e retornar "fortemente ..." se as mesmas relações entre o ABC ainda se mantiveremS=-D:'Grime-',N
Gr "Grime" se os relacionamentos estiverem em direções opostasN
se tudo mais falhar, apenas "não-transitivo"fonte
{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}
Python 2, 269
Aqui está uma pequena expressão agradável que avalia uma função. Aceita três listas de números inteiros. Passa em todos os casos de teste.
fonte
J -
311257 bytesAtualização (13 de janeiro de 2015):
Explicação: Usando Gerúndios, simplifique os
if.
s para@.
s.Versão antiga:
Primeiro tente codificar em J e também jogar golfe.
Execute-o usando uma sintaxe semelhante à seguinte (espaços extras para maior clareza):
Explicação:
g
é definido como um diad tomar duas matrizes que diz se primeiro dado bate segundo dadoh
é definido como uma diad tomar duas matrizes que diz se jogando duas vezes e soma, faz primeiros dados vencer segundaf
é uma mônada que leva uma tabela e retorna um string com o resposta corretaEditar: corrigir um erro na condição Grime-não-transitória (substituindo
,
por*
)fonte
Pitão 129
133Tente aqui , ou pelo menos você poderia, mas o online
eval
não parece gostar de listas de listas :( Se você quiser experimentá-lo, armazene manualmente uma lista de 3 dados em uma variável não usada pelo programa e substitua todas as instânciasQ
dessa variável.Um exemplo de inicialização:Isso passa em todos os casos de teste de Martin, não tenho o coração examinado todos os casos de Peter: P
Explicação (isso vai ficar doozy)
Muito simples, cria uma função
y
que retorna a soma de cada par de valores cartesianos de forma iterável. Para equivalentes:def y(b):return map(lambda d:sum(d),product(b,repeats=2))
. Isso é usado para criar matrizes de vários lados que simulam jogar as matrizes regulares duas vezes.Define uma função
g
de 2 argumentos que retorna quantas vezes um dado vence outro. Equivalente adef g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H)
.Define uma função
P
que recebe uma lista de dois dados como argumento. Isso retorna -1 se o primeiro dado 'perder', 0 para um empate e 1 se o primeiro dado 'vencer'. Equivalente a:A
AGH
atribuição atua como uma atribuição python de 2 tuplas. EssencialmenteG,H=(result)
Indo para trás através dos mapas.
m,@Qb@QhbUQ
itera sobre b = 0..2 e gera 2 tuplas de dados com o índice be índice b + 1. Isso nos dá dados (A, B), (B, C), (C, A) (pyth modifica automaticamente os índices pelo comprimento da lista).Em seguida,
m,PkP,yhkyek
itera sobre o resultado do mapa anterior, com cada par de dados sendo armazenado em k em cada execução. Retornatuple(P(k),P(tuple(y(k[0]),y(k[-1]))))
para cada valor. Isso se resume a `((A bate B ?, 2 * A bate 2 * B), (B bate C ?, 2 * B bate ..)).Finalmente,
msdC
soma os valores do mapa anterior depois que ele foi compactado. O zíper faz com que todos os dados individuais 'batam' na primeira tupla e os dados duplos na segunda.Uma coisa nojenta que imprime os resultados. Se L é 0 ou não divisível por três, este capturas bot +/- 3, (
|!G%G3
), gravurasnone
, de outra forma imprime a soma da lista follwing:[not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]
. Eu acho que os booleanos são bastante auto-explicativos no que diz respeito às definições na pergunta. Observe que G não pode ser zero aqui, pois isso é capturado pela verificação anterior.fonte
J (204)
Por muito tempo, provavelmente poderia ser muito jogado por ter um sistema mais eficiente para escolher a corda certa.
fonte
Matlab (427)
Não é tão curto e tenho certeza de que pode jogar muito mais, tentei resolver esse desafio porque achei que era uma tarefa muito divertida, então obrigado a MartinBüttner por criar esse desafio!
Aqui está o código completo com alguns comentários, se você quiser entender o que está acontecendo. Incluí alguns casos de teste hare e excluí os comandos de entrada:
fonte
input()
e depois atribuir os três elementosa,b,c
? Além disso, por favor use as cordas exatas nas especificações (none
,nontransitive
e capitalizadoGrime
) ... deve provavelmente até poupar bytes.disp
comandos na versão longa, elas eram apenas para testar o programa, mas a mensagem final é armazenadam
. E eu corrigi oG
.JavaScript - 276 bytes
Não sou muito bom em probabilidade; portanto, para ter certeza dos meus resultados, prefiro jogar os dados centenas de milhares de vezes.
A expressão é avaliada como uma função, que deve ser chamada com apenas um argumento: uma matriz de três matrizes de números inteiros. Verifique o Fiddle para poder executar o código sozinho.
Aqui está a versão não destruída:
fonte