# Card pair probability

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 *

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.

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>

• adjacency not wrapping around is a deceptively complicated twist Dec 22, 2015 at 23:36
• @Sparr You gave me an idea! :-) Dec 23, 2015 at 0:47

# 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.
}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.


# 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


# LabVIEW, 58 LabVIEW Primitives

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

# 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.

• This happens to be my first go at Pyth (and my first answer), so criticism and help is especially welcome. Dec 23, 2015 at 20:50

# 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.

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

## Mathematica, 9392 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...

• it's going to involve a nested loop of permutation calculations. Dec 22, 2015 at 23:50