Tifa's CP Library

:warning: texas_holdem (src/code/game/texas_holdem.hpp)

Depends on

Code

#ifndef TIFALIBS_GAME_TEXAS_HOLDEM
#define TIFALIBS_GAME_TEXAS_HOLDEM

#include "../bit/cntlsb.hpp"
#include "../util/util.hpp"

namespace tifa_libs::game {
namespace texas_holdem_impl_ {
constexpr int bsr(int x) { return 30 - bit::cntlsb(x); }
// Returns the submask containing highest k bits set
// Returns -1 instead if std::popcount(a) < k
constexpr int hbits(int a, int k) {
  int b = 0;
  for (int i = 0; i < k; ++i) {
    if (!a) return -1;
    a &= ~(b |= 1 << bsr(a));
  }
  return b;
}

class th_card {
 protected:
  int data = 0;

 public:
  static constexpr char RANKS[16] = "0123456789TJQKA";
  static constexpr char SUITS[5] = "CDHS";
  explicit constexpr th_card() {}
  constexpr th_card(char rank, char suit) { encode(rank, suit); }
  explicit constexpr th_card(strnv str) : th_card(str[0], str[1]) { assert(str.size() == 2); }
  // Parses a card in a format as "2C"
  // @return: 4 * (rank - 2) + suit  (2 <= rank <= 14)
  constexpr void encode(char rank, char suit) {
    int r = 2, s = 0;
    for (; r < 15; ++r)
      if (RANKS[r] == rank) break;
    assert(r < 15);
    for (; s < 4; ++s)
      if (SUITS[s] == suit) break;
    assert(s < 4);
    data = (r - 2) << 2 | s;
  }
  constexpr int get_rank() const { return (data >> 2) + 2; }
  constexpr int get_suit() const { return data & 3; }
  // @return: {rank_char, suit_char}
  constexpr ptt<char> decode() const { return {RANKS[get_rank()], SUITS[get_suit()]}; }
  friend std::istream &operator>>(std::istream &is, th_card &card) {
    char rk, st;
    is >> rk >> st;
    card.encode(rk, st);
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, th_card const &card) {
    auto &&_ = card.decode();
    return os << _.first << _.second;
  }
};

enum th_category {
  HIGH_CARD,
  ONE_PAIR,
  TWO_PAIR,
  THREE_OF_A_KIND,
  STRAIGHT,
  FLUSH,
  FULL_HOUSE,
  FOUR_OF_A_KIND,
  STRAIGHT_FLUSH
};

class th_hand {
  vec<th_card> cds;
  // ranks for all
  int rka = 0;
  // suit -> rank
  int mps[4] = {};
  // rank -> count
  int cnt[15] = {};
  // count -> rank
  int mpc[5] = {};

 public:
  explicit constexpr th_hand() : cds(5) {}
  // Set first 5 element as hand
  constexpr void reset(vec<th_card> const &cards) {
    assert(cards.size() >= 5);
    std::copy(cards.begin(), cards.begin() + 5, cds.begin());
    for (auto &&card : cds) {
      auto r = card.get_rank(), s = card.get_suit();
      rka |= mps[s] |= 1 << r;
      ++cnt[r];
    }
    for (int r = 2; r < 15; ++r) mpc[cnt[r]] |= 1 << r;
  }
  // Returns the best poker hand with the tie-breaker in [0, 2^20)
  constexpr std::pair<th_category, int> parse() const {
    assert(cds.size() == 5);
    for (auto &&func : checks)
      if (auto [valid, cat, ans] = func(*this); valid) return {cat, ans};
    exit(1);
  }

  constexpr th_card &operator[](u32 x) { return cds[x]; }
  constexpr th_card const &operator[](u32 x) const { return cds[x]; }

  friend std::istream &operator>>(std::istream &is, th_hand &hands) {
    for (u32 i = 0; i < 5; ++i) is >> hands.cds[i];
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, th_hand const &hands) {
    for (u32 i = 0; i < 4; ++i) os << hands.cds[i] << ' ';
    return os << hands.cds[4];
  }

 private:
  // 8. STRAIGHT_FLUSH: highest (5 for A2345)
  static constexpr std::tuple<bool, th_category, int> is_straight_flush(th_hand const &h) {
    int f = 0;
    for (int s = 0; s < 4; ++s) f |= h.mps[s] & h.mps[s] << 1 & h.mps[s] << 2 & h.mps[s] << 3 & (h.mps[s] << 4 | h.mps[s] >> 14 << 5);
    return {!!f, STRAIGHT_FLUSH, bsr(f)};
  }
  // 7. FOUR_OF_A_KIND: quadruple, other card
  static constexpr std::tuple<bool, th_category, int> is_four_of_a_kind(th_hand const &h) {
    if (!h.mpc[4]) return {false, FOUR_OF_A_KIND, 0};
    const int r4 = bsr(h.mpc[4]);
    return {true, FOUR_OF_A_KIND, r4 << 4 | bsr(h.rka ^ 1 << r4)};
  }
  // 6. FULL_HOUSE: triple, pair
  static constexpr std::tuple<bool, th_category, int> is_full_house(th_hand const &h) {
    if (!h.mpc[3]) return {false, FULL_HOUSE, 0};
    const int r3 = bsr(h.mpc[3]), d = (h.mpc[3] ^ 1 << r3) | h.mpc[2];
    if (!d) return {false, FULL_HOUSE, 1};
    const int r2 = bsr(d);
    return {true, FULL_HOUSE, r3 << 4 | r2};
  }
  // 5. FLUSH: 5 highest cards
  static constexpr std::tuple<bool, th_category, int> is_flush(th_hand const &h) {
    int flush = -1;
    for (int s = 0, _ = 0; s < 4; ++s)
      if (flush < (_ = hbits(h.mps[s], 5))) flush = _;
    return {flush >= 0, FLUSH, flush};
  }
  // 4. STRAIGHT: highest (5 for A2345)
  static constexpr std::tuple<bool, th_category, int> is_straight(th_hand const &h) {
    const int f = h.rka & h.rka << 1 & h.rka << 2 & h.rka << 3 & (h.rka << 4 | h.rka >> 14 << 5);
    return {!!f, STRAIGHT, bsr(f)};
  }
  // 3. THREE_OF_A_KIND: triple, 2 highest other cards
  static constexpr std::tuple<bool, th_category, int> is_three_of_a_kind(th_hand const &h) {
    if (!h.mpc[3]) return {false, THREE_OF_A_KIND, 0};
    const int r3 = bsr(h.mpc[3]);
    return {true, THREE_OF_A_KIND, r3 << 16 | hbits(h.rka ^ 1 << r3, 2)};
  }
  // 2. TWO_PAIR: larger pair, smaller pair, other card
  // 1. ONE_PAIR: pair, 3 highest other cards
  static constexpr std::tuple<bool, th_category, int> is_pair(th_hand const &h) {
    if (!h.mpc[2]) return {false, ONE_PAIR, 0};
    const int r2 = bsr(h.mpc[2]);
    const int d = h.mpc[2] ^ 1 << r2;
    if (!d) return {true, ONE_PAIR, r2 << 16 | hbits(h.rka ^ 1 << r2, 3)};
    const int r22 = bsr(d);
    return {true, TWO_PAIR, r2 << 8 | r22 << 4 | bsr(h.rka ^ 1 << r2 ^ 1 << r22)};
  }
  // 0. HIGH_CARD: 5 highest cards
  static constexpr std::tuple<bool, th_category, int> is_high_card(th_hand const &h) { return {true, HIGH_CARD, hbits(h.rka, 5)}; }
  //! The judger of all the categories
  static constexpr std::tuple<bool, th_category, int> (*checks[8])(th_hand const &) = {
      is_straight_flush,
      is_four_of_a_kind,
      is_full_house,
      is_flush,
      is_straight,
      is_three_of_a_kind,
      is_pair,
      is_high_card};
};
}  // namespace texas_holdem_impl_

using texas_holdem_impl_::th_category, texas_holdem_impl_::th_card, texas_holdem_impl_::th_hand;

}  // namespace tifa_libs::game

#endif
#line 1 "src/code/game/texas_holdem.hpp"



#line 1 "src/code/bit/cntlsb.hpp"



namespace tifa_libs::bit {

template <class T>
constexpr int cntlsb(T x) {
  constexpr int nd = sizeof(T) * 8;
  static_assert(nd <= 64);
  if constexpr (nd <= sizeof(unsigned) * 8) return __builtin_clrsb(x);
  else if constexpr (nd <= sizeof(unsigned long) * 8) return __builtin_clrsbl(x);
  else return __builtin_clrsbll(x);
}

}  // namespace tifa_libs::bit


#line 1 "src/code/util/util.hpp"



#include <bits/stdc++.h>

template <class T>
constexpr T abs(T x) { return x < 0 ? -x : x; }

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using isz = ptrdiff_t;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
using usz = size_t;

using f32 = float;
using f64 = double;
using f128 = long double;

template <class T>
using ptt = std::pair<T, T>;
template <class T>
using pt3 = std::tuple<T, T, T>;
template <class T>
using pt4 = std::tuple<T, T, T, T>;

template <class T, usz N>
using arr = std::array<T, N>;
template <class T>
using vec = std::vector<T>;
template <class T>
using vvec = vec<vec<T>>;
template <class T>
using v3ec = vec<vvec<T>>;
template <class U, class T>
using vecp = vec<std::pair<U, T>>;
template <class U, class T>
using vvecp = vvec<std::pair<U, T>>;
template <class T>
using vecpt = vec<ptt<T>>;
template <class T>
using vvecpt = vvec<ptt<T>>;

template <class T, class C = std::less<T>>
using pq = std::priority_queue<T, vec<T>, C>;
template <class T>
using pqg = std::priority_queue<T, vec<T>, std::greater<T>>;

using strn = std::string;
using strnv = std::string_view;

using vecu = vec<u32>;
using vvecu = vvec<u32>;
using v3ecu = v3ec<u32>;
using vecu64 = vec<u64>;
using vecb = vec<bool>;
using vvecb = vvec<bool>;

#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif

using namespace std::literals;

constexpr i8 operator""_i8(unsigned long long x) { return (i8)x; }
constexpr i16 operator""_i16(unsigned long long x) { return (i16)x; }
constexpr i32 operator""_i32(unsigned long long x) { return (i32)x; }
constexpr i64 operator""_i64(unsigned long long x) { return (i64)x; }
constexpr isz operator""_iz(unsigned long long x) { return (isz)x; }

constexpr u8 operator""_u8(unsigned long long x) { return (u8)x; }
constexpr u16 operator""_u16(unsigned long long x) { return (u16)x; }
constexpr u32 operator""_u32(unsigned long long x) { return (u32)x; }
constexpr u64 operator""_u64(unsigned long long x) { return (u64)x; }
constexpr usz operator""_uz(unsigned long long x) { return (usz)x; }

inline const auto fn_0 = [](auto&&...) {};


#line 6 "src/code/game/texas_holdem.hpp"

namespace tifa_libs::game {
namespace texas_holdem_impl_ {
constexpr int bsr(int x) { return 30 - bit::cntlsb(x); }
// Returns the submask containing highest k bits set
// Returns -1 instead if std::popcount(a) < k
constexpr int hbits(int a, int k) {
  int b = 0;
  for (int i = 0; i < k; ++i) {
    if (!a) return -1;
    a &= ~(b |= 1 << bsr(a));
  }
  return b;
}

class th_card {
 protected:
  int data = 0;

 public:
  static constexpr char RANKS[16] = "0123456789TJQKA";
  static constexpr char SUITS[5] = "CDHS";
  explicit constexpr th_card() {}
  constexpr th_card(char rank, char suit) { encode(rank, suit); }
  explicit constexpr th_card(strnv str) : th_card(str[0], str[1]) { assert(str.size() == 2); }
  // Parses a card in a format as "2C"
  // @return: 4 * (rank - 2) + suit  (2 <= rank <= 14)
  constexpr void encode(char rank, char suit) {
    int r = 2, s = 0;
    for (; r < 15; ++r)
      if (RANKS[r] == rank) break;
    assert(r < 15);
    for (; s < 4; ++s)
      if (SUITS[s] == suit) break;
    assert(s < 4);
    data = (r - 2) << 2 | s;
  }
  constexpr int get_rank() const { return (data >> 2) + 2; }
  constexpr int get_suit() const { return data & 3; }
  // @return: {rank_char, suit_char}
  constexpr ptt<char> decode() const { return {RANKS[get_rank()], SUITS[get_suit()]}; }
  friend std::istream &operator>>(std::istream &is, th_card &card) {
    char rk, st;
    is >> rk >> st;
    card.encode(rk, st);
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, th_card const &card) {
    auto &&_ = card.decode();
    return os << _.first << _.second;
  }
};

enum th_category {
  HIGH_CARD,
  ONE_PAIR,
  TWO_PAIR,
  THREE_OF_A_KIND,
  STRAIGHT,
  FLUSH,
  FULL_HOUSE,
  FOUR_OF_A_KIND,
  STRAIGHT_FLUSH
};

class th_hand {
  vec<th_card> cds;
  // ranks for all
  int rka = 0;
  // suit -> rank
  int mps[4] = {};
  // rank -> count
  int cnt[15] = {};
  // count -> rank
  int mpc[5] = {};

 public:
  explicit constexpr th_hand() : cds(5) {}
  // Set first 5 element as hand
  constexpr void reset(vec<th_card> const &cards) {
    assert(cards.size() >= 5);
    std::copy(cards.begin(), cards.begin() + 5, cds.begin());
    for (auto &&card : cds) {
      auto r = card.get_rank(), s = card.get_suit();
      rka |= mps[s] |= 1 << r;
      ++cnt[r];
    }
    for (int r = 2; r < 15; ++r) mpc[cnt[r]] |= 1 << r;
  }
  // Returns the best poker hand with the tie-breaker in [0, 2^20)
  constexpr std::pair<th_category, int> parse() const {
    assert(cds.size() == 5);
    for (auto &&func : checks)
      if (auto [valid, cat, ans] = func(*this); valid) return {cat, ans};
    exit(1);
  }

  constexpr th_card &operator[](u32 x) { return cds[x]; }
  constexpr th_card const &operator[](u32 x) const { return cds[x]; }

  friend std::istream &operator>>(std::istream &is, th_hand &hands) {
    for (u32 i = 0; i < 5; ++i) is >> hands.cds[i];
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, th_hand const &hands) {
    for (u32 i = 0; i < 4; ++i) os << hands.cds[i] << ' ';
    return os << hands.cds[4];
  }

 private:
  // 8. STRAIGHT_FLUSH: highest (5 for A2345)
  static constexpr std::tuple<bool, th_category, int> is_straight_flush(th_hand const &h) {
    int f = 0;
    for (int s = 0; s < 4; ++s) f |= h.mps[s] & h.mps[s] << 1 & h.mps[s] << 2 & h.mps[s] << 3 & (h.mps[s] << 4 | h.mps[s] >> 14 << 5);
    return {!!f, STRAIGHT_FLUSH, bsr(f)};
  }
  // 7. FOUR_OF_A_KIND: quadruple, other card
  static constexpr std::tuple<bool, th_category, int> is_four_of_a_kind(th_hand const &h) {
    if (!h.mpc[4]) return {false, FOUR_OF_A_KIND, 0};
    const int r4 = bsr(h.mpc[4]);
    return {true, FOUR_OF_A_KIND, r4 << 4 | bsr(h.rka ^ 1 << r4)};
  }
  // 6. FULL_HOUSE: triple, pair
  static constexpr std::tuple<bool, th_category, int> is_full_house(th_hand const &h) {
    if (!h.mpc[3]) return {false, FULL_HOUSE, 0};
    const int r3 = bsr(h.mpc[3]), d = (h.mpc[3] ^ 1 << r3) | h.mpc[2];
    if (!d) return {false, FULL_HOUSE, 1};
    const int r2 = bsr(d);
    return {true, FULL_HOUSE, r3 << 4 | r2};
  }
  // 5. FLUSH: 5 highest cards
  static constexpr std::tuple<bool, th_category, int> is_flush(th_hand const &h) {
    int flush = -1;
    for (int s = 0, _ = 0; s < 4; ++s)
      if (flush < (_ = hbits(h.mps[s], 5))) flush = _;
    return {flush >= 0, FLUSH, flush};
  }
  // 4. STRAIGHT: highest (5 for A2345)
  static constexpr std::tuple<bool, th_category, int> is_straight(th_hand const &h) {
    const int f = h.rka & h.rka << 1 & h.rka << 2 & h.rka << 3 & (h.rka << 4 | h.rka >> 14 << 5);
    return {!!f, STRAIGHT, bsr(f)};
  }
  // 3. THREE_OF_A_KIND: triple, 2 highest other cards
  static constexpr std::tuple<bool, th_category, int> is_three_of_a_kind(th_hand const &h) {
    if (!h.mpc[3]) return {false, THREE_OF_A_KIND, 0};
    const int r3 = bsr(h.mpc[3]);
    return {true, THREE_OF_A_KIND, r3 << 16 | hbits(h.rka ^ 1 << r3, 2)};
  }
  // 2. TWO_PAIR: larger pair, smaller pair, other card
  // 1. ONE_PAIR: pair, 3 highest other cards
  static constexpr std::tuple<bool, th_category, int> is_pair(th_hand const &h) {
    if (!h.mpc[2]) return {false, ONE_PAIR, 0};
    const int r2 = bsr(h.mpc[2]);
    const int d = h.mpc[2] ^ 1 << r2;
    if (!d) return {true, ONE_PAIR, r2 << 16 | hbits(h.rka ^ 1 << r2, 3)};
    const int r22 = bsr(d);
    return {true, TWO_PAIR, r2 << 8 | r22 << 4 | bsr(h.rka ^ 1 << r2 ^ 1 << r22)};
  }
  // 0. HIGH_CARD: 5 highest cards
  static constexpr std::tuple<bool, th_category, int> is_high_card(th_hand const &h) { return {true, HIGH_CARD, hbits(h.rka, 5)}; }
  //! The judger of all the categories
  static constexpr std::tuple<bool, th_category, int> (*checks[8])(th_hand const &) = {
      is_straight_flush,
      is_four_of_a_kind,
      is_full_house,
      is_flush,
      is_straight,
      is_three_of_a_kind,
      is_pair,
      is_high_card};
};
}  // namespace texas_holdem_impl_

using texas_holdem_impl_::th_category, texas_holdem_impl_::th_card, texas_holdem_impl_::th_hand;

}  // namespace tifa_libs::game


Back to top page