Poker hand

See the original problem on HackerRank.

Solutions

The solutions revolve around finding the frequency of the card values. In addition, checking flush requires us to verify all the suits are equal. This check can be done in advance or while counting the frequency of each card.

Afterwards, mapping the card frequency to the score is straighforward: find the maximum frequency and that will give the score: 1 is “High Card” 2 is “Pair”, 3, 4 and 5 are “Three of a Kind”).

For simplicity with indexes, we keep the frequency of the card ‘0’ even though it does not make any sense.

In this first solution, flush is checked in advanced:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

vector<int> ranks(5);  // alternatively, using std::array is possible
vector<char> suits(5); // alternatively, using std::array is possible
copy_n(istream_iterator<int>(cin), 5, begin(ranks));
copy_n(istream_iterator<char>(cin), 5, begin(suits));

if (adjacent_find(begin(suits), end(suits), not_equal_to<>{}) == end(suits))
    return "Flush";

array<int, 14> freq{};
for (auto c : ranks)
    freq[c]++;
auto max = *max_element(begin(freq), end(freq));
static const std::map<int, std::string> hands = {
    {1, "High Card"},
    {2, "Pair"},
    {3, "Three of a Kind"},
    {4, "Three of a Kind"}
};
return hands.at(max);

In this variation, checking flush does not require an extra iteration:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

array<int, 14> freq{};
bool flush = true;
for (auto i=1u; i<ranks.size(); ++i)
{
    flush &= suits[i-1] == suits[i];
    freq[ranks[i-1]]++;
}
freq[ranks[ranks.size()-1]]++;

if (flush)
    return "Flush";

auto max = *max_element(begin(freq), end(freq));
static const std::map<int, std::string> hands = {
    {1, "High Card"},
    {2, "Pair"},
    {3, "Three of a Kind"},
    {4, "Three of a Kind"}
};
return hands.at(max);

Here is a compact solution in Python by mrv96:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

numbers = input().split()
semi = input().split()

max_nums = max(numbers.count(el) for el in numbers)

if len(set(semi)) == 1:
    print('Flush')
elif max_nums >= 3:
    print('Three of a Kind')
elif max_nums == 2:
    print('Pair')
else:
    print('High Card')

In this variant, the “Flush” is checked by comparing the only possible suit strings as they are limited:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import sys
nums = input().split(" ")
colors = "".join(input().split(" "))

def hist(arr):
    ist = [0 for _ in range(13)]
    for n in arr:
        ist[int(n) - 1] += 1
    return ist
ist = hist(nums)

if colors == "aaaaa" or colors == "bbbbb" or colors == "ccccc" or colors == "ddddd":
    print("Flush")
elif max(ist) >= 3:
    print("Three of a Kind")
elif max(ist) == 2:
    print("Pair")
else:
    print("High Card")

Design considerations

The full “Poker” game is more interesting as it includes other scores, such as:

  • double pair
  • full house
  • poker
  • straight
  • straigh flush

A simple technique consists in calculating the “histogram” of the poker hand that represents how many cards have a certain frequency. For example, suppose we have such an input

1
2

1 5 3 1 3
a a b c d

The card frequencies follow:

1

0 2 0 2 0 1 0 ...

The histogram “compacts” these numbers as follow:

1

0 1 2 0 0

In other words:

  • there are zero card values occurring zero times (this is to simplify indexes)
  • there is one card value occurring once (5)
  • there are two card values occurring twice (1 and 3)
  • there are zero card values occurring three times
  • there are zero card values occurring four times

Another example:

1
2

2 2 2 3 3
a b c d c

Frequencies:

1

0 0 3 2 0 0 0 ...

Histogram:

1

0 1 1 0 0

In other words, there is one card value occurring twice and one occurring three times (it’s a full house).

You see that the histogram allows us to find most of the scores easily:

  • poker: histogram[4] is 1
  • full house: histogram[3] and histogram[2] are both 1
  • three of a kind: histogram[3] is 1
  • double pair: histogram[2] is 2
  • pair: histogram[2] is 1
  • high card: histogram[1] is not zero

To check against straight and royal straight, the histogram is not of much help (it would be in similar games like Yahtzee). A possible way consists in sorting the card values in ascending order and checking if the car values are part of any of the two predefined straight patterns:

1
2
3
4
5
6
7
8

bool is_straight(hand hand)
{
    static const std::array straight { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };
    static const std::array straight_to_ace { 1, 10, 11, 12, 13 };
    sort(begin(hand), end(hand));
    return std::search(begin(straight), end(straight), begin(hand), end(hand))!= end(straight))
        || std::equal(begin(straight_to_ace), end(straight_to_ace), begin(hand), end(hand);
}

An alternative consists in checking if either the array does not contain any adjacent pair whose difference is greater than 1 or is exactly the predefined straight “10 to ace”:

1
2
3
4
5
6

bool is_straight_variant(hand cards)
{
    std::sort(begin(cards), end(cards));    
    return std::adjacent_find(begin(cards), end(cards), [](auto i, auto j){ return j - i > 1; }) == end(cards)
        || cards == std::array{1, 10, 11, 12, 13};
}

Just for fun, here is a variant that, after sorting, iterates the array only once:

1
2
3
4
5
6

bool is_straight_variant(std::array<int, 5> cards)
{
    std::sort(begin(cards), end(cards));    
    return std::adjacent_find(std::next(begin(cards)), end(cards), [](auto i, auto j){ return j - i > 1; }) == end(cards) 
        && (cards[1]-cards[0]==1 || (cards[0]==1 && cards[1]==10));
}

Thus, all the “check rules” could be encapsulated in functions and applied in a specified order, in a sort of “chain of responsibility” fashion. We propose an implementation based on std::optional:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

using histogram_t = std::array<int, 5>;
using cards_t = std::array<int, 5>;

struct hand
{
    cards_t cards;
    histogram_t histo;
    bool is_flush;
};

bool is_straight(hand hand)
{
    static const std::array straight { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };
    static const std::array straight_to_ace { 1, 10, 11, 12, 13 };
    sort(begin(hand), end(hand));
    return std::search(begin(straight), end(straight), begin(hand), end(hand))!= end(straight))
        || std::equal(begin(straight_to_ace), end(straight_to_ace), begin(hand), end(hand);
}

std::optional<std::string> maybe_straight_flush(const hand& hand)
{
    return hand.histo[0] == 5 && hand.is_flush && is_straight(hand.cards) ? std::optional<std::string>{"Straight Flush"} : std::nullopt;
}

std::optional<std::string> maybe_poker(const hand& hand)
{
    return hand.histo[4] ? std::optional<std::string>{"Poker"} : std::nullopt;
}

std::optional<std::string> maybe_full(const hand& hand)
{
    return hand.histo[2] && hand.histo[3] ? std::optional<std::string>{"Full House"} : std::nullopt;
}

std::optional<std::string> maybe_flush(const hand& hand)
{
    return hand.is_flush ? std::optional<std::string>{"Flush"} : std::nullopt;
}

std::optional<std::string> maybe_straight(const hand& hand)
{
    return hand.histo[1] == 5 && is_straight(hand.cards) ? std::optional<std::string>{"Straight"} : std::nullopt;
}

std::optional<std::string> maybe_three_of_a_kind(const hand& hand)
{
    return hand.histo[3] ? std::optional<std::string>{"Three of a Kind"} : std::nullopt;
}

std::optional<std::string> maybe_double_pair(const hand& hand)
{
    return hand.histo[2] == 2 ? std::optional<std::string>{"Double Pair"} : std::nullopt;
}

std::optional<std::string> maybe_pair(const hand& hand)
{
    return hand.histo[2] ? std::optional<std::string>{"Pair"} : std::nullopt;
}

std::optional<std::string> maybe_high_card(const hand& hand)
{
    return hand.histo[1] ? std::optional<std::string>{"High Card"} : std::nullopt;
}

std::string calculate_hand(const hand& h)
{
    std::array rules = {maybe_straight_flush, maybe_poker, maybe_full, maybe_flush, maybe_straight, maybe_three_of_a_kind, maybe_double_pair, maybe_pair, maybe_high_card};
    
    std::optional<std::string> res;
    auto it = begin(rules);
    while (!res)
    {
        res = (*it++)(h);
    }
    return *res;
}

int main()
{
    array<int, 5> ranks{};
	array<char, 5> suits{};
	copy_n(istream_iterator<int>(cin), 5, begin(ranks));
	copy_n(istream_iterator<char>(cin), 5, begin(suits));

	array<int, 14> freq{};
	bool flush = true;
	for (auto i=1u; i<ranks.size(); ++i)
	{
		flush &= suits[i-1] == suits[i];
		freq[ranks[i-1]]++;
	}
	freq[ranks[ranks.size()-1]]++;
	
    histogram_t histogram{};
    for (auto i : freq)
    {
		if (i) 
		{	
			histogram[i] += 1;
		}
	}

    std::cout << calculate_hand({ranks, histogram, flush});
}

The main point is: we search for the first “check rule” that returns a valued optional, otherwise we keep on searching. Clearly, at least the “high card” rule will succeed.

Then it’s possible to refactor this a bit more. For example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

using rule_fn = std::function<std::optional<std::string>(const hand&)>;

rule_fn make_check(const char* name, auto check)
{
    return [=](const hand& h){
        return check(h) ? std::optional<std::string>{name} : std::nullopt;
    };
}

std::string calculate_hand(const hand& h)
{
    std::vector<rule_fn> rules = {
        make_check("Straight Flush", [](const hand& h) { return h.histo[0] == 5 && h.is_flush && is_straight(h.cards); }),
        make_check("Poker", [](const hand& h) { return h.histo[4]; }),
        make_check("Full House", [](const hand& h) { return h.histo[3] && h.histo[2]; }),
        make_check("Flush", [](const hand& h) { return h.is_flush; }),
        make_check("Straight", [](const hand& h) { return h.histo[1] == 5 && is_straight(h.cards); }),
        make_check("Three of a Kind", [](const hand& h) { return h.histo[3]; }),
        make_check("Double Pair", [](const hand& h) { return h.histo[2] == 2; }),
        make_check("Pair", [](const hand& h) { return h.histo[2]; }),
        make_check("High Card", [](const hand& h) { return h.histo[1]; })
    };
    
    std::optional<std::string> res;    
    auto it = begin(rules);
    while (!res)
    {
        res = (*it++)(h);
    }
    return *res;
}

This approach allows to create and use rules dynamically.

Anyway, there exist design alternatives. What about trying others?

frequency table  design 
We've worked on this challenge in these gyms: modena 
comments powered by Disqus