Probabilidade do par de cartões

9

Dado um baralho composto por N cópias de cartas com valores inteiros [ 1 , M ] para um total de N * M cartas, calcule a probabilidade de uma carta com o valor de 1 ser adjacente a uma carta com o valor de 2 .

Sua solução pode ser exata ou aproximada e não precisa ser a mesma para cada execução, com as mesmas entradas. A resposta dada deve estar dentro de +/- 5% da solução verdadeira (exceto as chances muito raras de que o RNG não esteja a seu favor). Seu programa deve fornecer a resposta em um período de tempo razoável (digamos, menos de 10 minutos em qualquer hardware que você tenha). Você pode assumir que M e N são razoavelmente pequenos e que a verificação de erros não é necessária.

O baralho não é cíclico; portanto, se a primeira carta for 1 e a última carta for 2 , isso não atenderá aos requisitos de adjacência.

Como um caso de teste, para N = 4 e M = 13 (um baralho de 52 cartas) a solução esperada é de ~ 48,6%.

Aqui está um exemplo de implementação não-golfada em Python + NumPy usando embaralhamento aleatório:

from __future__ import division
from numpy import *

def adjacent(N, M):
    deck = array([i for i in range(1, M+1)]*N)
    trials = 100000
    count = 0
    for i in range(trials):
        random.shuffle(deck)
        ores = (deck == 1)
        tres = (deck == 2)
        if(any(logical_and(ores[1:], tres[:-1])) or
           any(logical_and(ores[:-1], tres[1:]))):
            count += 1
    return count/trials

A saída pode estar em qualquer forma que você achar conveniente (valor de retorno da função, saída do terminal, arquivo etc.) e a entrada pode estar em qualquer forma que você achar conveniente (parâmetro de função, entrada do terminal, linha de comando arg, etc.)

Aplicam-se orifícios padrão.

Este é o código golf, o código mais curto (em bytes) vence.

Entre os melhores

Mostrar snippet de código

code-golf probability-theory simulation helloworld922
fonte
11
adjacência não envolvendo em torno é uma torção enganosamente complicado
Sparr
@Sparr Você me deu uma ideia! :-)
Luis Mendo

Respostas:

2

Pitão, 23 22 bytes

csm}1sM.:.S*vzUQ2J^T4J

Executa 10000 iterações. O número pode ser alterado sem custo de bytes. A entrada é separada por nova linha. Demora cerca de 9 segundos no meu computador.

Demonstração

csm}1sM.:.S*vzUQ2J^T4J
                 J^T4     J = 10000
  m              J        Do the following J times.
           *vzUQ          Set up the deck. (0 .. n-1, repeated m times.)
         .S               Shuffle the deck.
       .:       2         Find all 2 elment substrings.
     sM                   Add them up.
   }1                     Check if any pairs add to 1 ([0, 1] or [1, 0])
 s                        Add up the results (True = 1, False = 0)
c                     J   Divide by J.
isaacg
fonte
2

MATL , 44 46 bytes

Isso usa a versão 3.1.0 do idioma, que é anterior a esse desafio.

O cálculo é feito com um loop que desenha 1000 realizações aleatórias. Demora alguns segundos para executar. Isso poderia ser feito mais rapidamente de maneira vetorizada. Entrada é da forma [N M].

Versão antiga : gera um baralho aleatório e verifica duas vezes: primeiro na frente e depois na direção inversa.

itpw1)1e3:"2$twZ@w/Y]t1HhXfnwH1hXfn|bb]xxN$hYm

Nova versão : gera um baralho aleatório e anexa uma versão invertida com um 0meio. Dessa forma, a verificação pode ser feita apenas uma vez, na direção direta. Isso economiza dois bytes.

itpw1)1e3:"2$twZ@w/Y]tP0whh1HhXfngbb]xxN$hYm

Exemplo

>> matl itpw1)1e3:"2$twZ@w/Y]tP0whh1HhXfngbb]xxN$hYm
> [4 13]
0.469

Explicação

i                 % input: [N M]
tpw1)             % produce N*M and N
1e3:"             % repeat 1000 times
  2$twZ@w/Y]      % produce random deck of cards from 1 to N*M
  tP0whh          % append 0 and then flipped version of deck
  1Hh             % vector [1 2]
  Xf              % find one string/vector within another                          
  ng              % was it found at least once?
  bb              % bubble up element in stack, twice                     
]                 % end                                                     
xx                % delete top of the stack, twice
N$h               % vector with all elements in stack
Ym                % mean value
Luis Mendo
fonte
1

LabVIEW, 58 Primitivas do LabVIEW

cria matrizes de cartões e as embaralha. Procure 1s e verifique os cartões adjacentes por 2s.

Eumel
fonte
1

Pitão, 16 bytes

JE?>J1-1^-1c2JQZ

Demonstração.

Isto segue o

  • faça um palpite,
  • verifique se está perto o suficiente,
  • repetir

estratégia de programação. O palpite educado vencedor neste caso é

1 - (1 - 2 / M) ** N

o que diz aproximadamente que há Nchances de cair em baldes, e fração de baldes válidos é 2 / M. Os baldes sendo slots estão próximos a 0s e as chances são 1s.

O erro nunca parece ultrapassar 3% (surpreendentemente) e parece convergir para 0% à medida que os parâmetros aumentam (como eu esperaria).

A entrada é separada por nova linha.

              Q  Q = eval(input())
JE               J = eval(input())
  ?>J1           if J > 1
      -1^-1c2JQ  then 1 - (1 - 2 / J) ** Q
               Z else 0

Você pode salvar um personagem se aceitar o fato óbvio disso False == 0e o fizer JE&>J1-1^-1c2JQ.

Veedrac
fonte
Por acaso, é a minha primeira vez em Pyth (e minha primeira resposta); portanto, críticas e ajuda são especialmente bem-vindas.
Veedrac
1

MATL , 44 38 bytes

Isso também usa o MATL versão 3.1.0 , que é anterior a esse desafio.

Nova versão, obrigado a Luis Mendo por economizar 4 bytes!

iiXI*XJxO1e4XH:"JZ@I\TTo3X53$X+1=a+]H/

Versão antiga (44 bytes):

OiitXIx*XJx1e4XH:"JJZrI\[1 1]3X5,3$X+1=a+]H/

Explicação

i               % take input for N
i               % take input for M
XI              % save M into clipboard I
*XJ             % multiply N and M and store in clipboard J
x               % clear the stack
O               % make a zero to initialise count of pairs
1e4XH:"         % 1e4=10000, XH saves into clipboard H, : makes the vector 1:1e4
                % which is used to index a for loop, started using "
    JZ@         % Use randperm to generate a random permutation of the vector 1:N*M
    I\          % take the result mod M, now each card has a value one less than before
    TTo3X53$X+  % convolve vector of card values with [1 1] to do pairwise summation
    1=a         % find if any sums equal 1, which means there is a [0 1] or [1 0]         
    +           % add the logical value to the count of pairs
]
H/              % divide the count by the number of deals to get the probability

Por exemplo,

>> matl 'iiXI*XJxO1e4XH:"JZ@I\TTo3X53$X+1=a+]H/'
> 4
> 13
0.4861

Nota (21/5/16): A partir do MATL release 18.0.0, X+foi removida, mas Y+pode ser usada em seu lugar. As alterações da versão 3.1.0 para 18.0.0 do MATL significam que agora essa resposta pode ser escrita em apenas 31 bytes *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym,.

David
fonte
Eu sei que já existe uma resposta MATL, mas acho que os métodos são bem diferentes, então eu ainda postei essa.
David
Adoro convolução!
Luis Mendo
Você pode economizar um pouco de mudança [1 1]em TTo. Além disso, você não precisa de vírgula.
Luis Mendo
@LuisMendo thanks! Eu pensei que deveria ter havido uma maneira melhor de fazer isso!
David
Agora vejo como a convolução funciona aqui. O uso de nomes com base em 0 dos cartões foi muito inteligente!
Luis Mendo
0

Mathematica, 93 92 91 bytes

N@Count[RandomSample@Flatten[Range@#~Table~{#2}]~Table~{a=1*^5},{b=___,1,2,b}|{b,2,1,b}]/a&

Ainda à procura de um formulário fechado ...

LegionMammal978
fonte
isso envolverá um loop aninhado de cálculos de permutação.
Sparr