Project Euler Problem 54 Solution

Project Euler Problem 54 Solution

Poker Hands

by {BetaProjects} | Project Euler & HackerRank

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:

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:

  1. Counting Card Frequencies:

    The function uses Counter to tally how many times each card value appears in the hand.

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

  3. 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 rank 0.

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

  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 to 8 (Straight Flush); otherwise, it assigns rank 4 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:

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

  2. Hand Separation:

    It splits the input line into two separate lists: player1 and player2, each containing five card strings.

  3. Rank Comparison:

    Using the hand_rank function, it evaluates both players' hands. Since the hand_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.

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