The Problem: Project Euler #54
In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:
The cards are valued in the order: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives. But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared; if the highest cards tie then the next highest cards are compared, and so on.
...
The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1's cards and the last five are Player 2's cards. You can assume that all hands are valid (no invalid characters or repeated cards), each player's hand is in no specific order, and in each hand there is a clear winner.
How many hands does Player 1 win?
The solution:
I've been an avid poker player since college (and incidentally about the time the WPT got on ESPN). That is why, when I saw the description for problem 54, I leapt to start working on it. On the surface it seemed very straightforward: - Parse the hands - Assign a numeric score to each based on the table of hand ranks - Calculate winner in event of a tie (highest cards) - Tally wins / losses
After wasting about 2 hours on something that didn't really work, I took a break to think about how to model the poker hand data in a way that would make it easy to calculate the 'score' of a hand, and if a tie occurred, find the best 5-card hand (I decided to add the ability to do more than just 5-card poker hands, in the spirit of reusability and since most poker games use 7 cards). In the end, I opted for dictionaries of lists. The keys represent the 4 possible quantities of a certain card a hand could contain.
data = { 1: [J, 9], 2: [], 3: [K], 4: [] }
There are three main benefits to using this model. One, it makes it easy to 'score' a hand - just see if there is anything in the 4-bucket, 3-bucket, and so on. Two, it makes deciding the winner in the event of a tie very easy. Since lists are comparable, if two hands each have a three-of-a-kind, comparing the contents of the 3-bucket will reveal the winner. If two hands share the same pair, the comparison skips to the next lowest bucket. Lastly, when calculating a 5-card poker hand from a hand that potentially contains 7 cards, it is good to know how many cards you've "used" - and this is where the key / value relationship shines. If data[2] = [K, J] and data[1] = [A], I know I have a hand of KKJJA (multiplying the items in the list by the key), and likewise if data[2] = [K, J, 9] and data[1] = [Q], I can tell that KKJJQ is actually the best hand instead of [KKJJ9(9)].
Here's how I sort a poker hand according to the above guidelines (I automatically correct for quirky 7-card hands like 2x3-of-a-kind or 3x2-of-a-kind).
def poker_sort(hand):
data = { 1: [], 2: [], 3: [], 4: [] }
vals = values_from_hand(hand)
for card in vals:
added = False
for i in range(3, 0, -1):
if card in data*:
card_list = data*
idx = card_list.index(card)
del(data*[idx])
data[i+1].append(card)
added = True
if not added:
data[1].append(card)
for k, v in data.items():
v.sort()
v.reverse()
# correct for 5-card hands (i.e., 2x3-of-a-kind or 3x2-of-a-kind)
if len(data[3]) > 1:
data[2].append(data[3][-1])
del(data[3][-1])
if len(data[2]) > 2:
data[1].append(data[2][-1])
del(data[2][-1])
return data
# populate first 2 spots with dummies so indices match to actual values
CARDS = ['!', '!', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A']
def values_from_hand(hand):
"""
Return sorted numeric values of cards in a hand
"""
values = []
for card in hand:
val = CARDS.index(card[0]) # cards look like 'KH' for King of hearts
values.append(val)
values.sort()
return values
My implementation can be found on GitHub:
Poker hand evaluator.
Also check out the other Project Euler solutions.
Commenting has been closed, but please feel free to contact me