Problem 369: Badugi

View on Project Euler

Project Euler Problem 369 Solution

EulerSolve provides an optimized solution for Project Euler Problem 369, Badugi, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For each \(n\), let \(f(n)\) be the number of \(n\)-card hands from a standard 52-card deck that contain a Badugi: a 4-card selection whose suits are all different and whose ranks are all different. The required quantity is $$\sum_{n=4}^{13} f(n).$$ The local solutions do not enumerate hands directly. They process the 13 ranks one by one and keep track of which suit subsets can already be realized using cards taken from distinct ranks. Mathematical Approach Step 1: Encode the hand rank by rank Let the suit universe be \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\). For each rank \(r\), define a subset \(T_r\subseteq U\): suit \(b\in U\) belongs to \(T_r\) exactly when the card of rank \(r\) and suit \(b\) is present in the hand. Because a fixed rank contains exactly one card of each suit, choosing \(T_r\) completely determines the cards of that rank. Therefore each hand corresponds to exactly one sequence \((T_1,\dots,T_{13})\) with \(T_r\subseteq U\), and the hand size is $$n=\sum_{r=1}^{13} |T_r|.$$ Step 2: Compress the Badugi condition Simply knowing which suits appear in the full hand is not enough: the four witness cards must also come from different ranks. After processing some ranks, define \(\mathcal R\) as the family of suit subsets that can be formed by choosing cards from pairwise distinct processed ranks....

Detailed mathematical approach

Problem Summary

For each \(n\), let \(f(n)\) be the number of \(n\)-card hands from a standard 52-card deck that contain a Badugi: a 4-card selection whose suits are all different and whose ranks are all different. The required quantity is

$$\sum_{n=4}^{13} f(n).$$

The local solutions do not enumerate hands directly. They process the 13 ranks one by one and keep track of which suit subsets can already be realized using cards taken from distinct ranks.

Mathematical Approach

Step 1: Encode the hand rank by rank

Let the suit universe be \(U=\{\mathrm{S},\mathrm{H},\mathrm{D},\mathrm{C}\}\). For each rank \(r\), define a subset \(T_r\subseteq U\): suit \(b\in U\) belongs to \(T_r\) exactly when the card of rank \(r\) and suit \(b\) is present in the hand.

Because a fixed rank contains exactly one card of each suit, choosing \(T_r\) completely determines the cards of that rank. Therefore each hand corresponds to exactly one sequence \((T_1,\dots,T_{13})\) with \(T_r\subseteq U\), and the hand size is

$$n=\sum_{r=1}^{13} |T_r|.$$

Step 2: Compress the Badugi condition

Simply knowing which suits appear in the full hand is not enough: the four witness cards must also come from different ranks. After processing some ranks, define \(\mathcal R\) as the family of suit subsets that can be formed by choosing cards from pairwise distinct processed ranks.

Equivalently, \(M\subseteq U\) belongs to \(\mathcal R\) if we can pick \(|M|\) cards from already processed ranks, no two with the same rank, so that their set of suits is exactly \(M\).

There are only \(2^4=16\) suit subsets, so \(\mathcal R\) itself can be stored as a 16-bit mask. Bit \(j\) is set when the suit subset encoded by \(j\) is reachable. Initially only the empty subset is reachable:

$$\mathcal R_0=\{\varnothing\},\qquad \mathrm{rmask}=1.$$

This compression is sufficient because future ranks only need to know which suit subsets are achievable with distinct ranks; the identities of the earlier ranks never matter again.

Step 3: Transition for one new rank

Suppose the current rank contributes suit set \(T\subseteq U\). The actual hand may contain all cards in \(T\), so the hand size increases by \(|T|\). However, a Badugi witness may use at most one card from this rank, otherwise two chosen cards would share a rank.

Hence every reachable subset \(M\in\mathcal R\) can either stay unchanged, or be extended by one unused suit \(b\in T\setminus M\):

$$M \longrightarrow M\cup\{b\},\qquad b\in T\setminus M.$$

Therefore the updated reachable family is

$$\mathcal R'=\mathcal R\cup \left\{M\cup\{b\}: M\in\mathcal R,\ b\in T\setminus M\right\}.$$

This is exactly the transition precomputed by build_updates() in C++ and Java, and memoized by get_update(rmask, t) in Python.

Step 4: Dynamic programming over ranks and hand size

Let \(D_r(n,\mathrm{rmask})\) be the number of ways to process the first \(r\) ranks such that the hand currently has \(n\) cards and the reachable-family bitmask is \(\mathrm{rmask}\). The initial condition is

$$D_0(0,1)=1.$$

For every current state and every suit subset \(T\subseteq U\), we add the current count to the next state

$$D_{r+1}\bigl(n+|T|,\mathrm{upd}(\mathrm{rmask},T)\bigr).$$

After all 13 ranks, a hand contains a Badugi exactly when the full suit set \(U\) is reachable. In the bit encoding this is subset \(1111_2=15\), so

$$f(n)=\sum_{\substack{\mathrm{rmask}\\ \text{bit }15\text{ set}}} D_{13}(n,\mathrm{rmask}).$$

Step 5: Checkpoints

For \(n=4\), every Badugi hand must use all four suits and four distinct ranks, so we may choose the ranks and then assign the four suits:

$$f(4)=\binom{13}{4}\cdot 4! = 17160.$$

The C++ implementation checks this value and also verifies

$$f(5)=514800.$$

Running the full DP yields the Project Euler answer

$$\sum_{n=4}^{13} f(n)=862400558448.$$

How the Code Works

The C++ and Java programs precompute update[rmask][t] for all \(2^{16}\) reachability masks and all 16 suit masks \(t\). They then run a rolling two-layer DP over hand sizes \(0,\dots,13\). The Python version uses the same state definition, but stores only visited states in dictionaries and memoizes transitions lazily.

The constant kMaxN = 13 matches the problem statement: larger hand sizes are irrelevant to \(\sum_{n=4}^{13} f(n)\), so transitions with \(n+|T| > 13\) are skipped immediately.

Complexity Analysis

The dense DP loops over 13 ranks, 14 hand sizes, \(2^{16}\) reachability masks, and 16 suit masks. Thus the dominant running time is

$$O\!\left(13\cdot 14\cdot 2^{16}\cdot 16\right).$$

Memory usage is two DP layers of size \(14\times 2^{16}\), so

$$O\!\left(14\cdot 2^{16}\right)$$

64-bit counters, plus the precomputed transition table of size \(2^{16}\times 16\). The Python version has the same worst-case state space, but in practice stores only nonzero states.

References

  1. Problem page: https://projecteuler.net/problem=369
  2. Badugi rules and terminology: Wikipedia — Badugi
  3. Dynamic programming with bitmasks: cp-algorithms — Introduction to DP
  4. Counting poker hands and combinatorial states: Wikipedia — Combination

Problem 369 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

constexpr int kMaxN = 13;
constexpr int kReachStates = 1 << 16;  // bitset over all suit-subsets (16 subsets)

u64 comb_u64(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k > n - k) {
        k = n - k;
    }
    u128 num = 1;
    u128 den = 1;
    for (int i = 1; i <= k; ++i) {
        num *= static_cast<u128>(n - k + i);
        den *= static_cast<u128>(i);
    }
    return static_cast<u64>(num / den);
}

std::array<std::array<std::uint16_t, 16>, kReachStates> build_updates() {
    std::array<std::array<std::uint16_t, 16>, kReachStates> update{};

    for (int rmask = 0; rmask < kReachStates; ++rmask) {
        for (int t = 0; t < 16; ++t) {
            int next_mask = rmask;

            for (int matched = 0; matched < 16; ++matched) {
                if ((rmask & (1 << matched)) == 0) {
                    continue;
                }
                const int available = t & (~matched);
                int b = available;
                while (b != 0) {
                    const int suit_bit = __builtin_ctz(b);
                    b &= (b - 1);
                    const int new_subset = matched | (1 << suit_bit);
                    next_mask |= (1 << new_subset);
                }
            }

            update[static_cast<std::size_t>(rmask)][static_cast<std::size_t>(t)] =
                static_cast<std::uint16_t>(next_mask);
        }
    }

    return update;
}

std::array<u64, kMaxN + 1> compute_f_values() {
    const auto update = build_updates();
    std::array<int, 16> popcount{};
    for (int t = 0; t < 16; ++t) {
        popcount[static_cast<std::size_t>(t)] = __builtin_popcount(static_cast<unsigned>(t));
    }

    std::vector<std::vector<u64>> curr(static_cast<std::size_t>(kMaxN + 1),
                                       std::vector<u64>(static_cast<std::size_t>(kReachStates), 0ULL));
    std::vector<std::vector<u64>> next(static_cast<std::size_t>(kMaxN + 1),
                                       std::vector<u64>(static_cast<std::size_t>(kReachStates), 0ULL));

    // Only empty matching set is reachable initially.
    curr[0][1] = 1ULL;  // bit 0 set

    for (int rank = 0; rank < 13; ++rank) {
        for (int n = 0; n <= kMaxN; ++n) {
            std::fill(next[static_cast<std::size_t>(n)].begin(), next[static_cast<std::size_t>(n)].end(), 0ULL);
        }

        for (int n = 0; n <= kMaxN; ++n) {
            for (int rmask = 0; rmask < kReachStates; ++rmask) {
                const u64 ways = curr[static_cast<std::size_t>(n)][static_cast<std::size_t>(rmask)];
                if (ways == 0ULL) {
                    continue;
                }

                for (int t = 0; t < 16; ++t) {
                    const int nn = n + popcount[static_cast<std::size_t>(t)];
                    if (nn > kMaxN) {
                        continue;
                    }
                    const int nr = update[static_cast<std::size_t>(rmask)][static_cast<std::size_t>(t)];
                    next[static_cast<std::size_t>(nn)][static_cast<std::size_t>(nr)] += ways;
                }
            }
        }

        curr.swap(next);
    }

    std::array<u64, kMaxN + 1> f{};
    for (int n = 0; n <= kMaxN; ++n) {
        u64 badugi_hands = 0ULL;
        for (int rmask = 0; rmask < kReachStates; ++rmask) {
            if ((rmask & (1 << 15)) != 0) {  // suit subset {all 4 suits} is reachable
                badugi_hands += curr[static_cast<std::size_t>(n)][static_cast<std::size_t>(rmask)];
            }
        }
        f[static_cast<std::size_t>(n)] = badugi_hands;
    }

    return f;
}

bool run_checkpoints() {
    const auto f = compute_f_values();

    if (f[5] != 514800ULL) {
        std::cerr << "Checkpoint failed: f(5)\n";
        return false;
    }

    // Sanity: for each n <= 13, badugi and non-badugi counts partition all n-card hands.
    // Here we only verify that f(n) never exceeds C(52,n) and f(4)=17160 (all 4-card badugis).
    for (int n = 0; n <= kMaxN; ++n) {
        if (f[static_cast<std::size_t>(n)] > comb_u64(52, n)) {
            std::cerr << "Checkpoint failed: f(n) exceeds total hands for n=" << n << '\n';
            return false;
        }
    }

    if (f[4] != 17160ULL) {
        std::cerr << "Checkpoint failed: f(4)\n";
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const auto f = compute_f_values();
    u64 answer = 0ULL;
    for (int n = 4; n <= 13; ++n) {
        answer += f[static_cast<std::size_t>(n)];
    }

    std::cout << answer << '\n';
    return 0;
}

Python

def solve():
    update_memo = {}
    def get_update(rmask, t):
        key = (rmask << 4) | t
        if key in update_memo: return update_memo[key]
        
        next_mask = rmask
        for matched in range(16):
            if (rmask & (1 << matched)) == 0: continue
            available = t & (~matched)
            b = available
            while b != 0:
                isolate = b & -b
                suit_bit = isolate.bit_length() - 1
                b &= b - 1
                new_subset = matched | (1 << suit_bit)
                next_mask |= (1 << new_subset)
                
        update_memo[key] = next_mask
        return next_mask

    popcounts = [int.bit_count(t) for t in range(16)]
    
    curr = [{} for _ in range(14)]
    curr[0][1] = 1
    
    for rank in range(13):
        nxt = [{} for _ in range(14)]
        for n in range(14):
            if not curr[n]: continue
            for rmask, ways in curr[n].items():
                for t in range(16):
                    nn = n + popcounts[t]
                    if nn > 13: continue
                    nr = get_update(rmask, t)
                    nxt[nn][nr] = nxt[nn].get(nr, 0) + ways
        curr = nxt
        
    ans = 0
    for n in range(4, 14):
        total_for_n = 0
        for rmask, ways in curr[n].items():
            if (rmask & (1 << 15)) != 0:
                total_for_n += ways
        ans += total_for_n
        
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

public class Euler369 {

    static final int kMaxN = 13;
    static final int kReachStates = 1 << 16;

    static short[][] buildUpdates() {
        short[][] update = new short[kReachStates][16];
        for (int rmask = 0; rmask < kReachStates; rmask++) {
            for (int t = 0; t < 16; t++) {
                int nextMask = rmask;
                for (int matched = 0; matched < 16; matched++) {
                    if ((rmask & (1 << matched)) == 0)
                        continue;
                    int available = t & (~matched);
                    int b = available;
                    while (b != 0) {
                        int isolate = b & -b;
                        int suitBit = Integer.numberOfTrailingZeros(isolate);
                        b &= b - 1;
                        int newSubset = matched | (1 << suitBit);
                        nextMask |= (1 << newSubset);
                    }
                }
                update[rmask][t] = (short) nextMask;
            }
        }
        return update;
    }

    static String solve() {
        short[][] update = buildUpdates();
        int[] popcount = new int[16];
        for (int t = 0; t < 16; t++) {
            popcount[t] = Integer.bitCount(t);
        }

        long[][] curr = new long[kMaxN + 1][kReachStates];
        long[][] next = new long[kMaxN + 1][kReachStates];

        curr[0][1] = 1L;

        for (int rank = 0; rank < 13; rank++) {
            for (int n = 0; n <= kMaxN; n++) {
                for (int rmask = 0; rmask < kReachStates; rmask++) {
                    next[n][rmask] = 0L;
                }
            }

            for (int n = 0; n <= kMaxN; n++) {
                for (int rmask = 0; rmask < kReachStates; rmask++) {
                    long ways = curr[n][rmask];
                    if (ways == 0L)
                        continue;

                    for (int t = 0; t < 16; t++) {
                        int nn = n + popcount[t];
                        if (nn > kMaxN)
                            continue;
                        int nr = update[rmask][t] & 0xFFFF;
                        next[nn][nr] += ways;
                    }
                }
            }

            long[][] temp = curr;
            curr = next;
            next = temp;
        }

        long answer = 0L;
        for (int n = 4; n <= 13; n++) {
            long badugiHands = 0L;
            for (int rmask = 0; rmask < kReachStates; rmask++) {
                if ((rmask & (1 << 15)) != 0) {
                    badugiHands += curr[n][rmask];
                }
            }
            answer += badugiHands;
        }

        return Long.toString(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}