競技プログラミング風 C++問題集【第15回】

ポーカー：役判定（難易度：★★★☆☆）

問題

引数で与えられたカード配列の役を判定する関数 int checkHand(const vector<Card>& v) を実装しなさい。

ただし、無役は0を、ワンペアは1を、…、ストレートフラッシュは8を返すものとする（テストコードのポーカー役 enum 参照）。
また、Card は一枚のカードを表す構造体で、スート（マーク）とランク（数字）から構成される（テストコードの Card 構造体参照）。

#include <iostream>       //  標準入出力ライブラリ
#include <string>
#include <vector>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
typedef unsigned int uint;
enum {      //  ポーカー役・スート・ランク定数定義
    HIGH_CARD = 0,      //  無役
    ONE_PAIR,           //  ワンペア
    TWO_PAIR,           //  ツーペア
    THREE_OF_A_KIND,    //  スリーカード
    STRAIGHT,           //  ストレート
    FLUSH,              //  フラッシュ
    FULL_HOUSE,         //  フルハウス
    FOUR_OF_A_KIND,     //  フォーカード
    STRAIGHT_FLUSH,     //  ストレートフラッシュ
    N_KIND_HAND,        //  役種類数
    SPADES = 0,         //  スペード
    CLUBS,
    HEARTS,
    DIAMONDS,
    N_SUIT,             //  スート（マーク）種類数
    RANK_BLANK = -1,
    RANK_2 = 0,
    RANK_3, RANK_4, RANK_5, RANK_6,
    RANK_7, RANK_8, RANK_9, RANK_10,
    RANK_J, RANK_Q, RANK_K, RANK_A,
    N_RANK,             //  数字種類数
    N_CARD = N_SUIT * N_RANK,           //  全カード枚数
};
//  １枚のカードを表す構造体（ジョーカーは除く）
struct Card
{
public:
    Card(char suit = 0, char rank = -1) : m_suit(suit), m_rank(rank) {}
    void    print() const { std::cout << toString(); }
    void    printW() const;
    std::string toString() const
    {
        if( m_suit < 0 || m_suit >= N_SUIT || m_rank < 0 || m_rank >= N_RANK )
            return std::string("??");
        std::string str(1, "SCHD"[m_suit]);
        str += "23456789TJQKA"[m_rank];
        return str;
    }
    int     numRank() const { return m_rank + (2-RANK_2); }     //  A は 14 を返す
    bool    operator==(const Card &x) const { return m_suit == x.m_suit && m_rank == x.m_rank; }
public:
    char    m_suit;     //  スート（マーク）
    char    m_rank;     //  0: 2,… 7: 9, 8:10, 9:J, 10:Q, 11:K, 12:A
};
typedef std::vector<Card> Cards;
int checkHand(const Cards& v) {
    //  ToDo: 
    return HIGH_CARD;
}
int main() {
    DO_TEST(checkHand(Cards{ {SPADES, RANK_A}, {SPADES, RANK_2}, {CLUBS, RANK_4},
                                {CLUBS, RANK_6}, {HEARTS, RANK_Q} }) == HIGH_CARD);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_7}, {CLUBS, RANK_10}, {DIAMONDS, RANK_6},
                                {SPADES, RANK_5}, {HEARTS, RANK_8} }) == HIGH_CARD);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_Q}, {SPADES, RANK_2}, {CLUBS, RANK_4},
                                 {CLUBS, RANK_6}, {HEARTS, RANK_Q} }) == ONE_PAIR);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_Q}, {SPADES, RANK_6}, {CLUBS, RANK_4},
                                {CLUBS, RANK_6}, {HEARTS, RANK_Q} }) == TWO_PAIR);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_J}, {SPADES, RANK_6}, {CLUBS, RANK_J},
                                {CLUBS, RANK_A}, {HEARTS, RANK_J} }) == THREE_OF_A_KIND);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_7}, {CLUBS, RANK_9}, {DIAMONDS, RANK_6},
                                {SPADES, RANK_5}, {HEARTS, RANK_8} }) == STRAIGHT);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_A}, {CLUBS, RANK_2}, {DIAMONDS, RANK_3},
                                {SPADES, RANK_5}, {HEARTS, RANK_4} }) == STRAIGHT);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_Q}, {SPADES, RANK_2}, {SPADES, RANK_4},
                                {SPADES, RANK_6}, {SPADES, RANK_Q} }) == FLUSH);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_Q}, {SPADES, RANK_6}, {CLUBS, RANK_Q},
                                {CLUBS, RANK_6}, {HEARTS, RANK_Q} }) == FULL_HOUSE);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_J}, {SPADES, RANK_6}, {CLUBS, RANK_J},
                                {DIAMONDS, RANK_J}, {HEARTS, RANK_J} }) == FOUR_OF_A_KIND);
    DO_TEST(checkHand(Cards{ {SPADES, RANK_10}, {SPADES, RANK_J}, {SPADES, RANK_Q},
                                {SPADES, RANK_K}, {SPADES, RANK_A} }) == STRAIGHT_FLUSH);
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

・役を判定するには、まず各ランク（数字）・スート（マーク）枚数をカウントするといいぞ。
・スートのどれかの枚数が5以上ならフラッシュだぞ。
・ランクが連続していればストレートだ。ストレートかつフラッシュならばストレート・フラッシュだぞ。
・ランクのどれかの枚数が4ならフォーカードだぞ。
・ランクのどれかの枚数が3ならスリーカードだぞ。
・ランクのどれかの枚数が2ならペアだぞ。それが2組あればツーペアだ。
・ランクのどれかの枚数が2と3のものがあればフルハウスだぞ。
・上記のどれでもなければハイカードだぞ。
・このように地道に判定していくしかないぞ。

解答例

int checkHand(const Cards& v) {
    vector<int> rcnt(13, 0);    //  各ランク枚数
    vector<int> scnt(4, 0);     //  各スート枚数
    for (uint i = 0; i < v.size(); ++i) {
        rcnt[v[i].m_rank] += 1;     //  各ランク枚数カウント
        scnt[v[i].m_suit] += 1;     //  各スート枚数カウント
    }
    int s = -1;
    if( scnt[s = 0] >= 5 || scnt[s = 1] >= 5 || scnt[s = 2] >= 5 || scnt[s = 3] >= 5 ) {
        //  フラッシュ確定
        uint bitmap = 0;
        for (uint i = 0; i < v.size(); ++i) {   //  フラッシュのスートのランクをビットマップ化
            const Card c = v[i];
            if( c.m_suit == s )
                bitmap |= 1 << (c.m_rank);
        }
        uint mask = 0x1f00;     //  AKQJT
        for (int i = 0; i < 9; ++i, mask>>=1) {
            if( (bitmap & mask) == mask ) {     //  上位カードから5枚連続している場合
                return STRAIGHT_FLUSH;
            }
        }
        if( bitmap == 0x100f )  //  1 0000 00000 1111 = A5432
            return STRAIGHT_FLUSH;
    } else
        s = -1;     //  フラッシュではない
    int threeOfAKindIX = -1;    //  スリーカードになったランク保存用
    int threeOfAKindIX2 = -1;   //  同上
    int pairIX1 = -1;   //  ペアになったランク保存用
    int pairIX2 = -1;   //  同上
    for (int i = 0; i < 13; ++i) {
        switch( rcnt[i] ) {
            case 4:
                return FOUR_OF_A_KIND;      //  フォーカード確定
            case 3:     //  スリーカード
                if( threeOfAKindIX < 0 )    //  スリーカードになったランクを保存
                    threeOfAKindIX = i;
                else
                    threeOfAKindIX2 = i;
                break;
            case 2:
                pairIX2 = pairIX1;      //  ペアになったランクを保存
                pairIX1 = i;
                break;
        }
    }
    //  3カード*2 もフルハウス（for ホールデムの場合対応）
    if( threeOfAKindIX >= 0 && (pairIX1 >= 0 || threeOfAKindIX2 >= 0) )
        return FULL_HOUSE;
    if( s >= 0 )
        return FLUSH;       //  フラッシュ確定
    uint bitmap = 0;
    uint mask = 1;
    for (int i = 0; i < 13; ++i, mask<<=1) {    //  ランクをビットマック化
        if( rcnt[i] != 0 )
            bitmap |= mask;
    }
    mask = 0x1f00;      //  AKQJT
    for (int i = 0; i < 9; ++i, mask>>=1) {
        if( (bitmap & mask) == mask )   //  5枚連続していれば
            return STRAIGHT;            //  ストレート確定
    }
    if( (bitmap & 0x100f) == 0x100f )       //  5432A
        return STRAIGHT;
    if( threeOfAKindIX >= 0 )           //  スリーカードがある場合
        return THREE_OF_A_KIND;
    if( pairIX2 >= 0 )      //  ペアが２つ以上ある場合
        return TWO_PAIR;
    if( pairIX1 >= 0 )      //  ペアがある場合
        return ONE_PAIR;
    return HIGH_CARD;       //  無役の場合
}

解説

ポーカーの役を判定するには、まず各ランク（数字）・スート（マーク）枚数をカウントするとよい。
スート枚数のどれかが5枚以上ならフラッシュなので、最初に簡単なフラッシュかどうかを判定する。ただし、この時点ではフラッシュが確定しない。なぜなら、ストレート・フラッシュやフォーカードやフルハウスの場合はフラッシュより強い役で、最も強い役が優先になるからだ。
ストレートかどうかを判定するには、そのフラッシュスートの各ランク枚数をビットマップ化し、ビットが５つ以上続いているかどうかを判定する。ストレートであれば、フォーカードより強いので、ストレート・フラッシュが確定する。
この時点でフラッシュにはなっているが、それより強いフォーカード、フルハウスでないかどうかを先に判定する必要がある。そのために最初に計算した各ランクの枚数を調べ、4枚以上のものがあればフォーカードが確定となる。スリーカード、ペアがあればそのランクを覚えておき、スリーカードとペアの両方があればフルハウスが確定となる。
この時点でフラッシュが残った役の中では最強となるので、フラッシュであれば、フラッシュを返す。
あとは、スリーカードがあればスリーカードを、ペアが２つ以上あればツーペアを、ペアが１つだけであればワンペアを返す。
上記の役のどれでもなければハイカード（無役）を返す。

このようにポーカーの役判定は結構地道なコードの積み重ねだ。もっとエレガントなアルゴリズムがあるのであれば、筆者にこっそりご教授していただきたい。