Problem 54: Poker Hands

Mathematical Development

Formal Development

Definition 1 (Card and Hand). A card is a pair $(v, s)$ where $v \in \{2, 3, \ldots, 14\}$ is the value (with $11 = \mathrm{J}$, $12 = \mathrm{Q}$, $13 = \mathrm{K}$, $14 = \mathrm{A}$) and $s \in \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\}$ is the suit. A hand is an ordered 5-tuple of distinct cards $H = (c_1, c_2, c_3, c_4, c_5)$.

Definition 2 (Derived Quantities). For a hand $H$ with values $v_1, \ldots, v_5$ and suits $s_1, \ldots, s_5$, define:

• Frequency function: $f(v) = |\{i : v_i = v\}|$ for each $v \in \{2, \ldots, 14\}$.
• Frequency partition: The multiset $\{f(v) : f(v) > 0\}$, sorted in decreasing order.
• Flush predicate: $\phi(H) \iff s_1 = s_2 = \cdots = s_5$.
• Straight predicate: $\sigma(H) \iff$ the sorted distinct values form 5 consecutive integers, or equal $\{2, 3, 4, 5, 14\}$ (the ace-low, or “wheel,” straight).

Definition 3 (Hand Category). The category $c(H) \in \{0, 1, \ldots, 9\}$ is defined by the following decision procedure, evaluated in order of priority (highest first):

Definition 4 (Comparison Key). The comparison key $\kappa(H)$ is a tuple enabling lexicographic comparison:

where $(\tau_1, \ldots, \tau_m)$ are tiebreaker values defined as follows:

• For straights and straight flushes: $\tau_1 =$ the high card of the straight (with the wheel having high card 5, not 14).
• For all other categories: the distinct values appearing in $H$, sorted by $(f(v), v)$ in descending order.

Theorem 1 (Correctness of Lexicographic Comparison). For any two hands $H_1, H_2$ (with no ties, as guaranteed by the problem), $H_1$ beats $H_2$ if and only if $\kappa(H_1) > \kappa(H_2)$ in lexicographic order.

Proof. The proof proceeds by case analysis on the structure of the comparison key.

Primary comparison. If $c(H_1) \neq c(H_2)$, the hand with higher category wins. This is correct since the category ordering reflects the standard poker hand hierarchy.

Tiebreaking within a category. Suppose $c(H_1) = c(H_2) = c$. The standard poker rules prescribe:

1. Four of a Kind ($c = 7$): Compare the value of the quadruple, then the kicker. The key $(\tau_1, \tau_2)$ = (quad value, kicker value) achieves this.

2. Full House ($c = 6$): Compare the triple value, then the pair value. The key $(\tau_1, \tau_2)$ = (triple value, pair value) achieves this.

3. Flush / High Card ($c \in \{0, 5\}$): Compare values in descending order. Since all frequencies are 1, sorting by $(f(v), v)$ descending is equivalent to sorting by $v$ descending.

4. Straight / Straight Flush ($c \in \{4, 8, 9\}$): The straight’s high card determines the winner.

5. Three of a Kind ($c = 3$): Compare triple value, then kickers in descending order.

6. Two Pairs ($c = 2$): Sorting by $(f(v), v)$ descending yields (higher pair, lower pair, kicker), which is the correct comparison order.

7. One Pair ($c = 1$): Sorting yields (pair value, then kickers descending).

In each case, the lexicographic ordering of $\kappa$ faithfully implements the poker comparison rules. $\blacksquare$

Lemma 1 (Ace-Low Straight Correction). When the sorted values are $\{2, 3, 4, 5, 14\}$ and the straight predicate holds, the ace must be reinterpreted as value 1. The comparison key uses high card $= 5$.

Proof. By standard poker rules, $A$-$2$-$3$-$4$-$5$ is the lowest straight (high card 5). Without this correction, the ace (value 14) would make this straight rank above $2$-$3$-$4$-$5$-$6$ (high card 6), contradicting the rules. $\blacksquare$

Editorial

We read the file line by line, split each record into the two five-card hands, and evaluate both hands into comparison keys. Each key consists of the hand category together with the category-specific tiebreak values derived from frequencies, straights, and flushes, including the ace-low straight correction. Player 1 wins precisely when the lexicographic key of the first hand exceeds that of the second, so the final answer is the total number of such lines.

Pseudocode

Algorithm: Counting Poker Hands Won by Player 1
Require: A list of poker deals, each containing two five-card hands.
Ensure: The number of deals for which Player 1 has the stronger hand.
1: Read all game records and initialize wins ← 0.
2: For each record, split the ten cards into hands H_1 and H_2.
3: Evaluate each hand H into a comparison key kappa(H) determined by its category and the corresponding tie-break values.
4: If kappa(H_1) > kappa(H_2), update wins ← wins + 1.
5: Return wins.

Complexity Analysis

Proposition 1 (Time). The algorithm processes $H = 1000$ hands. Each hand evaluation involves:

• Parsing 5 cards: $O(5) = O(1)$.
• Sorting 5 values: $O(5 \log 5) = O(1)$.
• Frequency counting over at most 13 values: $O(1)$.
• Category classification and key construction: $O(1)$.
• Lexicographic comparison of fixed-length tuples: $O(1)$.

Total: $O(H) = O(1000)$.

Proposition 2 (Space). $O(1)$ per hand evaluation. $O(H)$ if all lines are stored; $O(1)$ if processed line-by-line.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 54: Poker Hands
 *
 * Usage:
 *   Place 'poker.txt' in the same directory and run:
 *       ./solution
 *   Or pipe via stdin:
 *       ./solution < poker.txt
 *
 *   Download poker.txt from: https://projecteuler.net/problem=54
 *   (requires a free Project Euler account)
 *
 * Answer: 376
 */

int card_value(char c) {
    if (c >= '2' && c <= '9') return c - '0';
    if (c == 'T') return 10;
    if (c == 'J') return 11;
    if (c == 'Q') return 12;
    if (c == 'K') return 13;
    if (c == 'A') return 14;
    return 0;
}

// Compute comparison key kappa(H) as a vector for lexicographic comparison
vector<int> evaluate(vector<pair<int,char>>& hand) {
    vector<int> vals;
    set<char> suits;
    map<int,int> freq;
    for (auto& [v, s] : hand) {
        vals.push_back(v);
        suits.insert(s);
        freq[v]++;
    }
    sort(vals.begin(), vals.end());

    bool is_flush = (suits.size() == 1);

    bool is_straight = false;
    int straight_high = 0;
    set<int> unique_vals(vals.begin(), vals.end());
    if (unique_vals.size() == 5) {
        if (vals[4] - vals[0] == 4) {
            is_straight = true;
            straight_high = vals[4];
        }
        if (unique_vals.count(14) && unique_vals.count(2) &&
            unique_vals.count(3) && unique_vals.count(4) && unique_vals.count(5)) {
            is_straight = true;
            straight_high = 5;
        }
    }

    // Sort values by (frequency desc, value desc)
    vector<pair<int,int>> freq_val;
    for (auto& [v, f] : freq) freq_val.push_back({f, v});
    sort(freq_val.begin(), freq_val.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second > b.second;
    });

    vector<int> tiebreakers;
    for (auto& [f, v] : freq_val) tiebreakers.push_back(v);

    vector<int> counts;
    for (auto& [f, v] : freq_val) counts.push_back(f);

    int rank = 0;
    if (is_straight && is_flush) {
        rank = (straight_high == 14) ? 9 : 8;
        tiebreakers = {straight_high};
    } else if (counts.size() >= 1 && counts[0] == 4) {
        rank = 7;
    } else if (counts.size() >= 2 && counts[0] == 3 && counts[1] == 2) {
        rank = 6;
    } else if (is_flush) {
        rank = 5;
    } else if (is_straight) {
        rank = 4;
        tiebreakers = {straight_high};
    } else if (counts.size() >= 1 && counts[0] == 3) {
        rank = 3;
    } else if (counts.size() >= 2 && counts[0] == 2 && counts[1] == 2) {
        rank = 2;
    } else if (counts.size() >= 1 && counts[0] == 2) {
        rank = 1;
    } else {
        rank = 0;
    }

    vector<int> result = {rank};
    for (int t : tiebreakers) result.push_back(t);
    return result;
}

int main() {
    ifstream fin("poker.txt");
    if (!fin.is_open()) fin.open("p054_poker.txt");
    istream& in = fin.is_open() ? fin : cin;

    int p1_wins = 0;
    string line;
    while (getline(in, line)) {
        if (line.empty()) continue;
        istringstream iss(line);
        vector<pair<int,char>> h1(5), h2(5);
        string card;
        bool valid = true;
        for (int i = 0; i < 5; i++) {
            if (!(iss >> card) || card.size() < 2) { valid = false; break; }
            h1[i] = {card_value(card[0]), card[1]};
        }
        for (int i = 0; i < 5; i++) {
            if (!(iss >> card) || card.size() < 2) { valid = false; break; }
            h2[i] = {card_value(card[0]), card[1]};
        }
        if (!valid) continue;

        auto s1 = evaluate(h1);
        auto s2 = evaluate(h2);
        if (s1 > s2) p1_wins++;
    }

    cout << p1_wins << endl;
    return 0;
}

"""
Problem 54: Poker Hands

How many hands does Player 1 win in the poker game?

Usage:
    Place 'poker.txt' (or 'p054_poker.txt') in the same directory, then run:
        python solution.py
    Or pipe via stdin:
        python solution.py < poker.txt

    Download poker.txt from: https://projecteuler.net/problem=54
    (requires a free Project Euler account)
"""
import sys
import os
from collections import Counter


def card_value(c):
    values = {'2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8,
              '9': 9, 'T': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}
    return values[c]


def evaluate(cards):
    """
    Compute the comparison key kappa(H) for a 5-card poker hand.
    Returns a tuple for lexicographic comparison.

    Categories: 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,
    8=Straight Flush, 9=Royal Flush
    """
    values = sorted([card_value(c[0]) for c in cards], reverse=True)
    suits = [c[1] for c in cards]

    is_flush = len(set(suits)) == 1

    unique_vals = sorted(set(values))
    is_straight = False
    straight_high = 0

    if len(unique_vals) == 5:
        if unique_vals[-1] - unique_vals[0] == 4:
            is_straight = True
            straight_high = unique_vals[-1]
        if unique_vals == [2, 3, 4, 5, 14]:
            is_straight = True
            straight_high = 5

    freq = Counter(values)
    groups = sorted(freq.items(), key=lambda x: (-x[1], -x[0]))
    counts = [f for v, f in groups]
    tiebreakers = tuple(v for v, f in groups)

    if is_straight and is_flush:
        rank = 9 if straight_high == 14 else 8
        return (rank, straight_high)
    elif counts[0] == 4:
        return (7,) + tiebreakers
    elif counts[0] == 3 and len(counts) > 1 and counts[1] == 2:
        return (6,) + tiebreakers
    elif is_flush:
        return (5,) + tiebreakers
    elif is_straight:
        return (4, straight_high)
    elif counts[0] == 3:
        return (3,) + tiebreakers
    elif counts[0] == 2 and len(counts) > 1 and counts[1] == 2:
        return (2,) + tiebreakers
    elif counts[0] == 2:
        return (1,) + tiebreakers
    else:
        return (0,) + tiebreakers


def solve():
    lines = None

    script_dir = os.path.dirname(os.path.abspath(__file__))
    for filename in ['poker.txt', 'p054_poker.txt', '0054_poker.txt']:
        filepath = os.path.join(script_dir, filename)
        if os.path.exists(filepath):
            with open(filepath) as f:
                lines = f.readlines()
            break

    if lines is None:
        if not sys.stdin.isatty():
            lines = sys.stdin.readlines()
        else:
            print("Error: poker.txt not found.")
            print("Download from https://projecteuler.net/problem=54")
            print("Or pipe via stdin: python solution.py < poker.txt")
            return

    p1_wins = 0
    for line in lines:
        line = line.strip()
        if not line:
            continue
        cards = line.split()
        if len(cards) < 10:
            continue
        hand1 = cards[:5]
        hand2 = cards[5:10]
        if evaluate(hand1) > evaluate(hand2):
            p1_wins += 1

    print(p1_wins)

solve()