8
\$\begingroup\$

Summer Klerance, a senior in college, is what her teachers refer to as GBL*. Students in her probability class have been assigned individual problems to work on and turn in as part of their final grade. Summer, as usual, procrastinated much too long, and, having finally looked at her problem, realizes it is considerably more advanced than those covered in her course and has several parts as well. An average programmer, Summer decides to take a Monte Carlo gamble with her grade. Her prof. said that answers could be rounded to the nearest integer, and she doesn't have to show her work. Surely if she lets her program run long enough, her results will be close enough to the exact results one would get "the right way" using probability theory alone.

Challenge

You (playing alone) are dealt consecutive 13-card hands. Every hand is from a full, shuffled deck. After a certain number of deals, you will have held all 52 cards in the deck at least once. The same can be said for several other goals involving complete suits.

Using your favorite random-number tools, help Summer by writing a program that simulates one million 13-card deals and outputs the average number of deals needed for you to have seen (held) each of these seven goals:

1 (Any) one complete suit
2 One given complete suit
3 (Any) two complete suits
4 Two given suits
5 (Any) three complete suits
6 Three given complete suits
7 The complete deck (all four suits)  

Each goal number (1-7) must be followed by the average number of hands needed (rounded to one decimal, which Summer can then round to the nearest integer and turn in) and (just for inquisitive golfers) add the minimum and maximum number of hands needed to reach that goal during the simulation. Provide output from three runs of your program. The challenge is to generate all the averages. The min. and max. are (required) curiosities and will obviously vary run to run.

Test Runs

Input: None

Sample Output: Three separate million-deal runs for the average, minimum, and maximum number of hands needed to reach each of the seven goals.

1 [7.7, 2, 20 ]       1 [7.7, 3, 18]        1 [7.7, 2, 20 ]
2 [11.6, 3, 50]       2 [11.7, 3, 54]       2 [11.6, 3, 63]
3 [10.0, 4, 25]       3 [10.0, 4, 23]       3 [10.0, 4, 24]
4 [14.0, 5, 61]       4 [14.0, 4, 57]       4 [14.0, 4, 53]
5 [12.4, 6, 30]       5 [12.4, 6, 32]       5 [12.4, 6, 34]
6 [15.4, 6, 51]       6 [15.4, 6, 53]       6 [15.4, 6, 51]
7 [16.4, 7, 48]       7 [16.4, 7, 62]       7 [16.4, 7, 59]

Rules:

  1. Every hand must be dealt from a full, shuffed deck of 52 standard French playing cards.

  2. Results for each goal must be based on one million hands or deals. You can collect all the results in a single million-deal run, or program as many million-deal runs as you like. However, each of the seven goals should reflect the result of one million deals.

  3. Averages for the number of hands should be rounded to one decimal.

  4. Output should be formatted roughly as above: each goal number (1-7) followed by its results (avg., min., and max. number of hands). Provide output for three runs of your program (side by side or consecutively), which will serve as a check of the accuracy/consistency of the averages (column 1) only (columns 2 and 3 are required, but will obviously vary run to run).

  5. Shortest program in bytes wins.


Note: FYI, I believe the exact calculation (via formula) for the average number of hands needed to see the complete deck (goal # 7) works out to ≈ 16.4121741798


*Good but lazy

\$\endgroup\$
6
  • \$\begingroup\$ Are you doing million instances where each instance deals until the goal is met? so the actual number of dealt hands is more than 1m? If not, I don't understand how the average is to be calculated. \$\endgroup\$
    – Jonah
    Jul 19, 2021 at 21:23
  • \$\begingroup\$ For example, the stats for goal 1 and goal 2 each reflect the results of 1 million deals. You can collect the stats together for one run of 1 million deals, or you can collect the stats for goal 1 and goal 2 on two separate runs of 1 million deals. What counts is that each of the 7 averages was for 1 million deals. In other words, there are seven separate questions (goals), each based on a million deals. Does that clarify it? Since it's code golf, I leave it up to you, since running time isn't an issue. \$\endgroup\$
    – DjinTonic
    Jul 19, 2021 at 21:35
  • \$\begingroup\$ Chat room started. \$\endgroup\$
    – DjinTonic
    Jul 19, 2021 at 21:42
  • \$\begingroup\$ It's still unclear to me. Say after 57 deals I have gotten every card in the deck. Does that now count as 1 data point? And now I start over? Then say 23 deals later I have received every card again. Is my 2nd data point now 23? And then i just keep going this way until 1m? This means my last sample will likely end prematurely. Do I just throw it out? And then average the various sample sizes? \$\endgroup\$
    – Jonah
    Jul 19, 2021 at 21:46
  • 1
    \$\begingroup\$ Yes, your first goal took 57 deals and your second took 23 deals. Your running total is now 80 deals. You toss a last, incomplete goal-- over 1 million deals it won't change the first decimal place :) In any case, counting stops, the million deals are over and if you didn't reach your goal, so be it. \$\endgroup\$
    – DjinTonic
    Jul 19, 2021 at 22:05

7 Answers 7

4
\$\begingroup\$

JavaScript (V8),  251  247 bytes

A full program that prints 7 tuples (avg, min, max).

[1,21845,279,30583,6015,32639,32767].map(b=>{for(M=k=t=c=0,m=n=1e6;c++||(x=[j=0]),n--;){for(d=[],i=14;--i;){while(d[v=Math.random()*52|0]);j|=((d[v]=x[v&3]|=1<<v/4)>8190)<<v%4}b>>j&1||(t+=c,M=c>M?c:M,m=c<m?c:m,k+=.1,c=0)}print(~~(t/k+.5)/10,m,M)})

Try it online!

Example output

1   7.7  2 19   7.7  2 18   7.7  3 18
2   11.6 3 52   11.6 3 58   11.6 3 49
3   10.0 4 24   10.0 4 23   10.0 4 29
4   14.0 4 51   14.0 5 59   14.0 4 55
5   12.4 6 32   12.4 5 33   12.4 6 33
6   15.4 6 54   15.4 6 52   15.4 6 60
7   16.4 7 56   16.4 7 54   16.4 7 54
\$\endgroup\$
3
\$\begingroup\$

Jelly, 80 61 bytes

%4‘ċⱮ4=13¹ḣƭS<
8⁸€;Q¥€52Ẋḣ13¤ẋç¥"JH$Ʋȷ6СẈ€¬ZT€IµÆmær1;Ṃ;Ṁ)ṖĖ

Try it online!

A pair of links that is run as a nilad and returns a list with a member for each goal. Each goal is represented as [goal number, [mean deals, min deals, max deals]]. The TIO link only does 10,000 deals per trial since that’s the most that can be done within the 60 second limit. The ȷ6 above is the number of deals for each trial in something like scientific notation (ȷ6 means \$10^6\$), so for TIO I’ve used ȷ4 instead.

Full explanation to follow.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 196 bytes

7.times{|g|c=r=[]
1.upto(1e6){$.+=1
c|=[*1..52].sample 13
d=(0..3).map{|i|c.count{|j|j%4==i}}
(r<<$.;*c,$.=0)if[d.max(m=g/2+1),d[0,m]][g%2].sum/m>12}
p g+1,[r.sum.fdiv(r.size).round(1),*r.minmax]}

Try it online! The number of deals on TIO is set to 1e5 instead of 1e6 to avoid timing out.

Sample output for three local runs with 1e6 deals (side by side for ease of reading and to save space):

1              1              1              
[7.7, 2, 20]   [7.7, 2, 18]   [7.7, 2, 19] 
2              2              2            
[11.7, 2, 52]  [11.6, 3, 45]  [11.6, 3, 60]
3              3              3            
[10.0, 4, 24]  [10.0, 4, 26]  [10.0, 4, 23]
4              4              4            
[14.0, 4, 57]  [14.0, 5, 51]  [14.0, 5, 51]
5              5              5            
[12.4, 6, 31]  [12.4, 6, 34]  [12.4, 6, 32]
6              6              6            
[15.4, 6, 62]  [15.4, 6, 57]  [15.4, 6, 53]
7              7              7            
[16.4, 7, 51]  [16.4, 7, 53]  [16.4, 7, 48]

Explanation

As the deals progress, a count is kept of the number of cards seen from each suit. This count is stored in the 4-element array d in the code.

Goals 1, 3, 5, and 7 are achieved when all 13 cards from any \$m=1, 2, 3, 4\$ suits, respectively, have been seen, or in other words when the sum of the \$m\$ greatest elements of d equals \$13m\$.

Goals 2, 4, and 6 are equivalent to choosing a particular ordering of suits and seeing all 13 cards from the first \$m=1,2,3\$ suits, respectively. In these cases, the goal is achieved when the sum of the first \$m\$ elements of d equals \$13m\$.

7.times{|g|    # for each goal
  c=r=[]       # initialise
  1.upto(1e6){ # 1 million times
    $.+=1      # count deals towards current goal
    c|=[*1..52].sample 13 # randomly select 13 cards and keep track of history (set union)
    d=(0..3).map{|i|c.count{|j|j%4==i}} # count cards seen from each suit
    (r<<$.;*c,$.=0)if[d.max(m=g/2+1),d[0,m]][g%2].sum/m>12 # if goal is achieved, store deal counter then reset counter and history
  }
  p g+1,[r.sum.fdiv(r.size).round(1),*r.minmax] # formatted output
}
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 136 bytes

≔E⁷⟦⟧ε≔Eε⁰ζ≔⮌ζηF×φφ«≔⟦⟧θF¹³⊞θ‽⁻E⁵²λθ≧|ΣX²θη≦⊕ζ≔Eη↨⁻⊖X²¦⁵³κ⁸¹⁹²δF⁷F⎇﹪κ²⁼¹Σ…§δκ⊘⁺³κ›⊗№§δκ⁰κ«⊞§εκ§ζκ§≔ζκ⁰§≔ηκ⁰»»Eε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘LιLιχ⌊ι⌈ι⟧⟧ 

Try it online! Link is to verbose version of code. Note: TIO link limited to 10,000 iterations as 1,000,000 is too slow. Explanation:

≔E⁷⟦⟧ε≔Eε⁰ζ≔⮌ζη

Start with an array of 7 empty lists of counts needed to reach the goal, a list of counts tracking the next goal, and a list of cards seen so far for each goal.

F×φφ«

Loop 1,000,000 times.

≔⟦⟧θF¹³⊞θ‽⁻E⁵²λθ

Deal 13 different cards at random.

≧|ΣX²θη

Convert the cards into a bitmask and mark them as having been seen for each goal.

≦⊕ζ

Increment the count for each goal.

≔Eη↨⁻⊖X²¦⁵³κ⁸¹⁹²δ

For each goal, find all the suits for which all of the cards have now been seen.

F⁷F⎇﹪κ²⁼¹Σ…§δκ⊘⁺³κ›⊗№§δκ⁰κ

For each goal, check whether it has been satisfied: goals 2, 4 and 6 require specific suits to have been seen while the other goals only require a count of seen suits.

«⊞§εκ§ζκ§≔ζκ⁰§≔ηκ⁰»»

If the goal has been satisfied then save the count and restart that goal.

Eε⪫⟦⊕κ⟦∕÷⁺×χΣι⊘LιLιχ⌊ι⌈ι⟧⟧ 

Format the averages as desired. Sample outputs (from TIO):

1 [7.7, 3, 16]  [7.8, 3, 16]  [7.7, 3, 14] 
2 [11.7, 4, 35] [11.6, 4, 32] [11.7, 3, 33]
3 [10.0, 5, 21] [10.0, 5, 20] [10.0, 5, 19]
4 [13.9, 6, 39] [14.1, 6, 34] [14.0, 7, 33]
5 [12.4, 7, 27] [12.5, 7, 23] [12.5, 7, 24]
6 [15.7, 8, 39] [15.6, 7, 37] [15.4, 7, 39]
7 [16.5, 8, 39] [16.5, 9, 38] [16.5, 8, 37]
\$\endgroup\$
1
\$\begingroup\$

Python 2 (PyPy), 244 bytes

from random import*
R=range
for g in R(1,8):
 j=s=0;r=[]
 for _ in R(10**6):
	for c in sample(R(52),13):s|=1<<c
	S=[s>>13*i&8191>8190for i in R(4)];j+=1.;g%2>0>S.sort()
	if all(S[g/-2:]):r+=j,;j=s=0
 print g,round(sum(r)/len(r),1),min(r),max(r)

Try it online!

Results of three runs:

1  7.7 2 19    1  7.7 3 18    1  7.7 3 18
2 11.6 3 50    2 11.6 3 49    2 11.6 3 45
3 10.0 4 24    3 10.0 4 24    3 10.0 4 24
4 14.0 4 46    4 14.0 4 47    4 14.0 5 58
5 12.4 5 33    5 12.4 6 30    5 12.4 6 32
6 15.4 5 52    6 15.4 5 51    6 15.4 6 54
7 16.4 7 53    7 16.4 7 54    7 16.4 7 51

By replacing the inner for loop by exec, we can trade in 10 bytes for a bit of memory usage1:

from random import*
R=range
for g in R(1,8):j=s=0;r=[];exec'for c in sample(R(52),13):s|=1<<c\nS=[s>>13*i&8191>8190for i in R(4)];j+=1.;g%2>0>S.sort()\nif all(S[g/-2:]):r+=j,;j=s=0\n'*10**6;print g,round(sum(r)/len(r),1),min(r),max(r)

Don't try it online!

1 After changing 10**6 to 10**5 this finished while using 4 GB of RAM. 10*4 = 40?

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

Perl 5 (List::Util), 195 231 bytes

for$g(map'^('.($_%2?'':'(.{13})*').'1{13}){'.($_/2^0).'}',2..8){my@n;for(1..1e6){$n=0;$s=0 x52;while($s!~$g){$h=1x13;substr$h,rand 1+length$h,0,0for 1..39;$s|=$h;$n++}push@n,$n}printf++$i." %.1f %d %d\n",sum(@n)/@n,min(@n),max(@n)}

Try it online!

A million times gave the following output from the three runs which took more than 14 minutes each:

1 7.7 2 20     |  1 7.7 2 22     |  1 7.7 2 22
2 11.6 2 61    |  2 11.6 2 69    |  2 11.6 2 58
3 10.0 4 26    |  3 10.0 4 28    |  3 10.0 4 28
4 14.0 4 59    |  4 14.0 4 58    |  4 14.0 4 61
5 12.4 5 36    |  5 12.4 5 40    |  5 12.4 5 36
6 15.4 5 62    |  6 15.4 5 56    |  6 15.4 6 60
7 16.4 6 65    |  7 16.4 6 61    |  7 16.4 6 60
\$\endgroup\$
4
  • \$\begingroup\$ You forgot the minimum and maximum number of hands. \$\endgroup\$
    – DjinTonic
    Jul 23, 2021 at 21:01
  • \$\begingroup\$ @DjinTonic I've updated now. Misinterpreted an earlier version of the text as to min and max being optional. \$\endgroup\$
    – Kjetil S
    Jul 24, 2021 at 12:51
  • \$\begingroup\$ No problem. I wanted to make sure your code included it to make the playing field even. I hope you enjoyed the challenge. \$\endgroup\$
    – DjinTonic
    Jul 24, 2021 at 12:59
  • \$\begingroup\$ yep I did :---) \$\endgroup\$
    – Kjetil S
    Jul 24, 2021 at 15:32
0
\$\begingroup\$

PHP, 364, 348, 343, 342, 338, 330

for(;$r<23;){if(7==$l=$r++%8)continue;for($d=$x=$c=$s=$g=0,$m=2e6;$d++<1e6;){foreach(array_rand(range(0,51),13)as$a)$u[$a]=$a%4;$t=array_count_values($u);~$l&1&&rsort($t);for($h=-1;$h++<$o=$l>>1;)if(($t[$h]??0)<13)break;$c++;if($h>$o){$s+=$c;$m=min($m,$c);$x=max($x,$c);$g++;$c=0;$u=[];}}$f=round($s/$g,1);echo++$l.":$f,$m,$x\n";}

Try it online!

Outputs three consecutive sets of seven goals

-4 bytes thanks to @Djin Tonic for the idea to shuffle cards differently!

Original naive implementation ungolfed:

for($run=1;$run<=3;$run++){
  $row=1;
  for($suit_match_count=0;$suit_match_count<=3;$suit_match_count++){//number of given suits to match (-1)
    for($match_type_switch=0;$match_type_switch<=1;$match_type_switch++){//switch between 'any' and 'given'
      if($suit_match_count==3 && $match_type_switch==1) {//last two cases are the same so skip
        continue;
      }
      $goal_count=0;
      $goal_deals_sum=0;
      $goal_deal_count=0;
      $running=[];
      $min_deals=1000001;//outside of range
      $max_deals=0;
      for($deal_count=0;$deal_count<1000000;$deal_count++){//million deals
        $deal=[];
        for(;count($deal)<13;){//one deal
          $card=rand(1,52);
          $deal[$card]=1;
          $running[$card]=$card%4;
        }

        $suit_count = array_count_values($running);//check for complete suits
    
        if($match_type_switch==0){
          rsort($suit_count);
        }
        
        for($check_suit_match=0;$check_suit_match<=$suit_match_count;$check_suit_match++){
          if (($suit_count[$check_suit_match]??0)!=13) {
            break;
          }
        }
        $goal_deal_count++;
        if($check_suit_match==($suit_match_count+1)){//we have our desired number of matched suits
          $goal_count++;
          $goal_deals_sum+=$goal_deal_count;

          if($goal_deal_count<$min_deals){
            $min_deals=$goal_deal_count;
          }
          if($goal_deal_count>$max_deals){
            $max_deals=$goal_deal_count;
          }
          $goal_deal_count=0;
          $running=[];
        }
      }
      echo "$row [".(intval(10*$goal_deals_sum/$goal_count)/10).",$min_deals,$max_deals]\n";
      
      $row++;
    }
  }
  echo "\n\n";
}
\$\endgroup\$
5
  • \$\begingroup\$ Your output for 1 million runs is wrong at TryItOnline. Please add your output for 3 runs of your program. Then compare them to all the results others got. For example, the average number of hands to reach goal 7 is 16.4, not 15.4 or 15.3. \$\endgroup\$
    – DjinTonic
    Jul 25, 2021 at 12:42
  • \$\begingroup\$ Thanks. Counting logic and incorrect sorting fixed. \$\endgroup\$ Jul 25, 2021 at 14:22
  • \$\begingroup\$ I don't know PHP, but would it save anything if a hand was generated as just positions 0-12 of the result of calling shuffle() on the array [1...52], rather than adding 13 random cards in 1-52 to an empty array? \$\endgroup\$
    – DjinTonic
    Jul 25, 2021 at 15:19
  • \$\begingroup\$ I could do: $a=range(0,51);shuffle($a);$a=array_slice($a,0,13); . Except that I'm doing two things at once in my loop, both finding unique cards out of 52 (as a key) and getting the suit for each card (as a value). I would still need a loop to get suits even with shuffle(). \$\endgroup\$ Jul 25, 2021 at 15:33
  • \$\begingroup\$ Roger that, thanks. \$\endgroup\$
    – DjinTonic
    Jul 25, 2021 at 15:47

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.