Project Euler Problem 54 Statement
In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:
- High Card: Highest value card.
- One Pair: Two cards of the same value.
- Two Pairs: Two different pairs.
- Three of a Kind: Three cards of the same value.
- Straight: All cards are consecutive values.
- Flush: All cards of the same suit.
- Full House: Three of a kind and a pair.
- Four of a Kind: Four cards of the same value.
- Straight Flush: All cards are consecutive values of same suit.
- Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.
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 (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then the highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.
Consider the following five hands dealt to two players:
Hand | Player 1 | Player 2 | Winner | |||
1 | 5H 5C 6S 7S KD Pair of Fives | 2C 3S 8S 8D TD Pair of Eights | Player 2 | |||
2 | 5D 8C 9S JS AC Highest card Ace | 2C 5C 7D 8S QH Highest card Queen | Player 1 | |||
3 | 2D 9C AS AH AC Three Aces | 3D 6D 7D TD QD Flush with Diamonds | Player 2 | |||
4 | 4D 6S 9H QH QC Pair of Queens Highest card Nine | 3D 6D 7H QD QS Pair of Queens Highest card Seven | Player 1 | |||
5 | 2H 2D 4C 4D 4S Full House With Three Fours | 3C 3D 3S 9S 9D Full House with Three Threes | Player 1 |
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?
Solution
This is a discussion describing a solution to Project Euler Problem 54, which involves determining the winner between two poker hands based on standard poker hand rankings. Below is a detailed breakdown of the script's functionality and logic.
1. Importing Necessary Modules and Defining Card Values
The script begins by importing the Counter
class from the collections
module. Counter
is instrumental in tallying the frequency of each card value in a hand, which is crucial for identifying pairs, three-of-a-kind, and other combinations.
from collections import Counter
# Define card values, mapping each rank to its numerical value
values = {r: i for i, r in enumerate('23456789TJQKA', start=2)}
Here, a dictionary named values
maps each card rank (from '2' up to 'A' for Ace) to its corresponding numerical value. This numerical representation simplifies the comparison of card ranks later in the script.
2. Defining Straights and Hand Rankings
# Define all possible straights, including the Ace-low straight as (5,4,3,2,1)
straights = [(v, v-1, v-2, v-3, v-4) for v in range(14, 5, -1)] + [(5, 4, 3, 2, 1)]
# Define ranks based on frequency of card values
# The index represents the hand type's strength
# 0: High card, 1: One Pair, 2: Two Pairs, 3: Three of a Kind,
# 4: Straight, 5: Flush, 6: Full House, 7: Four of a Kind
ranks = [
(1, 1, 1, 1, 1), # High card
(2, 1, 1, 1), # One Pair
(2, 2, 1), # Two Pairs
(3, 1, 1), # Three of a Kind
(), # Straight (handled separately)
(), # Flush (handled separately)
(3, 2), # Full House
(4, 1) # Four of a Kind
]
The straights
list comprehensively includes all possible sequences of five consecutive card values, accounting for the special case where Ace acts as the lowest card in a straight (i.e., A-2-3-4-5).
Next, the script defines a ranks
list that categorizes different hand types based on the frequency of card values:
Each tuple within ranks
represents the frequency pattern of card values in a hand. For example, (2, 1, 1, 1)
corresponds to one pair, while (3, 2)
denotes a full house.
3. Determining the Rank of a Hand
The core functionality resides in the hand_rank
function, which evaluates and assigns a rank to a given poker hand:
def hand_rank(hand):
# Count the frequency of each card value
counts = Counter(card[0] for card in hand)
# Sort the counts first by frequency descending, then by card value descending
sorted_counts = sorted(((v, values[k]) for k, v in counts.items()), reverse=True)
# Zip the sorted counts to separate frequencies and values
score = list(zip(*sorted_counts))
# Determine the rank based on the frequency pattern
try:
score[0] = ranks.index(score[0])
except ValueError:
score[0] = 0 # Default to High card if not found
# Check for Flush (all cards have the same suit)
if len(set(card[1] for card in hand)) == 1:
score[0] = 5 # Flush rank
# Current straight sequence
current_straight = tuple(score[1])
# Handle Ace-low straight by adjusting card values
if current_straight == (14, 5, 4, 3, 2):
score[1] = (5, 4, 3, 2, 1)
current_straight = (5, 4, 3, 2, 1)
# Check for Straight or Straight Flush
if current_straight in straights:
score[0] = 8 if score[0] == 5 else 4 # 8: Straight Flush, 4: Straight
return score
Step-by-Step Breakdown:
- Counting Card Frequencies:
The function uses
Counter
to tally how many times each card value appears in the hand. - Sorting Counts:
It sorts the card counts in descending order of frequency and then by the card's numerical value. This sorting helps in identifying the hand type based on the frequency pattern.
- Determining Hand Rank:
By matching the sorted frequency pattern with the predefined
ranks
list, the function assigns a rank to the hand. If the pattern isn't found (which implies a high card scenario), it defaults to rank0
. - Checking for a Flush:
A flush is identified if all cards share the same suit. If a flush is detected, the hand's rank is updated to
5
. - Handling Straights:
The function verifies if the hand forms a straight by checking if the sorted card values match any sequence in the
straights
list. It also accounts for the Ace-low straight by adjusting the card values accordingly. If a straight is present and the hand is also a flush, it upgrades the rank to8
(Straight Flush); otherwise, it assigns rank4
for a regular straight.
4. Processing Input and Determining the Winner
Finally, the script reads input test cases, evaluates each player's hand, and determines the winner:
# Read number of test cases
for _ in range(int(input())):
hand = input().split()
# Split into Player 1 and Player 2's hands
player1 = hand[:5]
player2 = hand[5:]
# Compare the ranks and determine the winner
if hand_rank(player1) > hand_rank(player2):
print("Player 1")
else:
print("Player 2")
Execution Flow:
- Input Handling:
The script first reads the number of test cases. For each test case, it expects a line containing ten cards, representing two five-card hands–five for Player 1 and five for Player 2.
- Hand Separation:
It splits the input line into two separate lists:
player1
andplayer2
, each containing five card strings. - Rank Comparison:
Using the
hand_rank
function, it evaluates both players' hands. Since thehand_rank
function returns a list where the first element is the primary rank, and subsequent elements are tie-breakers (like high card values), Python's list comparison inherently handles the comparison logic. - Outputting the Winner:
If Player 1's hand rank is superior to Player 2's, the script prints "Player 1"; otherwise, it prints "Player 2".
Python Source Code
from collections import Counter
values = {r: i for i, r in enumerate('23456789TJQKA', start=2)}
straights = [(v, v-1, v-2, v-3, v-4) for v in range(14, 5, -1)] + [(5, 4, 3, 2, 1)]
ranks = [(1, 1, 1, 1, 1), (2, 1, 1, 1), (2, 2, 1), (3, 1, 1), (), (), (3, 2), (4, 1)]
def hand_rank(hand):
counts = Counter(card[0] for card in hand)
sorted_counts = sorted(((v, values[k]) for k, v in counts.items()), reverse=True)
score = list(zip(*sorted_counts))
try:
score[0] = ranks.index(score[0])
except ValueError:
score[0] = 0 # Default to High card if not found
if len(set(card[1] for card in hand)) == 1:
score[0] = 5 # Flush rank
current_straight = tuple(score[1])
if current_straight == (14, 5, 4, 3, 2):
score[1] = (5, 4, 3, 2, 1)
current_straight = (5, 4, 3, 2, 1)
if current_straight in straights:
score[0] = 8 if score[0] == 5 else 4 # 8: Straight Flush, 4: Straight
return score
for _ in range(int(input())):
hand = input().split()
player1, player2 = hand[:5], hand[5:]
print("Player 1" if hand_rank(player1) > hand_rank(player2) else "Player 2")
Last Word
Ace Duality: In poker, Ace can act as both the highest (A, K, Q, J, T) and the lowest (A, 2, 3, 4, 5) card in straights.