Prawdopodobieństwo pary kart

9

Biorąc pod uwagę talię składającą się z N kopii kart o wartościach całkowitych [ 1 , M ] dla łącznie N * M kart, oblicz prawdopodobieństwo, że karta o wartości 1 przylega do karty o wartości 2 .

Twoje rozwiązanie może być dokładne lub przybliżone i nie musi być takie samo dla każdego przebiegu przy tych samych danych wejściowych. Podana odpowiedź powinna mieścić się w granicach +/- 5% prawdziwego rozwiązania (z wyjątkiem naprawdę rzadkich szans, że RNG nie jest na twoją korzyść). Twój program powinien udzielić odpowiedzi w rozsądnym czasie (powiedzmy mniej niż 10 minut na dowolnym sprzęcie). Możesz założyć, że M i N są rozsądnie małe i sprawdzanie błędów nie jest wymagane.

Talia nie jest cykliczna, więc jeśli pierwsza karta to 1, a ostatnia karta to 2 , nie spełnia to wymagań sąsiednich.

W przypadku testowym dla N = 4 i M = 13 (standardowa talia 52 kart) oczekiwane rozwiązanie wynosi ~ 48,6%.

Oto przykład implementacji bez golfa w Pythonie + NumPy przy użyciu losowych losowań:

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

Dane wyjściowe mogą być w dowolnej dogodnej dla ciebie formie (wartość zwracana przez funkcję, wyjście terminala, plik itp.), A dane wejściowe mogą być w dowolnej dogodnej dla ciebie formie (parametr funkcji, wejście terminala, argument linii poleceń itp.)

Obowiązują standardowe otwory przelotowe.

To jest kod golfowy, wygrywa najkrótszy kod (w bajtach).

Tabela liderów

helloworld922
źródło
1
sąsiedztwo, które nie owija się wokół, jest zwodniczo skomplikowanym zwrotem akcji
Sparr
@Sparr Dałeś mi pomysł! :-)
Luis Mendo

Odpowiedzi:

2

Pyth, 23 22 bajtów

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

Uruchamia 10000 iteracji. Liczbę można zmienić bez kosztu bajtu. Wejście jest oddzielone znakiem nowej linii. Na moim komputerze trwa około 9 sekund.

Demonstracja

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
źródło
2

MATL , 44 46 bajtów

Używa wersji 3.1.0 języka, która jest wcześniejsza niż to wyzwanie.

Obliczenia wykonuje się za pomocą pętli, która rysuje 1000 losowych realizacji. Uruchomienie zajmuje kilka sekund. Można to zrobić szybciej w wektorowy sposób. Dane wejściowe mają formę [N M].

Stara wersja : generuje losową talię kart i sprawdza ją dwukrotnie: najpierw do przodu, a następnie do tyłu.

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

Nowa wersja : generuje losową talię kart, a następnie dołącza jej odwróconą wersję z pośrodkiem 0. W ten sposób sprawdzenie można wykonać tylko raz, w kierunku do przodu. To oszczędza dwa bajty.

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

Przykład

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

Wyjaśnienie

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
źródło
1

LabVIEW, 58 LabVIEW Prymitywy

tworzy tablice kart, a następnie tasuje je. Wyszukaj 1s, a następnie sprawdź sąsiednie karty przez 2s.

Eumel
źródło
1

Pyth, 16 bajtów

JE?>J1-1^-1c2JQZ

Demonstracja.

To wynika z

  • zgadnij,
  • sprawdź, czy jest wystarczająco blisko,
  • powtarzać

strategia programowania. W tym przypadku zwycięską zgadywanką jest

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

co z grubsza mówi, że są Nszanse, aby wpaść w segmenty, a odsetek prawidłowych segmentów to 2 / M. Wiadra są gniazdami umieszczonymi obok 0s, a szanse są 1s.

Błąd nigdy nie wydaje się przekraczać 3% (zaskakująco) i wydaje się zbliżać do 0%, gdy parametry stają się większe (jak bym się spodziewał).

Wejście jest oddzielone znakiem nowej linii.

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

Możesz uratować postać, jeśli zaakceptujesz oczywisty fakt, że False == 0to zrobisz, i JE&>J1-1^-1c2JQzamiast tego.

Veedrac
źródło
To zdarza się po raz pierwszy w Pyth (i moja pierwsza odpowiedź), dlatego krytyka i pomoc są szczególnie mile widziane.
Veedrac
1

MATL , 44 38 bajtów

To również używa MATL w wersji 3.1.0 , która jest wcześniejsza niż to wyzwanie.

Nowa wersja, dzięki Luisowi Mendo za zapisanie 4 bajtów!

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

Stara wersja (44 bajty):

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

Wyjaśnienie

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

Na przykład,

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

Uwaga (21/5/16): Od wersji MATL 18.0.0 X+został usunięty, ale Y+można go użyć zamiast niego. Zmiany od wersji 3.1.0 Mátl do 18.0.0 oznaczać, że odpowiedź ta może być teraz pisane w ciągu zaledwie 31 bajtów *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym.

David
źródło
Wiem, że jest już odpowiedź MATL, ale myślę, że metody są zupełnie inne, więc wciąż to opublikowałem.
David
Uwielbiam splot!
Luis Mendo
Można zaoszczędzić trochę zmienia [1 1]się TTo. Ponadto nie potrzebujesz przecinka
Luis Mendo
@LuisMendo dzięki! Pomyślałem, że musi być lepszy sposób!
David
Teraz widzę, jak działa tutaj splot. Używanie nazw kart opartych na 0 było bardzo sprytne!
Luis Mendo
0

Mathematica, 93 92 91 bajtów

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

Wciąż szukam zamkniętego formularza ...

LegionMammal978
źródło
będzie obejmować zagnieżdżoną pętlę obliczeń permutacji.
Sparr