Problem 54 — Poker Hands

solved Thu, 12 Dec 2019, 09:35 · level 3 · difficulty 8% projecteuler.net github

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 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?


Problem Analysis

At its core, this problem asks me to impose a total order on poker hands - a rule that, given any two hands, decides unambiguously which one is greater. A total order is a comparison relation under which every pair of elements can be ranked relative to each other with no ties (the problem guarantees a clear winner). The technique is to map each hand to a comparison key that captures both its category (pair, flush, full house, and so on) and the cascading tie-breaker data (which pair first, then which kicker, then the next). Once each hand is reduced to such a key, choosing the winner is a single comparison.

The key observation is that every poker category can be detected with two cheap pieces of derived data: a frequency count of how often each card value appears, plus two boolean flags - whether all five suits match (a flush) and whether the five distinct values form a consecutive run (a straight). Four-of-a-kind, full house, three-of-a-kind, two pairs, and one pair are distinguished purely by the shape of the frequency counts; flush and straight come from the two flags; straight flush and royal flush are their combination. Because a hand is always exactly five cards, every per-hand operation - counting, sorting, flag checks - is O(1). Processing N lines from the file is therefore O(N) overall, and here N is just 1000.

Solution Approach

Canonical Hand Evaluation with a Sorted Frequency Table

Both the Python (p0054_s0.py) and C (p0054_s0.c) solutions implement the same algorithm and differ only in language idioms. For each line, the ten whitespace-separated tokens are split into Player 1's first five cards and Player 2's last five. Each hand is evaluated independently into a (rank, tie-breakers) structure, and the two structures are then compared.

My first design decision is how to turn a card character into a number. I encode the value ordering as the string "23456789TJQKA" and take each card's integer rank from its position in that string, so '2' maps to 0, 'T' to 8, and 'A' to 12. In Python this is VALUES.index(c); in C it is pointer arithmetic via strchr. I prefer this over a dictionary or a switch because the ordering is implicit in the string and the data stays collocated and readable.

Next I compute the two flags. is_flush is true when all five suits are identical. is_straight is true when the five values are all distinct and max - min == 4 - a compact test for "five consecutive values" that avoids explicitly sorting and walking the run. If both flags hold, the hand is a straight flush; if additionally the lowest value is 8 (the run T-J-Q-K-A), it is a royal flush. Settling these top categories first keeps the high-end cases short.

For everything else, I build a frequency table of (count, value) pairs and sort it by count descending, then value descending. This single sort into canonical form is the heart of the classification: the dominant group always lands first, so I only need to inspect the first one or two entries. A leading count of 4 is four-of-a-kind; 3 followed by 2 is a full house; a lone 3 is three-of-a-kind; two consecutive 2s is two pairs; a single 2 is one pair; otherwise high card. Crucially, I build the tie-breaker sequence in priority order at the same time - the dominant value first, then kickers in descending order - so that comparing two hands of equal rank becomes a plain lexicographic comparison of the tie-breaker tuples with no extra branching.

In Python the result is a HandRank dataclass with a custom __gt__; the hand itself is a PokerHand dataclass whose hand_rank is a functools.cached_property, and the categories are an IntEnum so they compare as integers. The C version mirrors this with a HandRank struct holding the rank enum plus a fixed five-element tie-breaker array and a count, and a hand_rank_gt function that returns on the first differing element. The C code also defends against blank and short lines, using strtok_r for reentrant tokenisation.

workbench

Test cases

categoryinputanswer
main file_url = https://projecteuler.net/resources/documents/0054_poker.txt 376

Results

solutioncategoryanswerverdict avg seconds cavg seconds py
p0054_s0 main 376 correct 0.000431 (63) 0.008660 (63)

Files

Tags & blogs