Probabilitas pasangan kartu

9

Diberikan setumpuk yang terdiri dari N salinan kartu dengan nilai integer [ 1 , M ] untuk total kartu N * M , hitung probabilitas bahwa kartu dengan nilai 1 berdekatan dengan kartu dengan nilai 2 .

Solusi Anda mungkin tepat atau hampir sama, dan tidak harus sama untuk setiap proses dengan input yang sama. Jawaban yang diberikan harus dalam +/- 5% dari solusi yang sebenarnya (kecuali kemungkinan sangat kecil RNG tidak mendukung Anda). Program Anda harus memberikan jawaban dalam jumlah waktu yang wajar (katakanlah, kurang dari 10 menit pada perangkat keras apa pun yang Anda miliki). Anda dapat mengasumsikan bahwa M dan N adalah wajar kecil dan pengecekan kesalahan tidak diperlukan.

Dek tidak bersifat siklis, jadi jika kartu pertama adalah 1 dan kartu terakhir adalah 2 , ini tidak memenuhi persyaratan kedekatan.

Sebagai test case, untuk N = 4 dan M = 13 (standar kartu 52 kartu) solusi yang diharapkan adalah ~ 48,6%.

Berikut adalah contoh implementasi un-golfed di Python + NumPy menggunakan acak acak:

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

Outputnya mungkin dalam bentuk apa pun yang Anda rasa nyaman (nilai pengembalian fungsi, output terminal, file, dll.), Dan input mungkin dalam bentuk apa pun yang Anda rasa nyaman (parameter fungsi, input terminal, baris perintah, dll.)

Lubang loop standar berlaku.

Ini adalah kode golf, kode terpendek (dalam byte) menang.

Papan peringkat

Tampilkan cuplikan kode

code-golf probability-theory simulation helloworld922
sumber
1
adjacency tidak membungkus adalah twist rumit rumit
Sparr
@Parr Anda memberi saya ide! :-)
Luis Mendo

Jawaban:

2

Pyth, 23 22 byte

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

Menjalankan 10000 iterasi. Jumlahnya dapat diubah tanpa biaya byte. Input dipisahkan baris baru. Membutuhkan waktu sekitar 9 detik di komputer saya.

Demonstrasi

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

MATL , 44 46 byte

Ini menggunakan rilis 3.1.0 bahasa, yang lebih awal dari tantangan ini.

Perhitungan dilakukan dengan loop yang menarik 1000 realisasi acak. Butuh beberapa detik untuk menjalankannya. Itu bisa dilakukan lebih cepat dengan cara vektor. Input berupa formulir [N M].

Versi lama : menghasilkan setumpuk kartu acak dan memeriksanya dua kali: pertama di depan dan kemudian di belakang.

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

Versi baru : menghasilkan setumpuk kartu acak dan kemudian menambahkan versi membaliknya dengan 0di antaranya. Dengan begitu pengecekan bisa dilakukan hanya sekali, ke arah depan. Ini menghemat dua byte.

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

Contoh

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

Penjelasan

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

LabVIEW, 58 LabVIEW Primitif

susunan kartu creats kemudian mengocoknya. Cari 1s kemudian periksa kartu yang berdekatan untuk 2s.

Eumel
sumber
1

Pyth, 16 byte

JE?>J1-1^-1c2JQZ

Demonstrasi.

Ini mengikuti

  • membuat tebakan yang berpendidikan,
  • periksa apakah itu cukup dekat,
  • ulang

strategi pemrograman. Tebakan berpendidikan menang dalam hal ini adalah

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

yang secara kasar mengatakan bahwa ada Npeluang untuk jatuh ke ember, dan sebagian kecil dari ember yang valid adalah 2 / M. Bucket yang menjadi slot ditempatkan di sebelah 0s, dan kemungkinan menjadi 1s.

Kesalahan tampaknya tidak pernah naik di atas 3% (mengejutkan), dan tampaknya konvergen ke 0% ketika parameter semakin besar (seperti yang saya harapkan).

Input dipisahkan baris baru.

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

Anda dapat menyimpan karakter jika Anda menerima fakta yang jelas-jelas jelas itu False == 0, dan lakukan JE&>J1-1^-1c2JQsebaliknya.

Veedrac
sumber
Ini kebetulan pertama saya pergi di Pyth (dan jawaban pertama saya), jadi kritik dan bantuan sangat disambut.
Veedrac
1

MATL , 44 38 byte

Ini juga menggunakan MATL versi 3.1.0 , yang lebih awal dari tantangan ini.

Versi baru, terima kasih kepada Luis Mendo karena telah menghemat 4 byte!

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

Versi lama (44 byte):

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

Penjelasan

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

Sebagai contoh,

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

Catatan (21/5/16): Pada rilis MATL 18.0.0, X+telah dihapus, tetapi Y+dapat digunakan sebagai gantinya. Perubahan dari MATL versi 3.1.0 ke 18.0.0 berarti bahwa jawaban ini sekarang dapat ditulis hanya dalam 31 byte *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym,.

David
sumber
Saya tahu sudah ada jawaban MATL, tapi saya pikir metodenya sangat berbeda sehingga saya masih memposting yang ini.
David
Saya suka belitan!
Luis Mendo
Anda dapat menyimpan sedikit berubah [1 1]menjadi TTo. Selain itu, Anda tidak memerlukan koma
Luis Mendo
@LuisMendo terima kasih! Saya pikir pasti ada cara yang lebih baik untuk melakukan itu!
David
Sekarang saya melihat bagaimana konvolusi bekerja di sini. Menggunakan penamaan kartu berbasis 0 sangat pintar!
Luis Mendo
0

Mathematica, 93 92 91 byte

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

Masih mencari formulir tertutup ...

LegionMammal978
sumber
itu akan melibatkan loop bersarang dari perhitungan permutasi.
Sparr