Feb 17, 2021

Sortable Poker Hands

Recently one of the problems that I had to solve on one of my interviews was the sortable poker hands problem , and because I received very good feedback and my solution was described as “uniquely structured to solve the problem in a human way” I thought to share this solution.

TL;DR

You can find the source code for this solution in this repository github.com/gabihodoroaga/sortable-poker-hands.

Prerequisites

  • python3
  • enough time to have a little fun

The problem

The problem was taken from this Kata and I will describe it in detail below.

Create a poker hand that has a constructor that accepts a string containing 5 cards:

hand = PokerHand("KS 2H 5C JD TD")

The characteristics of the string of cards are:

  • A space is used as card separator
  • Each card consists of two characters
  • The first character is the value of the card, valid characters are:
    2, 3, 4, 5, 6, 7, 8, 9, T(en), J(ack), Q(ueen), K(ing), A(ce)
  • The second character represents the suit, valid characters are:
    S(pades), H(earts), D(iamonds), C(lubs)

The poker hands must be sortable by rank, the highest rank first.

Apply the Texas Hold’em rules for ranking the cards. There is no ranking for the suits. An ace can either rank high or rank low in a straight or straight flush. Example of a straight with a low ace: "5C 4D 3C 2S AS"

The solution

When we, humans, play poker we draw cards one by one and after each draw we evaluate the rank of the hand to see if we have a pair, or a full house, or something else.

This is best explained by an example:

  • Draw the first card: 9 of spades (9S), our hand rank is now High card.
  • Draw the second card: 9 of hearts (9H), now we have a Pair now and we hope for a three of a kind.
  • Draw the third card: 9 of clubs (9C), now we have a Three of a kind, very well, but we hope for the 4th nine.
  • Draw the fourth card: 9 of diamond (9D), best card that you can draw, now we have Four of a kind.
  • Draw the fifth card: 6 of hearts (6H), it really does not matter that much for this hand.

With this hand you have very good chances to become rich.

The algorithm that we will develop next will follow the same logic.

First let’s create some helper classes

class PokerCard:
    values = {'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'T':10,'J':12,'Q':13,'K':14,'A':15}
    suites = ['S','H','D','C']

    def __init__(self, card):
        # no card validation for better performance
        self.value = card[0]
        self.suite = card[1]

    def __lt__(self, card):
        return self.values[self.value] < self.values[card.value]

The next class will be the base for all other classes

class Hand:
    def __repr__(self):
        return self.__class__.__name__

We will define a class for each of the possible hand ranks, and each class is responsible to decide the rank when a new card is drawn by implementing the Draw method, and also we need to implement the __lt__ function in order to be able to decide which hand has a higher value when the rank is the same.

First possible rank is the High card

class HighCard(Hand):
    def __init__(self):
        self.rank = 1
        self.cards = []

    def __lt__(self, other):
        myCards = self.allCards()
        cardCards = other.allCards()

        for i in range(0, 5):
            if myCards[i] < cardCards[i]:
                return True 
            if myCards[i] > cardCards[i]:
                return False
        return False
    
    @lru_cache(None)
    def allCards(self):
        return sorted(self.cards, reverse=True)

    def Draw(self, card):
        pc = PokerCard(card)
        # check for pair
        if next((c for c in self.cards if c.value == pc.value), None) != None:
            self.cards.append(pc)
            return Pair(self.cards, pc)

        self.cards.append(pc)

        if len(self.cards) == 5:
            ## check for flush
            isFlush = next((c for c in self.cards[:-1] if c.suite != pc.suite), None) == None
            ## check for straight
            cards = sorted(self.cards)
            valueList = list(PokerCard.values)
            firstCardIdx = valueList.index(cards[0].value)
            isStraight = True
            for i in range(0, 5):
                if cards[i].value != valueList[firstCardIdx + i]:
                    isStraight = False
                    break

            # check for low straight
            if (cards[0].value == '2' and 
                cards[1].value == '3' and 
                cards[2].value == '4' and
                cards[3].value == '5' and
                cards[4].value == 'A'):
                isStraight = True

            if isFlush and isStraight:
                return StraightFlush(self.cards)
            if isFlush:
                return Flush(self.cards)
            if isStraight:
                return Straight(self.cards)

        return self

If we have a High card and we draw another card we have the following options:

  • draw another card with the same value which means we have a pair
  • have a straight, a flush, or a straight flush, and this is possible only if we have 5 cards

Also, when we have two high cards, we need to know which one has a lower value according to the rules. Check the __lt__ implementation of the class

Next we have the Pair rank

class Pair(Hand):

    def __init__(self, cards, pair):
        self.rank = 2
        self.cards = cards
        self.pair = pair

    def __lt__(self, card):
        if self.pair < card.pair:
            return True
        if self.pair > card.pair:
            return False

        myOtherCards =  self.otherCards()
        cardOtherCards = card.otherCards()
        for i in range(3):
            if myOtherCards[i] < cardOtherCards[i]:
                return True
            if myOtherCards[i] > cardOtherCards[i]:
                return False
        return False
    
    @lru_cache(None)
    def otherCards(self):
        return sorted([c for c in self.cards if c.value != self.pair.value], reverse=True)

    def Draw(self, card):
        pc = PokerCard(card)

        # check for 3 of a kind 
        if self.pair.value == pc.value:
            self.cards.append(pc)
            return ThreeOfKind(self.cards, pc)

        # check for second pair
        pair2 = next((c for c in self.cards if c.value != self.pair.value and c.value == pc.value), None)
        if (pair2 != None):
            self.cards.append(pc)
            return TwoPairs(self.cards, self.pair, pc)

        self.cards.append(pc)
        return self

When we have a pair, the next possible options when we draw another card are:

  • three of a kind
  • two pairs

Next is two pairs rank

class TwoPairs(Hand):

    def __init__(self, cards, pair1, pair2):
        self.rank = 3
        self.cards = cards 
        self.pair1 = pair1
        self.pair2 = pair2

    def __lt__(self, card):
        myPairs = self.pairs()
        cardPairs = card.pairs() 
        for i in range(2):
            if myPairs[i] < cardPairs[i]:
                return True
            if myPairs[i] > cardPairs[i]:
                return False

        return self.otherCard() < card.otherCard()
    
    @lru_cache(None)
    def otherCard(self):
        return next((c for c in self.cards if c.value != self.pair1.value and c.value != self.pair2.value), None)

    def pairs(self):
        return sorted([self.pair1, self.pair2], reverse=True)

    def Draw(self, card):
        pc = PokerCard(card)
        # check for full house
        pair3 = next((c for c in self.cards if c.value == pc.value), None)
        if pair3 != None:
            self.cards.append(pc)
            return FullHouse(self.cards, 
                pc, self.pair2 if pc.value == self.pair1.value else self.pair1)
 
        self.cards.append(pc)
        return self

From two pairs you can only go to a full house or to remain as two pairs, which is not that bad after all.

Next is three of a kind rank

class ThreeOfKind(Hand):

    def __init__(self, cards, pair):
        self.rank = 4
        self.cards = cards
        self.pair = pair 

    def __lt__(self, card):
        if self.pair < card.pair:
            return True
        if self.pair > card.pair:
            return False
        
        myOtherCards =  self.otherCards()
        cardOtherCards = card.otherCards()
        for i in range(3):
            if myOtherCards[i] < cardOtherCards[i]:
                return True
            if myOtherCards[i] > cardOtherCards[i]:
                return False
        return False
    
    @lru_cache(None)
    def otherCards(self):
        return sorted([c for c in self.cards if c.value != self.pair.value], reverse=True)

    def Draw(self, card):
        pc = PokerCard(card)
        
        # Check for FourOfKind
        if self.pair.value == pc.value:
            self.cards.append(card)
            return FourOfKind(self.cards, pc)
        
        # Check for FullHouse 
        if len(self.cards) == 4:
            pair = next((c for c in self.cards 
                if c.value != self.pair.value and c.value == pc.value), None)
            if pair != None:
                self.cards.append(pc)
                return FullHouse(self.cards, self.pair, pc)

        self.cards.append(pc)
        return self

From three of a kind the next options are:

  • full house
  • four of a kind

Next is four of a kind

class FourOfKind(Hand):

    def __init__(self, cards, pair):
        self.rank = 8
        self.cards = cards
        self.pair = pair 
    
    def __lt__(self, card):
        if self.pair < card.pair:
            return True
        if self.pair > card.pair:
            return False
        return self.otherCard() < card.otherCard()
    
    @lru_cache(None)
    def otherCard(self):
        return next((c for c in self.cards if c.value != self.pair.value), None)

    def Draw(self, card):
        pc = PokerCard(card)
        self.cards.append(card)
        return self

From four of a kind we can’t go anywhere, we are done but we still need to implement the function to compare 2 four of a kind.

Next is full house rank

class FullHouse(Hand):

    def __init__(self, cards, three, two):
        self.rank = 7
        self.cards = cards
        self.three = three
        self.two = two 
    
    def __lt__(self, card):
        if self.three < card.three:
            return True
        if self.three > card.three:
            return False
        if self.two < card.two:
            return True

        return False

    def Draw(self, card):
        raise ValueError("This should not be possible")

I know that by now this is becoming boring, but these are the rules of the game and we have to implement all the possible ranks.

Next is straight rank

class Straight(Hand):

    def __init__(self, cards):
        self.rank = 5
        self.cards = cards

    def __lt__(self, card):
        return self.allCards()[0] < card.allCards()[0]
    
    @lru_cache(None)
    def allCards(self):
        sortedCards = sorted(self.cards, reverse=True)
        if sortedCards[0].value == "A" and sortedCards[4].value == '2':
            sortedCards.append(sortedCards.pop(0))
            return sortedCards

        return sortedCards

    def Draw(self, card):
        raise ValueError("This should not be possible")

and flush rank

class Flush(Hand):

    def __init__(self, cards):
        self.rank = 6
        self.cards = cards
        
    def __lt__(self, card):
        myCards = self.allCards()
        cardCards = card.allCards()

        for i in range(0, 5):
            if myCards[i] < cardCards[i]:
                return True 
            if myCards[i] > cardCards[i]:
                return False
        return False
    
    @lru_cache(None)
    def allCards(self):
        return sorted(self.cards,reverse=True)

    def Draw(self, card):
        raise ValueError("This should not be possible")

and the straight flush rank

class StraightFlush(Hand):

    def __init__(self, cards):
        self.rank = 9
        self.cards = cards
    
    def __lt__(self, card):
        return self.allCards()[0] < card.allCards()[0]

    @lru_cache(None)
    def allCards(self):
        sortedCards = sorted(self.cards, reverse=True)
        if sortedCards[0].value == "A" and sortedCards[4].value == '2':
            sortedCards.append(sortedCards.pop(0))
            return sortedCards

        return sortedCards

    def Draw(self, card):
        raise ValueError("This should not be possible")

In order to implement the __lt__ operator I used helper functions like allCards() or otherCards() and if you add some caching capabilities to this functions you will get huge improvement in performance. You can read all about caching in python here.

Now, let’s put all together and create our final class


class PokerHand(object):

    def __repr__(self):  return self.hand

    def __init__(self, hand):
        self.value = None
        self.hand = hand
        self.calcValue()
        # Your code below:
    def __lt__(self, hand):
        if self.value.rank == hand.value.rank:
            return self.value > hand.value
        return self.value.rank > hand.value.rank

    def calcValue(self):
        r = HighCard()
        for card in self.hand.split():
            r = r.Draw(card.upper())
        self.value = r

The __lt__ function is implemented here in the reverse order to comply with the requirements of the problem.

Now we can play. Let’s test if a pair is lower than a four of a kind.

print(PokerHand("AS AH 9C 8D 2S") > PokerHand("9S 9H 9C 9D JS")) # reverse

You can test the complete solution using this Kata. There are 25.000 random tests. Check out the timing.

Conclusion

Sometimes the best solution to a problem can be found by mimic how we do it in the real world.

You can find all the full source code, and tests of course, here at github.com/gabihodoroaga/sortable-poker-hands.

python

1733 Words

2021-02-17 20:22 +0000