7
\$\begingroup\$

This was a very fun and thought provoking problem, and I'm quite proud of the way I was able to pull it off. I broke it down into 2 parts, testing and comparing.

  • Testing each group of cards for a playable hand. This returns a boolean value depending on if the cards meet the criteria for the hand. A set of cards may test positive for multiple hands. It is this reason we start with the highest ranked hand and go down. If player 1 tests positive and the other does not, then player 1 wins that play

  • If both players test positive for the same type of hand, then we must compare both hands. The compare functions test each hand to determine who wins based on highest value according to the rules of Poker.

  • If both players do not have a poker and at the end of the tests, do a simple high card comparison to determine winner

Per instructions, this solution does not attempt to verify validity of provided data. The Card class is a recycled bit of code from an old project of mine that proved to be a nice little container for card data, making the solution easier.

One thing I think I could improve on is creating a Hand class that holds the cards. Maybe I could then store some data that is frequent (such as my use of groupby in the tests), and make some nifty comparitive operators to compare Hand classes themselves to find out which one outranks the other. Never done something like that before though, don't really know how to start.

Full problem text can be found here.

from itertools import groupby
from urllib2 import urlopen
file = 'https://projecteuler.net/project/resources/p054_poker.txt'
data = urlopen(file)

class Card():
    suitNames = ('Diamonds', 'Clubs', 'Hearts', 'Spades')
    faceNames = ('2', '3', '4', '5', '6', '7', '8', '9', 'Ten', 'Jack', 'Queen', 'King', 'Ace')

    def __init__(self, str='AS'):
        # start conversion of human-readable string to proper indices
        n = len(str)
        face, suit = str[0], str[1]

        for i in range(0, 4):
            if self.suitNames[i][0] == suit:
                suit = i
                break

        if face.isdigit() is True:
            face = int(face) - 2 # index of given face value
        else:
            for i in range(8, 13):
                if self.faceNames[i][0] == face:
                    face = i
                    break

        self.suitIndex = suit
        self.faceIndex = face
        self.rank = face + 2

    def __int__(self):
        return self.rank

def testStraight(hand):
    # We test that all cards are unique in rank, and of proper sequence:
    # RankHigh - RankLow == #Cards - 1 (only works if list is uniquw)
    l = set([c.rank for c in hand])
    return len(l) is 5 and max(l) - min(l) is len(l) - 1

def testFlush(hand):
    # We test that all cards are of same suit
    return len(set(c.suitIndex for c in hand)) is 1

def testRoyal(hand):
    # We test that all cards are of same suit and
    # that lowest rank of card is ten
    return testFlush(hand) and min(hand, key=lambda x: x.rank).rank == 10

def testStraightFlush(hand):
    return testStraight(hand) and testFlush(hand)

def testFourKind(hand):
    # We group the list based on the rank of each card and test
    # if there is a 4 in the result
    l = [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    return 4 in l

def testFullHouse(hand):
    # We group the list based on the rank of each card and test
    # if there is a 3 and 2 in the result
    l = [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    return 3 in l and 2 in l

def testThreeKind(hand):
    # We group the list based on the rank of each card and test
    # if there is a 3 in the result
    l = [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    return 3 in l

def testTwoPairs(hand):
    # We group the list based on the rank of each card and test
    # if there are two groups of 2
    l = [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    return l.count(2) == 2

def testPair(hand):
    # We group the list based on the rank of each card and test
    # if there is a 2 in the result
    l = [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    return 2 in l

def compareSingleSets(hand1, hand2, n):
    # We do the same operations when comparing Pairs, Three of a Kind, and
    # Four of a Kind in that we compare the set values. 3/4 of a Kind do not
    # need additional processing as they will never tie but we include
    # additional steps for the Pair compare

    # get dict of value : number of occurrences
    l1 = {key:len(list(group)) for key, group in groupby(hand1, key=lambda x: x.rank)}
    l2 = {key:len(list(group)) for key, group in groupby(hand2, key=lambda x: x.rank)}

    # Get the value of the pairs to test
    t1 = l1.keys()[l1.values().index(n)]
    t2 = l2.keys()[l2.values().index(n)]

    if t1 > t2:
        return hand1
    elif t2 > t1:
        return hand2
    else:  # used to compare tied Pairs
        # store values of cards
        v1 = sorted(l1.keys(), reverse=True)
        v2 = sorted(l2.keys(), reverse=True)

        # remove the pair tested
        v1.remove(t1)
        v2.remove(t2)

        if v1 > v2:
            return hand1
        elif v2 > v1:
            return hand2

def compareThreeKind(hand1, hand2):
    return compareSingleSets(hand1, hand2, 3)

def comparePair(hand1, hand2):
    return compareSingleSets(hand1, hand2, 2)

def compareFourKind(hand1, hand2):
    return compareSingleSets(hand1, hand2, 4)

def compareTwoPairs(hand1, hand2):
    # Two pair is slightly different, so we cannot use the other method

    # get dict of value : number of occurrences
    l1 = {key:len(list(group)) for key, group in groupby(hand1, key=lambda x: x.rank)}
    l2 = {key:len(list(group)) for key, group in groupby(hand2, key=lambda x: x.rank)}

    # Get the value of the loner and remove it from dict
    t1 = l1.keys()[l1.values().index(1)]
    t2 = l2.keys()[l2.values().index(1)]
    l1.pop(t1)
    l2.pop(t2)
    k1 = sorted(l1.keys(), reverse=True)
    k2 = sorted(l2.keys(), reverse=True)
    if k1 > k2:
        return hand1
    elif k2 > k1:
        return hand2
    elif t1 > t2:
        return hand1
    return hand2

def compareStraight(hand1, hand2):
    # Dead simple, simply compare the highest card. Assumes hand is ordered
    if hand1[-1].rank > hand2[-1].rank:
        return hand1
    return hand2

def compareHighestCard(hand1, hand2):
    # Very simple. Make a list of all values and compare. This is also used to
    # compare Flushes
    l1 = sorted([c.rank for c in hand1], reverse=True)
    l2 = sorted([c.rank for c in hand2], reverse=True)

    if l1 > l2:
        return hand1
    return hand2

def compareFullHouse(hand1, hand2):
    # This takes a similar approach than the others, however we simply check the
    # set of 3 cards and don't check the remaining ones because there cannot be
    # two players with the same value in a regular deck without wildcards.

    #  get dict of value : number of occurrences
    l1 = {key:len(list(group)) for key, group in groupby(hand1, key=lambda x: x.rank)}
    l2 = {key:len(list(group)) for key, group in groupby(hand2, key=lambda x: x.rank)}

    # Get the value of the pairs to test
    t1 = l1.keys()[l1.values().index(3)]
    t2 = l2.keys()[l2.values().index(3)]

    if t1 > t2:
        return hand1
    return hand2

tests = [
    testPair,
    testTwoPairs,
    testThreeKind,
    testStraight,
    testFlush,
    testFullHouse,
    testFourKind,
    testStraightFlush,
    testRoyal
]

compares = [
    comparePair,
    compareTwoPairs,
    compareThreeKind,
    compareStraight,
    compareHighestCard,
    compareFullHouse,
    compareFourKind,
    compareStraight,  # compare straight flush is the same as straight
    None  # two Royals is not possible (IRL, players would split pot)
]

compareMapping = dict(zip(tests, compares))

p1_pts = 0
p2_pts = 0

for play in data:
    play = play.split(" ")
    p1_hand = sorted([Card(c) for c in play[:5]], key=lambda x: x.rank)
    p2_hand = sorted([Card(c) for c in play[5:]], key=lambda x: x.rank)

    for test in reversed(tests):
        t1 = test(p1_hand)
        t2 = test(p2_hand)
        if test(p1_hand) and not test(p2_hand):
            p1_pts += 1
            break
        elif test(p2_hand) and not test(p1_hand):
            p2_pts += 1
            break
        elif test(p1_hand) and test(p2_hand):
            # tie in rank, start comparing
            func = compareMapping[test]
            winner = func(p1_hand, p2_hand)
            if winner == p1_hand:
                p1_pts += 1
            else:
                p2_pts += 1
            break
    else:
        # if we reach here, neither player has an interesting hand. Use
        # basic compare
        winner = compareHighestCard(p1_hand, p2_hand)
        if winner == p1_hand:
            p1_pts += 1
        elif winner == p2_hand:
            p2_pts += 1

print "Player 1 pts:",p1_pts
\$\endgroup\$
7
\$\begingroup\$

1. Bugs

  1. testStraight returns False for an ace-low straight:

    >>> hand = sorted(map(Card, '3C AH 4D 2S 5C'.split()), key=lambda x:x.rank)
    >>> testStraight(hand)
    False
    

    Luckily there are no ace-low straights in the Project Euler data.

  2. A comment says "two Royals is not possible" but although this happens to be true of the Project Euler data, this is incorrect in general. If both players get royal flushes then the code fails with:

    TypeError: 'NoneType' object is not callable
    
  3. The code compares numbers using is, but this operator is the wrong choice: it tests for object identity, not numeric equality. In CPython, it appears to work for small integers:

    >>> 2 + 2 is 4
    True
    

    but this is an artefact of the way the implementation caches small int objects, and it fails for larger numbers:

    >>> 200 + 200 is 400
    False
    

    Compare numbers using the == operator instead.

2. Other review comments

  1. The comments at the start of each function could be turned into docstrings, so that you can read them from the interactive interpreter using the help function. For example:

    def testFlush(hand):
        """Return True if all cards in hand belong to the same suit."""
    
  2. This line creates an unnecessary list:

    set([c.rank for c in hand])
    

    Use a generator expression instead:

    set(c.rank for c in hand)
    
  3. This key function appears many times in the code:

    key=lambda x: x.rank
    

    This repetition could be avoided by giving the Card class a __lt__ method so that Card objects sort into order by their rank.

  4. This expression appears several times:

    [len(list(group)) for key, group in groupby(hand, key=lambda x: x.rank)]
    

    It would be better to compute this just once. What this line does is to count how many cards there are of each rank. This could be computed more simply using collections.Counter:

    Counter(card.rank for card in hand).values()
    
  5. The function testThreeKind returns True if the hand is three-of-a-kind or if the hand is a full house. Similarly, testPair returns True if the hand is a pair, or two pair, or a full house. So these functions only return the correct result if the higher-quality hands have already been tested and rejected. It is hard to check the correctness of code when it depends on the order of operations like this. It would be better to make these functions test the exact condition that we are interested in. For example, in testPair, instead of the condition 2 in l, we could write:

     sorted(l) == [1, 1, 1, 2]
    
  6. There is no need to handle royal flushes as a special case. A royal flush is just an ace-high straight flush, and so it tests and compares under the same rules as an ordinary straight flush.

3. Code length

This code is very long. The longer code is, the harder it is to read, check, and maintain.

A key idea for making this code shorter is to convert each poker hand to a canonical form: a simple data structure that can be compared using Python's built-in comparison operators.

A convenient choice of canonical form consists of a number giving the quality of the hand (high card=1, pair=2, two pair=3, and so on) and a list of the card ranks in descreasing order by frequency and then by rank (using jack=11, queen=12, king=13 and ace=14). So two pairs (tens and sevens) with a king would have the canonical form (3, [10, 7, 13]). This wins against two pairs (tens and sevens) with a queen, because:

(3, [10, 7, 13]) > (3, [10, 7, 12])

but loses to two pairs (jacks and fours) with a nine, because:

(3, [10, 7, 13]) < (3, [11, 4, 9])

Here's an implementation of this idea:

from collections import Counter
from enum import IntEnum, unique

@unique
class Quality(IntEnum):
    """Quality of a poker hand. Higher values beat lower values."""
    high_card = 1
    pair = 2
    two_pairs = 3
    three = 4
    straight = 5
    flush = 6
    full_house = 7
    four = 8
    straight_flush = 9

def canonical(hand):
    """Return the canonical form of the poker hand as a pair (q, r) where
    q is a value from the Quality enumeration, and r is a list of the
    distinct card ranks in the hand (from 1=low ace to 14=high ace),
    ordered in descreasing order by frequency and then by rank. These
    canonical forms can be compared to see who wins. The hand must be
    a sequence of five cards given as two-character strings in the
    form 2H, TS, JC etc.

    >>> canonical('TD 7H KH TS 7S'.split()) # two pairs (tens and sevens)
    (<Quality.two_pairs: 3>, [10, 7, 13])
    >>> canonical('3C AH 4D 2S 5C'.split()) # ace-low straight
    (<Quality.straight: 5>, [5, 4, 3, 2, 1])
    >>> canonical('JH 2H JC JS 2D'.split()) # full house (twos and jacks)
    (<Quality.full_house: 7>, [11, 2])
    >>> canonical('TS 4S 8S QS 5S'.split()) # queen-high flush
    (<Quality.flush: 6>, [12, 10, 8, 5, 4])

    """
    flush = len(set(suit for _, suit in hand)) == 1
    ranks = sorted('--23456789TJQKA'.find(rank) for rank, _ in hand)
    if ranks == [2, 3, 4, 5, 14]: # ace-low straight
        ranks = [1, 2, 3, 4, 5]
    straight = ranks == list(range(ranks[0], ranks[0] + 5))
    count = Counter(ranks)
    counts = sorted(count.values())
    distinct_ranks = sorted(count, reverse=True, key=lambda v:(count[v], v))
    if flush and straight:       q = Quality.straight_flush
    elif counts == [1, 4]:       q = Quality.four
    elif counts == [2, 3]:       q = Quality.full_house
    elif flush:                  q = Quality.flush
    elif straight:               q = Quality.straight
    elif counts == [1, 1, 3]:    q = Quality.three
    elif counts == [1, 2, 2]:    q = Quality.two_pairs
    elif counts == [1, 1, 1, 2]: q = Quality.pair
    else:                        q = Quality.high_card
    return q, distinct_ranks

Notes:

  1. The computation of the canonical form is just 18 lines of code, which fits on a single screen for easy reading, checking and maintaining.

  2. I didn't use the Card class: it's simpler to do without it and work with the string representations directly. The decoding of the cards is just two lines here.

  3. The enum module was new in Python 3.4. If you're stuck on an earlier Python, you could use global variables instead:

    HIGH_CARD = 1
    PAIR = 2
    # etc.
    
\$\endgroup\$
  • \$\begingroup\$ All of these are wonderful suggestions. Some of the bugs that you mentioned don't exist with the problem data, but indeed, if this were to be used in a poker app, they would have to be accounted for. Comparison overrides would be the next thing for me to look into. As for converting to canonical form, I thought about trying something like that but wasn't sure if I could make it evaluate correctly every time. Thank you for such a thorough response! \$\endgroup\$ – blitzmann Jun 29 '15 at 17:57
1
\$\begingroup\$

A few details quickly

Iterable upacking

You can rewrite :

face, suit = str[0], str[1]

like this

face, suit = str

Useless argument

0 as a first argument of range is useless.

For loop and enumerate

You should try to use iterations over iterable instead of using indices as much as possible.

For instance,

    for i in range(0, 4):
        if self.suitNames[i][0] == suit:
            suit = i
            break

corresponds to an iteration over suitNames. If you really need the index, enumerate is what you should be using.

for i, name in enumerate(suitNames):
    if name[0] == suite:
        suit = i
        break

Using the right data structure

More reallistically, it's probably easier to build a dict and query it to get the initial string from the first letter :

>>> suitNames = ('Diamonds', 'Clubs', 'Hearts', 'Spades')
>>> suitDict = { s[0]:s for s in suitNames }
>>> suitDict['D']
'Diamonds'
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.