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