9
\$\begingroup\$

Given a deck consisting of N copies of cards with integer values [1,M] for a total of N*M cards, compute the probability that a card with the value of 1 is adjacent to a card with the value of 2.

Your solution may be exact or approximated, and it does not need to be the same for every run given the same inputs. The given answer should be within +/-5% of the true solution (barring really rare chances the RNG is not in your favor). Your program should give the answer in a reasonable amount of time (say, less than 10 minutes on whatever hardware you have). You may assume that M and N are reasonable small and error checking is not required.

The deck is not cyclical, so if the first card is a 1 and the last card is a 2, this does not meet the adjacency requirements.

As a test case, for N=4 and M=13 (a standard 52-card deck) the expected solution is ~48.6%.

Here is an example un-golfed implementation in Python+NumPy using random shuffles:

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

The output may be in any form you find convenient (function return value, terminal output, file, etc.), and input may be in any form you find convenient (function parameter, terminal input, command line arg, etc.)

Standard loop-holes apply.

This is code golf, the shortest code (in bytes) wins.

Leaderboard

var QUESTION_ID=67431,OVERRIDE_USER=31729;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • 1
    \$\begingroup\$ adjacency not wrapping around is a deceptively complicated twist \$\endgroup\$ – Sparr Dec 22 '15 at 23:36
  • \$\begingroup\$ @Sparr You gave me an idea! :-) \$\endgroup\$ – Luis Mendo Dec 23 '15 at 0:47
2
\$\begingroup\$

Pyth, 23 22 bytes

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

Runs 10000 iterations. The number can be changed at no byte cost. Input is newline separated. Takes about 9 seconds on my computer.

Demonstration

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.
\$\endgroup\$
2
\$\begingroup\$

MATL, 44 46 bytes

This uses release 3.1.0 of the language, which is earlier than this challenge.

The computation is done with a loop that draws 1000 random realizations. It takes a couple of seconds to run. It could be done faster in a vectorized way. Input is of the form [N M].

Old version: generates a random deck of cards and checks it twice: first in the forward and then in the backward direction.

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

New version: generates a random deck of cards and then appends a flipped version of it with a 0 in between. That way checking can be done just once, in the forward direction. This saves two bytes.

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

Example

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

Explanation

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
\$\endgroup\$
1
\$\begingroup\$

LabVIEW, 58 LabVIEW Primitives

creats card arrays then shuffles them. Search for 1s then check adjacent cards for 2s.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 16 bytes

JE?>J1-1^-1c2JQZ

Demonstration.

This follows the

  • make an educated guess,
  • check that it's close enough,
  • repeat

strategy of programming. The winning educated guess in this case is

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

which roughly says that there are N chances to fall into buckets, and fraction of valid buckets is 2 / M. The buckets being slots places next to 0s, and the chances being 1s.

The error never seems to go above 3% (surprisingly), and seems to converge to 0% as the parameters get larger (as I would expect).

Input is newline separated.

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

You can save a character if you accept the plainly obvious fact that False == 0, and do JE&>J1-1^-1c2JQ instead.

\$\endgroup\$
  • \$\begingroup\$ This happens to be my first go at Pyth (and my first answer), so criticism and help is especially welcome. \$\endgroup\$ – Veedrac Dec 23 '15 at 20:50
1
\$\begingroup\$

MATL, 44 38 bytes

This also uses MATL version 3.1.0, which is earlier than this challenge.

New version, thanks to Luis Mendo for saving 4 bytes!

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

Old version (44 bytes):

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

Explanation

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

For example,

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

Note (21/5/16): As of MATL release 18.0.0, X+ has been removed, but Y+ can be used in its place. The changes from MATL version 3.1.0 to 18.0.0 mean that this answer can now be written in just 31 bytes, *xO1e4:"2:Gtb*Z@w\TT2&Y+1=ah]Ym.

\$\endgroup\$
  • \$\begingroup\$ I know there is already a MATL answer, but I think the methods are quite different so I've still posted this one. \$\endgroup\$ – David Dec 22 '15 at 23:59
  • \$\begingroup\$ I love convolution! \$\endgroup\$ – Luis Mendo Dec 23 '15 at 0:48
  • \$\begingroup\$ You can save a little changing [1 1] into TTo. Also, you don't need the comma \$\endgroup\$ – Luis Mendo Dec 23 '15 at 0:50
  • \$\begingroup\$ @LuisMendo thanks! I thought there must have been a better way to do that! \$\endgroup\$ – David Dec 23 '15 at 0:50
  • \$\begingroup\$ Now I see how convolution works here. Using 0-based naming of the cards was very clever! \$\endgroup\$ – Luis Mendo Dec 23 '15 at 0:55
0
\$\begingroup\$

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&

Still looking for a closed form...

\$\endgroup\$
  • \$\begingroup\$ it's going to involve a nested loop of permutation calculations. \$\endgroup\$ – Sparr Dec 22 '15 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.