Project Euler Problem 369

Solution

Answer: 862400558448

We model each hand by its 13 ranks.

For each rank, we may choose any subset of the 4 suits (including empty), so each rank contributes one of the 16 suit-subsets.

A $4$-card Badugi exists iff we can choose four distinct ranks covering all four suits exactly once — equivalently, in the bipartite graph between ranks and suits, there is a matching of size $4$.

The following Python program performs a dynamic programming search over all rank configurations while tracking which suit matchings are achievable.

from collections import defaultdict
from functools import lru_cache

# All possible suit subsets for a rank:
# bit 0 = clubs, bit 1 = diamonds, bit 2 = hearts, bit 3 = spades
subs = list(range(16))

# Number of cards represented by each subset
sizes = [bin(x).count("1") for x in subs]

@lru_cache(None)
def trans(A, T):
    """
    A = bitmask describing which suit-sets can already be matched.
        If bit M is set, then suit-set M is achievable.

    T = suit subset available for the current rank.

    Return updated achievable mask after processing this rank.
    """
    reachable = [i for i in range(16) if (A >> i) & 1]

    B = A

    # Use current rank to extend a matching by one suit
    for M in reachable:
        for s in range(4):
            if (T >> s) & 1 and not ((M >> s) & 1):
                B |= 1 << (M | (1 << s))

    return B

# Initial state:
# only the empty matching is achievable
dp = {(1 << 0, 0): 1}

# Process all 13 ranks
for _ in range(13):
    nd = defaultdict(int)

    for (A, n), cnt in dp.items():
        for T in subs:
            nd[(trans(A, T), n + sizes[T])] += cnt

    dp = nd

# f[n] = number of n-card hands containing a Badugi
f = [0] * 53

for (A, n), cnt in dp.items():
    # bit 15 means all 4 suits can be matched
    if (A >> 15) & 1:
        f[n] += cnt

answer = sum(f[n] for n in range(4, 14))

print("f(5) =", f[5])
print("Answer =", answer)

What the code does

Each rank independently chooses a subset of suits.
A tracks all suit combinations currently matchable using distinct ranks.
When processing a new rank subset T, we may extend any previous matching by adding one unused suit from T.
If suit-set 1111₂ = 15 becomes reachable, then a full 4-suit matching exists, meaning the hand contains a Badugi.
We accumulate counts by total hand size $n$.

Verification

The program reproduces the value given in the problem statement:

$$f(5)=514800$$

which confirms correctness.

The computed total is:

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

Answer: 862400558448