Problem 8 of Monte Carlo solutions to Fifty Challenging Problems...

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 8: What is the chance of being dealt a perfect hand in bridge? (being dealt 13 cards of the same suit?)

This is one place where Monte Carlo falls flat on its face. Modeling this in any sort of reasonably simple (read: naive) fashion results in a program that takes quite some time to run. It's far better to find the probability through direct combinatorial calculations. This still poses some interesting programming problems, but they're of the numerical sort, so they won't appear in this series. (It would be really great if someone would post a comment linking to a solution of this problem using hadoop on EC2 or EMR!)

#!/usr/bin/env ruby

TRIALS=100

# We model this by laying out the 52 cards in an 
# array, calling the spades 1..13.
#
# Then, we "deal" by breaking it up into contiguous
# 13-card chunks.  If any the 4 chunks of 13 are 
# 1..13, we win the "deal a perfect hand" game.
# Otherwise, we lose.

perfect_hands = 0

# I had some concerns about the performance here.
def perfect_hand_by_sort?(a)
	ap = a.sort
	return 12 == ap[12]-ap[0]
end

def perfect_hand_by_scan?(a, handno)
	x = (handno-1)*13
	min = 0
	max = 53
	while (x < (handno)*13) 
		ai = a[x]
		min = ai if ai < min
		max = ai if ai > max
		x += 1
	end

	return 12 == max-min
end

def perfect_hand_by_minmax?(a, handno)
	x = (handno-1)*13
	min = a[x..x+12].min
	max = a[x..x+12].max

	return 12 == max-min
end

t_by_sort = 0.0
t_by_scan = 0.0
t_by_minmax = 0.0


TRIALS.times do
	cards = (1..52).to_a
	cards.shuffle!

	t0 = Time.now
	hand1 = cards[0..12]
	hand2 = cards[13..25]
	hand3 = cards[26..38]
	hand4 = cards[39..51]

	p_sort = 0
	[hand1, hand2, hand3, hand4].each { |hand| 
		p_sort += 1 if perfect_hand_by_sort?(hand)
	}
	dt_sort = Time.now - t0
	t_by_sort += dt_sort

	p_scan = 0
	t0 = Time.now
	[1,2,3,4].each { |handno| 
		p_scan += 1 if perfect_hand_by_scan?(cards, handno)
	}
	dt_scan = Time.now - t0
	t_by_scan += dt_scan

	p_minmax = 0
	t0 = Time.now
	[1,2,3,4].each { |handno| 
		p_minmax += 1 if perfect_hand_by_minmax?(cards, handno)
	}
	dt_minmax = Time.now - t0
	t_by_minmax += dt_minmax

	perfect_hands += p_sort
end

puts "After #{TRIALS} trials, we got #{perfect_hands}"

puts "Times: "
puts " sort: #{t_by_sort}"
puts " scan: #{t_by_scan}"
puts " minmax: #{t_by_minmax}"

I've been coding my way through Fifty Challenging Problems in Statistics with Solutions. This post is a part of the Fifty Challenging Problems series.

This was brought to you by Josh Myer. He has other fun things at his homepage.