Project Euler Solution 54: Poker Hands

Code & Zahlen

Project Euler Problem 54: Poker Hands is one without mathematical insights and just complex business logic. We have to rank poker hands.

We are given a list of poker hands and have to decide which player has one.

Using the given examples, we can already write a first test:

def test_with_examples() -> None:
    assert not player_1_wins("5H 5C 6S 7S KD 2C 3S 8S 8D TD")
    assert player_1_wins("5D 8C 9S JS AC 2C 5C 7D 8S QH")
    assert not player_1_wins("2D 9C AS AH AC 3D 6D 7D TD QD")
    assert player_1_wins("4D 6S 9H QH QC 3D 6D 7H QD QS")
    assert player_1_wins("2H 2D 4C 4D 4S 3C 3D 3S 9S 9D")

In order to solve this problem, we need to be able to parse these hands. One complication are that there are some numerical ones, but also alphabetic values. We have T for 10, J for jack, Q for queen, K for king and A for ace. We need t a function that maps a number or string to a value:

def map_value(value: str) -> int:
    try:
        return int(value)
    except ValueError:
        return {"T": 10, "J": 11, "Q": 12, "K": 13, "A": 14}[value]

Then we can use that to parse a hand:

def parse_hand(hand: str) -> list[tuple[int, str]]:
    cards = hand.split()
    return [(map_value(pair[0]), pair[1]) for pair in cards]

We parse the hands of player 1 and player 2. Then we sort the cards such that they have a defined order. We first sort by the value, then by the suit. Next we let another function give a rating of the whole hand. In the end we just compare whether the hand of player 1 is greater than the hand of player 2 and know that player 1 wins. This is the function:

def player_1_wins(line: str) -> bool:
    cards = parse_hand(line.strip())
    hand_1 = cards[:5]
    hand_2 = cards[5:]
    hand_1.sort()
    hand_2.sort()
    rating_1 = rate_special_hand(hand_1)
    rating_2 = rate_special_hand(hand_2)
    return rating_1 > rating_2

We need to implement rate_special_hand. This has a number of predicates which determine whether a hand is of some special type, we'll look into these shortly. The function rate_special_hand iterates the predicates in reverse and picks the one which matches. If then returns the index of the predicate and the results of the predicate. These results are to be a list of the cards with the important cards first such that it defines a sensible order.

def rate_special_hand(hand: list[tuple[int, str]]) -> int:
    predicates = [
        is_high_card,
        is_one_pair,
        is_two_pairs,
        is_three_of_a_kind,
        is_straight,
        is_flush,
        is_full_house,
        is_four_of_a_kind,
        is_straight_flush,
        is_royal_flush,
    ]
    for index, predicate in reversed(list(enumerate(predicates))):
        if result := predicate(hand):
            return [index, predicate.__name__] + result

The high card is simplest. It is always the case, and we just return the values of the cards in descending order. This way the high card is first and the next card can be used as a tie-breaker.

def is_high_card(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    return sorted((value for value, suit in hand), reverse=True)

Pairs are the next special type. For this we need a helper function which can group the cards by value. And then it sorts the groups by their length. This way we can for instance take a hand with cards [3, 3, 4, 5, 5] and get [[5, 5], [3, 3], 4] and have a two pairs, fives and threes.

def group_card_values(hand: list[tuple[int, str]]) -> list[list[int]]:
    values = [value for value, suit in hand]
    values.sort(reverse=True)
    groups = [list(group) for key, group in itertools.groupby(values)]
    groups.sort(key=lambda group: (len(group), group[0]), reverse=True)
    return groups

And then we need an utility function to flatten lists:

def flatten(xss: list[list[int]]) -> list[int]:
    return [x for xs in xss for x in xs]

This lets us write a predicate for a single pair rather easily. We group the cards and if the first group has two elements, then there is at least one pair. If there is more, the other predicates will have already gotten this one. We then return the flattened list with the values.

def is_one_pair(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    groups = group_card_values(hand)
    if len(groups[0]) == 2:
        return flatten(groups)

Two pairs work very similarly. We just need to check for the first two groups.

def is_two_pairs(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    groups = group_card_values(hand)
    if len(groups[0]) == 2 and len(groups[1]) == 2:
        return flatten(groups)

And three of a kind are also straightforward to check with this.

def is_three_of_a_kind(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    groups = group_card_values(hand)
    if len(groups[0]) == 3:
        return flatten(groups)

The straigt is different. We have to see whether the values form a range. This can be checked by just taking the values, sorting them, and seeing whether that matches a range of numbers with the same start and end.

def is_straight(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    values = [value for value, suit in hand]
    values.sort(reverse=True)
    expected = list(reversed(range(min(values), max(values) + 1)))
    if values == expected:
        return values

The flush only looks at the suit of the cards. We therefore form a set of all the suits and check whether it has length 1. If that is the case, we just return all the values sorted descendingly.

def is_flush(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    if len({suit for value, suit in hand}) == 1:
        return sorted((value for value, suit in hand), reverse=True)

Using our function group_card_values, the full house is also easy to implement:

def is_full_house(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    groups = group_card_values(hand)
    if len(groups[0]) == 3 and len(groups[1]) == 2:
        return flatten(groups)

Four of a kind is just a special case of that as well, so we just write a similar function as well:

def is_four_of_a_kind(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    groups = group_card_values(hand)
    if len(groups[0]) == 4:
        return flatten(groups)

The straight flush is both a straight and a flush, so we just use the existing predicates:

def is_straight_flush(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    if is_straight(hand):
        return is_flush(hand)

The royal flush is a straight flush which ends on an ace. We can also reuse the previous predicate here:

def is_royal_flush(hand: list[tuple[int, str]]) -> Optional[list[int]]:
    if max(value for value, suit in hand) == 14:
        return is_straight_flush(hand)

The driver code then just reads the file and rates the hands.

def solution() -> int:
    wins_player_1 = 0
    with open("data/p054_poker.txt") as f:
        for line in f:
            if player_1_wins(line):
                wins_player_1 += 1
    return wins_player_1

The solution runs within 46 ms and produces the correct result. The difficulty here was not really so much in insights but rather in structuring the software such that it properly ranks all the hands in a robust way.